Dihotomie

Dihotomia ( greacă διχοτομία : δῐχῆ , „în doi” + τομή , „împărțire”) este o bifurcare , o împărțire consistentă în două părți, mai conectate în interior decât între ele. O metodă de împărțire logică a unei clase în subclase, care constă în faptul că conceptul divizibil este complet împărțit în două concepte care se exclud reciproc. Împărțirea dihotomică în matematică , filozofie , logică și lingvistică este o modalitate de a forma subsecțiuni ale unui concept sau termen și servește la formarea unei clasificări a elementelor.

Avantaje și dezavantaje

Diviziunea dihotomică este atractivă prin simplitatea sa. Într-adevăr, într-o dihotomie avem de-a face întotdeauna doar cu două clase, care epuizează sfera conceptului divizibil. Astfel, împărțirea dihotomică este întotdeauna proporțională; membrii de diviziune se completează unul pe altul, deoarece fiecare obiect al mulțimii divizibile se încadrează doar într-una dintre clasele a sau nu a ; divizarea se realizează pe o singură bază - prezența sau absența unui semn. Notând conceptul divizibil cu litera a și evidențiind în volumul său un anumit tip, să spunem, b , putem împărți volumul a în două părți - b și nu b .

Împărțirea dihotomică are un dezavantaj: la împărțirea domeniului de aplicare a unui concept în două concepte, de fiecare dată rămâne extrem de nedefinită acea parte a acestuia, căreia îi aparține particula „nu”. Dacă oamenii de știință sunt împărțiți în istorici și non-istorici , atunci al doilea grup este foarte neclar. În plus, dacă la începutul unei diviziuni dihotomice este de obicei destul de ușor să stabiliți prezența unui concept contradictoriu, atunci pe măsură ce vă îndepărtați de prima pereche de concepte, devine din ce în ce mai dificil să îl găsiți.

Aplicație

Dihotomia este de obicei folosită ca ajutor în stabilirea unei clasificări.

Este cunoscut și pentru o metodă de căutare destul de utilizată, așa-numita metodă dihotomie . Este folosit pentru a găsi valorile unei funcții cu valori reale determinate de un anumit criteriu (aceasta poate fi o comparație pentru un minim , un maxim sau un anumit număr). Să luăm în considerare metoda dihotomiei de optimizare unidimensională condiționată (pentru definiția minimizării).

Metoda dihotomiei

Metoda dihotomiei este oarecum similară cu metoda bisecției , dar diferă de aceasta prin criteriul de eliminare a capetelor.

Să fie dată o funcție . $f(x):\;[a,\;b]\la \mathrm {R} ,\;f(x)\in \mathrm {C} ([a,\;b])$

Să împărțim segmentul dat mental în jumătate și să luăm două puncte simetrice față de centru și astfel încât: $x_{1}$ $x_{2}$

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

unde este un număr în intervalul . $\delta$ $\left(0,\;{\frac {ba}{2)}\right)$

Să calculăm două valori ale funcției în două puncte noi. Prin comparație, determinăm în care dintre cele două noi puncte valoarea funcției este maximă. Renunțăm la sfârșitul segmentului inițial, de care punctul cu valoarea maximă a funcției s-a dovedit a fi mai aproape (reamintim, căutăm un minim ), adică: $f(x)$ $f(x)$

Dacă , atunci segmentul este luat și segmentul este aruncat. $f(x_{1})>f(x_{2})$ $[x_{1},\;b]$ $[a,\;x_{1}]$
În caz contrar, un segment care este oglindit în raport cu mijlocul este luat și aruncat . $[a,\;x_{2}]$ $[x_{2},\;b]$

Procedura se repetă până când se atinge precizia specificată, de exemplu, până când lungimea segmentului atinge de două ori valoarea erorii specificate.

La fiecare iterație, trebuie calculate noi puncte. Este posibil să se asigure că la următoarea iterație este necesar să se calculeze un singur punct nou, care ar contribui semnificativ la optimizarea procedurii. Acest lucru se realizează prin împărțirea în oglindă a segmentului în secțiunea de aur , în acest sens , metoda secțiunii de aur poate fi considerată ca o îmbunătățire a metodei dihotomiei cu parametrul , unde este secțiunea de aur . $\delta =(ba)\left({\frac {1}{\Phi }}-{\frac {1}{2}}\right)$ $\Phi \!={\frac {{\sqrt {5}}+1}{2}}\aprox 1{,}6180339887\dots$

Vezi și

Literatură

Levitin A. V. Capitolul 11. Depășirea constrângerilor: Metoda Bisecției // Algoritmi. Introducere în dezvoltare și analiză - M . : Williams , 2006. - S. 476-480. — 576 p. — ISBN 978-5-8459-0987-9
Akulich I. L. Programare matematică în exemple și sarcini: Proc. indemnizație pentru economia studenților. animale de companie. universități. - M . : Liceu, 1986.
Amosov A. A., Dubinsky Yu. A., Kopchenova N. P. Metode de calcul pentru ingineri. — M .: Mir, 1998.
Bakhvalov N. S., Zhidkov N. P. , Kobelkov G. G. Metode numerice. - Ed. a 8-a. - M . : Laboratorul de Cunoștințe de bază, 2000.
Volkov E. A. Metode numerice. — M. : Fizmatlit, 2003.
Gill F., Murray W., Wright M. Optimizare practică. Pe. din engleza. — M .: Mir, 1985.
Korn G., Korn T. Manual de matematică pentru oameni de știință și ingineri. - M . : Nauka, 1970. - S. 575-576.
Korshunov Yu. M., Korshunov Yu. M. Fundamentele matematice ale ciberneticii. — M .: Energoatomizdat, 1972.
Maksimov Yu. A., Filippovskaya EA Algoritmi pentru rezolvarea problemelor de programare neliniară. — M .: MEPhI, 1982.
Maksimov Yu. A. Algoritmi de programare liniară și discretă. — M .: MEPhI, 1980.

Metode de optimizare
Unidimensional	metoda secțiunii de aur Dihotomie Metoda parabolelor Căutare în grilă Metoda de căutare uniformă a blocurilor Metoda Fibonacci Căutare ternară metoda Piyavsky Metoda Strongin
Comanda zero	metoda Gauss Metoda Nelder-Mead Metoda Hook-Jeeves metoda Rosenbrock metoda Powell
Prima comanda	coborâre în gradient Metoda Zeutendijk Coordonarea coborârii Metoda gradientului conjugat Metode cvasi-newtoniene Algoritmul Levenberg-Marquardt
a doua comanda	metoda lui Newton Metoda Newton-Raphson Algoritmul Broyden-Fletcher-Goldfarb-Shanno (BFGS)
Stochastic	Metoda Monte Carlo Recoacere simulată Algoritmi evolutivi evolutie diferentiala Algoritmul furnicilor Metoda roiului de particule Algoritmul coloniilor de albine Metoda de mers aleatoriu
Metode de programare liniară	Metoda simplex algoritmul lui Gomori Metoda elipsoidă Metoda potențială
Metode de programare neliniară	Programare secvenţială pătratică