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

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

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

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

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

Дата и время Название Место Материалы
24 апреля
15:20–16:40
Лекция 1, лекция 2-й учебный корпус К(П)ФУ Нет
25 апреля
17:00–18:40
Лекция 2, лекция 2-й учебный корпус К(П)ФУ Нет
26 апреля
17:00–18:40
Лекция 3, лекция 2-й учебный корпус К(П)ФУ Нет