Дискретная математика: Теория графов и булева алгебра

Алгебра логики (Булева алгебра)

Булева алгебра оперирует значениями 0 и 1 (Ложь и Истина). Каждая логическая схема процессора — это комбинация элементов И (AND), ИЛИ (OR) и НЕ (NOT).

С помощью Законов де Моргана и карт Карно математики и инженеры минимизируют булевы функции, сокращая количество транзисторов в процессоре!

Теория графов в фундаментальных задачах

Граф G = (V, E) состоит из вершин V и рёбер E. Вузовская дискретная математика изучает:

1. Эйлеровы и Гамильтоновы циклы: Задача о кенигсбергских мостах и задача коммивояжёра (NP-полная задача).
2. Раскраска графов: Минимальное число цветов (хроматическое число \chi(G)), нужное для раскраски графа. Применяется при распределении регистров в компиляторах и частот в беспроводных сетях.
3. Деревья и решётки: Бинарные деревья, остовы минимального веса и префиксные коды Хаффмана.