# Зачет

## Структура билета
Весь курс разбит на четыре главные темы:
* машины Тьюринга;
* вычислимые функции;
* бестиповое λ-исчисление;
* Scala.

Каждый билет будет состоять из следующих частей:
* Часть А
* первый вопрос: комплексный вопрос или вопрос на доказательство;
* Часть B
* второй вопрос: вопрос на описание, определение или формулировку без доказательства;
* третий вопрос: вопрос на описание, определение или формулировку без доказательства;
* Часть C
* практическое задание;
* решение задачи на Scala.

## Выбор билета
1. Вы загадываете и сообщаете мне число от 1 до 21. Я генерирую случайное число от 1 до 21. Перемножаю Ваше и свое число. Результатом остатка от деления прозведения на 21 будет номер вопроса из части A.
2. Случайным образом выбираются 2 темы, из списка тем, за исключением той темы, которая вошла в первый вопрос. По каждой из двух тем проводится процедура, описанная выше, т.о. выбираются два вопроса из части B.
3. Я даю одно практическое задание или на машину Тьюринга, или на λ-исчисление по своему усмотрению.
4. Я даю задачу для решения на Scala.

## Вопросы к части A
### Машина Тьюринга
1. Задание одноленточной машины Тьюринга. Конфигурация одноленточной машины Тьюринга. Протокол одноленточной машины Тьюринга. Детерминизм машины Тьюринга.
2. Задание многоленточной машины Тьюринга. Конфигурация многоленточной машины Тьюринга. Протокол многоленточной машины Тьюринга. Связь одноленточной и многоленточной машин Тьюринга.

### Вычислимые функции
3. Перечислимые множества, эквивалентные определения перечислимых множеств. Доказательство эквивалентности двух определений на выбор.
4. Теорема об объединении и пересечении перечислимых множеств. Доказательство.
5. Теорема Поста. Доказательство.
6. Понятие универсальной функции. Теорема о существовании универсальной функции. Доказательство.
7. Теорема о (не)существовании всюду определенной универсальной функции. Доказательство.
8. Теорема о существовании вычислимой функции, от которой любая другая функция не может всюду отличаться. Доказательство.
9. Теорема о существовании вычислимой функции, не имеющей всюду определенного определенного вычислимого продолжения. Доказательство.
10. Теорема о существовании перечислимого неразрешимого множества. Доказательство. Проблема останова.
11. Определение примитивно рекурсивной функции
* Базисные функции
* Композиция
* Примитивная рекурсия
12. Определение частично рекурсивной функции. Оператор минимизации.

### Бестиповое λ-исчисление
13. Определение терма в λ-исчислении. Снятие и расстановки скобок в λ-терме.
14. Определение свободных переменных λ-терме. Определение связанных переменных λ-терме. α-конверсия. Правила замены.
15. β-редукция. Правила подстановки.
16. Теорема о неподвижной точке. Комбинатор неподвижной точки. Доказательство.
17. Представление булевых значений и операций в λ-исчислении: True, False, конструкция if-then-else. Общее представление нумералов в λ-исчислении, нумералы Чёрча, операция succ.
18. Представление примитивно рекурсивных функций λ-исчислении.
19. Теорема Чёрча-Россера (без доказательства). Следствие о единственности нормальной формы (с доказательством).

### Scala
20. Функции в Scala, связь функций и def. Рекурсивные функции. Хвостовая рекурсия. Функции высших порядков.
21. Type parameter. Верхние и нижние границы для type parameter. Ковариантность, контрвариантность и инвариантность и их связь с подтипами и супертипами.

## Вопросы к части B
### Машина Тьюринга
1. Понятие вычислимости по Тьюрингу.
2. Задание одноленточной машины Тьюринга.
3. Конфигурация одноленточной машины Тьюринга.
4. Протокол одноленточной машины Тьюринга.
5. Детерминизм машины Тьюринга.
6. Задание многоленточной машины Тьюринга.
7. Конфигурация многоленточной машины Тьюринга.
8. Протокол многоленточной машины Тьюринга.
9. Связь одноленточной и многоленточной машин Тьюринга.

### Вычислимые функции
1. Понятие вычислимой функции.
2. Разрешимые множества.
3. Перечислимые множества.
4. Теорема поста.
5. Понятие универсальной функции.
6. Перечислимое неразрешимое множество. Проблема останова.
7. Определение примитивно рекурсивной функции: базисные функции.
8. Определение примитивно рекурсивной функции: композиция.
9. Определение примитивно рекурсивной функции: примитивная рекурсия.
10. Определение частично рекурсивной функции: оператор минимизации.

### Бестиповое λ-исчисление
1. Определение терма в λ-исчислении.
2. Снятие и расстановки скобок в λ-терме.
3. Определение свободных переменных λ-терме.
4. Определение связанных переменных λ-терме.
5. α-конверсия. Правила замены.
6. β-редукция.
7. Правила подстановки при β-редукции.
8. Комбинатор неподвижной точки.
9. Представление булевых значений и операций в λ-исчислении: True, False, конструкция if-then-else.
10. Общее представление нумералов в λ-исчислении, нумералы Чёрча.
11. Операция succ на нумералах Чёрча.
12. Представление примитивно рекурсивных функций λ-исчислении: базисные функции.
13. Представление примитивно рекурсивных функций λ-исчислении: композиция.
14. Представление примитивно рекурсивных функций λ-исчислении: примитивная рекурсия.
15. Теорема Чёрча-Россера. Следствие о единственности нормальной формы.

### Scala
1. Понятие ссылочной прозрачности. Чистая функция. Примеры и контрпримеры.
2. Функции в Scala, связь функций и def. Рекурсивные функции.
3. Хвостовая рекурсия.
4. Функции высших порядков.
5. Type parameter: верхние и нижние границы для type parameter.
6. Type parameter: ковариантность, контрвариантность и инвариантность и их связь с подтипами и супертипами.

**GLHF**