Программный способ записи алгоритмов

Алгоритм, предназначенный для исполнения на компьютере, должен быть записан на понятном ему языке. В этом случае язык для записи ал­горитмов должен быть формализован. Такой язык принято называть язы­ком программирования, а запись алгоритма на этом языке — програм­мой.

Проблема постановки задач.

Сущность алгоритмизации не в том, что решение задачи представляется в виде набора элементарных операций, а в том, что процесс решения задачи разбивается на два этапа:

¾ Творческий (выполняется программистом)

¾ Автоматический (выполняется исполнителем)

1-я проблема: непонимание программистом исполнителя и наоборот.

2-я проблема: единообразие (понимание) возможно только с помощью формального языка.

№2. Универсальные модели алгоритмов. Машина Тьюринга. Примеры реализации.

Универсальная модель алгоритмов.

1-ый тип: связан с вычисляемыми и числовыми функциями. Например индукция.

2-ой тип: алгоритмы основанные на представлении об алгоритме как о конкретном устройстве Машина Turing. Архитектура Фон Неймана.

3-ий тип: алгоритмы связаны с преобразованием слов и подстановкой их отдельных компонентов.

(Нормальный алгоритм Маркова)

Turing Machine:

Гиппотетически аппарат (автомат) позволяющий выполнить любую математическую операцию представленную в виде последовательности действий в условиях унарной системы исчисления.

Элементы машины Тюринга:

1) Лента

2) Считыватель (считывание, запись информации)

3) Таблица

Логические элементы:

1) Состояние (q) – состояние считывателя в данный момент времени

2) Правило – действие считывателя при переходе в конкретное состояние.

7 действий, которые может выполнять:

1) Движение вправо на 1 ячейку

2) Движение влево на 1 ячейку

3) Остановиться на месте

4) Стирание символов

5) Записывание символов

6) Переход к следующей команде

7) Остановка машины

AL

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

Правило подготовки вычислений в машине Тюринга:

Определить и установить стартовое положение считывателя

То что каждый новый элемент выделяется *…*

Свободные клетки обычно обозначаются

Если для данного состояния нет такой операции с таким символом, то операция останавливается.

К

О

Т

Таблица:

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

aR

Chrch – Turing Thesis

Если задача сложности К имеет решение в недетерминированном полиномиальном сегменте, то она имеет формальизации является не решённой либо не решаемой во все.

№3.Универсальные модели алгоритмов. Нормальные алгоритмы Маркова. Примеры реализации.

Универсальная модель алгоритмов.

1-ый тип: связан с вычисляемыми и числовыми функциями. Например индукция.

2-ой тип: алгоритмы основанные на представлении об алгоритме как о конкретном устройстве Машина Turing. Архитектура Фон Неймана.

3-ий тип: алгоритмы связаны с преобразованием слов и подстановкой их отдельных компонентов.

(Нормальный алгоритм Маркова)

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

Это универсальная модель алгоритмов представляющая формализацию от любой полиноминальной задачи в виде операции с символами из определённого алфавита.

Алфавит. Все символы с которыми встретился {a,b,c}

Схема – таблица с прописанными всеми правилами замены.

1. Задача

bb cc c

aabbcc

1. abbcc

2. abcc

3. abc

1.

2. Начиная каждый раз с 1 правила в исходном слове ищутся совпадения.

3. Для 1-го же найденного совпадения применяется следующее правило.

Пометки:

1. Зелёный - цвет № вопросов.

2. Красный – сами вопросы

3. Оранжевый – либо материал, не обязательный, но желательный. Либо не до конца записано в лекциях или ещё какие проблемы с этим материалом. И ещё вариант материал, которого я не помню, чтобы упоминался в лекциях.

УдачногопрочтенияиподготовкикЭкзамену,всемудачииХороших оценок;-)