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

Материал из MathINFO
Перейти к навигации Перейти к поиску

На этой странице будут появляться различные материалы и объявления, связанные с курсом «Дискретная математика для лингвистов», читаемого для студентов 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