Алгоритмы и анализ сложности. Содержание курса

Июль 30, 2022

Главная
Информатика
Алгоритмы и анализ сложности. Содержание курса

Содержание

2. Введение в теорию алгоритмов.
3. Несколько примеров интуитивного понятия алгоритма: Алгоритм — точный набор инструкций, описывающих порядок действий исполнителя для достижения
4. Основные свойства алгоритмов Дискретность Детерминированность (определённость) Понятность Завершаемость (результативность, конечность) Массовость (универсальность) Однозначность результата
5. Дискретность. Алгоритм должен представлять процесс решения задачи как порядок выполнения некоторого конечного множества элементарных шагов. При
6. Основные задачи теории алгоритмов формализация понятия «алгоритм» и исследование формальных алгоритмических систем; формальное доказательство алгоритмической неразрешимости
7. Понятие данных Память Элементарный шаг Детерминированность Результативность Схема определения понятия «алгоритм»:
8. Алгоритм как некое детерминированное устройство - абстрактные машины. Машина Тьюринга и машина Поста. Алгоритм как процедура
9. Машина Поста.
10. Тезис Поста - “Всякий алгоритм представим в форме машины Поста”. Алгоритм (по Посту) — программа для
11. Всего для машины Поста существует шесть типов команд:
12. останов по команде "стоп". Такой останов называется результативным и указывает на корректность алгоритма; останов при выполнении
13. Пример: покажем, как можно воспользоваться командой условного перехода для организации циклического процесса. Пусть на ленте имеется
14. 1 -> 2 2 ? 1;3 3 4 V 5 5 ! Пример: увеличить число 3
15. Пример: на ленте машины Поста расположен массив из n меток. Составить программу, действуя по которой машина
16. Пример: зацикливание. 1 → 2 2 ← 1
17. Машина Тьюринга
18. В зависимости от считываемого символа и собственного состояния, управляющий модуль может производить следующие операции: записывать символ
19. Формально машина Тьюринга может быть описана следующим образом:
20. Способы задания МТ
22. Конфигурации МТ
24. Приведение конфигураций к стандартному виду
25. Определение вычислимости по Тьюрингу
26. Определение вычислимости для функций нескольких переменных
27. Примеры
30. Операции над машинами Тьюринга
35. Построение универсальной МТ.
37. Скачать презентацию

Слайд 2

Введение в теорию алгоритмов.

Слайд 3

Несколько примеров интуитивного понятия алгоритма:
Алгоритм — точный набор инструкций, описывающих порядок

действий исполнителя для достижения результата решения задачи за конечное время.
Алгоритм — это понятные и точные предписания исполнителю совершить конечное число шагов, направленных на решение поставленной задачи.
«Алгоритм — это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность». (Д. Кнут)
«Алгоритм — это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату». (А. Марков)

Слайд 4

Основные свойства алгоритмов
Дискретность
Детерминированность (определённость)
Понятность
Завершаемость (результативность, конечность)
Массовость (универсальность)
Однозначность результата

Слайд 5

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

конечного множества элементарных шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, то есть преобразование исходных данных в результат осуществляется во времени дискретно.
Детерминированность (определённость). В каждый момент времени следующий шаг работы алгоритма однозначно определяется состоянием системы, т.е. после каждого шага указывается, какой шаг следует выполнять дальше либо указывается, когда следует работу алгоритма считать законченной.
Понятность. Алгоритм должен включать только те команды, которые доступны исполнителю и входят в его систему команд.
Завершаемость (результативность, конечность). При корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов.
Массовость (универсальность). Это свойство состоит в том, что алгоритм решения задачи разрабатывается в общем виде и должен быть применим для некоторого класса задач, различающихся лишь исходными данными.
Однозначность результата. В какой бы форме не был записан алгоритм при одних и тех же данных должен быть получен один и тот же результат.

Слайд 6

Основные задачи теории алгоритмов
формализация понятия «алгоритм» и исследование формальных алгоритмических систем;
формальное

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

Слайд 7

Понятие данных
Память
Элементарный шаг
Детерминированность
Результативность
Схема определения понятия «алгоритм»:

Слайд 8

Алгоритм как некое детерминированное устройство - абстрактные машины. Машина Тьюринга и

машина Поста.
Алгоритм как процедура вычисления некой числовой функции. Рекурсивные функции Черча.
Алгоритм как последовательность преобразований цепочек в каком-либо алфавите.(Комбинаторные операции над словами). Нормальные алгоритмы Маркова.

Основные типы алгоритмических моделей

Слайд 9

Машина Поста.

Слайд 10

Тезис Поста - “Всякий алгоритм представим в форме машины Поста”.
Алгоритм (по

Посту) — программа для машины Поста, приводящая к решению поставленной задачи.
Если задача имеет алгоритмическое решение, то она представима в форме команд для машины Поста.

Слайд 11

Всего для машины Поста существует шесть типов команд:

Слайд 12

останов по команде "стоп". Такой останов называется результативным и указывает на

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

Варианты окончания выполнения программы на машине Поста

Слайд 13

Пример: покажем, как можно воспользоваться командой условного перехода для организации циклического

процесса. Пусть на ленте имеется запись из нескольких меток подряд, и головка находится над самой крайней меткой справа. Требуется перевести головку влево до первой пустой позиции.
1←2
2 ? 3; 1
3 !

Слайд 14

1 -> 2
2 ? 1;3
3 <- 4
4 V 5
5 !
Пример: увеличить

число 3 на единицу (изменить значение в памяти с 3 на 4). Допустим, точно известно, что каретка стоит где-то слева от меток и обозревает пустую ячейку. Тогда программа увеличения числа на единицу может выглядеть так:

Слайд 15

Пример: на ленте машины Поста расположен массив из n меток. Составить программу, действуя

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

Слайд 16

Пример: зацикливание.
1 → 2
2 ← 1

Слайд 17

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

Слайд 18

В зависимости от считываемого символа и собственного состояния, управляющий модуль может

производить следующие операции:
записывать символ алфавита в ячейку (в том числе и пустой), заменяя находившийся в ней (в том числе и пустой);
передвигать головку на одну ячейку влево, вправо или оставаться на месте;
менять свое внутреннее состояние;

Слайд 19