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