Дихотомии

Дихотомия (с лат. dichotomia — «деление на две части») — это очень эффективный вид деления. Она характеризуется тем, что члены деления не пересекаются (т. е. исключают друг друга), такое деление производится только по одному основанию, а также соблюдается правило соразмерности. Однако, несмотря на бесспорное удобство дихотомического деления, у него есть серьезный недостаток — дихотомия применима не всегда. В случаях когда невозможно четко поставить критерий деления, такой вид деления не выполняет своей функции. Это происходит при попытках деления понятий с «размытым» объемом.

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

Дихотомия значительно отличается от указанного вида деления, что обусловливает сферу ее применения. Дихотомия — это деление объема определенного понятия на два противоречащих (не имеющих пересечения) друг другу понятия. При буквенном обозначении процесса дихотомического деления возникает следующая картина: понятие А (понятие, над которым производится деление) делится на два — В и не = В. Это простой вид дихотомического деления, которое ограничивается одним этапом. В более «сложных» случаях возможно деление не = В на С и не = С и т. д. Примером дихотомического деления может служить деление преступлений на умышленные и неумышленные; граждан на совершеннолетних и несовершеннолетних; животных на позвоночных и беспозвоночных и т. д.

Как видно, дихотомическое деление имеет ряд преимуществ. Так, например, здесь нет необходимости перечисления всех видов делимого понятия, а достаточно лишь выделить один вид и противоречащее ему понятие. В последнее входят все остальные виды. Отсюда следует, что два образованных дихотомией понятия исчерпывают весь объем делимого понятия, поэтому рассматриваемый предмет отражается только в одном из них.

Вместе с тем объем отрицательного понятия слишком широк, что подразумевает возникновение размытости и неопределенности. Как уже говорилось, дихотомия характеризуется строгим и последовательным характером. Однако второй и последующие этапы дихотомического деления в большей или меньшей степени теряют свою строгость и последовательность. В этой связи исследователи чаще всего ограничиваются первым этапом деления.

Необходимо упомянуть проблему, возникающую при отождествлении деления понятий и мысленного расчленения их на части. Основным отличием деления от расчленения является то, что части целого не являются видами делимого (родового) понятия. Нельзя делением признавать расчленение понятия «корабль» на нос, корму, мачту, дно и прочее, как нельзя назвать последние видами указанного родового понятия. Здесь мы имеем дело лишь с частями целого. Также частями, но никак не видами понятия «компьютер» являются монитор, системный блок, клавиатура и мышь. Проиллюстрировать сказанное можно следующим способом: представим, что указанные части целого являются членами деления, а следовательно, видами родового понятия. В этом случае можно сказать, что, например, монитор является компьютером (видом компьютера). Очевидно, что это не так.

Несмотря на сказанное выше, нельзя пренебрегать операцией расчленения понятий. Она широко применяется в учебном процессе как старших, так и младших классов средней школы. Данная операция используется в ботанике, биологии, физике, химии и т. д. Цель разделения — получение представления о составных частях какого-либо предмета. Например, можно разделять на части скелет человека, а также эти части делить на меньшие. Также можно расчленить, скажем, яйцо на скорлупу, белок и желток. Применение расчленения, конечно, не ограничивается учебным процессом средних школ, а применяется в вузах, в науке и повседневной жизни. Скажем, в медицине организм человека имеет деление на грудной и брюшной отделы.

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

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

Пример

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

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

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

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

Применение

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

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

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

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

Пускай задана функция .

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

,

где — некоторое число в интервале

Отбросим тот из концов изначального интервала, к которому ближе оказалась одна из двух вновь поставленных точек с максимальным значением (напомним, мы ищем минимум), то есть:

  • Если , то берётся отрезок , а отрезок отбрасывается.
  • Иначе берётся зеркальный относительно середины отрезок , а отбрасывается .

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

На каждой итерации приходится вычислять новые точки. Можно добиться того, чтобы на очередной итерации было необходим высчитывать лишь одну новую точку, что заметно способствовало бы оптимизации процедуры. Это достигается путём зеркального деления отрезка в золотом сечении, в этом смысле метод золотого сечения можно рассматривать, как улучшение метода дихотомии с параметром .

