8 мая в 15:20 в аудитории 1011 состоится лекция "Сложность вычислений" минкурса  "Основы теории вычислимости и сложность вычислений". Докладчик Селиванов Виктор Львович. 

Цель миникурса – познакомить слушателей с некоторыми понятиями, результатами, методами и приложениями теории вычислимости, теории сложности вычислений и теории автоматов.  Сложность вычислений будет проиллюстрирована теорией NP-полноты и теоремами Тарского о разрешимости в теории полей.

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