Дискретная математика: различия между версиями

Материал из MathINFO
Перейти к навигации Перейти к поиску
 
(не показано 5 промежуточных версий этого же участника)
Строка 180: Строка 180:
 
| [http://math-hse.info/a/2021-22/ling-dm/seminars/homework1.pdf Домашнее задание]
 
| [http://math-hse.info/a/2021-22/ling-dm/seminars/homework1.pdf Домашнее задание]
 
| Домашнее задание предназначено для дополнительной отработки тем и подготовки к экзамену. Не предполагается, что вы сделаете все задачи, нужно выбирать те темы, которые вы хотите отработать (и получить по решению задач обратную связь). Сдавать задачи можно частями. Файл с задачами должен быть формата pdf и иметь названия ФамилияИмяНомергруппы_NN.pdf, где NN - номер файла, который вы загружаете (т.е. если задание делится на 3 части, то мои файлы были бы подписаны MikhailovichAnna507_1.pdf, MikhailovichAnna507_2.pdf, MikhailovichAnna507_3.pdf). За один день сдавать не больше одного файла. Файлы с решениями присылать на dmfikl2021@yandex.ru.
 
| Домашнее задание предназначено для дополнительной отработки тем и подготовки к экзамену. Не предполагается, что вы сделаете все задачи, нужно выбирать те темы, которые вы хотите отработать (и получить по решению задач обратную связь). Сдавать задачи можно частями. Файл с задачами должен быть формата pdf и иметь названия ФамилияИмяНомергруппы_NN.pdf, где NN - номер файла, который вы загружаете (т.е. если задание делится на 3 части, то мои файлы были бы подписаны MikhailovichAnna507_1.pdf, MikhailovichAnna507_2.pdf, MikhailovichAnna507_3.pdf). За один день сдавать не больше одного файла. Файлы с решениями присылать на dmfikl2021@yandex.ru.
 +
|-
 +
|}
 +
 +
==Дополнительные лекции==
 +
{| class="wikitable"
 +
! лекция
 +
 +
! тема
 +
 +
! материал
 +
 +
! комментарии
 +
 +
|-
 +
| 1<br>
 +
| Коды, исправляющие ошибки. Базовые понятия<br>
 +
|
 +
 +
[https://disk.yandex.ru/i/OHgnVB40hfRu_Q Презентация]
 +
 +
[http://new.math.msu.su/department/dm/data/uploads/dm-4-1/4k-1-sent20.pdf Страницы 77-79]
 +
|
 +
|-
 +
| 2<br>
 +
| Коды Рида-Маллера<br>
 +
|
 +
 +
[https://disk.yandex.ru/d/3r-A6QRKkQ6WSQ Лекция 2]
 +
 +
[http://new.math.msu.su/department/dm/data/uploads/dm-4-1/4k-1-sent20.pdf Страницы 86-90]
 +
|
 +
|-
 +
| 3<br>
 +
| Мощности самокорректирующихся кодов<br>
 +
|
 +
 +
 +
[https://disk.yandex.ru/d/ibLLOP-xpOc2dQ Лекция 3]
 +
 +
[http://new.math.msu.su/department/dm/data/uploads/dm-4-1/4k-1-sent20.pdf Страницы 86-90]
 +
|
 +
|-
 +
| 4<br>
 +
| Языки и грамматики. Основные определения. Классификация грамматик. Дерево вывода.<br>
 +
|
 +
[https://disk.yandex.ru/i/fPK2jH5Sz7ct9g Презентация]
 +
 +
[https://disk.yandex.ru/d/l6EvBhjbKgnxqA Лекция 4]
 +
|
 +
|-
 +
| 5<br>
 +
|
 +
Контекстно-свободные языки и грамматики. Нормальные формы. <br>
 +
Пример не К-С языка. Теоретико-множественные операции для К-С языков.
 +
|
 +
[https://disk.yandex.ru/i/-iZF8KexNO8j6A Презентация]
 +
 +
[https://disk.yandex.ru/d/tcQcDumdWidVOA Лекция 5]
 +
|
 +
|-
 +
| 6<br>
 +
|
 +
Автоматы с магазинной памятью
 +
|
 +
[https://disk.yandex.ru/i/6A2fC-p7FlLUJg Презентация]
 +
 +
[https://disk.yandex.ru/d/aOLpjIxOmC74jQ Лекция 6]
 +
|
 
|-
 
|-
 
|}
 
|}

Текущая версия на 15:26, 6 июня 2022

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