См. также

  • Двоичный поиск
  • Метод золотого сечения

Литература

Журнал Потенциал

Введение

Ваш друг задумал целое число от одного до десяти включительно. Он честно отвечает на ваши вопросы «да» или «нет». Какое минимальное число вопросов вам потребуется, чтобы гарантированно отгадать задуманное число?

Под фразой «гарантированно отгадать» следует понимать, что какое бы число из диапазона {\displaystyle } ни было загадано, задавая вопросы в соответствии с некоторым правилом, вам заведомо хватит M {\displaystyle M} вопросов, где M {\displaystyle M} — искомый минимум. Строго говоря, предлагается не только ответить на вопрос задачи, но и составить алгоритм отгадывания задуманного числа за минимальное число вопросов.

Биты и количество информации

Отвлечёмся и вспомним более простую задачу. Вы, конечно, помните, что такое один бит информации? Бит — это количество информации, уменьшающее степень неопределённости в два раза.

Классический пример — представим себе, что Вася не готовился к контрольной работе по математике, и может получить любую из оценок от двойки до пятерки. И вот, запыхавшийся Вася на пороге, и на вопрос «Как контрольная?» следует ответ: «Четыре!» Сколько бит информации сообщил вам Вася?

Для того, чтобы ответить на этот вопрос, разобьём наш вопрос «Как контрольная?» на этапы, причём таким образом, чтобы на каждом этапе неопределённость уменьшалась ровно в два раза. С точки зрения нормального человека это довольно необычный способ узнать ответ на вопрос. Но, тем не менее, приступим.

Первым этапом может быть, например, вопрос: «Оценка выше тройки?» Всего различных оценок четыре, этот вопрос разделяет их на две группы — «больше трёх» и «меньше либо равно трём». Очень важно, что эти группы одинаковы по количеству элементов — в каждой ровно по две возможных оценки. В первой группе находятся «отлично» и «хорошо», во второй — «удовлетворительно» и «плохо». Теперь нам предстоит определить одну оставшуюся оценку из двух, то есть уменьшить неопределённость ещё в два раза и получить ещё один бит информации. Отсюда следует, что искомое число бит в ответе Васи «Четвёрка!» равно двум — первый бит из четырёх возможных вариантов выбирает два, второй — выбирает из двух один.

Необходимо отметить, что разбиение потенциальных оценок на «группы» — исключительно дело вкуса, нужно лишь чтобы эти группы состояли из одинакового числа элементов. Вопрос первого этапа мог бы звучать, например, так: «Твоя оценка — двойка или пятерка?»

Пополам не делится

Искушённый читатель, должно быть, уже заметил, что в данном случае в ответ закрадываются степени двойки. И он не ошибся. Для того, чтобы передать один из двух возможных вариантов, требуется один бит. Два бита могут передать один из 2 ⋅ 2 = 4 {\displaystyle 2\cdot 2=4} вариантов. Три бита — один из 2 ⋅ 2 ⋅ 2 = 8 {\displaystyle 2\cdot 2\cdot 2=8} вариантов. С помощью n {\displaystyle n} бит можно передать один из 2 n {\displaystyle 2^{n}} вариантов.

Мы не будем подробно останавливаться на философском вопросе «А как же быть, если число вариантов не является степенью двойки?» Дотошного читателя не устраивает метод полутора землекопов.

Отгадаем число от 1 до 10

В какую минимальную степень n {\displaystyle n} необходимо возвести двойку, чтобы она стала больше десяти? В четвёртую, 2 4 = 16 {\displaystyle 2^{4}=16} . Из предыдущего абзаца следует, что четырёх вопросов будет достаточно для отгадывания. Первая часть задачи решена.

А как следует задавать вопросы, чтобы уложиться в дозволенные четыре вопроса? Уж точно не отгадывать число по порядку, начиная с единицы — это ведёт в худшем случае к девяти вопросам. Общее правило одно — нужно каждым вопросом уменьшать неопределённость в два раза. Если число вариантов не является степенью двойки, то в некоторых вопросах количество вариантов в «половинах» может различаться, но не более, чем на единицу. Итак, перед первым вопросом мы имеем десять различных вариантов. Десять пополам — пять. Спросим: «Задуманное число больше пяти?» Теперь самое главное не ошибиться нигде на единицу, не сказать не подумав «больше» вместо «больше либо равно» и наоборот.

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

