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

Август 20, 2022

Главная
Информатика
Теория алгоритмов

Содержание

2. Понятие алгоритма и алгоритмической системы Алгоритм – это общий, единообразный, точно установленный способ решения любой задачи
3. Характеристики алгоритма Дискретность Элементарность шагов алгоритма Детерминированность Результативность или сходимость Массовость
4. Алгоритмические модели (системы) это - формализация понятия «алгоритм». Алгоритмические системы допускают описание любых алгоритмов. Выделяют три
5. Машина Тьюринга состоит из: управляющего устройства, которое может находиться в одном из состояний, образующих множество Q={q1,
6. внутренняя память машины Тьюринга – это множество состояний внешняя память – лента Лента бесконечна в обе
7. Машина Тьюринга может описываться системой правил (команд), имеющих вид: 1) qiaj →qi′ aj′ dk 2) aj
8. Конфигурацией машины Тьюринга называется ее полное состояние: внутреннее состояние, состояние ленты, положение головки. Другое название конфигурации
9. Правильная запись словарного вектора α1*α2 * … αk-1 * αk (*-символ–разделитель) α1 λ α2 λ …
10. Пусть f – функция, отображающая множество векторов над Аисх в множество векторов над Арез . f:
11. Если для f существует машина Тьюринга, которая правильно ее вычисляет, то f называется правильно вычислимой по
12. Будем рассматривать числовые функции, т.е. f:N→N, Натуральные числа будем представлять в единичном (унарном) коде, т.е. А
13. Пример (Сложение, машина Т+) q1* → qzλR q11 → q2λR q21 → q21R q2* → q31L
15. Скачать презентацию

Слайд 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

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

Содержание

Понятие алгоритма и алгоритмической системыАлгоритм – это общий, единообразный, точно установленный

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

Алгоритмические модели (системы) это - формализация понятия «алгоритм». Алгоритмические системы

Машина Тьюринга состоит из:управляющего устройства, которое может находиться в одном из состояний,

внутренняя память машины Тьюринга – это множество состояний внешняя память –

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