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

Материал из MathINFO
Перейти к навигации Перейти к поиску
 
(не показаны 22 промежуточные версии этого же участника)
Строка 41: Строка 41:
 
| Комбинаторика<br>
 
| Комбинаторика<br>
 
| [http://math-hse.info/a/2021-22/ling-dm/lectures/lecture3_comb1.pdf Комбинаторика]
 
| [http://math-hse.info/a/2021-22/ling-dm/lectures/lecture3_comb1.pdf Комбинаторика]
 +
 +
[http://math-hse.info/a/2021-22/ling-dm/lectures/lecture3_comb2.pdf Немного о линейных рекуррентных последовательностях]
 +
 
[https://disk.yandex.ru/i/8byIZSQ8Wi0pxQ Презентация]
 
[https://disk.yandex.ru/i/8byIZSQ8Wi0pxQ Презентация]
  
 
[https://disk.yandex.ru/d/-HWLe4iH1FF2ww Лекции 3, 4 (видео)]
 
[https://disk.yandex.ru/d/-HWLe4iH1FF2ww Лекции 3, 4 (видео)]
 +
 +
[https://disk.yandex.ru/d/APb2WL5MiDnQKg Лекция 12 (последние 20 минут)]
 
| [http://math-hse.info/a/2021-22/ling-dm/seminars/seminar_2_comb1.pdf Задачи (14-16 сентября).]  
 
| [http://math-hse.info/a/2021-22/ling-dm/seminars/seminar_2_comb1.pdf Задачи (14-16 сентября).]  
  
Строка 51: Строка 56:
  
 
(ДЗ на 22.09 - №№ 1-6, 9-13, 19, '''24-28 --- задачи по материалам последней лекции''')
 
(ДЗ на 22.09 - №№ 1-6, 9-13, 19, '''24-28 --- задачи по материалам последней лекции''')
 +
 +
[http://math-hse.info/a/2021-22/ling-dm/seminars/seminar_4_comb3.pdf Задачи на тему '''Рекурретные соотношения'''.]
 
|-
 
|-
 
| 4<br>
 
| 4<br>
Строка 65: Строка 72:
  
 
[http://math-hse.info/a/2021-22/ling-dm/lectures/lecture8_predikat.pdf Предикаты.]
 
[http://math-hse.info/a/2021-22/ling-dm/lectures/lecture8_predikat.pdf Предикаты.]
 +
 +
[http://math-hse.info/a/2021-22/ling-dm/lectures/lecture12_bool_cube.pdf Булев куб (раздел не завершён).]
  
 
[https://disk.yandex.ru/d/T__jGZNi9ul9TA Лекция 7, 8]
 
[https://disk.yandex.ru/d/T__jGZNi9ul9TA Лекция 7, 8]
Строка 71: Строка 80:
  
 
[https://disk.yandex.ru/d/MGAyrequbu_VXg Лекция 9 (первые 40 минут)]
 
[https://disk.yandex.ru/d/MGAyrequbu_VXg Лекция 9 (первые 40 минут)]
 +
 +
[https://disk.yandex.ru/d/APb2WL5MiDnQKg Лекция 12 (приблизительно третья четверть записи)]
 +
 +
[http://elsper.ru/2011/02/giperkuby-2/ Изображения гиперкубов]
  
 
| [http://math-hse.info/a/2021-22/ling-dm/seminars/seminar_6_log1.pdf Задачи (29-30 сентября, 6-7 октября).]  
 
| [http://math-hse.info/a/2021-22/ling-dm/seminars/seminar_6_log1.pdf Задачи (29-30 сентября, 6-7 октября).]  
Строка 81: Строка 94:
 
| 6
 
| 6
 
| Контрольная работа<br>
 
| Контрольная работа<br>
|  
+
| [https://disk.yandex.ru/d/QufYlb888itFwA Разбор контрольной работы]
  
  
Строка 92: Строка 105:
 
| 7<br>
 
| 7<br>
 
| Элементы теории графов<br>
 
| Элементы теории графов<br>
|  
+
| [http://math-hse.info/a/2021-22/ling-dm/lectures/lecture11_graph1.pdf Элементы теории графов.]
 
 
[http://math-hse.info/a/2021-22/ling-dm/lectures/lecture11_graph1.pdf Элементы теории графов.]
 
  
 
[https://disk.yandex.ru/d/MGAyrequbu_VXg Лекция 10 (после первых 30-40 минут)]
 
[https://disk.yandex.ru/d/MGAyrequbu_VXg Лекция 10 (после первых 30-40 минут)]
  
 
[https://disk.yandex.ru/i/NvbNny3X15C-aA Презентация]
 
[https://disk.yandex.ru/i/NvbNny3X15C-aA Презентация]
|  
+
 
 +
[https://disk.yandex.ru/d/APb2WL5MiDnQKg Лекция 11]
 +
| [http://math-hse.info/a/2021-22/ling-dm/seminars/seminar_9_gr1.pdf Задачи (27-28 октября, 10-11 ноября).]
 
|-
 
|-
 
| 8<br>
 
| 8<br>
 
| Регулярные языки и автоматы<br>
 
| Регулярные языки и автоматы<br>
|  
+
| [http://math-hse.info/a/2021-22/ling-dm/lectures/lecture12_languages.pdf Регулярные языки и автоматы.]
 +
 
 +
[https://disk.yandex.ru/i/N838CONBwsDxRg Презентация]
 +
 
 +
[https://disk.yandex.ru/d/SGsMzVEEe-Hghg  Лекции 13, 14]
  
 +
[https://disk.yandex.ru/d/zgLbh71MMfJ0qA Лекция 15 (первый час)]
 +
| [http://math-hse.info/a/2021-22/ling-dm/seminars/seminar_11_lang0.pdf Задачи (10-11 ноября).]
  
|
+
[http://math-hse.info/a/2021-22/ling-dm/seminars/seminar_11_lang1.pdf Задачи (17-18 ноября).]
 
|-
 
|-
 
| 9<br>
 
| 9<br>
 
| Кодирование<br>
 
| Кодирование<br>
|  
+
| [http://math-hse.info/a/2021-22/ling-dm/lectures/lecture13_koding.pdf Кодирование.]
 +
 
 +
[https://disk.yandex.ru/i/NzrKFIXzKZyDsA Презентация]
 +
 
 +
[https://disk.yandex.ru/d/zgLbh71MMfJ0qA Лекции 15, 16]
 +
 
 +
[https://disk.yandex.ru/d/hZB3xOBYCIIDVw Лекция 17]
 +
 
 +
[https://disk.yandex.ru/d/PJvrXv_PMhFFpg Лекции 18, 19]
 +
 
 +
 
 +
[http://math-hse.info/a/2021-22/ling-dm/seminars/seminar_coding2.pdf Разбор задачи про (не)однозначно декодируемые коды]
 +
 
 +
| [http://math-hse.info/a/2021-22/ling-dm/seminars/seminar_13_coding_19.pdf Задачи (17-18 ноября).]
  
 +
[http://math-hse.info/a/2021-22/ling-dm/seminars/seminar_coding1.pdf Задачи (24-25 ноября).]
  
|
+
[http://math-hse.info/a/2021-22/ling-dm/seminars/seminar_coding3.pdf Задачи (1-2 декабря и дальше).]
 
|-
 
|-
 
| 10<br>
 
| 10<br>
Строка 121: Строка 154:
  
 
|  
 
|  
 +
[http://math-hse.info/a/2021-22/ling-dm/seminars/seminar_add2_komb_graph.pdf Индукция. Комбинаторика. Графы. (повторение)]
  
 +
[http://math-hse.info/a/2021-22/ling-dm/seminars/seminar_add1_mathlog.pdf Функции алгебры логики (повторение)]
  
 
+
[http://math-hse.info/a/2021-22/ling-dm/seminars/seminar_add3_lang_kod.pdf Языки и кодирование (повторение)]
  
 
|-
 
|-
Строка 145: Строка 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