Уважаемые посетители Портала Знаний, если Вы найдете ошибку в тексте, выделите, пожалуйста, ее мышью и нажмите Сtrl+Enter. Мы обязательно исправим текст!


Случайная цитата


Чтобы правильно задать вопрос, нужно знать большую часть ответа. (Шекли)

Алгоритмы

Алгоритм Евклида

Примеры

Задача Тезея и алгоритм поиска чудовища

Пример 1

Пример 2

Вывод

Чтобы успешно применять современный анализ данных, нам нужно познакомиться с понятием алгоритма. Алгоритм – это основное понятие математики и современного анализа данных.

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

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

Лучше всего познакомиться с понятием алгоритма на примерах.

Мы начнем с классического примера – алгоритма Евклида.

Алгоритм Евклида

Пусть у вас имеется два натуральных числа a и b, например, 2014 и 15. Ваша цель – найти наибольший общий делитель этих чисел.

Итак, нужно найти делитель, который должен быть, во-первых, общим для двух чисел, во-вторых, максимальным.

Очевидно, различных задач такого типа существует столько, сколько различных пар чисел а, b.

Нам необходимо найти последовательность действий, пригодную для всех натуральных чисел a и b.

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

Очевидно, вначале он обозрел два числа и предположил, что одно из них больше другого, например, a > b.

Далее можно предположить, что b является таким делителем.

Вопрос: как это проверить?

Деление – это обобщение вычитания, поэтому будем из числа a последовательно вычитать число b. Сделаем это несколько раз подряд, пока не получим 0.

Если получили 0, то решение найдено, b и есть искомый наибольший делитель.

Но пусть 0 не найден, а на определенном шаге у нас получается остаток – число b1 меньшее b, и мы не знаем, что делать дальше.

Разумно сосредоточиться на этом остатке.

У нас возникает предположение, что если есть общий делитель, то он должен находиться именно в этом остатке b1.

Задача. Попробуйте доказать, что это действительно так!

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

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

Мы применили эти действия к двум числам, предполагая, что a > b.

Если это неравенство не выполняется, мы просто меняем числа местами и достигаем поставленной цели.

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

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

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

Алгоритмы, в соответствии с которыми решение поставленных задач сводится к четырем арифметическим действиям, называются численными алгоритмами.

Они играют важную роль в самых разнообразных областях математики.

Например, пусть нужно решить систему двух уравнений первой степени с двумя неизвестными:

Алгоритм решения этой системы дается формулами

image005.png

которых полностью выражен как состав действий, так и порядок их выполнения.

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

Конечно, нам нужно предположить, что знаменатели не обращаются в 0.

Можно написать последовательность действий, рассматривающую все варианты значений коэффициентов уравнений. Можно также по шагам исключить одно неизвестное, найти значение другого, как это делается в школе. Именно важен сам принцип алгоритмистики.

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

В частности, так обстоит дело и в случае алгоритма Евклида, где число вычитаний, которые могут понадобиться, зависит от выбора той или иной пары чисел а, b.

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

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

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

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

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

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

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

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

Примеры

Приведем пример такого класса однотипных задач, для решения которых современная математика не располагает алгоритмом.

Рассмотрим всевозможные диофантовы уравнения, т. е. уравнения вида

где P является многочленом с целочисленными коэффициентами.

Уравнения названы в честь древнегреческого математика Диофанта. Диофа́нт Александри́йский  — древнегреческий математик, живший предположительно в III веке н. э.

Основное произведение ДиофантаАрифметика в 13 книгах, из которых сохранились только 6 первых книг из 13.

Примеры диофантовых уравнений:

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

Уравнение может иметь целочисленное решение, а может и не иметь его.

Первое из приведенных уравнений имеет целочисленное решение

Второе уравнение не имеет целочисленного решения, ибо для любого целого х легко устанавливается неравенство

В 1901 году немецкий математик Давид Гильберт огласил список 20 трудных задач, среди них была и такая задача:

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

