ТАФЯ — чек-лист самопроверки
Используйте после прохождения обзора и статей 40–45. Цель — проверить понимание, а не вызубрить определения: отвечайте своими словами, затем сверяйтесь с подсказками ниже и с указанными статьями.
- Закройте подсказки и ответьте на вопрос в 2–4 предложениях или нарисуйте схему.
- Если застряли — откройте только «Куда смотреть», без «Суть ответа».
- После ответа сверьтесь с «Суть ответа» и при необходимости перечитайте раздел статьи.
- Вопросы 31–35 — связка с реальной разработкой; их удобно обсуждать в паре «теория + код».
Блок 1. Алгоритмы и вычислимость
1. Чем задача отличается от экземпляра?
Куда смотреть: 40, раздел «Общее понятие алгоритма», таблица задача / экземпляр.
Суть ответа: задача — семейство «вход → ответ» для всех допустимых входов одного типа; экземпляр — один конкретный вход (один файл, один массив). Алгоритм описывает задачу целиком.
2. Назовите пять свойств алгоритма в формулировке теории.
Куда смотреть: 40, «Основные требования» и сводная таблица.
Суть ответа: дискретность, определённость (детерминированность в постановке), конечность (завершаемость на допустимых входах), массовость, результативность; часто отдельно упоминают конструктивность и (на другом уровне) эффективность.
3. Что такое алфавитный оператор и как он связан с распознавателем?
Куда смотреть: 40, «Понятие алфавитного оператора».
Суть ответа: правило Σ* → Σ* (или в {да, нет}), преобразующее строку. Распознаватель языка — оператор, который по слову отвечает, входит ли оно в язык L.
4. Перечислите четыре формальные модели вычисления и сформулируйте тезис Чёрча–Тьюринга.
Куда смотреть: 40, таблица моделей; 42.
Суть ответа: машина Тьюринга, λ-исчисление, частично-рекурсивные функции, нормальные алгоритмы Маркова (достаточно трёх + одна). Тезис: всё интуитивно эффективно вычислимое реализуемо на МТ (и эквивалентных моделях).
5. Чем примитивная рекурсия отличается от рекурсии в Python?
Куда смотреть: 41, callout «Не путать»; схема примитивной рекурсии.
Суть ответа: в Python — способ написать код; примитивная рекурсия — строгая схема из базовых функций, дающая только тотальные функции с гарантированным завершением. Обычный рекурсивный def без ограничений может не уложиться в примитивный класс (хотя может быть вычислимым).
6. Почему функция Аккермана вычислима, но не примитивно рекурсивна?
Куда смотреть: 41, раздел про Аккерман.
Суть ответа: для каждой пары (m,n) результат конечен — есть алгоритм (МТ / μ-рекурсия). Рост слишком быстрый, чтобы выразить конечным числом применений только примитивных схем от S и проекций.
7. Чем разрешимый язык отличается от рекурсивно перечислимого?
Куда смотреть: 41, таблица «Языки и множества».
Суть ответа: разрешимый — и «да», и «нет» решаются алгоритмом с остановкой. RE — есть полуалгоритм: для слов из языка ответ «да» за конечное время; для слов вне языка процедура может не остановиться.
8. Сформулируйте проблему остановки и идею доказательства.
Куда смотреть: 42, «Проблема остановки», диаграмма с D.
Суть ответа: нет программы, которая для любой пары (код P, вход x) всегда за конечное время решает, остановится ли P на x. Доказательство: предположить такую H, построить D, ведущую себя противоположно H на входе ⟨D⟩ — противоречие.
9. Что делает универсальная машина Тьюринга?
Куда смотреть: 42, «Универсальная машина».
Суть ответа: одна фиксированная МТ U, которая на ленте получает код программы ⟨P⟩ и вход x и симулирует шаги P на x — аналог интерпретатора / VM.
10. Назовите одну разрешимую и одну неразрешимую задачу про программы.
Куда смотреть: 42, таблицы; 44 для разрешимых на подклассе.
Суть ответа (примеры): разрешимая — «принимает ли ДКА слово w»; «эквивалентны ли два минимальных ДКА». Неразрешимая в общем виде — остановка, эквивалентность двух произвольных программ, тотальность семантики (дух теоремы Райса в 41).
Блок 2. Грамматики и разбор
11. Запишите кортеж G = (N, Σ, P, S) и поясните компоненты.
Куда смотреть: 43, «Основные понятия».
Суть ответа: N — нетерминалы, Σ — терминалы, P — правила, S — стартовый символ. Язык — все строки только из терминалов, выводимые из S.
12. Чем сентенциальная форма отличается от предложения?
Куда смотреть: 43, «Сентенциальные формы».
Суть ответа: сентенциальная форма — промежуточная строка (терминалы + нетерминалы); предложение — сентенциальная форма без нетерминалов (готовое «слово» языка).
13. Чем дерево вывода отличается от AST?
Куда смотреть: 43, таблица после «Дерево вывода».
Суть ответа: дерево вывода отражает все применения правил грамматики; AST — сжатое дерево для семантики и оптимизаций, без синтаксического шума.
14. Перечислите типы 0–3 по Хомскому и автоматы.
Суть ответа: 3 — регулярная / КА; 2 — КС / МП-автомат; 1 — контекстно-зависимая / ЛОА; 0 — без ограничений / МТ. Вложение 3 ⊂ 2 ⊂ 1 ⊂ 0.
15. Чем левый вывод связан с LL, правый — с LR?
Куда смотреть: 43, «Левый и правый вывод».
Суть ответа: LL строит левосторонний вывод (сверху вниз); LR сворачивает к корню, соответствует правостороннему выводу (снизу вверх).
16. Пример неоднозначной грамматики.
Куда смотреть: 43, «висячий else», приоритет + и *.
Суть ответа: вложенные if без else / if … else — два дерева; или a + b * c без приоритета в грамматике — два дерева с разной группировкой.
17. Зачем устраняют левую рекурсию перед LL(1)?
Куда смотреть: 43, «Преобразования КС-грамматик».
Суть ответа: LL-разбор «разворачивает» нетерминал слева; правило A → Aα заставляет снова выбирать A без продвижения по входу — бесконечная рекурсия в парсере. Замена на A → βA', A' → αA' | ε устраняет это.
18. Для чего FIRST и FOLLOW?
Куда смотреть: 43, «LL(1)».
Суть ответа: FIRST — с каких терминалов может начаться вывод из символа/строки; FOLLOW — что может идти после нетерминала. Вместе заполняют таблицу LL(1): по текущему нетерминалу и lookahead выбирают правило.
19. Почему { aⁿbⁿ } не регулярный, но обычно КС?
Куда смотреть: 44, лемма о накачке; 45, стек.
Суть ответа: нужен счётчик a перед b — КА с конечной памятью не помнит произвольное n. МП-автомат кладёт a на стек и снимает на b — язык КС.
20. Почему { aⁿbⁿcⁿ } не контекстно-свободный?
Куда смотреть: 43, лемма о накачке для КС.
Суть ответа: накачка для КС позволяет «раздувать» два сегмента v и y синхронно; для трёх блоков aⁿbⁿcⁿ при накачке нарушается равенство трёх счётчиков — язык требует тип 1 (или сильнее), не чистый КС.
Блок 3. Автоматы
21. Кортеж ДКА и условие принятия слова.
Куда смотреть: 44.
Суть ответа: A = (Q, Σ, δ, q₀, F); слово w принято, если δ̂(q₀, w) ∈ F.
22. Почему НКА не сильнее ДКА по языкам?
Куда смотреть: 44, детерминизация подмножеств.
Суть ответа: каждый НКА можно преобразовать в эквивалентный ДКА (состояния ДКА — подмножества состояний НКА); класс языков тот же.
23. Построение НКА из regex (Thompson).
Куда смотреть: 44, таблица Thompson.
Суть ответа: рекурсивно собирают мини-автоматы для ∅, ε, символа, объединения, конкатенации, звезды с ε-переходами; в конце — один НКА для всего выражения.
24. Что делает детерминизация подмножеств?
Куда смотреть: 44.
Суть ответа: строит ДКА, чьи состояния — множества состояний НКА (после ε-замыкания); переход по символу a — объединение δ(q,a) по всем q из множества, снова замыкание.
25. Лемма о накачке и aⁿbⁿ.
Куда смотреть: 44.
Суть ответа: в ДКА после p символов повторяется состояние на префиксе из a; накачка только y из a даёт слово с лишними a и тем же числом b — не в языке aⁿbⁿ.
26. Минимальный ДКА и Майхилл–Нероде.
Куда смотреть: 44.
Суть ответа: минимальный ДКА — наименьшее число состояний для языка; Нероде: язык регулярен ⟺ отношение «строки z ведут себя одинаково» имеет конечное число классов.
27. Где в компиляторе КА, где МП-автомат?
Куда смотреть: 44, 45, диаграмма пайплайна.
Суть ответа: лексер — ДКА/regex; синтаксический парсер — МП-автомат (стек) + грамматика.
28. Компоненты МП-автомата и роль стека.
Куда смотреть: 45.
Суть ответа: Q, Σ, Γ, δ, q₀, Z₀, F; стек хранит вложенность (нетерминалы, маркеры скобок), LIFO.
29. Мили и Мура.
Куда смотреть: 45, таблица.
Суть ответа: Мили — выход на переходе (ребре); Мура — выход привязан к состоянию. Классы эквивалентны с ростом числа состояний при преобразовании.
30. Диагностическая последовательность.
Куда смотреть: 45, 44 минимизация.
Суть ответа: входная цепочка, на которой два состояния (или два автомата) ведут себя по-разному — их можно различить; если такой цепочки нет, состояния сливают при минимизации.
Практические вопросы
31. Почему regex не заменяет парсер JSON?
Суть ответа: JSON с вложенными объектами и массивами — КС (нужен стек), regex — регулярный уровень 44. Плюс семантика (числа, escape) — отдельные правила.
32. Почему статический анализ «всех багов» невозможен?
Суть ответа: полная проверка произвольной семантики упирается в неразрешимость остановки и теорему Райса; инструменты ограничивают класс программ или свойств.
33. ReDoS и тип автомата.
Суть ответа: наивный backtracking regex может перебирать экспоненциально много путей; детерминированный ДКА после компиляции даёт линейное время по длине входа 44.
34. Когда «сессия как 5 кружков» ломается?
Суть ответа: вложенные подсценарии (оплата внутри заказа, 3DS) требуют стека состояний 45, а не одного плоского КА 44.
35. Уровень Хомского для сбалансированных скобок?
Суть ответа: тип 2 (КС), МП-автомат 45; регулярного типа 3 44 недостаточно.
Типичные путаницы (самопроверка)
| Путают | На самом деле |
|---|---|
| «Рекурсия в Python» = «примитивная рекурсия» | разные уровни: код vs формальная схема 41 |
| «Недетерминированный» = «случайный» | в НКА «существует путь»; в коде — random 44 |
| «МТ = реальный ПК» | МТ с бесконечной лентой; ПК с лимитом RAM 42 |
| «AST = дерево вывода» | AST сжатое 43 |
| «PEG = КС» | упорядоченный выбор / — другая семантика 43 |
Оценка готовности
| Результат | Что делать дальше |
|---|---|
| ≥ 28 уверенных ответов | можно углублять компилятор и алгоритмы |
| 15–27 | перечитайте слабые блоки по таблице «куда смотреть» |
| меньше 15 | пройдите цепочку 40→45 по одной статье в день с мини-лабораторными |
Назад к обзору ТАФЯ.
См. также
Другие статьи этого же раздела в боковом меню (как на странице «О разделе»). Когнитивистика для разработчиков — память, чанкинг, нагрузка при чтении кода и осознанное обучение новым технологиям. История термина «ментальная модель» - Крейк о внутренних представлениях мира, которые строит когнитивная система. Единый процесс - согласованные по цели, времени и пространству действия участников ради одного результата. Что такое система и её элементы, как все это связано и зачем нужно. Краткое знакомство с науками, которые лежат в основе логики программ, данных и вычислений — от булевой алгебры до теории информации. Булева и предикатная логика для разработки — операции, таблицы истинности, кванторы и законы де Моргана в условиях кода. Множества, отношения, графы и комбинаторика — язык описания структур данных, сетей, зависимостей и оценки сложности в IT. Делимость и НОД, запись алгоритмов псевдокодом, худший случай и асимптотика O(n) — связь с криптографией и проектированием кода. Векторы, матрицы, скалярное произведение и системы линейных уравнений — основа ML, графики и численных методов. События, условная вероятность, независимость и закон больших чисел — язык неопределённости в мониторинге, ML и рисках. Математические, имитационные и логические модели — от постановки задачи до валидации и рекомендаций для IT-инфраструктуры. Приближённое решение уравнений, интерполяция и метод наименьших квадратов — когда точная формула недоступна или слишком дорога.Когнитивистика - наука о мышлении
Ментальные модели
Тектология
Системы и модели
Математическая основа IT
Логика
Дискретная математика
Теория чисел, псевдокод и анализ алгоритмов
Линейная алгебра
Вероятность и статистика
Моделирование систем
Численные методы