Норма́льный алгори́тм Ма́ркова (НАМ) — один из стандартных способов формального определения понятия алгоритма, так же как и машина Тьюринга. Понятие нормального алгоритма введено А.А. Марковым в конце 1940-х годов. Нормальный алгоритм описывает метод переписывания строк, похожий по способу задания на формальные грамматики. На основе НАМ был создан функциональный язык программирования Рефал.

1 Билет Возникновение теории алгоритмов

Теория алгоритмов как наука. Задачи теории алгоритмов. Дескриптивная и метрическая теория алгоритмов.

Начальной точкой отсчета современной теории алгоритмов можно считать работу немецкого математика Курта Фридриха Гёделя (1931 год - теорема о неполноте символических логик), в которой было показано, что некоторые математические проблемы не могут быть решены алгоритмами из некоторого класса. Общность результата Геделя связана с тем, совпадает ли использованный им класс алгоритмов с классом всех (в интуитивном смысле) алгоритмов. Эта работа вызвала необходимость стандартизации понятия алгоритма.

Первые фундаментальные работы по теории алгоритмов были опубликованы независимо в 30-х годах XX века Аланом Тьюрингом, Алоизом Чёрчем и Эмилем Постом. Предложенные ими машина Тьюринга, машина Поста и лямбда-исчисление Чёрча оказались эквивалентными друг другу. Сформулированные ими тезисы (Поста и Черча-Тьюринга) постулировали эквивалентность предложенных ими формальных систем и интуитивного понятия алгоритма. Важным развитием этих работ стала формулировка и доказательство алгоритмически неразрешимых проблем.

Одним из наиболее удачных стандартизованных вариантов алгоритма является введённое А. А. Марковым понятие нормального алгоритма. Оно было разработано десятью годами позже работ Тьюринга, Поста, Чёрча и Клини в связи с доказательством алгоритмической неразрешимости ряда алгебраических проблем.

К 1960-70-ым годам оформились следующие направления в теории алгоритмов:

1) Классическая теория алгоритмов (формулировка задач в терминах формальных языков, понятие задачи разрешения, введение сложностных классов и др.);

2) Теория асимптотического анализа алгоритмов (понятие сложности и трудоёмкости алгоритма, критерии оценки алгоритмов, методы получения асимптотических оценок, в частности для рекурсивных алгоритмов, асимптотический анализ трудоемкости или времени выполнения);

3) Теория практического анализа вычислительных алгоритмов (получение явных функций трудоёмкости, интервальный анализ функций, практические критерии качества алгоритмов, методика выбора рациональных алгоритмов), основополагающей работой в этом направлении, очевидно, следует считать фундаментальный труд Д. Кнута «Искусство программирования для ЭВМ».

2 Билет

Возникновение термина «алгоритм». Наивное определение понятия "алгоритм". Различные подходы к понятию «алгоритм». Свойства алгоритма.

3 Билет

Теория рекурсивных функций. Рекурсивные функции. Базовые функции. Операторы суперпозиции, примитивной рекурсии и минимизации. Свойства операторов суперпозиции, примитивной рекурсии и минимизации (m-операция). Примитивно-рекурсивные функции. Частично-рекурсивные функции. Свойства примитивно-рекурсивных функций. Примеры примитивно-рекурсивных функций. Относительная примитивная рекурсивность. Свойства относительной примитивной рекурсивности. Тезис Черча. Определение частично рекурсивных функций. Универсальная частично-рекурсивная функция. Примеры частично-рекурсивных функций. Общерекурсивные функции. Примеры общерекурсивных функций.