1. Уметь дать определения следующих понятий и привести соответствующие примеры применительно к теории алгоритмов:

  - алфавит,

  - слово,

  - язык.

2. Конструктивное пространство, вычислимые функции. Дать определение и привести примеры.

3. Детерминированные конечные автоматы. Диаграммы Мура. Языки, распознаваемые конечными автоматами.

4. Машина Тьюринга. Внешний и внутренний алфавиты. Состояния, правила переходов. Арифметические действия на МТ, унарная запись числа. Тезис Тьюринга.

5. Уметь конструировать МТ для выполнения следующих арифметических операций над числами, заданными в унарном виде:

   - сложение двух натуральных чисел,

   - вычитание из натурального числа двойки,

   - умножение целого числа на двойку,

   - деление целого числа на двойку.

6. Примитивно рекурсивные функции. Базис Клини. Операции суперпозиции и примитивной рекурсии. Частично рекурсивные функции, общерекурсивные функции. Операция минимизации. Пример частично рекурсивной функции, которая не является примивно рекурсивной. Тезис Черча.

7. Уметь составлять следующие примитивно рекурсивные функции, используя базис Клини и операции примитивной рекурсии и суперпозиции:

- SUM(x,y) = x + y,

- MUL(x,y) = x*y,

- EXP (x,y) = x в степени y,

- TETR (x,y) - операция тетрации,

- FAC(x) = факториал x,

- PRED(x) = x - 1, x >0, 0 в противном случае,

- DIFF(x,y) = x - y, x > y, 0 в противном случае,

- ABS (x,y) = |x-y|,

- sg(x) = 1, x > 0, 0 в противном случае,

- anti_sg(x,y) = 0, x >0, 1 в противном случае,

- REM(x,y) - остаток от деления x на y,

- MOD(x,y) - целая часть при делении x на y.

8. Количественное определение вычислительной сложности. Классы сложности P, EXP, NP. Уметь привести примеры задач, относящихся к данным классам сложности. NP полные задачи. Привести примеры NP полных задач.

9. Количественный анализ эффективности алгоритмов. Минимальное, максимальное, среднее значения количества выполнения шагов алгоритма. Производящие функции и их использование для вычисления математического ожидания.

Анализ алгоритма нахождения максимального элемента в массиве.

10. Парадигмы (подходы) к построению алгоритмов:

 -Рекурсия,

-Divide and conquer,

-Dynamic programming,

-Greedy,

-Backtracking.

Привести примеры задач, эффективно решаемых данными алгоритмами.