Дихотомия - История изменений

Patarakin в 18:06, 19 октября 2022

2022-10-19T18:06:22Z

@@ Строка 1: / Строка 1: @@
-<!-- В этой статье нет точных указаний на источники информации -->{{другие значения|Дихотомия (значения)}}
+'''Дихотоми́я''' последовательное деление на две части, более связанные внутри, чем между собой. Способ логического деления класса на подклассы, который состоит в том, что делимое понятие полностью делится на два взаимоисключающих понятия. Дихотомическое деление в [[математика|математике]], [[философия|философии]], [[логика|логике]] и [[лингвистика|лингвистике]] является способом образования подразделов одного понятия или термина и служит для образования классификации элементов.
 == Преимущества и недостатки ==
@@ Строка 34: / Строка 31: @@
 На каждой итерации приходится вычислять новые точки. Можно добиться того, чтобы на очередной итерации было необходимо высчитывать лишь одну новую точку, что заметно способствовало бы оптимизации процедуры. Это достигается путём зеркального деления отрезка в [[золотое сечение|золотом сечении]], в этом смысле [[метод золотого сечения]] можно рассматривать, как улучшение метода дихотомии с параметром <math>\delta=(b-a)\left(\frac{1}{\Phi}-\frac{1}{2}\right)</math>, где <math>\Phi\! = \frac{ \sqrt{5}+1}{2} \approx 1{,}6180339887\dots</math> — [[золотое сечение]].
 [[Категория:Алгоритмы поиска]]

Patarakin: 1 версия импортирована

2022-10-19T17:54:59Z

1 версия импортирована

← Предыдущая версия		Версия от 20:54, 19 октября 2022
(нет различий)

ru_wikipedia>Bezik: Удалена Категория:2 (число) с помощью HotCat

2022-08-15T12:49:47Z

Удалена Категория:2 (число) с помощью HotCat

Новая страница

{{другие значения|Дихотомия (значения)}}
{{wiktionary|дихотомия}}
[[Файл:29th_Infantry_Division_SSI.svg|thumb|Дихотомия [[Инь и Ян]]]]
'''Дихотоми́я''' ({{lang-el|διχοτομία}}: {{lang-grc2|δῐχῆ}}, «надвое» + {{lang-grc2|τομή}}, «деление») — [[дуализм|раздвоенность]], последовательное деление на две части, более связанные внутри, чем между собой. Способ логического деления класса на подклассы, который состоит в том, что делимое понятие полностью делится на два взаимоисключающих понятия. Дихотомическое деление в [[математика|математике]], [[философия|философии]], [[логика|логике]] и [[лингвистика|лингвистике]] является способом образования подразделов одного понятия или термина и служит для образования классификации элементов.

== Преимущества и недостатки ==
Дихотомическое деление привлекательно своей простотой. Действительно, при дихотомии мы всегда имеем дело лишь с двумя классами, которые исчерпывают объём делимого понятия. Таким образом, дихотомическое деление всегда соразмерно; члены деления дополняют друг друга, так как каждый объект делимого множества попадает только в один из классов '''''а''''' или ''не '''а'''''; деление проводится по одному основанию — наличие или отсутствие некоторого признака. Обозначив делимое понятие буквой '''''а''''' и выделив в его объёме некоторый вид, скажем, '''''b''''', можно разделить объём '''''а''''' на две части — '''''b''''' и ''не '''b'''''.

Дихотомическое деление имеет недостаток: при делении объёма понятия на два понятия каждый раз остаётся крайне неопределённой та его часть, к которой относится частица «не». Если разделить учёных на ''историков'' и ''не историков'', то вторая группа оказывается весьма неясной. Кроме того, если в начале дихотомического деления обычно довольно легко установить наличие противоречащего понятия, то по мере удаления от первой пары понятий найти его становится всё труднее.

== Применение ==
Дихотомия обычно используется как вспомогательный приём при установлении классификации.

Она известна также благодаря достаточно широко используемому методу поиска, так называемому '''''методу дихотомии'''''. Он применяется для нахождения значений действительно-значной [[Функция (программирование)|функции]], определяемых по какому-либо критерию (это может быть сравнение на [[минимальный элемент|минимум]], [[максимальный элемент|максимум]] или конкретное число). Рассмотрим метод дихотомии условной одномерной [[оптимизация (математика)|оптимизации]] (для определённости минимизации).

=== Метод дихотомии ===
Метод дихотомии несколько схож с [[метод бисекции|методом бисекции]], однако отличается от него критерием отбрасывания концов.

Пусть задана функция <math>f(x):\;[a,\;b]\to\mathrm{R},\;f(x)\in\mathrm{C}([a,\;b])</math>.

