«Проблема P против NP» и классы вычислительной сложности: объяснение задачи тысячелетия и её значение для программирования
Категории
70 страниц
Информатика
Автоматы и теория формальных языков: что скрывается за регулярными выражениями и иерархией Хомского
Лямбда-исчисление (Lambda Calculus) и истоки функционального программирования: от теории Алонзо Чёрча до Lisp и Haskell
Машина Тьюринга и теория вычислимости: мысленный эксперимент Алана Тьюринга и «проблема остановки»
Игра «Жизнь» Конвея: Клеточный автомат, где из простых правил возникает сложность, подобная жизни
Проблема четырех красок (Four Color Theorem) - Можно ли раскрасить любую карту в 4 цвета
Проблема остановки (Halting Problem): Самая мощная программа, которую абсолютно невозможно создать
Теоремы Гёделя о неполноте: Математическое доказательство «истины, которую абсолютно невозможно доказать»
Алгоритм поиска цикла Флойда (Алгоритм черепахи и зайца)
Пределы факторизации простых чисел и объяснение нотации 'О-большое' (O) для вычислительной сложности