Позднее эту задачу Гильберта решали многие математики, заключительное доказательство принадлежит советскому математику Ю.В.Матиясевичу (см. Ю. В. Матиясевич Диофантовость перечислимых множеств // Доклады Академии наук СССР. — 1970. — Т. 191. — № 2. — С. 279—282).

Ю. В. Матиясевич Десятая проблема Гильберта. — М.: Наука: Физико-математическая литература, 1993. — 223 с. — (Математическая логика и основания математики; выпуск № 26). —ISBN 502014326X

Для частного случая диофантова уравнения с одним неизвестным такой алгоритм известен.

Рассмотрим уравнение

с целочисленными коэффициентами.

Если уравнение имеет целый корень , то обязательно image023.png делится на .

Алгоритм нахождения такого корня простой: нужно перебрать все делители свободного члена image023.png приводит к цели:

  1. найти все делители числа image023.png (их конечное число);
  2. подставлять поочередно найденные делители в левую часть уравнения и вычислять численное значение ее;
  3. если при подстановке некоторого делителя левая часть уравнения приняла значение 0, то данный делитель является корнем уравнения
  4. если ни для какого делителя левая часть уравнения не обращается в 0, то уравнение не имеет целочисленных корней.

Отметим общие свойства алгоритмов.

Детерминированность алгоритма

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

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

Алгоритм решает не индивидуальную задачу, а решает множество однотипных задач.

Далее мы используем отрывки из увлекательной книги Б.А.Трахтенброта Алгоритмы и машинное решение задач и расскажем о некоторых интересных алгоритмах.

Задача Тезея и алгоритм поиска чудовища

Греческая мифология повествует о легендарном герое Тезее, который отважился проникнуть в лабиринт для того, чтобы разыскать в нем чудовищного Минотавра. Ему помогла выбраться из лабиринта Ариадна, давшая Тезею клубок ниток, один конец которых держала она сама. По мере углубления Тезея в лабиринт клубок наматывался; наматывая потом нитки, Тезей благополучно вернулся к выходу.

Об этой древней легенде напомнила автоматическая игрушка «Мышь в лабиринте», созданная американским математиком и инженером Клодом Шэнноном.

В одном месте специального лабиринта ставится вещь, условно именуемая куском сала, в другом — «мышь». Мышь начинает блуждать по лабиринту, делая при этом петли, пока находит «сало». Если повторно запустить «мышь» с того же места, то она уже прямо бежит к «пище», не делая петель.

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

Геометрически лабиринт можно представить в виде системы точек А, В, С,... (изображающих площадки) и совокупности отрезков АВ, ВС, ... (изображающих коридоры), соединяющих некоторые пары этих точек (рис. 1).

Рисунок 1

Будем говорить, что площадка Y достижима из площадки X, если существует путь, ведущий от X к Y через промежуточные коридоры и площадки.

Точнее это означает, что либо X и Y—смежные площадки, либо существует последовательность площадок таких, что X и , и , и ,... и т. д. и, наконец, и Y смежны.

Например, на, рис. 1 площадка H достижима из тупика A посредством пути АВ, ВС, CD, DE, EF, FD, DH, в то время как площадка K не достижима из А.

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

В предыдущем примере пусть и не был простым, но, срезав петлю DB, EF, FD, мы получаем простой путь АВ, ВС, CD, DH.

Предполагается, что Минотавр находится на одной из площадок лабиринта (обозначим ее через М), а Тезей, отправляясь на его поиски с площадки А, на которой его ждет Ариадна.

Герой должен решить следующую задачу: достижим минотавра M из A или нет.

Если Минотавр достижим, то нужно добраться до него по какому бы то ни было пути, но вернуться к Ариадне нужно уже по простому пути (не делая петель).

Если же М не достижима, то вернуться к Ариадне.

Различных лабиринтов может быть бесчисленное множество, а взаимное расположение в данном лабиринте площадок А и М также можно варьировать.

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

Иными словами, решение мыслится в виде алгоритма, решающего любую из задач данного типа.

Для построения такого алгоритма рассмотрим один специальный метод поисков.

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

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

  1. Разматывание нити. Прохождение от данной площадки по любому зеленому коридору до смежной площадки. (При этом нить Ариадны разматывается вдоль этого коридора, который после прохождения уже считается желтым.)
  2. Наматывание нити. Возвращение от данной площадки по последнему пройденному желтому коридору до смежной площадки. При этом нить Ариадны, ранее размотанная вдоль этого коридора, обратно наматывается, а этот коридор уже объявляется красным.

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

Выбор того или иного хода зависит от обстановки, наблюдаемой Тезеем на той площадке, на которой он находится в данный момент.

Эту обстановку можно охарактеризовать следующими признаками:

  1. Признак Минотавр. На данной площадке обнаружен Минотавр.
  2. Признак Петля. Через данную площадку уже протянута нить Ариадны; иными словами, от данной площадки расходятся по крайней мере два желтых коридора.
  3. Признак Зеленая улица. От данной площадки есть выход по крайней мере в один зеленый коридор.
  4. Признак Ариадна. На данной площадке находится Ариадна.
  5. Признак Пятый случай. Отсутствие всех предыдущих признаков.

Метод поиска может быть теперь задан следующей схемой:

Признак

Ход

1 МинотаврОстановка
2 ПетляНаматывание нити
3 Зеленая улицаРазматывание нити
4 АриаднаОстановка
5 Пятый случайНаматывание нити

Таблица 1

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

Такие ходы делаются до тех пор, пока не наступает остановка.

Пригодность метода непосредственно вытекает из следующих трех утверждений:

  1. При любом взаимном расположении A и M в лабиринте после конечного числа ходов обязательно наступит остановка либо на площадке Минотавра, либо на площадке Ариадны.
  2. Если остановка наступила на площадке Минотавра, то Минотавр достижим. Более того, в этом случае нить Ариадны оказывается протянутой по простому пути, ведущему от А до М; наматывая нить, Тезей может теперь вернуться по этому пути к Ариадне.
  3. Если остановка наступила на площадке. Ариадны, то Минотавр не достижим.

Прежде чем доказывать эти утверждения, покажем на двух примерах, как работает метод.

Пример 1

Пусть с площадки А лабиринта (рис. 1) начинается поиск Минотавра, который находится в F.

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

Каким признаком руководствуется Тезей

Ход

Пройденный коридор

Цвет коридора после его прохождения

1 Зеленая улицаРазматывание нитиABЖелтый
2 Зеленая улицаРазматывание нитиBCЖелтый
3 Зеленая улицаРазматывание нитиCDЖелтый
4 Зеленая улицаРазматывание нитиDHЖелтый
5 Зеленая улицаРазматывание нити HJЖелтый
6 Пятый случайНаматывание нитиJHКрасный
7 Пятый случайНаматывание нити HDКрасный
8 Зеленая улицаРазматывание нити DBЖелтый
9 ПетляНаматывание нити BDКрасный
10 Зеленая улицаРазматывание нити DFЖелтый
11 МинотаврОстановка ...,,,

Таблица 2

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

АВ, ВС, CD, DF.

Пример 2

Если же поиск начинается с площадки K, то процесс поиска можно изобразить в схеме, представленной на таблице 2.

Мы видим, что в этом случае Минотавр не достижим.

Перейдем теперь к доказательству утверждений 1—3.

Доказательство утверждения 1.

Покажем методом индукции по числу ходов Тезея, что на любом этапе процесса поиска возникает следующая альтернатива (т. е. имеет место один из следующих двух случаев, взаимно исключающих друг друга):

Каким признаком руководствуется Тезкй

Ход

Пройденный коридор

Цвет коридора после прохождения

1 Зеленая улицаРазматываниеKNЖелтый
2 Зеленая улицаРазматываниеNLЖелтый
3 Зеленая улицаРазматываниеLMЖелтый
4 Зеленая улицаРазматываниеMNЖелтый
5 ПетляНаматывание NMКрасный
6 Пятый случайНаматываниеMLКрасный
7 Пятый случайНаматывание LNКрасный
8 Пятый случайНаматывание NKКрасный
9 АриаднаОстановка ...,,,

Таблица 3

a) В лабиринте нет желтых коридоров; при этом Тезей находится на площадке А (Ариадны).

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

