МЛиТА-2013

ФКТИ 3 семестр 2013-2014 учебного года

Математическая логика и теория алгоритмов.

Лектор: С.Н.Поздняков

нед

Дата лекции

 

Название и/или

краткое содержание лекции

Практика и самостоятельная работа

1

07.09

 

Понятие об алгебре логики.

Логические переменные, операции, формулы, тождества.

Классические логические задачи. Знакомство с идеей алгебры логики.

2

14.09

Булевы функции. Таблицы б.ф. Теорема о числе б.ф. от n переменных. Фиктивные переменные.

СДНФ.

Формулы алгебры логики. Логические операции, преобразования логических выражений.

3

21.09

Двойственность. СКНФ.

Многочлены Жегалкина.

Булевы функции: таблица, СДНФ, СКНФ. Выдача ИДЗ-1.

4

28.09

Минимизация СДНФ. Метод минимизирующих карт. Карты Карно.

Построение многочленов Жегалкина (три способа).

Решение различных задач.

5

05.10

Классы замкнутости. Решение теоретических задач (подготовка к экзамену).

Минимизация ДНФ (три алгоритма).

6

12.10

Теорема Поста.

Классы замкнутости и теорема Поста.

7

19.10

Исчисление высказываний. Автоматизация доказательства теорем исчисления высказываний.

 

Итоговое занятие по теме.

8

26.10

Исчисление предикатов. Автоматизация доказательства теорем исчисления предикатов.

 

Контрольная работа №1

9

02.11

Конечные автоматы.

 

Исчисление высказываний. Метод резолюций.

10

09.11

Автоматные грамматики и языки регулярных выражений. Теорема Клини.

Преобразование выражений с кванторами. Метод резолюций для исчисления предикатов.

11

16.11

Языки и грамматики. Технология построения синтаксических анализаторов*


Конечные автоматы и автоматные языки.

 Выдача ИДЗ-2 (выполняется самостоятельно без поддержки практикой).

Примерные темы (будут изменены).

12

23.11

Математическое понятие алгоритма: машина Тьюринга.

Алгоритмы над автоматами (удаление пустых символов, построение детерминированного автомата по недетерминированному).

13

30.11

Частично-рекурсивные функции.

Нормальные алгорифмы Маркова.

 

Машина Тьюринга, алгорифмы Маркова.

14

07.12

Прикладная теория алгоритмов: метод математической индукции в доказательстве корректности алгоритмов (на примере алгоритмов обработки формул).

Понятие матроида*. Жадные алгоритмы (на примере алгоритмов построения минимального остовного дерева).

Студенты самостоятельно работают в Школе дискретной математики и информатики на сайте kioschool.eltech.ru (эти результаты оценивает лектор)

 

Контрольная работа №2.

15

14.12

Прикладная теория алгоритмов: понятие инварианта цикла в доказательство корректности алгоритмов (на примере алгоритмов поиска кратчайших путей).

 

Алгоритмы на графах. Деревья. Алгоритмы построения минимальных остовных деревьев.

Выдача ИДЗ-3

16

21.12

Понятие о вычислительной сложности алгоритмов. Примеры NP-полных задач (поиск гамильтонова пути в графе, задача коммивояжера). Метод ветвей и границ*.

 

Алгоритмы на графах. Поиск кратчайших путей: алгоритмы Форда-Беллмана, Дейкстры, Флойда.

17

28.12

Обзорная лекция.

Итоговое занятие: прием ИДЗ-3.

 

По курсу выдается 3 индивидуальных задания, проводится 2 контрольных, организуется самостоятельная работа студентов по чтению дополнительной литературы, работе в Интернет-школе дискретной математики и информатики, выполнение прикладных работ по курсу, включающих программирование.

По материалам ИДЗ-2 и по результатам работы над изучением алгоритмов на графах (в Интернет-школе)  будут проведены коллоквиумы (первый устный - с проверкой реализации алгоритмов синтаксического анализа, второй - письменный - по теоретическому материалу).

Comments