Теория алгоритмов - это наука, изучающая общие свойства и закономерности алгоритмов, разнообразные формальные модели их представления. На основе формализации понятия алгоритма возможно сравнение алгоритмов по их эффективности, проверка их эквивалентности, определение областей применимости.
Разработанные в 1930-х годах разнообразные формальные модели алгоритмов (Пост, Тьюринг, Черч), равно как и предложенные в 1950-х годах модели Колмогорова и Маркова, оказались эквивалентными в том смысле, что любой класс проблем, разрешимых в одной модели, разрешимы и в другой.
В настоящее время полученные на основе теории алгоритмов практические рекомендации получают всё большее распространение в области проектирования и разработки программных систем. В связи с этим в государственный стандарт введёна специальная дисциплина “Математическая логика и теория алгоритмов”. Описание государственного стандарта регламентирует включение в состав дисциплины ряда понятий и методов теории алгоритмов.
В данном проекте рассмотрены основы таких разделов теории алгоритмов как: классическая теория алгоритмов (машина Поста, машина Тьюринга, алгоритмически неразрешимые проблемы), асимптотический анализ сложности алгоритмов, включая сложность рекурсивных реализаций, сложностные классы P, NP, NPC, включая проблему P = NP и практический сравнительный анализ алгоритмов. На примере криптосистемы RSA показана практическая важность результатов теории алгоритмов.
