ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 5719
Скачиваний: 13
91
Приведенные примеры показывают, что многие практиче-
ски встречающиеся задачи могут быть решены только на основе
интуитивного представления о том, что алгоритм — это общий
способ решения некоторой задачи при различных исходных
данных.
2 ìÚÓ˜ÌÂÌËfl ÔÓÌflÚËfl ‡Î„ÓðËÚχ
2.1 Необходимость уточнения понятия алгоритма
Существуют задачи, для решения которых не удается найти
алгоритмы их решения. Возникают вопросы: почему не удается?
Потому, что задача является слишком сложной и алгоритм бу-
дет найден, но позже, другими, более настойчивыми исследова-
телями? А может задачу никому не удастся решить по той при-
чине, что алгоритм ее решения вообще отсутствует? Если алго-
ритм решения данной задачи не существует, то как это дока-
зать?
Чтобы ответить на эти и им подобные вопросы, необходимо
дать более точный ответ на вопрос: что такое алгоритм? Поэто-
му многие специалисты предпринимали попытки дать понятию
алгоритма точное определение. Эта задача в 20-х годах была
одной из центральных математических проблем. Усилиями та-
ких исследователей, как Д. Гильберт, К. Гёдель, А.Чёрч,
Э. Пост, А. Тьюринг, А.А. Марков и др., было предложено не-
сколько точных определений понятия алгоритма, однако полно-
стью эта работа не завершена до сих пор и исследования в этой
области продолжаются.
С того времени было изучено немало подходов, в рамках
которых понятие алгоритма определялось гораздо точнее по
сравнению с интуитивными представлениями. Основными из
них являются следующие подходы, известные под названиями:
1) рекурсивные функции;
2) нормальные алгоритмы Маркова;
3) машины Тьюринга-Поста.
В данном пособии ограничимся иллюстрацией только одно-
го из подходов к уточнению понятия алгоритма (на примере
машины Тьюринга-Поста).
92
2.2 Машины Тьюринга-Поста
Тьюринг Алан Мэтисон (1912–1954) в 1937 г. в «Трудах
Лондонского математического общества» опубликовал работу,
где высказал идею, что алгоритмические процессы — это такие
процессы, которые могут быть реализованы механически, при
помощи определенным образом сконструированной машины.
Немного раньше, в октябре 1936 г., совершенно независимо
от Тьюринга, подобную же идею опубликовал американский
математик Эмиль Л. Пост в статье «Финитные комбинаторные
процессы, формулировка 1». Обе идеи были настолько похожи од-
на на другую, что редакция журнала к статье Поста сделала приме-
чание: «Читателю рекомендуется сравнить статью А.М. Тьюринга
″О вычислимых числах″, долженствующую появиться вскоре в
″Трудах Лондонского математического общества″».
Следует отметить, что термин «машина» применяет только
Тьюринг, в статье Поста этот термин не используется. Возмож-
но поэтому в литературе по теории алгоритмов в основном ссы-
лаются на Тьюринга, а статья Поста долгое время в публикациях
не упоминалась, хотя построения Поста гораздо проще машины
Тьюринга, а элементарность шагов у Поста доведена до теоре-
тического предела. Изложение идей Поста в виде машины было
представлено В.А. Успенским. В связи с этим идеи Поста будем
интерпретировать, подобно Тьюрингу, в виде машины.
Машина Тьюринга крайне проста. Её основу составляет уз-
кая лента неограниченной длины в обе стороны. Лента разделе-
на на одинаковые ячейки, например квадраты. Каждая ячейка
предназначена для записи в неё только одного знака, т.е. буквы
из некоторого алфавита, содержащего любое число букв, а в
пределе состоящего из двух знаков — пустого и какой-либо мет-
ки, например знака
∨, применяемого В.А. Успенским.
Лента — это внешняя память машины. Кроме неё, в струк-
туру машины входит логический блок, представляющий собой
управляющее устройство, содержащее внутреннюю память, ко-
торую можно представить как множество двоичных регистров
для хранения букв внутреннего алфавита. Главное назначение
логического блока — управление работой всей машины.
93
Кроме ленты и управляющего устройства в конструкцию
машины входит подвижная каретка. На ней размещена считы-
вающая головка, которая в каждый момент времени обозревает
только одну ячейку. Считывающая головка может:
1) перейти на одну ячейку влево (благодаря подвижной ка-
ретке);
2) перейти на одну ячейку вправо;
3) записать в обозреваемую ячейку одну букву из алфавита,
если она пуста, или стереть записанный в ячейке знак;
4) остановить работу.
Объединяет перечисленные составляющие механическое
устройство, передвигающее каретку и записывающее буквы на
ленту в зависимости от состояния внутренней памяти машины и
считываемого с ленты знака. Механическое устройство может
перемещать каретку относительно ленты либо ленту относи-
тельно головки. Принципиальной разницы в этом нет. И всё же
для определённости условимся считать, что механический блок
перемещает каретку относительно неподвижной ленты.
2.3 Программирование машины Поста
Существуют многочисленные варианты построения маши-
ны Тьюринга. Проиллюстрируем один из них на простейшем
примере машины в понимании В.А. Успенского.
Чтобы составить какую-либо программу для любой маши-
ны, необходимо, прежде всего, располагать системой команд.
Согласно В.А. Успенскому в соответствии с идеями Поста число
команд равно 6. Это теоретический предел. Перечислим их:
a.
→ b — команда имеет номер a. Стрелка обозначает сдвиг
каретки вправо на одну клетку. Буква b — это номер команды, к
которой должно перейти управляющее устройство, после того
как будет выполнена команда с номером a;
a.
← b — то же самое, но каретка сдвигается влево на одну
ячейку и машина переходит к выполнению команды b;
a.
∨ b — обозначает запись в клетку ленты непустого знака
(или метки, согласно терминологии В.А. Успенского);
94
a.
ε b — команда стирания знака, записанного в обозревае-
мой ячейке ленты;
a.
b
1
.
b
2
.
— команда условного перехода (передачи управле-
ния). Обозначает переход к команде b
1
, если обозреваемая ячей-
ка пуста, и переход к команде b
2
, если в обозреваемой ячейке
записана метка;
a. Стоп — команда остановки.
Эти шесть команд образуют функционально полный набор,
обеспечивающий построение любых программ для машины По-
ста. Применение перечисленных команд для реализации алго-
ритма проиллюстрируем на простейшем примере задачи при-
бавления единицы к некоторому числу a.
Пусть каретка стоит против пустой клетки, а справа от нее
на расстоянии конечного числа пустых ячеек записано число a,
представленное в унарном коде, т.е. в виде конечной последова-
тельности подряд идущих меток:
∨∨∨…∨, между которыми пус-
тых клеток нет. Например, число 0 можно закодировать одной
меткой, число 1 — двумя метками, число 2 — тремя и т.д. Тре-
буется составить программу так, чтобы меток оказалось на еди-
ницу больше, причем метку необходимо поставить в конце
унарного кода.
Программа имеет вид:
1.
→ 2. Так как каретка стоит против пустой клетки, то про-
верять, есть ли в ней метка, нет необходимости. Можно сразу
дать команду на перемещение каретки вправо с требованием
перейти после этого к выполнению команды с номером 2.
2.
1
3
Соседняя ячейка может оказаться занятой меткой.
Поэтому необходима проверка. Если метки нет, то надо повто-
рить первую команду. А при наличии метки необходимо перей-
ти к выполнению третьей команды.
3.
→ 4. Каретка стоит против ячейки с меткой. Длина числа
a неизвестна, но содержит не менее одной метки. Поэтому
третьей командой осуществляется сдвиг каретки в правую ячей-
ку и переход к выполнению команды 4.
95
4.
5
3
Проверка условия: если метка есть, то повторить
команду 3. Если метки нет, выполнить команду 5.
5.
∨ 6. Так как это первая после ряда меток пустая ячейка,
то в неё необходимо записать метку и перейти к команде 6.
6. Стоп. Этой командой работа алгоритма завершена.
В чём же состоит смысл уточнения понятия алгоритмиче-
ского процесса с привлечением машин Тьюринга и Поста? В
том, что реализация алгоритмического процесса при помощи
машин осуществляется полностью механически, где нет места
неоднозначности толкования ни одного действия, где не требу-
ется подвергать смысловому анализу ни исходные данные, ни
последовательность выполнения операций, ни результат перера-
ботки исходных данных. Иными словами, алгоритм — это всё
то, что может быть реализовано в виде программы на машине
Тьюринга или Поста.
2.4 Об алгоритмически неразрешимых проблемах
Существует ряд задач, которые длительное время не подда-
вались решению. Примерами могут служить задачи о квадрату-
ре круга и трисекции угла, а также задача удвоения куба. Фор-
мулируются они следующим образом:
1. В задаче о квадратуре круга требуется найти алгоритм
построения квадрата, равновеликого данному кругу. Иными
словами: дан круг определенного радиуса. Требуется построить
квадрат, площадь которого равнялась бы площади круга. При
этом разрешается пользоваться только циркулем и линейкой,
причем линейка может использоваться лишь для проведения
прямых, соединяющих те или иные две точки. Предполагается,
что на самой линейке нет никаких делений, и запрещается нано-
сить на нее какие-либо точки, штрихи, значки и др. Эта задача
является массовой, поскольку заданный круг может быть любо-
го радиуса. Существует строгое доказательство, что задача о
квадратуре круга является алгоритмически неразрешимой.
2. Согласно условию задачи трисекции угла требуется раз-
делить заданный угол на три равные части. При этом, как и в
предыдущем случае, пользоваться можно только циркулем и
линейкой. Очевидно, что задача трисекции угла также является