Магистратура
2022/2023
Комбинаторные конструкции в теоретической информатике
Статус:
Курс по выбору (Современные компьютерные науки)
Направление:
01.04.02. Прикладная математика и информатика
Где читается:
Факультет компьютерных наук
Когда читается:
1-й курс, 3, 4 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для своего кампуса
Прогр. обучения:
Современные компьютерные науки
Язык:
русский
Кредиты:
6
Контактные часы:
64
Программа дисциплины
Аннотация
Теория вычислений и логика в их современном виде появились одновременно (и даже в работах одних и тех же людей - Гёделя, Чёрча, Тьюринга и других), и это не случайно: процесс формального вывода (применение разрешённых правил) и процесс вычисления (детерминированное применение разрешённых правил) по природе близки. Знаменитая теорема Гёделя (не все истинные утверждения формально доказуемы) означает на языке теории вычислений, что множество истинных утверждений неперечислимо - и в такой форме легко следует из классических результатов теории вычислений. Впоследствии появились и другие связи: логические теории можно использовать для доказательства свойств программ, классы сложности можно описывать в логических терминах, поэтому знакомство с основными понятиями и результатами логики входит в базовое образование программистов.