Логика и информатика

Логика и школьная информатика: таблицы истинности, равносильность выражений, объём графики и звука, графы, маски файлов и количество программ исполнителя.

Таблица истинности

Логическое выражение → таблица истинности и тип выражения

Равносильность логических выражений

Проверка равносильности, значение выражения и законы алгебры логики

Объём информации: графика, звук, текст

Объём изображения, звукозаписи и текста, глубина цвета по числу цветов

Графы: пути между вершинами

Количество путей, кратчайший путь и достижимость вершин

Логические запросы поисковых систем

Круги Эйлера и формула включений-исключений для запросов И, ИЛИ, НЕ

Маски файлов

Проверка имён файлов по маске с символами * и ?

Количество программ исполнителя

Динамическое программирование: сколько программ ведёт из одного числа в другое

Условие Фано и префиксные коды

Проверка условия Фано, декодирование цепочки и кратчайшее кодовое слово

Теория игр: выигрышные позиции

Кто выигрывает из позиции, какие ходы ведут к победе и где проигрышные позиции (ЕГЭ 19–21)

Исполнитель алгоритма

Кузнечик, Черепаха и Робот: трассировка программы, конечная координата и число шагов

Количество информации: Хартли и Шеннон

N = 2^i, алфавитный подход и энтропия H = −Σpᵢ·log₂pᵢ

Логические схемы

Схема И/ИЛИ/НЕ → логическая функция, таблица истинности и число вентилей