Третьим вопросом мы снижаем число вариантов с двух до одного либо с трёх до двух. Если после второго вопроса осталось всего два варианта (например, на вопрос: «Число больше либо равно восьми?» последовал отрицательный ответ), то потребуется всего три, а не четыре вопроса. В любом случае, последним вопросом мы выбираем между двумя оставшимися числами и узнаём ответ.

Описанный метод называется методом деления пополам или, по-научному, дихотомией.

Упражнения

Сколько потребуется вопросов для того, чтобы отгадать:

  • Число от одного до ста?
  • В чью пользу и с каким счётом окончился матч в шахматы, который вёлся до трех побед и завершился победой одной из сторон?
  • Определённую перестановку из четырёх различных элементов, например, порядок из всех возможных способов выкладывания этих четырёх предметов в ряд.
  • Какие вопросы следует задавать в предыдущем задании? Пусть для простоты элементы (предметы) называются A {\displaystyle A} , B {\displaystyle B} , C {\displaystyle C} и D {\displaystyle D} .

Петя… нет, пусть будет, скажем, Андрей. Андрей предложил другой способ задавать вопросы. Первый вопрос: «Является ли твое число чётным?» Второй вопрос (если он нужен): «Является ли частное от деления твоего числа на два чётным?» В третьем вопросе изучается чётность частного от деления числа на четыре, в четвертом — на восемь, и вообще, в n {\displaystyle n} -м вопросе изучается чётность частного от деления задуманного числа на 2 n − 1 {\displaystyle 2^{n-1}} (не забывайте, что 2 0 = 1 {\displaystyle 2^{0}=1} ). Допустим, на пять вопросов Андрей получил ответы «Да, да, нет, да, нет» именно в таком порядке, и положим, что задуманное число лежит в диапазоне от 1 {\displaystyle 1} до 32 {\displaystyle 32} . Какое число было задумано? Придумайте общий способ называть задуманное число по набору ответов «Да»/»Нет» при условии задавания вопросов по данному принципу.

Докажите, что «варьирование» числа вопросов, которое мы наблюдали в примере с «не всегда обязательным» четвёртым вопросом, возможно тогда и только тогда, когда число возможных вариантов не является степенью двойки.

Поиск элемента в массиве

M = x , i = ? {\displaystyle M=x,\quad i=?}

Как решить эту задачу максимально быстро, то есть за возможно меньшее число обращений к массиву?

Ясно, что проверять все элементы массива начиная с первого — не самая лучшая идея. Необходимо придумать способ, который подстраивал бы следующую «попытку» на основании предыдущих. Не подойдет ли здесь метод дихотомии?

Вспомните, как вы ищете в словаре незнакомое слово — для простоты положим, что вы точно знаете написание. Разве вы пойдёте от начала словаря по всем словам? Если это словарь русского языка, в котором 40000 = 4 ⋅ 10 4 {\displaystyle 40000=4\cdot 10^{4}} слов, и ваша «скорость сканирования» составляет одно слово в секунду (не считая переворачивания страниц и перерывов на кофе), то процесс пролистывания словаря займёт у вас 40000 / ( 60 ⋅ 60 ) ≈ 11 {\displaystyle 40000/(60\cdot 60)\approx 11} часов. Удивительно, что словари пользуются такой популярностью.

Вероятнее всего, вначале вы найдёте первую букву вашего слова (если вы, конечно, не герой Джона Траволты в фильме «Phenomenon», но в данной статье мы изучаем классические методы). Это обычно несложно сделать, учитывая то, что первые буквы в словаре обычно помечены специальным образом. Затем, когда мы знаем, с какой по какую страницу искать искомое слово, логично искать вторую букву (строго говоря, человеческий мозг использует несколько другой механизм поиска, который грубо можно аппроксимировать градиентным методом оптимизации, тем не менее, пример со словарем достаточно показателен), за ней третью и так далее. В итоге либо искомое слово будет найдено, либо найдутся два слова, между которыми оно должно быть, но его там нет.

