скачать ТВЕРСКОЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ  ФАКУЛЬТЕТ Прикладной математики и кибернетики
 Кафедра информатики Учебно-методический комплекс Специальность | 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.
Добавить документ в свой блог или на сайт
|