Когда вы открываете навигатор на смартфоне и просите проложить маршрут от дома до работы в обход пробок, в недрах приложения запускаются алгоритмы дискретной математики по поиску кратчайших путей на взвешенных графах. В отличие от простого поиска в ширину (BFS), который эффективен только для сетей с одинаковой длиной ребер, реальный мир требует работы с графами, где каждое ребро имеет свой "вес" — время, километраж или стоимость проезда.

В 2000 году Математический институт Клэя опубликовал список из семи "Задач тысячелетия", предложив за решение каждой из них награду в один миллион долларов. Одной из них является вопрос, который не дает покоя программистам, криптографам и математикам по всему миру: равны ли классы P и NP (P = NP)? Ответ на этот вопрос в дискретной математике может либо навсегда изменить наш мир, либо подтвердить, что наши текущие ограничения непреодолимы.

Задолго до создания первых электронных компьютеров, в 1936 году, 24-летний британский математик Алан Тьюринг придумал абстрактную вычислительную машину. Эта мысленная конструкция стала абсолютным математическим мерилом того, что в принципе можно вычислить алгоритмическим путем, а что — нельзя. Машина Тьюринга является краеугольным камнем теоретической информатики и дискретной математики.