МЛиТА-2018

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

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

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

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

 Лабораторные работы выложены на специально созданном сайте в формате Олимпиады по дискретной математике и теоретической информатике

Для работы нужно зарегистрироваться (кнопка регистрации "подать заявки на участие" находится ниже текста, видимого на экране, в анкете укажите учебного заведения "ЛЭТИ", класс - номер группы, регион - СПб). Поработайте сначала с тренировочными задачами. Когда будете готовы, перейдите на задачи заочного тура - это и есть лабораторные работы - время (3 часа) начнет отсчитываться автоматически сразу после нажатия, второй раз начать прохождение задач заочного тура нельзя.

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

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

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

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

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

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

нед

Дата лекции 

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

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

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

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

1

08.09

 

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

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

Интересная и популярная книга С.Б. Гашков "Сложение однобитных чисел"

Использование более сложных логических схем для ускорения сложения двоичных чисел

Бинарные диаграммы решений (БДР), упорядоченные БДР (УБДР), сокращенные УБДР (СУБДР):

первое знакомство в Википедии
более детальное изложение в лекции на Intuit.ru
обратите внимание на мнение Кнута и первую статью по этой теме

АЭ: Курс "Сложность булевых функций" (для тех, кто по этой теме сдает альтернативный экзамен)

2

15.09

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


Видео. Лекция 2. Свойства булевых функций, СДНФ, Двойственность 


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

 
В течение недели нужно зарегистрироваться на сайте КИО-школы и (после допуска преподавателя к модулям) начать работу по прикладной теории графов

3

22.09

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


Видео. Лекция 3. Многочлен Жегалкина, Минимизация ДНФ (СДНФ) 


Видео-объявлениеIT сообщество "Vector Way"  (в открытом доступе)

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

 Дайте обоснование различным "табличным" алгоритмам нахождения коэффициентов многочлена Жегалкина. Насколько эффективными они являются? Оцените сложность. Попробуйте повысить эффективность или доказать, что этого сделать нельзя.

4

29.09

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

Видео. Лекция 4. Минимизация ДНФ. Конструирование логических схем из функциональных элементов. Классы замкнутости

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

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

Определите самостоятельно связь между минимизацией СДНФ 4-х переменных на четырехмерном кубе и операциями с картами Карно.
Сможете ли Вы перенести идею карт Карно на функции 5 и более переменных?

5

06.10

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

Видео. Лекция 5. Классы замкнутости. Теорема Поста.

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



6

13.10

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

Видео. Лекция 6. Исчисление высказываний. Основные теоремы логического вывода и метод резолюций.

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

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

7

20.10

Исчисление предикатов. Свойства кванторов. Предваренная форма. Нормальная сколемовская форма.

Видео. Лекция 7. Исчисление предикатов. Свойства кванторов. Предваренная форма. Нормальная сколемовская форма.

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

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

8

27.10

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

Видео.Лекция 8. Автоматизация доказательства теорем в исчислении предикатов. Алгоритм унификации.



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

(тема взята) АЭ: Две лекции известного ученого, академика Ю.В.Матиясевича "Алгоритм Тарского", где объясняется, что все задачи школьной геометрии могут быть доказаны автоматически сведением к многочленам (зажание на 2 человек для альтернативного экзамена)

(тема взята) АЭ Очень важная и достаточно понятная статья о связи логического доказательства и программирования через лямбда-исчисление:
Соответствие Карри—Ховарда: от математической логики к программированию и обратно (В. Н. Брагилевский, Дубна, 19–30 июля 2017 года)


9

03.11

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

Видео Лекция 9. Формальные языки грамматики. КС-грамматика

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

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

 ! АЭ Задания от Семена Вячеславовича Григорьева (преподавателя мат-меха, сотрудника JetBrains) по формальным грамматикам


АЭ: Очень советую всем студентам (а в особенности тем, кто выбрал на альтернативный экзамен это направление) прослушать две лекции Охотина, прочитанные недавно в ПОМИ РАН:
1 лекция2 лекция (кого ззаинтересует это направление, попробую связать с Семеном Григорьевым, семинар которого в прошлом семестре посещали три студента, которые под его руководством сделали работу, получившую диплом на конференции и готовящие публикацию по этой теме). 

