МЛиТА-2016‎ > ‎

МЛиТА-2017

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

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

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

Основной учебник С.В.Рыбин, С.Н.Поздняков. Дискретная математика.

Хорошая книга для поддержки курса (особенно логического вывода):

Карпов Ю.Г. Теория автоматов (другая ссылка для скачивания)

Хорошая книга по второй половине курса: 

Джон Хопкрофт и др. "Введение в теорию автоматов, языков и вычислений", 2-е издание, 2008.

Темы важных (командных) исследовательско-программистских проектов для альтернативного экзамена

Группа ВКонтакте для обсуждения задач по предмету МЛиТА

нед

Дата лекции 

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

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

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

 Дополнительные задания

1

02.09

 

Понятие об алгебре логики. Логические переменные, операции, формулы, тождества. Булевы функции. Таблицы б.ф. Теорема о числе б.ф. от n переменных. Фиктивные переменные.

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

Бинарные диаграммы решений (БДР), упорядоченные БДР (УБДР), сокращенные УБДР (СУБДР):
первое знакомство в Википедии
более детальное изложение в лекции на Intuit.ru
обратите внимание на мнение Кнута и первую статью по этой теме

2

09.09

Двойственность. Канонические представления. СДНФ.  СКНФ.

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

 

3

16.09

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

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

 

4

23.09

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

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

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

 

5

30.09

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

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



6

07.10

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

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

Калькулятор классов замкнутости (Работа Салина на альтернативном экзамене)

7

14.10

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

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

Д.М.Ицыксон «Что такое доказательство?»: взгляд из теоретической информатики
 
Ф.А.Новиков "... методы искусственного интеллекта ... сводятся к автоматическому доказательству теорем". Читайте книгу этого автора "Системы представления знаний"

8

21.10

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

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

 Это интересно тем, кто хочет узнать о моделировании человеческого интеллекта. Доклады специалиста по искусственному интеллекту А.Потапова: "Искусственный интеллект как совокупность вопросов" - Цикл лекций "Логика мышления" (2012) и "Задача обобщения" (2013)

9

28.10

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

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

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

 
Очень советую всем студентам (а в особенности тем, кто выбрал на альтернативный экзамен это направление) прослушать две лекции Охотина, прочитанные недавно в ПОМИ РАН:

10

04.11

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

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

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

 Полезно почитать интересную книгу: А.С.Потапов "Технологии искусственного интеллекта"

11

11.11

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

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

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

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

 

12

18.11

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

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

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

 

13

25.11

Частично-рекурсивные функции. Нормальные алгорифмы Маркова.

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

 

14

02.12

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

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

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

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

 

15

09.12

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

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

Выдача ИДЗ-3

 

16

16.12

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

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

 

17

23.12

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

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

 

 

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

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

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

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

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

Ċ
Sergey Pozdnyakov,
1 сент. 2017 г., 9:00
Comments