МЛиТА-2016

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

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

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

нед

Дата лекции

 

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

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

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

1

03.09

 

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

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

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

2

10.09

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

СДНФ.

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

3

17.09

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

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

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

4

24.09

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

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

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

Лабораторная работа 1 "Логические схемы".

5

01.10

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

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

6

08.10

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

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

7

15.10

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

 

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

Выполнение интернет-теста по теме "Булевы функции".

8

22.10

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

 

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

9

29.10

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

 

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

Лабораторная работа 2 "Миры Тарского"

10

05.11

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

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

Лабораторная работа 3 "Регулярные выражения"

11

12.11

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


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

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

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

12

19.11

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

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

Лабораторная работа 4 "Машина Тьюринга"

13

26.11

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

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

 

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

Тест по теме "Конечные автоматы, грамматики и алгоритмы"

14

03.12

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

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

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

 

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

15

10.12

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

 

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

Выдача ИДЗ-3

16

17.12

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

 

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

17

24.12

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

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

 

Индивидуальная работы состоит из:

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

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

По курсу проводятся 2 контрольные работы.

Экзамен проходит в двух формах: письменной (обычный экзамен) и в форме обсуждения отчетов по проектной работе (альтернативный экзамен, проводится только для студентов, показывающих хорошие и отличные результаты по текущей работе)

Подстраницы (1): МЛиТА-2017
Ċ
Sergey Pozdnyakov,
2 сент. 2016 г., 7:18
Comments