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

1.

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

2.

Цели и задачи теории алгоритмов
•Формализация понятия алгоритма и исследование
формальных алгоритмических систем.
•Формальные доказательства неразрешимости ряда
задач.
•Классификация задач, исследование сложных
классов.
•Алгоритмический анализ сложности алгоритма.
•Исследование и анализ рекурсивных алгоритмов.
•Получений явных функций трудоемкости
алгоритма с целью их сравнительного анализа.
•Разработка критериев оценки качества алгоритма.

3.

Понятие алгоритма интерпретируют
как точное описание, определенный
процесс,
набор
вычислительных
действий, соответствующих этому
вычислительному процессу.
Такое определение не является
строгим, так как в нем используют
произвольные данные.
Определение является интуитивным.

4.

цели за конечное число шагов.
Алгоритм
это
строгая
и
четкая
конечная
система
правил,
определяющая
последовательность действий
над
некоторыми
объектами,
которая после конечного числа
шагов приводит к достижению
поставленной
цели.
Появились задачи, для которых
невозможно
было
построить
алгоритм,
но
нельзя
было
доказать
невозможность
алгоритмического
решения
задачи.
Построить
формальное
определение алгоритма.

5.

Среди других определений рассматривают
определение Колмогорова:
Алгоритм – всякая система вычислений по
определенным данным, которые после числа
шагов приводят к решению задачи.
Определение Маркова:
Алгоритм
–
точное
предписание,
определенный
вычислительный
процесс,
варьирует исходные данные к результату.
Определения не являются математически
строгими и характеризуют набор свойств
алгоритма.

6.

Свойства алгоритма:
Дискретность информации. Каждый алгоритм имеет дело с
входными, промежуточными, выходными данными, которые
представлены в виде конечных слов в некотором формате.
Дискретность работы алгоритма. Алгоритм выполняется по
шагам. На каждом шаге выполняется только одна операция.
Выполнимость операций. В алгоритме не должно быть
невыполнимых операций.
Конечность алгоритма. Описание алгоритма должно быть
конечным.
Детерминированность алгоритма. Каждый шаг алгоритма
строго определен. После каждого шага указывается какой
шаг сделать следующим или указывается, что алгоритм
должен закончить работу.
Массовость алгоритма. Алгоритм должен решать задачи из
данного класса задач. Если найдется задача, для которой
алгоритм не применим, то последовательность нельзя
назвать алгоритмом.

7.

1. Описываемый процесс должен быть разбит на последовательность
отдельных шагов. Возникающая в результате такого разбиения запись
представляет собой упорядоченную совокупность четко разделенных друг
от друга предписаний (директив, команд, операторов), образующих
прерывную (или, как говорят, дискретную) структуру алгоритма. Только
выполнив требования одного предписания, можно приступить к
выполнению следующего. Рассмотренное свойство алгоритмов называют
дискретностью.
2. Используемые на практике алгоритмы составляются с ориентацией на
определенного исполнителя. Чтобы составить для него алгоритм, нужно
знать, какие команды этот исполнитель может понять и исполнить, а какие
- не может. У каждого исполнителя имеется своя система команд.
Очевидно, составляя запись алгоритма для определенного исполнителя,
можно использовать лишь те команды, которые имеются в его системе
команд. Это свойство алгоритмов будем называть понятностью.

8.

3. Будучи понятным, алгоритм не должен содержать предписаний, смысл
которых может восприниматься неоднозначно, т.е. одна и та же команда,
будучи понятна разным исполнителям, после исполнения каждым из них
должна давать одинаковый результат. Запись алгоритма должна быть
настолько четкой, полной и продуманной в деталях, чтобы у исполнителя
не могло возникнуть потребности в принятии решений, не
предусмотренных составителем алгоритма. Отмеченное свойство
алгоритмов называют определенностью или детерминированностью.
4. Результативность. При точном исполнении всех предписаний
алгоритма процесс должен прекратиться за конечное число шагов и при
этом должен получиться определенный результат. Вывод о том, что
решения не существует - тоже результат.
5.Алгоритмы должны обеспечить решение не одной конкретной задачи, а
некоторого класса задач данного типа. Это свойство алгоритма
называют массовостью. В простейшем случае массовость обеспечивает
возможность использования различных исходных данных.

9.

Подходы к формализации понятия «алгоритм»:
• теория конечных и бесконечных автоматов;
• теория вычислимых (рекурсивных) функций;
• λ-исчисление Черча.

10.

Тезис Тьюринга:
Всякий алгоритм может быть
реализован машиной Тьюринга.
Тезис Маркова:
Всякий алгоритм нормализуем.