Дихотомия

Дихотомия
Логотип Викисловаря
В Викисловаре есть статья «дихотомия»

Дихотоми́я (греч. διχοτομία: δῐχῆ, «надвое» + τομή, «деление») — раздвоенность, последовательное деление на две части, не связанные между собой. Дихотомическое деление в математике, философии, логике и лингвистике является способом образования взаимоисключающих подразделов одного понятия или термина и служит для образования классификации элементов.

Содержание

Пример

Объём понятия «человек» можно разделить на два взаимоисключающих класса: мужчины и не мужчины. Понятия «мужчины» и «не мужчины» являются противоречащими друг другу, поэтому их объёмы не пересекаются. От дихотомии следует отличать обычное деление, приводящее к тому же самому результату. Например, объём понятия «человек» можно разделить по признаку пола на мужчин и жен­щин. Но между понятиями мужчина и женщина нет логичес­кого противоречия, поэтому здесь нельзя говорить о дихотомичес­ком делении.

Преимущества и недостатки

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

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

Применение

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

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

Метод дихотомии

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

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

Разобьём мысленно заданный отрезок пополам и возьмём две симметричные относительно центра точки x_1\! и x_2\! так, что:

\begin{array}{ccc}
x_1 &=& \frac{a+b}{2}-\delta,\\
x_2 &=& \frac{a+b}{2}+\delta,
\end{array}\!

где \delta\! — некоторое число в интервале \left(0,\;\frac{b-a}{2}\right)\!.

Вычислим два значения функции f(x) в двух новых точках. Сравнением определим в какой из двух новых точек значение функции f(x) максимально. Отбросим тот из концов изначального отрезка, к которому точка с максимальным значением функции оказалась ближе (напомним, мы ищем минимум), то есть:

  • Если f(x_1)>f(x_2)\!, то берётся отрезок [x_1,\;b]\!, а отрезок [a,\;x_1]\! отбрасывается.
  • Иначе берётся зеркальный относительно середины отрезок [a,\;x_2]\!, а отбрасывается [x_2,\;b]\!.

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

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

См. также

Литература

  1. Ананий В. Левитин. Глава 11. Преодоление ограничений: Метод деления пополам // [= 0-201-74395-7 Алгоритмы: введение в разработку и анализ] = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 476-480.
  2. Акулич И. Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. пец. вузов. — М.: Высш. шк., 1986.
  3. Амосов А. А., Дубинский Ю. А., Копченова Н. П. Вычислительные методы для инженеров. — М.: Мир, 1998.
  4. Бахвалов Н. С., Жидков Н. П., Кобельков Г. Г. Численные методы. — 8-е изд. — М.: Лаборатория Базовых Знаний, 2000.
  5. Волков Е. А. Численные методы. — М.: Физматлит, 2003.
  6. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
  7. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.
  8. Коршунов Ю. М., Коршунов Ю. М. Математические основы кибернетики. — Энергоатомиздат, 1972.
  9. Максимов Ю. А., Филлиповская Е. А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
  10. Максимов Ю. А. Алгоритмы линейного и дискретного программирования. — М.: МИФИ, 1980.

Wikimedia Foundation. 2010.

Синонимы:

Смотреть что такое "Дихотомия" в других словарях:

  • дихотомия — дихотомия …   Орфографический словарь-справочник

  • ДИХОТОМИЯ — (от греч. dichotomia разделение на две части) деление на две непересекающиеся части (напр., проводимое в Ветхом Завете видение человека, как состоящего из души и тела); в логике деление класса предметов, обозначаемых исходным понятием, на две… …   Философская энциклопедия

  • ДИХОТОМИЯ — [гр. dichotomia < dicha на две части + tome сечение] 1) последовательное деление целого на две части, затем каждой части снова на две и т.д.; 2) биол. ветвление у растений, при котором ось разделяется на две новые, обычно одинаково развитые ветви …   Словарь иностранных слов русского языка

  • дихотомия — сопоставленность, противопоставленность, деление, разветвление Словарь русских синонимов. дихотомия сущ., кол во синонимов: 5 • деление (27) • …   Словарь синонимов

  • дихотомия — и, ж. dichotomie f. < dicha на две части + tome сечение. спец. Последовательное деление целого на две части. БАС 2. Дихотомический ая, ое. Дихотомические таблицы. Уш. 1934. Дихотомическое деление. БАС 2. Лекс. Ян. 1803: дихотомия; САН 1895:… …   Исторический словарь галлицизмов русского языка

  • ДИХОТОМИЯ — (от греческого dichotomia разделение надвое), способ классификации: множества, понятия, термины разбиваются на пары соподчиненных элементов …   Современная энциклопедия

  • ДИХОТОМИЯ — ДИХОТОМИЯ, дихотомии, жен. (греч. dichotomia рассечение надвое) (книжн. научн.). Последовательное деление на два. || Разветвление ствола на две ветви, каждой ветви опять на две и т.д. (бот.). Толковый словарь Ушакова. Д.Н. Ушаков. 1935 1940 …   Толковый словарь Ушакова

  • ДИХОТОМИЯ — ДИХОТОМИЯ, и, жен. (книжн.). Сопоставленность или противопоставленность двух частей целого. | прил. дихотомический, ая, ое. Дихотомическое разбиение по классам и подклассам. Толковый словарь Ожегова. С.И. Ожегов, Н.Ю. Шведова. 1949 1992 …   Толковый словарь Ожегова

  • ДИХОТОМИЯ — [διχότομος (δихотомос) разделенный на две части] в биологии вильчатое ветвление всей особи или какого либо элемента организма (ребра раковины, жилок листа) на две части без продолжения главной оси …   Геологическая энциклопедия

  • ДИХОТОМИЯ — (от греч. dichotomia разделение на две части) англ. dichotomy; нем. Dichotomic. 1.Влогике подразделение на два ряда. 2. В статистике переменная, имеющая только два возможных значения (напр., мужской и женский пол). Antinazi. Энциклопедия… …   Энциклопедия социологии

  • дихотомия —         ДИХОТОМИЯ (от греч. dichotomia: dicha на две части и tome сечение) 1) название одной из апорий Зенона Элейского; 2) классификационная система, основанная на принципе бинарного деления объемов входящих в ней понятий по схеме… …   Энциклопедия эпистемологии и философии науки

Книги

  • Дихотомия, Джесси Рассел. Эта книга будет изготовлена в соответствии с Вашим заказом по технологии Print-on-Demand. High Quality Content by WIKIPEDIA articles! Дихотоми?я (греч. ?????????: ????, «надвое» + ????,… Подробнее  Купить за 1125 руб
  • Идеализм, Джесси Рассел. Эта книга будет изготовлена в соответствии с Вашим заказом по технологии Print-on-Demand. High Quality Content by WIKIPEDIA articles! Идеализм (фр. id?alisme, через лат. idealis от др.-греч.… Подробнее  Купить за 1125 руб
  • Двоичный поиск, Джесси Рассел. Эта книга будет изготовлена в соответствии с Вашим заказом по технологии Print-on-Demand. High Quality Content by WIKIPEDIA articles! Двоичный (бинарный) поиск (также известен как метод… Подробнее  Купить за 1125 руб
Другие книги по запросу «Дихотомия» >>


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.