Dichotomie

Dichotomie ( řecky διχοτομία : δῐχῆ , „ve dvou“ + τομή , „dělení“) je bifurkace , konzistentní rozdělení na dvě části, spojené více uvnitř než mezi sebou. Metoda logického rozdělení třídy na podtřídy, která spočívá v tom, že dělitelný pojem je zcela rozdělen na dva vzájemně se vylučující pojmy. Dichotomické dělení v matematice , filozofii , logice a lingvistice je způsob, jak vytvořit podsekce jednoho pojmu nebo termínu a slouží k vytvoření klasifikace prvků.

Výhody a nevýhody

Dichotomické dělení je atraktivní svou jednoduchostí. V dichotomii se totiž vždy zabýváme pouze dvěma třídami, které vyčerpávají rozsah dělitelného pojmu. Dichotomické dělení je tedy vždy přiměřené; dělící členy se vzájemně doplňují, protože každý objekt dělitelné množiny spadá pouze do jedné z tříd a nebo ne a ; rozdělení se provádí na jednom základě - přítomnost nebo nepřítomnost nějakého znamení. Označíme-li dělitelný pojem písmenem a a zvýrazníme v jeho objemu určitý typ, řekněme b , můžeme objem a rozdělit na dvě části - b a ne b .

Dichotomické dělení má nevýhodu: když rozdělujeme rozsah pojmu na dva pojmy, pokaždé zůstává extrémně neurčitá ta jeho část, do které částice „ne“ patří. Pokud se vědci dělí na historiky a nehistoriky , pak je druhá skupina velmi nejasná. Kromě toho, pokud je na začátku dichotomického dělení obvykle docela snadné zjistit přítomnost rozporuplného pojmu, pak jak se vzdalujete od prvního páru pojmů, je stále obtížnější jej najít.

Aplikace

Dichotomie se obvykle používá jako pomůcka při stanovení klasifikace.

Známá je také poměrně široce používanou vyhledávací metodou, tzv. dichotomickou metodou . Používá se k nalezení hodnot funkce s reálnou hodnotou určené podle nějakého kritéria (může to být srovnání pro minimum , maximum nebo konkrétní číslo). Uvažujme dichotomickou metodu podmíněné jednorozměrné optimalizace (pro jednoznačnost minimalizace).

Metoda dichotomie

Metoda dichotomie je poněkud podobná metodě půlení , ale liší se od ní v kritériu pro vyřazení konců.

Nechť je dána funkce . $f(x):\;[a,\;b]\to \mathrm {R} ,\;f(x)\in \mathrm {C} ([a,\;b])$

Rozdělme mentálně daný segment na polovinu a vezměme dva body symetrické ke středu a tak: $x_{1}$ $x_{2}$

{\begin{array}{ccc}x_{1}&=&{\frac {a+b}{2}}-\delta ,\\x_{2}&=&{\frac {a+ b }{2}}+\delta ,\end{array}}

kde je nějaké číslo v intervalu . $\delta$ $\left(0,\;{\frac {ba}{2))\right)$

Pojďme vypočítat dvě funkční hodnoty ve dvou nových bodech. Porovnáním určíme, ve kterém ze dvou nových bodů je hodnota funkce maximální. Zahodíme konec původního segmentu, ke kterému se bod s maximální hodnotou funkce ukázal být blíže (připomeňme, hledáme minimum ), tedy: $f(x)$ $f(x)$

Pokud je , pak se segment vezme a segment se zahodí. $f(x_{1})>f(x_{2})$ $[x_{1},\;b]$ $[a,\;x_{1}]$
V opačném případě je segment, který je zrcadlen vzhledem ke středu, odebrán a zahozen . $[a,\;x_{2}]$ $[x_{2},\;b]$

Postup se opakuje, dokud není dosaženo zadané přesnosti, například dokud délka segmentu nedosáhne dvojnásobku hodnoty zadané chyby.

Při každé iteraci se musí počítat nové body. Je možné zajistit, že při další iteraci je nutné počítat pouze s jedním novým bodem, což by výrazně přispělo k optimalizaci postupu. Toho je dosaženo zrcadlovým rozdělením segmentu ve zlatém řezu , v tomto smyslu lze metodu zlatého řezu považovat za vylepšení metody dichotomie s parametrem , kde je zlatý řez . $\delta =(ba)\left({\frac {1}{\Phi }}-{\frac {1}{2}}\right)$ $\Phi \!={\frac {{\sqrt {5}}+1}{2}}\cca 1{,}6180339887\dots$

Viz také

Literatura

Levitin A. V. Kapitola 11. Překonávání omezení: Metoda půlení // Algoritmy. Úvod do vývoje a analýzy - M .: Williams , 2006. - S. 476-480. — 576 s. — ISBN 978-5-8459-0987-9
Akulich I. L. Matematické programování v příkladech a úlohách: Proc. příspěvek na studentské hospodářství. domácí mazlíčci. vysoké školy. - M .: Vyšší škola, 1986.
Amosov A. A., Dubinsky Yu. A., Kopchenova N. P. Výpočtové metody pro inženýry. — M .: Mir, 1998.
Bakhvalov N. S., Zhidkov N. P. , Kobelkov G. G. Numerické metody. - 8. vyd. - M . : Laboratoř základních znalostí, 2000.
Volkov E. A. Numerické metody. — M .: Fizmatlit, 2003.
Gill F., Murray W., Wright M. Praktická optimalizace. Za. z angličtiny. — M .: Mir, 1985.
Korn G., Korn T. Příručka matematiky pro vědce a inženýry. - M .: Nauka, 1970. - S. 575-576.
Korshunov Yu.M., Korshunov Yu.M. Matematické základy kybernetiky. — M .: Energoatomizdat, 1972.
Maksimov Yu. A., Filippovskaya EA Algoritmy pro řešení problémů nelineárního programování. — M. : MEPhI, 1982.
Maksimov Yu.A. Lineární a diskrétní programovací algoritmy. — M. : MEPhI, 1980.

Optimalizační metody
Jednorozměrný	metoda zlatého řezu Dichotomie Parabolová metoda Vyhledávání v mřížce Jednotná metoda vyhledávání bloků Fibonacciho metoda Ternární hledání Piyavského metoda Stronginovou metodou
Nulové pořadí	Gaussova metoda Metoda Nelder-Mead Hook-Jeevesova metoda Rosenbrockova metoda Powellova metoda
První objednávka	gradientní sestup Zeutendijkova metoda Souřadnicový sestup Metoda konjugovaného gradientu Kvazi-newtonské metody Levenberg-Marquardtův algoritmus
druhá objednávka	Newtonova metoda Newton-Raphsonova metoda Algoritmus Broyden-Fletcher-Goldfarb-Shanno (BFGS)
Stochastické	Metoda Monte Carlo Simulované žíhání Evoluční algoritmy diferenciální evoluce Algoritmus mravenců Metoda roje částic Algoritmus včelstva Metoda náhodné chůze
Metody lineárního programování	Simplexní metoda Gomoriho algoritmus Elipsoidní metoda Potenciální metoda
Metody nelineárního programování	Sekvenční kvadratické programování