1. Теория алгоритмов

1.1 Различные подходы к определению алгоритма:

10. Неформальное понятие алгоритма (последовательность инструкций для выполнения действия).

20. Машина с неограниченными регистрами (МНР).

30 Машина Тьюринга – Поста (МТ-П).

40 Нормальные алгоритмы Маркова (НАМ).

1.1.1 Машина с неограниченными регистрами (МНР).

Имеется некое устройство, в котором счетное число ячеек памяти (регистров), в которых хранятся целые числа.

Допустимые команды:

Z(n) - обнуление регистра Rn.

S(n) - увеличение числа в регистре Rn на 1.

T(m,n) - копирует содержимое Rm в регистор Rn.

I(p,q,n) - если содержимое Rp = Rq то выполняется команда с номером n , если нет

следующая.

Программа для МНР должна быть последовательностью команд Z, S, T, I с определенным порядком, выполняемые последовательно.

Тезис Черча (Churcha): Первое и второе определение алгоритма эквивалентны между собой. Любой неформальный алгоритм может быть представлен в программе для МНР.

1.1.2 Машина Тьюринга - Поста.

Имеется устройство просматривающее бесконечную ленту, где есть ячейки содержащие элементы алфавита: , где - пустой символ (пустое слово), который может принадлежать и не принадлежать А. Также существует управляющая головка (устройство) (УУ)/(УГ), которая в начальный момент расположена в определенном месте, в состоянии . Также существуют внутренние состояния машины:

Слово в данном алфавите - любая конечная упорядоченная последовательность букв данного алфавита, притом длина слова это количество букв в нем (у пустого слова длина 0).

Допустимые команды:

1.1.3 Нормальные алгоритмы Маркова.

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

Допустимые команды: (Для машин этого типа важна последовательность команд.)

1.1.4 Реализация функции натурального переменного.

но мы допускаем не всюду определенную функцию.

то это означает, что

притом , если f не определена, то и программа не должна ничего выдавать.

притом , если f не определена, то и программа не должна ничего выдавать.

( , а числа представляются в виде ,например .)

1.2 Эквивалентность трех подходов к понятию алгоритм.

1.2.1 Теорема об эквивалентности понятия вычислимой функции.

вычислима: ()

1) Если существует программа МНР, которая вычисляет эту функцию.

2) Если существует программа МТ-П, которая вычисляет эту функцию.

3) Если существует программа НАМ, которая вычисляет эту функцию.

Использование НАМ:

Теор.: Классы функций вычислимых на МТ-П, с помощью НАМ и с помощью МНР совпадают.

Пусть которая вычисляется на МТ-П, вычислим её на НАМ.

МТ-П:

НАМ:

Команда МТП: преобразуется по правилам:

Команда МТП:

2. Булевы функции.

2.1 Основные определения

2.1.1 Декартово произведение

- мн-во всевозможных упорядоченных пар элементов из А и В.

Пример: