Институт №8 МАИ

4 день. Теория алгоритмов, ДТ

Словарик программиста:

Глава 2. Элементы теории алгоритмов

2.1 Необходимость формального определения алгоритма

Неформальное определение алгоритма не даёт понимания, как именно выполнять “всем понятные” действия.

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

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

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

Формализация понятия реализуется построением алгоритмических моделей.

Рассмотрим 3 типа универсальных алгоритмических моделей:

2.1.1 Рекурсивные функции

© В Америке студенты пишут на lisp. Им устраивают таким образом дедовщину.

Рекурсивные функции были предложены в 30-ых годах прошлого века американским математиком Чёрчем (λ-исчисление).

В 60-ом американский математик Маккарти предложил интерпретируемый алгоритмический язык Lisp, также основанный на λ-исчислении.

На λ-исчислении основывается идея функционального программирования.

2.1.4 Тезис Тьюринга-Чёрча

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

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

Алгоритмические модели описывают один и тот же класс процессов обработки сообщений.

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

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

2.1.2 (+ 2.2) Машины Тьюринга

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

МТ расшифровывала криптограммы фашистов, что имело высокое значение в годы Второй мировой войны (машина enigma)

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

image

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

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

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

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

Команда МТ описывается упорядоченной четвёркой символов (q, a, v, q').

image

2.2 Математически строгое определение МТ (можно и без него обойтись)

image

image

image

image

image

image

image

image

Нам важно объяснить, какие моменты в Тьюринге не годятся для актуальных алгоритмических систем.

2.2.3 Диаграммы Тьюринга

В результате критики Тьюринга предложили диаграммы Тьюринга (5 лабы - низкоуровневое, сложное и неудобное программирование).

Любая программа выразима с помощью диаграммы, и наоборот.

Диаграммы представляют одни МТ через другие, более простые, при этом другим визуальным способом и без потери в строгости.

Комбинация нескольких одинаковых элементарных МТ l и r даёт машины L и R соответственно.

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

В диаграммерах этот принцип сохраняется.

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

image

Пример НЕ алгоритма.

image

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

image

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

image

Примеры диаграмм.

image

image

2.2.4 Понятие моделирования

Тут сложно. Ниже будет короче.

image

image

image

Главное запомнить идею о том, что всё связано с понятием отображения и образа.

Определение 2.2.5 Машина Т моделирует другую машину, если выполняются 5 условий:

1) Указан способ кодирования знаков;

2) Для каждого состояния машин определено отображение из множества состояний Q в Q’;

3) Если С0 — начальная конфигурации (положение) первой машины, то её образ C0’ есть конфигурация (положение) для второй машины.

4) Машина А останавливается в некотором положении Ck, тогда машина А’ останавливается в положении Ck’, где Ck’ — образ Ck.

5) Машина А проходит последовательность конфигураций такую, что для машины A’ последовательность пройденных конфигураций тоже будет образами.

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

Т.е. понятие моделирования говорит о том, что равенство алгоритмов есть равенство МТ.

2.2.5 Эквивалентность диаграмм и программ

Теорема 2.2.6 Каждой программе, задающей МТ Т = (A, Q, P, q0), можно эффективным образом сопоставить диаграмму D так, чтобы диаграмма моделировала машину Т.

Нам надо указать алгоритм эффективного построения диаграммы по программе, а потом убедиться в соответствии предыдущей формулировке.

План доказательства теоремы:

1) Построение диаграммы.

2) Проверка условия определения 2.2.5.

Теорема 2.2.6. Доказательство:

image

image

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

Доказательство в 2 этапа:

1) Построение программы.

2) Проверка условий определения 2.2.5.

Теорема 2.2.8. Доказательство:

image

image

image

Что покрывают диаграммы (какие цели):

Вычисления должны быть нормированы! При этом МТ не использует дополнительных букв.

Если алгоритм - это МТ, то равенство алгоритмов означает равенство МТ.

Тьюринговская теория позволяет сравнивать ‘мощность’ алгоритмов.