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

Алгоритм Тарского
Санкт-Петербург / осень 2017, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

Среди многочисленных результатов о разрешимости массовых проблем одним из самых замечательных является алгоритм Тарского, позволяющий установить истинность или ложность любой замкнутой арифметической формулы первого порядка с переменными для вещественных чисел. В качестве «бесплатного» приложения он дает разрешимость «элементарной» геометрии (через введенный Р. Декартом «метод координат»).

Первоначально для изложения алгоритма Тарскому пришлось написать отдельную книгу, очень трудную для чтения. В последующие годы разные авторы улучшали алгоритм и упрощали изложение, и сейчас алгоритм можно рассказать со всеми деталями за пару лекций. Для первого знакомства с алгоритмом Тарского будет представлена его версия, которая

  • легка для понимания,
  • легка для программирования,
  • очень неэффективна (по сравнению с современными «продвинутыми» алгоритмами).

Лекции основаны на докладе Hoon Hong 2002–го года.

Дополнительные материалы к лекциям:

Видеозапись прочтения курса в CS Клубе в 2008 году

Видеозапись лекций на IV Летней школе Современная математика (Дубна, 2004)

Подробный конспект лекций

Статья Юрия Владимировича Матиясевича Алгоритм Тарского в журнале Компьютерные инструменты в образовании

Ищите другие материалы на страничке смежного курса Юрия Владимировича https://compscicenter.ru/courses/realnumbers/2013-autumn/

Дата и время Занятие Место Материалы
17 сентября
11:15–12:45
Лекция 1, Лекция ПОМИ РАН слайды,  видеофайлы
17 сентября
13:00–14:30
Лекция 2, Лекция ПОМИ РАН видео