Вместе с тем будет обнаружено, что Тезей никогда не проходит по красному коридору.

Высказанные положения являются очевидными для начала процесса, когда Тезей еще находится на площадке А и никакой коридор еще не пройден (все коридоры — зеленые). Предположим теперь, что указанные альтернативы справедливы после (n—1)-го хода и покажем, что тогда они справедливы и после n-го хода (разумеется, если только (n— 1)-й ход еще не привел к остановке).

Пусть после (n— 1)-го хода имеет место случай а.

Тогда очередной ход может быть либо продвижением по зеленому коридору от А до некоторой смежной площадки K (после n-го хода возникает случай б с единственным желтым коридором AK), либо остановкой на площадке А (после n-го хода сохраняется случай a). Допустим теперь, что после (n— 1)-го хода имеет место случай б с s желтыми коридорами, образующими путь .

В зависимости от того, каким признаком руководствуется Тезей при выборе очередного n-го хода, после n-го хода имеются следующие возможности:

  1. Минотавр. Происходит остановка на площадке K с сохранением прежних желтых коридоров (случай б после n-го хода).
  2. Петля. Тезей наматывает нить, т. е. отступает по желтому коридору , который теперь уже становится красным. Желтый путь укорачивается на один коридор; если число s коридоров в прежнем пути было больше 1, то после и-го хода будет иметь место случай б с (s—1) желтыми коридорами; если же s =1, то будет иметь место случай а.
  3. Зеленая улица. Тезей разматывает нить, т. е. продвигается по зеленому коридору, который теперь уже становится желтым. Имеет место случай б с s+1 желтым коридором.
  4. Ариадна. Этим признаком Тезей не будет руководствоваться, ибо если он даже и вернется на площадку Ариадны, идя по желтому пути   (т. е. если K = А), то в соответствии с принятым методом поиска он должен руководствоваться признаком петля.
  5. При отсутствии первых четырех признаков происходит наматывание нити, которое приводит так же, как и в случае петли, к случаю а (при s = 1) или к случаю б (при s > 1).

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

