скачать
ТВЕРСКОЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ФАКУЛЬТЕТ
Прикладной математики и кибернетики
Кафедра
информатики
Учебно-методический комплекс
Специальность
|
010400 - Информационные технологии
|
Дисциплина
|
Математическая логика и теория алгоритмов
|
|
Общая дисциплина
|
^
Исчисления высказываний и предикатов. Теории первого порядка. Формальная арифметика. Введение в теорию алгебраических систем. Вычислимые и рекурсивные функции. Машины Тьюринга. Тезис Черча. Меры сложности алгоритмов. Классы задач P и NP. NP-полные задачи. Клаузальная логика, семантика дизъюнктов, секвенциальная нотация, семантические сети, хорновские дизъюнкты и их интерпретация, метод резолюций.
^
Цель курса - изучение основного материала из математической логики и теории алгоритмов, который создаёт грамотность, необходимую для осмысленного изучения программирования, а также содержит материал, используемый в дальнейших курсах.
^
Курсы информатики и дискретной математики
Знания и навыки, получаемые студентами при изучении дисциплины
Студент должен получить знания теории языков и математической
логики, необходимые для изучения специальных предметов.
^
Специальность
|
010400 - Информационные технологии
|
Курс
|
Семестр
|
Всего
|
Ауд.
|
Лекций
|
Прак.
|
Лаб.
|
Отчетность
|
2
|
3
|
170
|
75
|
45
|
30
|
0
|
Экзамен
|
2
|
4
|
128
|
110
|
66
|
44
|
0
|
Экзамен
|
^
Название темы Исчисление высказываний
|
Исчисление высказываний. Алфавит, формулы, секвенции. Схемы аксиом и правил вывода. Доказательство. Примеры доказуемых секвенций. Эквивалентность линейного доказательства и доказательства в виде дерева.
Эквивалентность формул. Булевы эквивалентности.
Теорема о замене. Нормальные формы.
Полнота и непротиворечивость.
Распределение времени
Лекций (часов)
|
10
|
Практики (часов)
|
6
|
Лабораторных (часов)
|
0
|
Самостоятельной работы (часов)
|
20
|
Содержание самостоятельной работы
Доказательство секвенций в исчислении высказываний. Изучение доказательства теорем.
Методические материалы и ссылки по теме
^
|
Описание материала
|
Файл материала
|
Учебное пособие
|
А.П.Столбоушкин, М.А.Тайцлин. Математические основания информатики. Часть 1. Тверь, 1998.
|
ch3.ps
|
Отчетность
Форма
|
Срок
|
Балл
|
^
|
Контрольная работа
|
октябрь
|
10
|
ch3.ps
|
Название темы Язык логики предикатов. Реляционные базы данных
|
Алгебраические системы. Язык логики предикатов. Формулы и термы. Истинность формулы в системе на состоянии.
Базы данных. Описание свойств баз данных на языке логики предикатов.
Распределение времени
Лекций (часов)
|
8
|
Практики (часов)
|
6
|
Лабораторных (часов)
|
0
|
Самостоятельной работы (часов)
|
15
|
Содержание самостоятельной работы
Запись различных свойств графов формулами логики предикатов. Определение истинности заданной формулы на заданном графе. Запись различных свойств арифметических операций.
Методические материалы и ссылки по теме
^
|
Описание материала
|
Файл материала
|
Учебное пособие
|
А.П.Столбоушкин, М.А.Тайцлин. Математические основания информатики. Часть 1. Тверь, 1998.
|
ch3.ps
|
Отчетность
Форма
|
Срок
|
Балл
|
^
|
Контрольная работа
|
октябрь
|
30
|
ch3.ps
|
Название темы Частичная рекурсивность функций, вычислимых на машинах Тьюринга
|
Частичная рекурсивность функций, вычислимых на машинах Тьюринга.
Универсальные функции.
Неразрешимость проблемы остановки для машин Тьюринга.
Существование частично рекурсивной функции с нерекурсивной областью определения.
Распределение времени
Лекций (часов)
|
10
|
Практики (часов)
|
6
|
Лабораторных (часов)
|
0
|
Самостоятельной работы (часов)
|
1
|
Содержание самостоятельной работы
Изучение теоретического материала.
Методические материалы и ссылки по теме
^
|
Описание материала
|
Файл материала
|
Учебное пособие
|
А.П.Столбоушкин, М.А.Тайцлин. Математические основания информатики. Часть 2. Тверь, 1998.
|
ch4.ps
|
Название темы Неразрешимость проблемы равенства в теории полугрупп
|
Полусистемы Туэ. Построение полусистемы Туэ по машине Тьюринга.
Ассоциативные исчисления. Построение ассоциативного исчисления по машине Тьюринга.
Неразрешимость проблемы равенства в теории полугрупп.
Распределение времени
Лекций (часов)
|
8
|
Практики (часов)
|
4
|
Лабораторных (часов)
|
0
|
Самостоятельной работы (часов)
|
1
|
Содержание самостоятельной работы
Изучение теоретического материала.
Методические материалы и ссылки по теме
^
|
Описание материала
|
Файл материала
|
Учебное пособие
|
А.П.Столбоушкин, М.А.Тайцлин. Математические основания информатики. Часть 2. Тверь, 1998.
|
ch4.ps
|
Отчетность
Форма
|
Срок
|
Балл
|
^
|
Контрольная работа
|
декабрь
|
20
|
|
Название темы Сложность алгоритмов
|
Машины Тьюринга с входом. Коды алгебраических систем. Алгоритмические проблемы. Классификация машин Тьюринга и алгоритмических проблем.
Зависимость сложности алгоритмической проблемы от числа входных лент, числа символов на рабочих лентах и от числа рабочих лент.
Полиномиальная сводимость.
NP-полные проблемы.
NP-полнота SAT.
Другие NP-полные проблемы.
Машины Тьюринга со стеком.
Теоремы Кука о связи временной и емкостной сигнализирующих.
Распределение времени
Лекций (часов)
|
10
|
Практики (часов)
|
8
|
Лабораторных (часов)
|
0
|
Самостоятельной работы (часов)
|
1
|
Содержание самостоятельной работы
Изучение теоретического материала. Построение машин Тьюринга для решения конкретных алгоритмических проблем.
Методические материалы и ссылки по теме
^
|
Описание материала
|
Файл материала
|
Учебное пособие
|
А.П.Столбоушкин, М.А.Тайцлин. Математические основания информатики. Часть 3. Тверь, 1998.
|
bookin.ps
|
Учебное пособие
|
М.А.Тайцлин. Теорема Кука.
|
cook1.ps
|
Отчетность
Форма
|
Срок
|
Балл
|
^
|
Контрольная работа
|
февраль
|
10
|
|
Название темы Неразрешимость логики предикатов на конечных моделях
|
Неразрешимость логики предикатов.
Существование конечной модели и существование периодической модели в арифметике.
Построение формулы по машине Тьюринга.
Неразрешимость логики предикатов на конечных моделях.
Распределение времени
Лекций (часов)
|
10
|
Практики (часов)
|
6
|
Лабораторных (часов)
|
0
|
Самостоятельной работы (часов)
|
2
|
Содержание самостоятельной работы
Изучение теоретического материала.
Методические материалы и ссылки по теме
^
|
Описание материала
|
Файл материала
|
Учебное пособие
|
А.П.Столбоушкин, М.А.Тайцлин. Неразрешимость логики предикатов на конечных моделях
|
tra.pdf
|
Отчетность
Форма
|
Срок
|
Балл
|
^
|
Контрольная работа
|
март
|
10
|
|
Название темы Представление рекурсивных функций в арифметике
|
Китайская теорема об остатках.
Функция Гёделя.
Представление рекурсивных функций в арифметике.
Неразрешимость арифметики.
Распределение времени
Лекций (часов)
|
8
|
Практики (часов)
|
4
|
Лабораторных (часов)
|
0
|
Самостоятельной работы (часов)
|
6
|
Содержание самостоятельной работы
Изучение теоретического материала. Задание конкретных функций формулами арифметики.
Отчетность
Форма
|
Срок
|
Балл
|
^
|
Контрольная работа
|
апрель
|
10
|
|
Название темы Неполнота логики предикатов для PTIME
|
Игры Эренфойхта.
Неопределимость связности в логике предикатов.
Определимость связности в PTIME.
Распределение времени
Лекций (часов)
|
10
|
Практики (часов)
|
4
|
Лабораторных (часов)
|
0
|
Самостоятельной работы (часов)
|
6
|
Содержание самостоятельной работы
Изучение теоретического материала. Построение невыразимых в логике предикатов глобальных предикатов из PTIME.
Методические материалы и ссылки по теме
^
|
Описание материала
|
Файл материала
|
Учебное пособие
|
М.А.Тайцлин. Теория баз данных
|
in.ps
|
Отчетность
Форма
|
Срок
|
Балл
|
^
|
Контрольная работа
|
май
|
10
|
|
Название темы Метод резолюций
|
Клаузулы. Резолюции. Алгоритм элиминации.
Подстановки. Алгоритм унификации.
Клаузулы в логике предикатов.
Резолюции в логике предикатов.
Распределение времени
Лекций (часов)
|
10
|
Практики (часов)
|
8
|
Лабораторных (часов)
|
0
|
Самостоятельной работы (часов)
|
1
|
Содержание самостоятельной работы
Решение задач методом резолюций.
Методические материалы и ссылки по теме
^
|
Описание материала
|
Файл материала
|
Учебное пособие
|
М.А.Тайцлин. Резолюции.
|
resol.pdf
|
Отчетность
Форма
|
Срок
|
Балл
|
^
|
Контрольная работа
|
июнь
|
20
|
|
Основная литература
А.П.Столбоушкин, М.А.Тайцлин. Математические основания информатики. Части 1, 2 и 3. Тверь, 1998.
М.А.Тайцлин. Теорема Кука.
А.И.Мальцев. Алгоритмы и рекурсивные функции. Москва. "Наука". 1965.
М.А.Тайцлин. Резолюции.
А.П.Столбоушкин, М.А.Тайцлин. Неразрешимость логики предикатов на конечных моделях.
Дополнительная литература
С.Кук. Характеристики машинных автоматов в терминах вычислителей, ограниченных во времени. В книге: Сложность вычислений и алгоритмов, Москва, Мир,1974.
Добавить документ в свой блог или на сайт
|
