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

анализа сложности алгоритмов
Методы построения алгоритмов
Основные алгоритмы обработки информации

порядок действий исполнителя для достижения результата решения задачи за конечное

время.

Алгоритм — это понятные и точные предписания исполнителю совершить конечное число шагов, направленных на решение поставленной задачи.

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

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

некоторого конечного множества элементарных шагов. При этом для выполнения каждого

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

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

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

и машина Поста.
Алгоритм как процедура вычисления некой числовой функции. Рекурсивные

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

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

(по Посту) — программа для машины Поста, приводящая к решению

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

на корректность алгоритма;
останов при выполнении недопустимой команды. Случаи, когда указатель

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

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

циклического процесса. Пусть на ленте имеется запись из нескольких меток

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

увеличить число 3 на единицу (изменить значение в памяти с

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

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

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

может производить следующие операции:
записывать символ алфавита в ячейку (в том

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