Логика и информатика
Логика и школьная информатика: таблицы истинности, равносильность выражений, объём графики и звука, графы, маски файлов и количество программ исполнителя.
Таблица истинности
Логическое выражение → таблица истинности и тип выражения
Равносильность логических выражений
Проверка равносильности, значение выражения и законы алгебры логики
Объём информации: графика, звук, текст
Объём изображения, звукозаписи и текста, глубина цвета по числу цветов
Графы: пути между вершинами
Количество путей, кратчайший путь и достижимость вершин
Логические запросы поисковых систем
Круги Эйлера и формула включений-исключений для запросов И, ИЛИ, НЕ
Маски файлов
Проверка имён файлов по маске с символами * и ?
Количество программ исполнителя
Динамическое программирование: сколько программ ведёт из одного числа в другое
Условие Фано и префиксные коды
Проверка условия Фано, декодирование цепочки и кратчайшее кодовое слово
Теория игр: выигрышные позиции
Кто выигрывает из позиции, какие ходы ведут к победе и где проигрышные позиции (ЕГЭ 19–21)
Исполнитель алгоритма
Кузнечик, Черепаха и Робот: трассировка программы, конечная координата и число шагов
Количество информации: Хартли и Шеннон
N = 2^i, алфавитный подход и энтропия H = −Σpᵢ·log₂pᵢ
Логические схемы
Схема И/ИЛИ/НЕ → логическая функция, таблица истинности и число вентилей