Вводный курс

Общая информация
ЛекторД. М. Ицыксон
Семестросень 2007
Дата начала23.09.2007
Количество пар4
Язык курсарусский
Слайды первой лекции
Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

1. Лекция 1
(23.09.2007 - 10:00 - 11:35)

Теорема о рекуррентных оценках. Машины Тьюринга. Основы теории вычислимости. Основы теории сложности вычислений.
2. Лекция 2
(30.09.2007 - 10:00 - 11:35)

Еще немного теории сложности вычислений: классы PSPACE, EXP, RP, BPP. Конечные автоматы: недетерминированные КА, регулярные выражения, pumping лемма.
3. Лекция 3
(07.10.2007 - 10:00 - 11:35)

Пропозициональные формулы, булевы функции. Системы доказательств, метод резолюций. Булевы схемы. Предикатные формулы.
4. Лекция 4
(14.10.2007 - 10:00 - 11:35)

Предикатные формулы 1–го порядка. Интерпретации, модели. Скулемовская нормальная форма. Эрбрановский универсум, эрбрановская интерпретация. Алгоритмическая неразрешимость исчисления предикатов. Теории и модели. 1–я Теорема Геделя о неполноте.
Ваша оценка: Пусто Средняя: 4.2 (5 votes)
Share |