Немного математики

Данная формула справедлива для оптимальной реализации алгоритма. Обычно, программисты пишут так, что на каждом шаге значение функции на одном из концов отрезка вычисляется повторно (одно из значений программа «знала» на предыдущем шаге). И в примере программы, который мы привели ниже, количество вызовов функции (вычислений значения функции) в два раза больше оптимального. На такие «мелочи» промышленные программисты обычно не обращают внимания.

Если попытаться обобщить всё сказанное выше, то метод дихотомии снижает вычислительную сложность задачи поиска нужного значения функции f {\displaystyle f} с N {\displaystyle N} до log 2 ⁡ N {\displaystyle \log _{2}N} , если функция монотонна. Когда необходимо выполнить большое число операций поиска, имеет смысл вначале упорядочить данные (привести функцию к монотонной), а затем уже выполнять поиск методом дихотомии.

Отметим, что так называемая быстрая сортировка, в которой также присутствует идея деления пополам, имеет асимптотическую сложность O ( N ⋅ log ⁡ N ) {\displaystyle O(N\cdot \log N)} , и это лучшая возможная асимптотика времени сортировки .

Задача посложнее

В предыдущий раз мы отгадывали задуманное число. Число было целым, и его можно было отгадать либо не отгадать — точнее, всегда отгадать, вопрос стоял лишь о числе попыток. Решим задачу посложнее, а именно, научимся находить приближённые (численные) значения корней уравнений, используя метод деления пополам.

Рассмотрим уравнение, корень которого представляет собой трансцендентное число:

e x = x − 2 {\displaystyle e^{x}=x-2}

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

Обозначим концы исследуемого отрезка соответственно a {\displaystyle a} и b {\displaystyle b} . Для нашей функции будет верно:

f ( a ) < 0 {\displaystyle f(a)<0} f ( b ) > 0 {\displaystyle f(b)>0}

Пример программы на языке Си++

#include <iostream> #include <cmath> using namespace std; const double epsilon = 1e-10; double f(double x) { return exp(x) — (x + 2); }; void main() { double a, b, c; a = 0; b = 2; while (b — a > epsilon) { c = (a + b) / 2; if(f(c) * f(b) >= 0) b = c; else a = c; }; cout << (a + b) / 2 << endl; }

Сложная задача

Часто бывает непросто увидеть метод дихотомии в хорошей задаче по информатике. В завершение статьи приведём подобный пример — задача «Провода́» с полуфинала чемпионата мира по программированию ACM, проходившему в Санкт-Петербурге в октябре 2002 года.

На складе имеется N {\displaystyle N} проводов целочисленной длины. Необходимо из них получить K {\displaystyle K} кусков провода одинаковой и как можно большей длины L {\displaystyle L} . Провода нельзя спаивать.

Выведите целое максимальное число L {\displaystyle L} — такое, что можно из имеющихся проводов получить K {\displaystyle K} кусочков длины L {\displaystyle L} .

Рассуждения о способах разрезания проводов, конечно, могут привести к решению, но гораздо более простой путь— дихотомия по длине про́вода. Функция общего числа проводов от проверяемой длины L {\displaystyle L} легко вычисляется, она, очевидно, является монотонной, и искать решение можно, например, на интервале от L = 1 {\displaystyle L=1} до L = 10 7 + 1 {\displaystyle L=10^{7}+1} .

Задача сводится к классической дискретной дихотомии, и её решение оказывается на удивление простым.

Резюме

В руках опытного программиста метод дихотомии представляет собой мощный инструмент для поиска точных ответов в случае дискретных, и приближённых, но весьма точных, — в случае непрерывных задач.

В качестве самостоятельного упражнения предлагаем читателю сдать задачу 071 «Провода́» онлайновой системе проверки задач по программированию на сайте http://acm.mipt.ru.

