## Functional Programming in Scala 2023-2024 Autumn
# Залік

Увесь курс розподілений на три головні теми:

* машини Тюрінга;
* безтипове λ-числення;
* Scala.

Кожен білет складатиметься з наступних частин:

* Частина A
* комплексне питання або питання на доведення по безтиповому λ-численню;
* Частина B
* питання щодо визначення або формулювання без доказу по машинах Тюрінга;
* питання щодо визначення або формулювання без доказу по безтиповому λ-численню;
* питання щодо визначення або формулювання по Scala;
* Частина C
* практичне завдання на машини Тюрінга, λ-числення або Scala;

## Вибір білета
1. Я генерирую випадкове число від 1 до 5. Результатом буде номер питання частини A.
2. Таким самим чином випадково обираються три питання з частини B: перше -- по машинах Тюрінга, друге -- по безтиповому λ-численню, третє -- по Scala.
3. Я даю одно практичне завдання або на машину Тюрінга, або на λ-числення, або на Scala на свій розсуд.

## Питання к частині A
### Безтипове λ-числення
1. Визначення терма в λ-числення. Зняття та розстановка дужок в λ-терме.
2. Визначення вільних змінних λ-термі. Визначення пов'язаних змінних λ-термі. α-конверсія. Правила заміни.
3. β-редукція. Правила підстановки.
4. Подання булевих значень та операцій у λ-численні: True, False, конструкція if-then-else. Загальне подання нумералів у λ-численні, нумерали Черча, операція succ.
5. Теорема Черча-Россера (без доведення). Слідство про єдиність нормальної форми (з доведенням).

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

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

### Scala
1. Концепція прозорості за посиланням. Чиста функція. Приклади та контрприклади.
2. Функції в Scala, звʼязок функций та def. Рекурсивні функціх.
3. Хвостова рекурсія.
4. Функції вищих порядків.

**GLHF**