1610906280-c80d8404f2eaa01776b47d41b0f18e85 (824375), страница 3
Текст из файла (страница 3)
Таким образом, у нас задан лабиринт, вход которогонаходится в правой нижней клетке, а выход — в левой верхней (выход помечен символом F, см. рисунок). В начальный момент времени на входной клетке находитсяробот Бендер, который умеет отличать стены от коридоров, умеет делать ходы наодну соседнюю незаштрихованную клетку сверху, справа, снизу или слева, умеетпринимать простейшие логические решения, и способен распознать символ F. Заранее известно, что в таком лабиринте существует как минимум один путь, ведущий10Глава I.
Предварительные сведенияпо коридорам из входа в выход. Необходимо запрограммировать Бендера так, чтобыон, руководствуясь данной программой несложных операций, смог найти выход излабиринта.Для этого мы зарезервируем достаточно большое количество меток, занумерованных натуральными числами. Этими метками Бендер будет помечать свои ходы.Искомая программа состоит из следующих шести пунктов:0) Помечаем правую нижнюю клетку меткой 0. Переходим к пункту (1).1) Проверяем, верно ли, что клетка, на которой стоит Бендер, является выходом.Если это верно, то переходим к пункту (5).
Если нет, переходим к пункту (2).2) Проверяем, существует ли хотя бы одна непомеченная соседняя (сверху, справа,снизу или слева) клетка. Если существует, то переходим к пункту (3). Если нет,то переходим к пункту (4).3) Выбираем каким-нибудь эффективным способом одну соседнюю непомеченнуюклетку. Например, можно выбирать первую непомеченную клетку при обходевсех четырех соседних клеток по часовой стрелке, начиная с верхней. Помечаемвыбранную клетку наименьшей неиспользованной меткой. Затем передвигаемБендера на эту клетку и переходим к пункту (1).4) Возвращаемся на один ход назад, т. е.
передвигаем Бендера обратно на ту клетку, с которой он в последний раз перешел на текущую клетку. Переходим кпункту (2).5) Работа алгоритма останавливается. Выход из лабиринта найден. Таким образом, задача решена.Данный алгоритм всегда приводит к нахождению выхода из лабиринта. Действительно, если бы алгоритм не приводил к успеху, то это означало бы, что Бендер,проделав определенное число ходов и расставив метки от 0 до некоторого n, вернулся бы на исходную позицию, т. е. в правый нижний угол. Но тогда искомый путь,который тоже начинается в правом нижнем углу, полностью содержался бы в множестве помеченных клеток. В частности, левая верхняя клетка тоже была бы помеченаБендером, а значит, он побывал бы на ней в процессе своего блуждания по лабиринту,но вернулся назад. Последнее невозможно в силу пункта (5) из описания алгоритма.Анализируя свойства алгоритма из данного примера, выделим теперь следующиеОсновные черты алгоритмичеких процессов:а) Конечность описания — любой алгоритм задается как набор инструкций конечных размеров, т.
е. программа имеет конечную длину. В нашем примереописание алгоритма состоит из 6 пунктов, каждый из которых записан с помощью конечного числа слов.б) Дискретность — алгоритм исполняется по шагам, происходящим в дискретномвремени. Шаги четко отделены друг от друга. В алгоритмах нельзя использовать аналоговые устройства и непрерывные методы. В нашем примере одиншаг работы алгоритма — это выполнение одного из пунктов (0)–(5), эти шаги можно занумеровать натуральными числами.
В итоге Бендер проделывает§ 3. Интуитивные свойства алгоритмов11всегда лишь конечное число шагов для того, чтобы найти выход (хотя в общемслучае допускается бесконечное количество шагов, т. е. алгоритмы могут неостанавливаться).в) Направленность — у алгоритма есть входные и выходные данные. В алгоритмечетко указывается, когда он останавливается, и что выдается на выходе послеостановки.
В нашем примере входные данные — это схема лабиринта, выходныеданные — путь по коридорам, ведущий к выходу.г) Массовость — алгоритм применим к некоторому достаточно большому классуоднотипных задач, т. е. входные данные выбираются из некоторого, как правило, бесконечного множества. В нашем примере один и тот же алгоритм годитсядля поиска выхода из любого лабиринта прямоугольной формы, а не толькодля того лабиринта 8 × 8, который изображен на рисунке.д) Детерминированность (или конечная недетерминированность) — вычисленияпродвигаются вперед детерминированно, т. е.
вычислитель однозначно представляет, какие инструкции необходимо выполнить в текущий момент. Нельзяиспользовать случайные числа или методы. Конечная недетерминированностьозначает, что иногда в процессе работы алгоритма возникает несколько вариантов для дальнейшего хода вычислений, но таких вариантов лишь конечноечисло. В нашем примере действия Бендера детерминированны, но этот алгоритм можно переделать и в недетерминированный, если предоставить Бендерусвободу самостоятельного выбора клетки в пункте (3).
При этом, посколькуэтот выбор конечен (соседних клеток всего четыре), можно представить дальнейшие действия Бендера в виде распределенных (параллельных) вычислений:в момент выбора Бендер создает несколько своих клонов, и каждый клон идетпо своему пути, руководствуясь теми же пунктами (0)–(5). Если хотя бы одиниз клонов находит выход, то задача считается решенной.Глава IIКонечные автоматы и формальныеграмматики§ 4.Детерминированные конечные автоматыКонечные автоматы относятся к классу словарных алгоритмов. С помощью конечных автоматов можно решать задачи из достаточно широкого семейства алгоритмических проблем.
Например, технология проектирования микросхем основана нарезультатах теории автоматов. Другой пример — это компиляторы, перерабатывающие текст программы, написанной на языке программирования высокого уровня,в программу на машинном языке. Работа любого такого компилятора состоит издвух стадий. Первая стадия — лексический анализ текста, который реализуется спомощью определенного конечного автомата.
Вторая стадия — синтаксический анализ, который осуществляется с помощью автомата с магазинной памятью. Однако,как будет видно позднее, не любая алгоритмическая задача поддается решению спомощью конечного автомата.Дадим сначала неформальное определение конечных автоматов и описание ихработы.Процессор: δСостояние:r2шаг работыавтоматаHH©©Процессор: δСостояние:HH©©r3 = δ(r2 , s3 )A ¢¢следующийшагAA¢¢s1 s2 s3 s4 .
. . sks1 s2 s3 s4 . . . skвходная лентавходная лентаВходными данными любого конечного автомата являются слова в некотором заранее фиксированном алфавите, выходными данными являются две логические константы true и false. В каждый момент времени автомат находится в определенномвнутреннем состоянии. Число состояний автомата конечно.
В начальный моментвремени автомат находится в начальном состоянии. Кроме этого, некоторые состояния автомата считаются выделенными. Входное слово записывается на входной ленте, разбитой на ячейки: в каждой ячейке содержится одна буква слова. Автоматсвязан с лентой посредством специальной управляющей головки, которая последовательно считывает символы из ячеек, двигаясь слева направо. Очередной считанный§ 4. Детерминированные конечные автоматы13символ отправляется в процессор, который по текущему состоянию и по данномусчитанному символу определяет новое состояние, в которое переводится автомат.Функция, вычисляющая это новое состояние называется функцией перехода. Функция перехода расположена внутри процессора и не изменяется в ходе вычислений.Считав все символы слова, автомат останавливается в определенном состоянии: если это состояние оказывается выделенным, то на выход подается константа true —автомат распознал слово, в противном случае подается константа false — автоматне распознал слово.Уже из неформального определения видно, что конечные автоматы обладаюттакими интуитивными свойствами, как конечность описания, дискретность, направленность и массовость.
Детерминированность также присутствует в данном описании: по текущему состоянию и считанному символу функция перехода однозначноопределяет новое состояние. Отличительной чертой конечных автоматов являетсяотсутствие памяти вне процессора, т. е. вся память автомата занята программой. Этаособенность позволяет пролить свет на причины неспособности конечных автоматоврешить любую алгоритмически разрешимую задачу (для алгоритмов определенноговида необходима дополнительная память).Теперь перейдем к формальным определениям в терминах теории множеств.Определение. Детерминированным конечным автоматом (сокращенно д.к.а.) называется упорядоченная пятерка A = hQ, A, δ, q0 , F i, состоящая из следующих объектов:а) Q = {q0 , .
. . , qm } — конечный алфавит внутренних состояний автомата;б) A = {a0 , . . . , an } — конечный входной алфавит автомата;в) δ : Q × A → Q — функция перехода;г) q0 ∈ Q — начальное состояние;д) F ⊆ Q — множество выделенных (конечных) состояний.Графическое изображение детерминированных автоматовАвтоматы удобно изображать графически, используя следующие геометрическиефигуры:id — выделенное состояние;H© i— начальное состояние;d — одновременно начальное и выделенноеi— промежуточное состояние; H© iсостояние;i a - i— такая дуга присутствует в автомате, если значение функцииперехода δ(q, a) = q 0 ;q0¥i¾ ¦a — такая петля присутствует в автомате, если значение функцииqперехода δ(q, a) = q.qПример.
Например, автомат A = hQ, A, δ, q0 , F i, где A = {0, 1}, Q = {q0 , q1 , q2 },F = {q2 }, а функция перехода задается соотношениямиδ(q0 , 0) = q0 ,δ(q0 , 1) = q1 ,δ(q1 , 0) = q0 ,δ(q1 , 1) = q2 ,δ(q2 , 0) = q2 ,δ(q2 , 1) = q2 ,14Глава II. Конечные автоматы и формальные грамматикиимеет следующее графическое изображение:0¨¥1?si 1 - iHid¾ ¥¦0, 1© kq0q1q20Определение. Путем в детерминированном конечном автомате A = hQ, A, δ, q0 , F iназовем любую конечную последовательность hr0 , s1 , r1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
