City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Основы теории вычислимости и сложность вычислений
Kazan / spring 2018, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

Цель миникурса – познакомить слушателей с некоторыми понятиями, результатами, методами и приложениями теории вычислимости, теории сложности вычислений и теории автоматов. Теория вычислимости будет проиллюстрирована примерами разрешимых и неразрешимых проблем в математике (в частности, будут кратко обсуждены 10-я проблема Гильберта и арифметика Пеано). Сложность вычислений будет проиллюстрирована теорией NP-полноты и теоремами Тарского о разрешимости в теории полей. Теорию автоматов проиллюстрируем автоматами Бюхи и применениями к задаче верификации систем с конечным числом состояний.

Хотя обсуждаемый материал носит теоретический характер, он тесно связан с практическими вопросами информатики. Для иллюстрации этого рассмотрим связь этих результатов с системами автоматического доказательства теорем, системами компьютерной алгебры, SAT-решателями и верификаторами.

Date and time Class|Name Venue|short Materials
24 April
15:20–16:40
Лекция 1, Lecture 2-й учебный корпус К(П)ФУ No
25 April
17:00–18:40
Лекция 2, Lecture 2-й учебный корпус К(П)ФУ No
26 April
17:00–18:40
Лекция 3, Lecture 2-й учебный корпус К(П)ФУ No