Вычисление как универсальное и фундаментальное понятие

Профессор Тим Рафгарден начинает курс с обманчиво простого вопроса: есть ли что-то, чего компьютеры не могут сделать? Ответ он ищет в 1936 году: за десятилетие до появления настоящих компьютеров Алан Тьюринг заложил основы информатики, решая на первый взгляд узкую математическую задачу. В своей работе он описал теоретическую машину (позже названную его именем) и доказал нечто ошеломляющее: существуют задачи, которые не решит никакой алгоритм, сколько бы времени и вычислительной мощности ни было доступно. Пример такой задачи, проблема остановки: вопрос, остановится ли когда-нибудь выполнение программы, принципиально неразрешим ни для одного компьютера.

Далее Рафгарден переходит к более тонкому вопросу: среди задач, которые компьютеры решить способны, какие решаются быстро? Он показывает алгоритмические хитрости, приёмы, которые позволяют программе не перебирать все возможные варианты. Карты на смартфоне используют алгоритм Дейкстры, чтобы находить кратчайший маршрут, не проверяя каждый возможный путь. Метод умножения Карацубы обгоняет по скорости способ, которому всех учат в школе. Эти приёмы выглядят почти как магия и рождают естественную надежду: может быть, подобный короткий путь существует для любой задачи.

Эта надежда разбивается о задачу коммивояжёра (TSP). Хотя она внешне почти неотличима от задачи о кратчайшем маршруте, для неё так и не нашли быстрый алгоритм, несмотря на все попытки. Рафгарден показывает, как эта головоломка привела к теории NP-полноты, одному из самых неожиданных открытий информатики. Тысячи на вид не связанных друг с другом задач (составление расписаний, решение головоломок, оптимизация сетей) оказались замаскированными версиями одной и той же проблемы: если для любой из них найдётся быстрый алгоритм, лёгкими станут все; если хотя бы одна из них действительно трудна, трудны все.

Так курс подходит к вопросу P против NP, важнейшему открытому вопросу информатики и одной из главных нерешённых проблем математики. Рафгарден прослеживает его историю через фигуры Гильберта, Гёделя и фон Неймана, показывая, как две независимые научные традиции, одна изучала, на что способны алгоритмы, другая, их ограничения, сошлись на одном и том же вопросе. Завершается курс разбором того, что может означать ответ на этот вопрос для криптографии, искусственного интеллекта, квантовых вычислений и понимания природы вычисления в целом. Предварительных знаний в информатике или математике не требуется.

Лекции можно посмотреть по ссылке на сайте курса, воспользоваться оглавлением по главам или смотреть на YouTube. Автор курса, Тим Рафгарден, профессор Школы математики Института перспективных исследований (Institute for Advanced Study); ранее семь лет преподавал на факультете информатики Колумбийского университета и пятнадцать лет, в Стэнфорде. Его основные интересы, связь информатики с экономикой и анализ пределов возможностей алгоритмов. Он автор книг «Twenty Lectures on Algorithmic Game Theory», «Beyond the Worst-Case Analysis of Algorithms» и серии «Algorithms Illuminated», а также множества научных статей; среди его наград, премия ACM имени Грейс Мюррей Хоппер и премия Гёделя.

Ключевые факты

• Тьюринг в 1936 году, за десять лет до появления настоящих компьютеров, доказал существование задач, которые не решит ни один алгоритм, например, проблема остановки программы.
• Карты на смартфоне используют алгоритм Дейкстры, чтобы находить кратчайший путь без перебора всех вариантов; метод умножения Карацубы быстрее школьного способа.
• Задача коммивояжёра (TSP) не поддаётся быстрым алгоритмам и привела к теории NP-полноты: тысячи разных задач (расписания, головоломки, сетевая оптимизация) оказались замаскированными версиями одной и той же проблемы.
• Курс подводит к вопросу P против NP, важнейшей открытой проблеме информатики и математики, к которой независимо друг от друга пришли две научные традиции через работы Гильберта, Гёделя и фон Неймана.
• Автор курса, Тим Рафгарден, профессор Института перспективных исследований, ранее преподававший в Колумбийском университете и Стэнфорде; курс бесплатный, лекции доступны на YouTube, подготовка не требуется.

Почему это важно

Курс в доступной форме излагает центральные результаты теории вычислений, неразрешимость проблемы остановки, теорию NP-полноты и вопрос P против NP. Это не узкоспециальная тема: она задаёт фундаментальные границы того, что вычисления в принципе способны и не способны сделать, и остаётся открытой десятилетиями, несмотря на огромные усилия математиков и информатиков.

Кому это важно

Курс адресован широкой аудитории без предварительной подготовки, программистам, студентам и всем, кто интересуется теоретическими основами информатики. Особенно полезен тем, кто хочет понять, почему криптография, безопасность и перспективы квантовых вычислений упираются именно в вопрос P против NP.

Как это применить

Лекции бесплатны и доступны на YouTube и на сайте курса с постраничным оглавлением по главам, можно смотреть последовательно или выбирать интересующие темы. Материал выстроен от простого к сложному: от машины Тьюринга и проблемы остановки к алгоритмическим приёмам, задаче коммивояжёра, NP-полноте и вопросу P против NP.

Можно ли доверять

Автор, признанный специалист: профессор Института перспективных исследований, ранее пятнадцать лет проработавший в Стэнфорде и семь лет в Колумбийском университете, лауреат премии ACM имени Грейс Мюррей Хоппер и премии Гёделя, автор нескольких стандартных учебников по алгоритмам. Материал академический, без сенсационных заявлений.

Риски и подводные камни

Несмотря на обещанную доступность для новичков, темы курса, глубокая абстрактная математика, и без реальной концентрации внимания усвоить их будет непросто. Стоит помнить и о статусе самого вопроса: P против NP остаётся нерешённой проблемой десятилетиями, и курс не предлагает ответа, он лишь объясняет, что этот ответ будет означать для криптографии, ИИ и квантовых вычислений.