МЛиТА-2018

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

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

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

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

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

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

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

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

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

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

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

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

нед

Дата лекции 

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

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

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

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

1

08.09

 

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

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

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

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

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

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

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

2

15.09

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

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

 

3

22.09

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

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

 

4

29.09

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

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

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

 

5

06.10

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

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



6

13.10

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

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

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

7

20.10

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

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

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

8

27.10

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

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

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

9

03.11

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

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

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

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


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

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

10

10.11

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

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

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

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

11

17.11

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

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

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

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

  ИДЗ-2 по МЛиТА

 

12

24.11

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

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

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

 

13

25.11

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

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

АЭ: Лямбда-исчисление и функциональное программирование: по курсу Кубенского "Функциональное программирование" - для тех, кто хочет сдавать альтернативный экзамен (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