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

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

ТЕОРИЯ АЛГОРИТМОВ
Иванилова Т.Н.
19 ноября 2019г.

2. Понятие алгоритма и алгоритмической системы

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

3. Характеристики алгоритма

Дискретность
Элементарность шагов алгоритма
Детерминированность
Результативность или сходимость
Массовость

4. Алгоритмические модели (системы)

это - формализация понятия «алгоритм».
Алгоритмические системы допускают описание
любых алгоритмов.
Выделяют три основных типа универсальных
алгоритмических систем:
• Рекурсивные функции
• Машина Тьюринга
• Канонические системы Поста, нормальный
алгоритм Маркова

5. Машина Тьюринга

состоит из:
• управляющего устройства, которое может находиться в
одном из состояний, образующих множество Q={q1, …, qn}
• ленты, разбитой на ячейки, в каждой из которых может быть
записан символ из конечного алфавита A={a1,…, am}
• устройства обращения к ленте – считывающей или пишущей
головки, которая в любой момент времени обозревает ячейку
ленты и, в зависимости от символа в ячейке и состояния
управляющего устройства, записывает в ячейку символ (может
быть совпадающий с прежним или пустой (т.е. стирает)).
Потом сдвигается на ячейку влево или вправо или остается на
месте. При этом управляющее устройство переходит в новое
состояние (или остается в старом). Обозначение - dk= L(R,C)

6.

• внутренняя память машины Тьюринга –
это множество состояний
• внешняя память – лента
• Лента бесконечна в обе стороны

7.

• Машина Тьюринга может описываться системой правил
(команд), имеющих вид:
• 1) qiaj qi′ aj′ dk
• 2)
aj
qi
qi′ aj′ dk
aj aj′ dk
3) qi
qi′

8.

• Конфигурацией машины Тьюринга
называется ее полное состояние:
внутреннее состояние, состояние ленты,
положение головки.
• Другое название конфигурации машинное слово,
• обозначение этого термина - α1qiα2,
Стандартная начальная конфигурация q1α
Стандартная заключительная конфигурация
qzα.

9. Правильная запись словарного вектора

• α1*α2 * … αk-1 * αk (*-символ–разделитель)
• α1 λ α2 λ … αk-1 λ αk (λ – пустой символ).

10.

• Пусть f – функция, отображающая множество векторов
над Аисх в множество векторов над Арез . f: Vисх Wрез ,
где Аисх ,Арез– алфавиты входных и выходных данных.
• Машина Тьюринга правильно вычисляет функцию f,
если
• 1. Для любого vЄ Vисх и w Є Wрез , таких, что f(v)=w,
следует q1v* qz w* (v*, w* - правильные записи v и w)
• 2. Для любого v, такого, что f (v) – не определена,
машина Т с начальной конфигурацией q1v* работает
бесконечно.

11.

• Если для f существует машина Тьюринга,
которая правильно ее вычисляет, то f
называется правильно вычислимой по
Тьюрингу

12.

• Будем рассматривать числовые функции,
т.е. f:N→N,
• Натуральные числа будем представлять в
единичном (унарном) коде, т.е. А = {1}
либо А = {1, *}, число x представляется
словом 1…1=1x.

13.

Пример (Сложение, машина Т+)
q1* qzλR
q11 q2λR
q21 q21R
q2* q31L
q31 q31L
q3λ qzλR