(тема взята) АЭ: Две лекции Талбота (на англ. языке) "Машинный перевод" (для тех, кто хочет пройти практику в фирме ПРОМТ, разработавшей translate.ru, 2 человека, заодно надо сделать конспект с переводом на русский  язык).

10

10.11

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

ВидеоЛекция 10. Построение синтаксического анализатора КС-грамматики. Конечные автоматы

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

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

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

11

17.11

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



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


Для подготовки к выполнению ИДЗ-2: Темы прошлых лет (будут изменены).

 Выдача ИДЗ-2 по МЛиТА-2018

 
(тема взята) АЭ. Лекции М. В. Волкова. Синхронизируемые автоматы. (для 4 человек)
Цитата: "Детерминированный конечный автомат называется синхронизируемым, если существует такое слово w, что любой путь в автомате, вдоль которого читается w, заканчивается в одном и том же состоянии. Это понятие, естественно возникающее в задаче восстановления контроля над дискретной системой, текущее состояние которой неизвестно, оказалось математически весьма содержательным и породило много просто формулируемых, но оказавшихся весьма трудными задач. Среди таких проблем особо выделяются проблема раскраски дорог, совсем недавно решенная А.Н.Трахтманом, и гипотеза Черни, остающаяся недоказанной уже 46 лет."
В лекциях рассказано о множестве вычислительных экспериментов, которые предлагается повторить, а может быть и развить.

12

24.11

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

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

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

 

13

25.11

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

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

(тема взята) АЭ: Лямбда-исчисление и функциональное программирование: по курсу Кубенского "Функциональное программирование" - для тех, кто хочет сдавать альтернативный экзамен (3-4 человека)

Доп. информация с сайта М.Л.Симуни:
1) литература по функциональному программированию
2) способ пройти бесплатно аттестацию в Stepic по курсу функционального программирования
3) пример контрольной работы
4) слайды М.Л.Симуни по курсу функционального програмирования

14

01.12

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

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

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

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

 
(тема взята) АЭ: Лекции Осипова "Поиск кратчайших путей в транспортных сетях: от теории к реализации" - для тех участников альтернативного экзамена, кто интересуется приложениями теории графов (3-4 человека).

15

08.12

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

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


Выдача ИДЗ-3

 


Коллоквиум по алгоритмам на графах

АЭ: Лекции Куликова "Алгоритмы для NP-трудных задач" (рекомендовано группе студентов, которые возьмут проект по игре "Жизнь")

(тема взята) АЭ: Две лекции "Алгоритмы решения задачи коммивояжера" (для альтернативного экзамена, предполагается реализация, экспериментальное сравнение на разных данных и улучшение алгоритмов для более узких классов задач, команда из 2 человек).

(тема взята) АЭ: Курс из 4 лекций Александра Тискина "Эффективные параллельные алгоритмы: методика BSP" (для альтернативного экзамена на 2-3 человек, представляет интерес возможность получить тему для последующей научной работы от этого лектора, который работает в Великобритании)

16

15.12

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

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

 
Популярно о неразрешимости проблемы останова (начало лекции Шеня). Вообще Шень - известный математик и все прочитанные здесь лекции крайне интересны и, главное, понятны. Полезно для повторения материала прошлого года и, есть, новые темы.
Лекции Шеня по теме курса и дополнительно) (1-3 - по тематике курса, 5-7 - теорема Гёделя - дополнительный материал)

(тема взята) АЭ: Курс Гирша "Сложность вычислений и основы криптографии" - дополнительный материал для тех, кто сдает экзамен альтернативно (группа из 3-4 человек)

(тема взята) АЭ: Три лекции Михайлина "Fine-grained complexity" (на русском языке, интересныое направление о "промежуточной" между полиномиальной и экспоненциальной сложностями, на 2 человек, лектор задает много вопросов, на которые нужно научиться отвечать)

17

22.12

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

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

 

 

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

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

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

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

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

ĉ
Sergey Pozdnyakov,
17 сент. 2018 г., 10:32
Comments