Дискретная математика

На этой странице будут появляться различные материалы и объявления, связанные с курсом «Дискретная математика для лингвистов», читаемого для студентов 1-го курса отделения лингвистики в 2021/2022 учебном году.

• Авторы курса: И.А. Хованская, Ю.Г.Кудряшов, В.В. Кочергин, А.В. Михайлович, И.В.Щуров

• Лекции читает: Михайлович Анна Витальевна, Кочергин Вадим Васильевич.

• Семинары ведут: А.В. Михайлович (avmikhailovich@gmail.com), Кочергин Вадим Васильевич (vvkoch@yandex.ru)

Материалы

лекция	тема	материал	задачи
1	Введение в теорию множеств	Элементы теории множеств Презентация Лекция 1 (видео) Лекция 2 (видео)	Задачи 1-14
2	Метод математической индукции	Метод математической индукции Лекция 2 (чуть меньше половины в конце)	Задачи 15-35
3	Комбинаторика	Комбинаторика Немного о линейных рекуррентных последовательностях Презентация Лекции 3, 4 (видео) Лекция 12 (последние 20 минут)	Задачи (14-16 сентября). (ДЗ на 15.09 - №№ 1, 2, 3, 4, 19, 20) Задачи (21-23 сентября). (ДЗ на 22.09 - №№ 1-6, 9-13, 19, 24-28 --- задачи по материалам последней лекции) Задачи на тему Рекурретные соотношения.
4	Делимость. Алгоритм Евклида.	Системы счисления. Делимость. Алгоритм Евклида. Лекция 5, 6	Задачи (29-30 сентября).
5	Функции алгебры логики и предикаты	Функции алгебры логики (раздел не завершён). Предикаты. Булев куб (раздел не завершён). Лекция 7, 8 Презентация (основные эквивалентности и пример построения СДНФ) Лекция 9 (первые 40 минут) Лекция 12 (приблизительно третья четверть записи) Изображения гиперкубов	Задачи (29-30 сентября, 6-7 октября). Задачи (6-7 октября). Задачи (7-15 октября).
6	Контрольная работа	Разбор контрольной работы
7	Элементы теории графов	Элементы теории графов. Лекция 10 (после первых 30-40 минут) Презентация Лекция 11	Задачи (27-28 октября, 10-11 ноября).
8	Регулярные языки и автоматы	Регулярные языки и автоматы. Презентация Лекции 13, 14 Лекция 15 (первый час)	Задачи (10-11 ноября). Задачи (17-18 ноября).
9	Кодирование	Кодирование. Презентация Лекции 15, 16 Лекция 17 Лекции 18, 19 Разбор задачи про (не)однозначно декодируемые коды	Задачи (17-18 ноября). Задачи (24-25 ноября). Задачи (1-2 декабря и дальше).
10	Повторение		Индукция. Комбинаторика. Графы. (повторение) Функции алгебры логики (повторение) Языки и кодирование (повторение)

Домашние задания

дата выдачи	срок сдачи	задание	комментарии
12.10.2021	Основная часть должна быть сдана до 22.10.2021 (23.59.59). Оставшиеся (не более 5 задач) - до 24.10.2021 (22.59.59)	Домашнее задание	Домашнее задание предназначено для дополнительной отработки тем и подготовки к экзамену. Не предполагается, что вы сделаете все задачи, нужно выбирать те темы, которые вы хотите отработать (и получить по решению задач обратную связь). Сдавать задачи можно частями. Файл с задачами должен быть формата pdf и иметь названия ФамилияИмяНомергруппы_NN.pdf, где NN - номер файла, который вы загружаете (т.е. если задание делится на 3 части, то мои файлы были бы подписаны MikhailovichAnna507_1.pdf, MikhailovichAnna507_2.pdf, MikhailovichAnna507_3.pdf). За один день сдавать не больше одного файла. Файлы с решениями присылать на dmfikl2021@yandex.ru.

Дополнительные лекции

лекция	тема	материал	комментарии
1	Коды, исправляющие ошибки. Базовые понятия	Презентация Страницы 77-79
2	Коды Рида-Маллера	Лекция 2 Страницы 86-90
3	Мощности самокорректирующихся кодов	Лекция 3 Страницы 86-90
4	Языки и грамматики. Основные определения. Классификация грамматик. Дерево вывода.	Презентация Лекция 4
5	Контекстно-свободные языки и грамматики. Нормальные формы. Пример не К-С языка. Теоретико-множественные операции для К-С языков.	Презентация Лекция 5
6	Автоматы с магазинной памятью	Презентация Лекция 6