Скачать 24.48 Kb.
|
Математическая логика и теория алгоритмов4 семестр, спец. ИУ3 ЛитератураОсновная литература
Дополнительная литература
ЛекцииМодуль 1. Теория алгоритмовЛекция 1. Предпосылки возникновения математической логики и теории алгоритмов. Проблемы математического определения алгоритма и доказательства. Интуитивная концепция алгоритма. Понятие конструктивного объекта. Алфавит, слово, язык, словарная функция. ОЛ-1, предисловие; ОЛ-2, введение; ОЛ-3, Д1.1, 7.1. Лекция 2. Машины Тьюринга. Вычислимость по Тьюрингу. Тезис Тьюринга. Понятие нормального алгорифма Маркова. Основные примеры. Вычислимость по Маркову. Принцип нормализации. ОЛ-3, Д7.4; ОЛ-1, гл. 5, §2. ОЛ-1, гл. 5, §1; ОЛ-2, §1, пп. 1.1 – 1.4, 1.9. Лекция 3. Эквивалентность алгорифмов. Теорема о переводе. Способы сочетания нормальных алгорифмов. ОЛ-1, гл. 5, §1; ОЛ-2, §1, пп. 1.5– 1.7. Лекция 4. Универсальный алгорифм. Разрешимые и перечислимые множества. Перечислимые множества и области применимости нормальных алгорифмов. Проблема применимости для нормальных алгорифмов и доказательство ее неразрешимости. ОЛ-1, гл. 5, §1; ОЛ-2, §1, пп. 1.7– 1.8; ОЛ-2, §§2, 3; ОЛ-2, §§2, 3. Модуль 2. Математическая логикаЛекция 5. Понятие формальной теории. Аксиомы и правила вывода. Выводимость и доказуемость. Примеры теорий. Исчисление высказываний (ИВ). ОЛ-1, гл. 1, §4; конспект лекций. Лекция 6. Теорема дедукции для ИВ. Правила естественного вывода. Примеры построения доказательств в ИВ. ОЛ-1, гл. 1, §4; конспект лекций. Лекция 7. Полнота и непротиворечивость ИВ. ОЛ-1, гл. 1, §4; конспект лекций; ДЛ-2, гл.1, гл. 2: 2.1, 2.2. Лекции 8. Понятие алгебраической системы. Операции и предикаты. Термы и формулы. Понятие интерпретации. Выполнимость, истинность и логическая общезначимость. Аксиомы и правила вывода исчисления предикатов 1-го порядка (ИП1). ОЛ-3, 4.1; ОЛ-1, гл. 2, §§ 1 – 4. Практические занятияМодуль 1. Теория алгоритмовЗанятия 1-2. Программирование вычислимых функций на машинах Тьюринга и нормальных алгорифмах Маркова. ОЛ-3, задачи 7.37, 7.38; МРК. Занятие 3-4. Построение разрешающих алгоритмов для разрешимых множеств. Анализ некоторых неразрешимых проблем. МРК. Модуль 2. Математическая логикаЗанятия 5-6. Построение доказательств в исчислении высказываний. ОЛ-1, упр. к. гл. 1; ДЛ-4, упр. к гл. 2, 5. Занятия 7-8. Построение доказательств в исчислении предикатов. ОЛ-1, упр. к гл. 1; ДЛ-4, упр. к гл. 3, 5. Контрольные мероприятияМодуль 1 Теория алгоритмов (8 неделя, максимум 45 баллов, минимум 25 баллов). Домашнее задание №1 «Теория алгоритмов» (выдача 3 неделя, прием 9 неделя). Рубежный контроль по модулю 1 (12 неделя). Модуль 2. Математическая логика (16 неделя, максимум 45 баллов, минимум 25 баллов). Домашнее задание №2 «Исчисление высказываний» (выдача 9 неделя, прием 13 неделя). Рубежный контроль по модулю (16 неделя). Кафедра ФН-12 Ответственный по кафедре А.Н. Канатников Автор документа А.И. Белоусов Телефон (499) 263-62-88 |