Алгоритм Тарского

Общая информация
ЛекторЮ. В. Матиясевич
Семестросень 2008
Дата начала07.09.2008
Количество пар2
Язык курсарусский
Видеоhttp://video.google.com/videoplay?docid=8182553124015161102
Аннотация

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

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

Лекции основаны на докладе Hoon Hong 2002–го года
(http://staff.fim.uni-passau.de/~sturm/professional/ACA02/talks/Hong–2).

Слайды первой лекции
Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

Ваша оценка: Пусто Средняя: 5 (2 голосов)
Share |
Студенты на лекции Юрия Владимировича Матиясевича