Примечания

  1. А ведь звучит — «Ответь мне честно «да» или «нет» на полтора вопроса!»? Вообще говоря, «количество информации», которое мы измеряем, в общем случае может не выражаться целым числом бит. Но, так как в данном случае мы говорим о числе вопросов, то будем для простоты считать, что мы ищем ту степень двойки, где она в первый раз будет больше либо равна данному числу. Если число вариантов представляет собой степень двойки, будет иметь место равенство, для не степеней двойки мы найдём первую превосходящую степень.
  2. Верно ли, что если мы будем иногда делить на части, которые отличаются в размере более, чем на единицу, то это неминуемо приведёт к увеличению числа вопросов в худшем случае?
  3. Подсказка: докажите вначале, что тот факт, что число возможных вариантов не является степенью двойки, является необходимым и достаточным условием появления на некотором шаге нечётного числа элементов, из которых нужно выбирать.
  4. Знаток информатики, вероятно, захочет подколоть автора тем, что возможен крайний случай, когда в словаре меньше двух слов, и найти два слова требуемым образом не удастся — ему мы возразим, что для словаря из одного слова задача решается несколько иными средствами, хотя и выразим свое восхищение не по годам развитой проницательностью читателя.
  5. Существуют алгоритмы, в которых деление данных пополам перемежается со случайными шагами. Они имеют тот же порядок роста функции сложности, но меньшую константу.
  6. Напомним, что трансцендентным называется число, которое не может являться корнем никакого многочлена с целыми коэффициентами.
  7. Не следует, однако, задавать слишком малые значения ε {\displaystyle \varepsilon } — машинная точность не бесконечна, и всегда есть риск «зацикливания» программы. Вычисление корня с погрешностью ε = 10 − 10 {\displaystyle \varepsilon =10^{-10}} часто бывает достаточно.

  • 9. Лекция: Однопараметрическая (одномерная) оптимизация. Методы одномерной оптимизации: метод дихотомии

Тема 1. Формы тестовых заданий

Практическое занятие 1

Учебные достижения (результат обучения) будем рассматривать в широком смысле, не только как уровень знаний, умений и навыков, но и уровень интеллектуального развития, достигнутый учащимся в процессе обучения в образовательном учреждении или в результате самообразова­ния по утвержденной программе.

Тестовое задание — минимальная содержательно законченная составляющая педагогического теста в виде задания в специфической (тестовой) форме.

Важнейший признак тестового задания, отличающий его от других видов учебных заданий, – возможность его однозначного оценивания, что обеспечивает объективность проверки результатов тестирования.

Оценка успешности выполнения теста определяется оценкой (баллом), полученной за каждое задание.

При первом подходе каждое задание оценивается альтернативно («выполнено верно», «выполнено неверно»), причем оценка «выполнено верно» обычно символизируется единицей, а «выполнено неверно» — нулем.

Такую систему оценки называют дихотомической, а само задание — дихотомическим тестовым заданием.

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

Система оценки в этом случае называется политомической, а само заданиеполитомическим тестовым заданием.

Таким образом,педагогический тест состоит изтестовых зада­ний и применяется в процессепедагогического тестирования с целью полученияколичественной оценки учебных достижений учащихся.

Структура тестового задания

тестовая форма проверочного задания содержит:

• инструкцию, в которой указывается, каким образом ученик должен выполнять задание (где и как записывать ответ, на какие клавиши компь­ютера нажимать и т.д.), причем возможна ситуация, когда несколько одно­типных заданий снабжено одной инструкцией, которая сообщается уча­щимся (размещается на листе) перед группой заданий. В некоторых случа­ях соответствующие пояснения могут даваться устно.

• текст задания, который должен соответствовать набору особых специфических требований, выполнение которых обеспечивает однознач­ное понимание вопроса (задачи) и исключает появление ошибочных отве­тов по формальным признакам;

• систему оценки выполнения задания (эталон ответа) — обязательный элемент тестового задания. Его наличие обеспечивает однозначную оценку выполнения тестового задания, независимо от того, кто проверяет это задание. Именно наличие эталона правильного ответа в тестовых заданиях отличает тестовое от других видов учебных заданий и позволяет счи­тать результаты тестирования объективным показателем подготовленности учащихся.

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

Тестовые задания закрытого типа

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

К числу недостатков закрытых тестовых заданий чаще всегоотносят возможность угадывания ответов.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *