6.1 Елементи теорії моделей
6.1.1 Поняття теорії моделей
6.1.2 Моделі та структури в теорії моделей
6.1.3 Інтерпретації формальних мов
6.1.4 Теорія повноти (Completeness Theorem) (для логіки першого порядку)
6.1.5 Принцип перенесення (Transfer Principle) моделей (для логіки першого порядку)
6.1.6 Визначуваність (Definability)
6.2 Теорія обчислюваності
6.2.1 Основи обчислюваності (Computability)
6.2.1.1 Визначення теорії обчислюваності
6.2.1.2 Поняття обчислюваної функції (Computable Function)
6.2.1.3 Примітивно-рекурсивні функції (Primitive Recursive Functions)
6.2.1.4 Частково-рекурсивні функції (Partial Recursive Functions)
6.2.1.5 Теза Черча-Тюрінга (Church–Turing
Thesis)
6.2.2 Розв’язність та розпізнаваність
6.2.2.1 Задача про прийняття рішень (Decision problem)
6.2.2.2 Розв’язні, напіврозв’язні та нерозв’язні проблеми
6.2.2.2.1 Розв’язні (Decidable)
проблеми
6.2.2.2.2 Напіврозв’язні (Semidecidability/Recursively enumerable/Recognizability) проблеми (розпізнавані проблеми)
6.2.2.2.3 Нерозв’язні (Undecidable)
проблеми
6.2.2.3 Проблема зупинки машини Тюрінга (Halting Problem)
6.2.2.4 Нерозв’язувана (Undecidable) задача про прийняття рішень та степінь Тюрінга (Turing Degrees)
6.2.3 Необчислюваність (Uncomputability)
6.2.3.1 Поняття необчислюваної функції (Uncomputable function)
6.2.3.2 Теореми Геделя про неповноту (Gödel's Incompleteness Theorems)
6.2.3.3 Обчислення з оракулом
6.2.4 Нумерації та універсальність (Gödel Numbering, Enumeration, Universality)
6.2.4.1 Нумерації алгоритмів
6.2.4.2 Нумерація Геделя
6.2.4.2 Головні універсальні функції та множини
6.2.4.3 Канторові нумерації кортежів натуральних чисел
6.2.4.4 Нумерації Кліні та Поста
6.2.4.5 Нумерація машин Тюрінга та частково-рекурсивних
функцій
6.2.4.6 Snm-теорема (Smn-теорема) та теорема Кліні про нерухому точку
6.2.5 Зведення однієї
задачі до іншої за поліноміальний час
6.2.5.1 Зведення однієї задачі до іншої за поліноміальний
час
6.2.5.2 Зведення Карпа (Karp reductions, many-one reductions)
6.2.5.3 Зведення Кука (Cook reduction)
6.2.5.4 Зведення Левіна (Levin reduction)
6.2.5.5 Зведення через таблицю істинності (truth-table reduction)
6.2.5.6 Зведення Тюрінга (Turing reduction)
6.3 Елементи теорії категорій
6.3.1 Поняття теорії категорій
6.3.2 Приклади категорій
6.3.3 Дуальна категорія (Dual category)
6.3.4 Морфізми в теорії категорій (Morphisms)
6.3.5 Початкові та термінальні об'єкти (Initial and terminal objects)
6.3.6 Функтори в теорії категорій
6.3.7 Натуральні перетворення (Natural transformations)
6.3.8 Категорії множин (Set category)
6.3.9 Категорії типів (Type
categories)
6.3.10 Картезіансько-замкнені (декартово замкнені) категорії (Cartesian
closed categories)
6.3.8 Моноїдальні (тензорні) категорії (Monoidal categories)
6.4 Імперативний та декларативний підходи до програмування
6.4.1 Класифікація парадигм програмування
6.4.2 Імперативне програмування (Imperative programming): структурне програмування (Structured programming), процедурне
програмування (Procedural programming)
та об’єктно-орієнтоване програмування (Object-Oriented
Programming, OOP)
6.4.3 Декларативне програмування (Declarative programming): функційне програмування (Functional programming), логічне
програмування (Logic programming) та
символьне і правилове програмування (Rule-based
and symbolic programming)
6.4.4 Семантична відмінність: опис «як зробити» проти «що
зробити»
6.4.5 Сучасні тренди у парадигмах програмування:
реактивне програмування (Reactive
programming), потокове програмування (Stream
processing), асинхронне та подійно-орієнтоване програмування
6.5 Функційні моделі обчислень та парадигма функційного програмування. Комбінаторна логіка.
6.5.1 Функційні моделі обчислень
6.5.1.1 Лямбда числення
6.5.1.1.1 Вступ до лямбда числення
6.5.1.1.2 Підстановки та перетворення при застосуванні лямбда числення
6.5.1.1.3 Розширення чистого лямбда числення
6.5.1.1.4 Теорема про нерухому точку
6.5.1.1.5 Редекси і нормальна форма
6.5.1.1.6 Теорема Черча-Россера
6.5.1.1.7 Редукція термів в лямбда численні
6.5.1.1.8 Типізоване лямбда числення
6.5.1.1.8.1 Поняття типу в типізованому лямбда численні
6.5.1.1.8.2 Просте типізоване лямбда числення
6.5.1.1.8.3 Підстановка типу та уніфікація
6.5.1.2 Комбінаторна логіка (як варіант лямбда числення)
6.5.1.3 Комбінаційна логіка (як функційна модель обчислень)
6.5.1.4 Абстрактна система переписувань (Abstract rewriting system)
6.5.2 Парадигма функційного програмування
6.5.3 Функційне програмування за допомогою сучасних мов програмування
6.5.3.1 Мова функційного програмування Haskell
6.5.3.1.1 Програмування на Haskell
6.5.3.1.2 Базові типи в Haskell
6.5.3.1.3 Системи модулів в Haskell
6.5.3.1.4 Списки в Haskell
6.5.3.1.5 Види поліморфізму. Параметричний та спеціальний поліморфізм в Haskell.
6.5.3.1.6 Класи типів в Haskell
6.5.3.1.7 Стандартні класи типів в Haskell
6.5.3.1.8 Реалізації класів типів в Haskell
6.5.3.1.9 Згортки в Haskell
6.5.3.1.10 Моноїди в Haskell
6.5.3.1.11 Клас типів Foldable
6.5.3.1.12 Функтори в Haskell
6.5.3.1.13 Клас типів Pointed
6.5.3.1.14 Аплікативні функтори
6.5.3.1.15 Клас типів Traversable
6.5.3.1.16 Клас типів монад
6.5.3.1.17 Монада Maybe
6.5.3.1.18 Монада IO
6.5.3.1.19 Монада Reader та монада Writer
6.5.3.1.20 Монада State
6.5.3.2. Загальний огляд засобів функційного програмування на С++
6.5.3.3. Загальний огляд мов функційного програмування Erlang та Elixir
6.5.3.4. Загальний огляд інших засобів функційного програмування
6.6 Паралельні моделі обчислень та парадигма реактивного програмування. Паралельне програмування.
6.6.1 Паралельні моделі обчислень
6.6.1.1 Мережа процесів Кана
6.6.1.2 Мережа Петрі
6.6.1.3 Мережа взаємодій
6.6.1.4 Синхронний потік даних
6.6.2 Парадигма реактивного програмування
6.6.3 Функційне реактивне програмування
6.6.4 Реактивне програмування за допомогою бібліотеки ReactiveX
6.6.4.1 Шаблон спостерігача (Observer pattern) та його розширення у ReactiveX
6.6.4.2 Сутності для спостереження (Observable)
6.6.4.3 Оператори бібліотеки ReactiveX
6.6.4.4 Сутність Single
6.6.4.5 Сутність суб’єкту (Subject)
6.6.4.6 Планувальник (Scheduler) рушія бібліотеки ReactiveX
6.6.4.7 Реалізації ReactiveX для
популярних мов програмування
6.6.5 Загальний огляд реактивного програмування за
допомогою фреймворку Spring WebFlux з набору фреймворків Spring
6.6.6 Паралельне програмування
6.7 Шаблони проектування програмного забезпечення
6.7.1 Використання шаблонів при проектуванні програмного забезпечення
6.7.2 GoF-шаблони
6.7.2.1 Твірні шаблони (Creational pattern)
6.7.2.2 Структурні шаблони (Structural pattern)
6.7.2.3 Поведінкові шаблони (Behavioral pattern)
6.7.3 GRASP-шаблони
6.7.4 Шаблони рівночасних обчислень (Concurrency pattern)
6.7.5 Шаблони архітектури програмного забезпечення (Architectural pattern)
6.7.6 Використані шаблони в ядрі Linux