– см. в тетради!

1 Билет

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

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

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

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

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

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

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

3) Теория практического анализа вычислительных алгоритмов (получение явных функций трудоёмкости, интервальный анализ функций, практические критерии качества алгоритмов, методика выбора рациональных алгоритмов).

2 Билет

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

3 Билет

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

С каждый алгоритмом однозначно связана функция, которую он вычисляет. Возникает естественный вопрос, для всякой ли функции существует вычисляющий её алгоритм? Если нет, то для каких функций он существует, как описать такие, как говорят, алгоритмически или эффективно вычислимые функции?

Исследование этих вопросов привело к созданию в 1930-х годах теории рекурсивных функций. Сначала были выбраны простейшие функции, эффективная вычисляемость которых была очевидна. Затем сформулированы некоторые правила (операторы), на основе которых можно строить новые функции из уже имеющихся. Тогда требуемым классом функций будет совокупность всех функций, получающихся из простейших с помощью выбранных операторов.

Рекурсия - метод определения функции через её предыдущие и ранее определенные значения, а так же способ организации вычислений, при котором функция вызывает сама себя с другим аргументом.

Некоторые функции являются первичными (базовыми). Их нельзя заменить вычислением более простых функций. Из этих первичных функций строится с помощью определенных операций всё множество известных нам вычислимых функций. Таких базовых функций всего три:

А) Функция константа

Б) Функция непосредственного следования (взятие следующего за данным числа)

В) Тождественная функция (для повторения значения одного из своих аргументов)

Для построения более сложных функций из первичных используют следующие операторы:

• Операция подстановки (супер-позиция). Эта операция заключается в том, что вместо каких-то переменных функции подставляют другие функции от тех же или иных переменных.

Пример 1.

Пусть и . Тогда подставив вместо переменной х функцию g(у), получим новую функцию:

• Операция примитивной рекурсии. Эту операцию можно представить следующим образом

Пример 2.

Пусть - известная вычислимая функция. Определим новую функцию f(x) следующим образом:

Это и есть определение функции с помощью операции примитивной рекурсии. Например, пусть

Это есть определение целочисленного умножения. Так f(3,3)=f(3,2)+3=f(3,1)+3+3=3+3+3=9.

• Операция минимизации (взятия минимального корня). Эта операция не всегда дает результат или, как говорят, не является полностью определенной (тотальной). Ее определение таково:

.

Эту операции можно для простоты обозначить как _y f(x,y).

Пример 3. Пусть . Тогда _y f(3,y)=2.

Частично рекурсивная функция - частичная функция, которая получена конечным числом операций суперпозиций, примитивных рекурсий и минимизации.

Частичная функция – функция от одного или нескольких аргументов, заданных на множестве всех положительных целых чисел или на некоторых его подмножествах.

Тезис Черча. Класс всех частично вычислимых функций над Z₊ совпадает с классом всех частично рекурсивных функций.

Иными словами, если функция является частично-рекурсивной, то она одновременно и вычислима.

Примитивно рекурсивная функция - функция, определяемая из базовых функций с помощью операций подстановки и/или примитивной рекурсии.

Общерекурсивная функция – всюду определённая частично-рекурсивная функция.