Город: Санкт-Петербург Казань Язык: Русский English

Десятая проблема Гильберта. Решение и применения в информатике


В десятой проблеме, поставленной в 1900 году, Гильберт просил найти алгоритм, который позволял бы по произвольному диофантову уравнению узнавать, имет ли оно решения. Семьдесят лет спустя было показано, что такого алгортма не существует. В спецкурсе будет приведено подробное доказательство этого результата и его приложения к установлению алгоритмической неразрешимости многих других проблем.

Никаких специальных знаний ни по теории чисел, ни по теории алгоритмов для слушания курса не требуется.

Прочтения курсов

Семестр
весна 2010