Глава 5. Введение в теорию алгоритмов
Понятие алгоритма является одним из основных понятий информатики. Эта глава посвящена пониманию природы алгоритмов как процесса обработки информации механического характера. В главе рассматриваются как классические проблемы теории алгоритмов (машина Тьюринга, тезис Черча-Тьюринга, алгоритмически неразрешимые проблемы и вопросы сложности алгоритмов), так и более недавно разработанные разделы, связанные с практическими проблемами проверки правильности алгоритмов - их верификация. Кроме того, рассматривается раздел, в классической теории алгоритмов не упоминаемый - это параллельные алгоритмы и их верификация на основе темпоральной логики.
В результате изучения материала этой главы читатель должен получить:
-
общее представление об алгоритмах и методах их формального представления;
-
умение представлять простейшие алгоритмы в виде программы для машины Тьюринга;
-
понимание смысла и значения тезиса Черча-Тьюринга, представление об алгоритмически неразрешимых проблемах;
-
знание о методах оценки сложности вычислительных алгоритмов и опыт оценки сложности;
-
знание основ теории корректности алгоритмов преобразования данных и ее использования при генерировании тестов;
Содержание главы 5
Понятие алгоритма. Формы представления алгоритмов. Машина Тьюринга. Машина Поста. Рекурсивные функции. Тезис Черча-Тьюринга. Алгоритмически неразрешимые проблемы. Сложность алгоритмов, методы оценки сложности. Подход Флойда к верификации последовательных программ обработки данных. Применение метода Флойда: систематический метод генерации тестов для программ обработки данных.
Примеры задач к главе 5:
-
Оценить сложность заданной программы.
-
Построить полное множество тестовых примеров для программы, заданной своей блок-схемой
СВЕДЕНИЯ ОБ АВТОРЕ
Карпов Юрий Глебович,
д.т.н., профессор,
заведующий кафедрой “Распределенные вычисления и компьютерные сети” факультета Технической кибернетики СПбГТУ
Тел: рабочий: 247-1639
домашний: 557-2585