Введение понятие комбинаторики

Задача о многопроцессорном расписании. Даны m одинаковых процессоров и n независимых задач, каждая из которых может решаться на любом процессоре. Время решения каждой задачи равно t_i, i = 1…n. Как распределить задачи по процессорам таким образом, чтобы выполнение всех задач было завершено в кратчайший срок?
В другой интерпретации это задача о куче камней: требуется так разложить n камней с весами t_i на m куч, чтобы вес самой тяжелой кучи был минимален.
Задача о раскраске графа. Дан неориентированный граф G = (V,E). Требуется каждой вершине графа сопоставить целое число (номер цвета) таким образом, чтобы никакие две смежные вершины не были одного цвета и при этом число использованных цветов было минимально.
Есть много несложных алгоритмов, дающих приближенные решения этой задачи, однако найти точное решение не так просто.
Широко известен вариант задачи о раскраске, в котором задано, что граф планарный (т.е. может быть нарисован на плоскости без пересечений ребер). По-другому это формулируется как задача раскраски карты (никакие две страны, имеющие общий отрезок границы, не должны быть одного цвета). С конца XIX века было известно, что для любой карты достаточно использовать 5 цветов, однако только в 80-х годах XX века удалось доказать, что всегда можно обойтись 4 цветами.
Задача о тождественной истинности ДНФ. Дана дизъюнктивная нормальная форма  от булевых переменных x₁, x₂, …, x_n. Непривычное для булевых величин обозначение x^ следует понимать как x¹ = x, x^-1 =x, x⁰ = 1. Таким образом, массив параметров _ji содержит информацию о том, входит ли i-тая переменная в j-тую элементарную конъюнкцию, и если входит, то c инверсией или без.
Требуется дать ответ, существует ли набор значений переменных x₁, x₂, …, x_n, при котором значение ДНФ равно 0, или же данная ДНФ является тождественно истинной, т.е. всегда равна 1.
Это задача поиска, ее решение завершается, если найден хотя бы один план, на котором ДНФ принимает значение 0.
Используя законы Де Моргана, нетрудно сформулировать двойственную задачу: дана конъюнктивная нормальная форма, требуется определить, существует ли набор значений переменных x₁, x₂, …, x_n, при котором значение КНФ равно 1. Эту задачу принято называть задачей о выполнимости КНФ. Как будет показано далее, задача о выполнимости играет важную роль в теории вычислительной сложности.