- •Тема 1. Основные понятия и определения дисциплины.
- •1.1 История развития теории алгоритмов.
- •1.2 Роль алгоритмов в науке и технике.
- •1.3 Понятие алгоритма.
- •1.4 Алгоритмический процесс.
- •1.5 Алгоритмы и языки.
- •1.6 Основные вопросы теории алгоритмов.
- •1.7 Классификация алгоритмов.
- •1.8 Свойства алгоритмов.
- •1.9 Методы доказательства корректности алгоритмов.
- •1.10 Сложность алгоритмов.
- •Можно показать, что нижняя граница
- •Сложность рекурсивных алгоритмов.
- •Тема 2. Традиционные подходы в теории алгоритмов.
- •2.1 Рекурсивные функции.
- •Операторы рекурсии.
- •2.2 Нормальные алгорифмы Маркова.
- •2.3 Машина Тьюринга.
- •Тема 3 Алгоритмически неразрешимые проблемы
- •Тема 4 Классы p- (polynomial) и np- (nondeterminated polynomial) задач.
- •4.1 Понятие р- и np-задач.
- •4.3 Примеры задач np-класса.
1.9 Методы доказательства корректности алгоритмов.
I. Корректность эмпирических алгоритмов обычно доказывается экспериментально. Такой алгоритм корректен, если он позволяет получить правильное решение для всего набора допустимых исходных данных.
II. Корректность теоретически обусловленных алгоритмов гарантируется формальным доказательством.
III. Корректность комбинационных алгоритмов, полученных на основе других ранее известных и заведомо корректных алгоритмов, определяется различными методами:
Конструирование алгоритмов. Новый алгоритм получают комбинированием уже известных алгоритм как составных частей.
Метод эквивалентных преобразований алгоритма. Два алгоритма считаются эквивалентными, если:
всякий вариант исходных данных, допустимый для одного алгоритма, также допустим и для другого;
применимость одного алгоритма к каким-либо исходным данным гарантирует, что и другой алгоритм тоже к ним применим;
результаты, даваемые как первым, так и вторым алгоритмами при одинаковых входных данных также одинаковы.
Всякое изменение алгоритма, в результате которого получается новый алгоритм, эквивалентный исходному, называется эквивалентным преобразованием алгоритма.
Интерес представляют такие эквивалентные преобразования корректно обусловленных алгоритмов, в результате которых может быть получен алгоритм более эффективный и тоже корректный.
Метод сужающих преобразований дает алгоритмы, являющиеся частными случаями решения задач, для которых имеются исходные алгоритмы.
Применение формального метода к нематематической проблеме, существующей в какой-либо предметной области.
Запись проблемы на математическом языке позволяет:
определить, существует ли в математике готовый алгоритм решения задачи того же класса;
разработать теоретически обусловленный корректный алгоритм.
Комментарии:
Корректность алгоритмов, полученных первым методом, не вызывает сомнений, если исходные алгоритмы дают точный результат. Если же они дают приближенный результат (алгоритмы численных методов), то обоснование корректности таких алгоритмов может потребовать сложных исследований.
Доказательством корректности алгоритмов, полученных с помощью эквивалентных преобразований, является правильность этих преобразований.
Корректность алгоритмов, полученных посредством сужающих преобразований, обеспечивается проверкой того, что каждый результат, полученный таким алгоритмом, тождественен результату исходного алгоритма.
Корректность алгоритма, полученного в результате формализации проблемы, выясняется либо теми же способами, что и для эмпирических алгоритмов, либо:
оценкой адекватности полученной математической модели, т. е. возможностью получения при ее решении результата, достаточно близкого к искомому результату;
доказательством корректности алгоритма решения математической задачи.
Эвристические алгоритмы тоже требуют обоснования. Их корректность доказывается так же, как для эмпирических алгоритмов, либо согласно формальному методу.