Разобьём мысленно заданный отрезок пополам и возьмём две симметричные относительно центра точки <math>x_1</math> и <math>x_2</math> так, что:
: <math>\begin{array}{ccc}
x_1 &=& \frac{a+b}{2}-\delta,\\
x_2 &=& \frac{a+b}{2}+\delta,
\end{array}</math>
где <math>\delta</math> — некоторое число в интервале <math>\left(0,\;\frac{b-a}{2}\right)</math>.

Вычислим два значения функции <math>f(x)</math> в двух новых точках. Сравнением определим в какой из двух новых точек значение функции <math>f(x)</math> максимально.
Отбросим тот из концов изначального отрезка, к которому точка с максимальным значением функции оказалась ближе (напомним, мы ищем [[минимум]]), то есть:
* Если <math>f(x_1)>f(x_2)</math>, то берётся отрезок <math>[x_1,\;b]</math>, а отрезок <math>[a,\;x_1]</math> отбрасывается.
* Иначе берётся зеркальный относительно середины отрезок <math>[a,\;x_2]</math>, а отбрасывается <math>[x_2,\;b]</math>.

Процедура повторяется, пока не будет достигнута заданная точность, к примеру, пока длина отрезка не достигнет удвоенного значения заданной погрешности.

На каждой итерации приходится вычислять новые точки. Можно добиться того, чтобы на очередной итерации было необходимо высчитывать лишь одну новую точку, что заметно способствовало бы оптимизации процедуры. Это достигается путём зеркального деления отрезка в [[золотое сечение|золотом сечении]], в этом смысле [[метод золотого сечения]] можно рассматривать, как улучшение метода дихотомии с параметром <math>\delta=(b-a)\left(\frac{1}{\Phi}-\frac{1}{2}\right)</math>, где <math>\Phi\! = \frac{ \sqrt{5}+1}{2} \approx 1{,}6180339887\dots</math> — [[золотое сечение]].

== См. также ==
{{кол}}
* [[Линейный поиск]]
* [[Двоичный поиск]]
* [[Метод бисекции]]
* [[Метод золотого сечения]]
* [[Троичный поиск]]
* [[Бифуркация]]
{{кол|конец}}

== Литература ==
* {{source|Q21694522|part=Глава 11. Преодоление ограничений: Метод деления пополам|pages=476—480}}
* {{книга|автор = Акулич И. Л.|заглавие = Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. пец. вузов|оригинал = |ссылка = |издание = |место = М.|издательство = Высшая школа|год = 1986|страницы =|isbn = }}
* {{книга|автор = Амосов А. А., Дубинский Ю. А., Копченова Н. П.|заглавие = Вычислительные методы для инженеров|оригинал = |ссылка
|издание = |место = М.|издательство = Мир|год = 1998|страницы =|isbn = }}
* {{книга|автор = Бахвалов Н. С., [[Жидков, Николай Петрович|Жидков Н. П.]], Кобельков Г. Г.|заглавие = Численные методы|оригинал = |ссылка = |издание = 8-е изд|место = М.|издательство = Лаборатория Базовых Знаний|год = 2000|страницы =|isbn = }}
* {{книга|автор = Волков Е. А.|заглавие = Численные методы|оригинал = |ссылка = |издание =|место = М.|издательство = Физматлит|год = 2003|страницы =|isbn = }}
* {{книга|автор = Гилл Ф., Мюррей У., Райт М.|заглавие = Практическая оптимизация. Пер. с англ|оригинал = |ссылка = |издание =|место = М.|издательство = Мир|год = 1985|страницы =|isbn = }}
* {{книга|автор = Корн Г., Корн Т.|заглавие = Справочник по математике для научных работников и инженеров|оригинал = |ссылка = |издание = |место = М.|издательство = Наука|год = 1970|страницы = 575—576|isbn = }}
* {{книга|автор = Коршунов Ю. М., Коршунов Ю. М.|заглавие = Математические основы кибернетики|оригинал = |ссылка = |издание =|место = М.|издательство = Энергоатомиздат|год = 1972|страницы =|isbn = }}
* {{книга|автор = Максимов Ю. А., Филлиповская Е. А.|заглавие = Алгоритмы решения задач нелинейного программирования|оригинал = |ссылка = |издание =|место = М.|издательство = МИФИ|год = 1982|страницы =|isbn = }}
* {{книга|автор = Максимов Ю. А.|заглавие = Алгоритмы линейного и дискретного программирования|оригинал = |ссылка = |издание = |место = М.|издательство = МИФИ|год = 1980|страницы =|isbn = }}

{{^}}
{{Методы оптимизации}}

[[Категория:Алгоритмы поиска]]
[[Категория:Алгоритмы оптимизации]]
[[Категория:Численные методы решения уравнений]]
[[Категория:Логика]]
[[Категория:Философские термины]]