🌎 The Golden Ticket: P, NP, and the Search for the Impossible. Lance Fortnow (2013)

❔ Чему вы научитесь:
🔵 понимать формулировку задачи P против NP и почему она остаётся открытой;
🔵 различать классы сложности и смысл NP-полноты;
🔵 распознавать NP-полные задачи в прикладных постановках — маршруты, расписания, упаковка;
🔵 оценивать, что изменилось бы в криптографии, логистике и медицине, окажись P равно NP;
🔵 разбираться в подходах к неразрешимым за разумное время задачам: эвристики, аппроксимации, квантовые вычисления.

"The Golden Ticket" — научно-популярное изложение: автор — исследователь в теории сложности, но формул в книге почти нет, объяснения строятся на аналогиях и истории вопроса. Подойдёт разработчикам без формального CS-образования и всем, кому интересна постановка задачи, а не её решение. Заменой учебнику по теории вычислений книга не является — это введение в проблему и её последствия.

🗄 Скачать курс

Backender