МЛиТА-2011

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

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

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

 

№№

дата

лекция

практика

1

1-2 недели

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

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

Булевы функции.

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

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

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

 

Булевы функции:

СДНФ, СКНФ, многочлен Выдача ИДЗ-1

2

3-4 недели

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

Исчисление высказываний.

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

Минимизация ДНФ. Теорема Поста.

3

5-6 недели

Исчисление предикатов.

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

Потоковая контрольная работа по теме “Булевы функции».

 Языки и грамматики.

 

Исчисление высказываний

4

7-8 недели

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

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

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

Исчисление предикатов

5

9-10 недели

Математическое понятие алгоритма: частично-рекурсивные функции.

Математическое понятие алгоритма: нормальные алгорифмы Маркова.

Понятие о вычислительной сложности алгоритмов.

Языки и грамматики. Выдача. ИДЗ-2.

6

11-12 недели

Потоковая контрольная работа №2.

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

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

 

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

7

13-14 неделя

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

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

Решение типовых задач.

Машина Тьюринга и другие формализации алгоритма.

Выдача ИДЗ-3.

8

15-16 неделя

Дополнительные главы курса. Обзорная лекция.

Прикладная теория алгоритмов.

9

17 неделя

Консультация.

 

 

 

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

Comments