Поскольку, кроме того, число всех коридоров в лабиринте конечно, то и последовательность ходов должна быть конечной; но эта последовательность может оборваться только при остановке Тезея на площадке Минотавра или на площадке Ариадны.

Доказательство утверждения 2. В случае остановки на площадке Минотавра факт достижимости очевиден, причем нить Ариадны протянута вдоль желтого пути, существование которого было установлено выше.

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

Доказательство утверждения 3. Заметим, что в случае остановки на площадке Ариадны

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

Предположим теперь от противного, что Минотавр достижим и пусть   —путь, ведущий от А к М.

Первый коридор в этом пути является красным, ибо он выходит из А, последний же является зеленым, ибо Тезей в своих поисках до Минотавра не добрался. Пусть — первый зеленый коридор в этой последовательности.

Таким образом, к примыкают зеленые и красные коридоры.

Рассмотрим теперь последнее прохождение Тезея через площадку ; оно, очевидно, произошло по одному из красных коридоров, примыкающих к

Однако последнего быть не может, ибо из выходит зеленый коридор .

Поэтому приходится допустить, что последнее прохождение через было связано с обнаружением петли. Однако это немедленно приводит к противоречию, чем и завершается доказательство утверждения 3.

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

Это противоречит допущению, что рассматривается последнее прохождение через .

Сделаем теперь следующее замечание. В предложенном нами предписании для поиска пути допускается известный элемент случайности.

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

Тем самым нарушается свойство детерминированности, о котором в предыдущем параграфе говорилось, что оно присуще всем алгоритмам.

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

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

Вывод

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


В начало

Содержание портала