Дискретная математика. Лектор: проф. Е.Б.Фейгин

АБB
АБB
АБB

Обычная версия сайта

4 модуль

Итоговая оценка в столбце ИТОГ, полный балл за экзамен ставился за 4 задачи
Обновлённый файл (от 19 июня)

Автоматы за 4 модуль

Объявления:

26 мая (вторник) вместо приёма задач состоится контрольная работа.
Выложен Листок 7, срок сдачи 9 июня
В понедельник и вторник, 11 и 12 мая, лекции, семинаров и математического практикума по дискретной математике не будет.
Выложен Листок 6, срок сдачи 19 мая
Выложен Листок 5, срок сдачи 21 апреля

Результаты десятиминуток и контрольных

10мин4мод+контр (PDF, 68 Кб)

Литература:

Р. Грэхем, Д. Кнут, О. Паташник "Конкретная математика: основание информатики".
С. К. Ландо "Введение в дискретную математику".
С. К. Ландо "Лекции о производящих функциях".
Р. Стенли "Перечислительная комбинаторика".
Е. Ю.Смирнов "Диаграммы Юнга, плоские разбиения и знакочередующиеся матрицы"
Д.Эндрюс "Теория разбиений"
Ф.Харари, Э.Палмер "Перечисление графов"

Листки:

Листок 5 (PDF, 100 Кб)

Листок 6 (PDF, 131 Кб)

Листок 7 (PDF, 123 Кб)

Семинары:

Семинар 11 (PDF, 104 Кб)

Семинар 12 (PDF, 100 Кб)

Семинар 13 (PDF, 79 Кб)

Семинар 14 (PDF, 141 Кб)

Семинар 15 (PDF, 117 Кб)

Семинар 16 (PDF, 92 Кб)

Семинар 17 (PDF, 95 Кб)

Семинар 18 (PDF, 97 Кб)

Семинар 19 (PDF, 103 Кб)

Десятиминутки:

10min_9_var1 (PDF, 50 Кб)

10min_9_var2 (PDF, 50 Кб)

10min_10_var1 (PDF, 43 Кб)

10min_10_var2 (PDF, 41 Кб)

10min_11_var1 (PDF, 63 Кб)

10min_11_var2 (PDF, 64 Кб)

10min_12_var1 (PDF, 60 Кб)

10min_12_var2 (PDF, 60 Кб)

10min_13_var1 (PDF, 76 Кб)

10min_13_var2 (PDF, 101 Кб)

10min_14_var1 (PDF, 94 Кб)

10min_14_var2 (PDF, 71 Кб)

10min_15_var1 (PDF, 81 Кб)

10min_15_var2 (PDF, 39 Кб)

Лекции:

Лекция 11, 30.03. Графы и деревья. Помеченные и корневые деревья. Коды Прюфера и теорема Кэли.
Литература. С.К.Ландо, Введение в дискретную математику, гл 8.
Р.Стенли, Перечислительная комбинаторика: деревья, том 2, гл. 5

Лекция 12, 06.04. Производящая функция корневых помеченных деревьев, функциональное уравнение. Теорема Кэли и формула обращения Лагранжа.
Литература. С.К.Ландо, Введение в дискретную математику, гл 8.
Р.Стенли, Перечислительная комбинаторика: деревья, том 2, гл. 5

Лекция 13, 13.04. Производящая функция корневых непомеченных деревьев. Цикловый тип перестановки, количество перестановок с данным цикловым типом. Цикловый индекс группы перестановок.
Литература. Ф.Харари, Э.Палмер. Перечисление графов, гл.2,3.

Лекция 14, 20.04. Пречисление корневых непомеченных деревьев, функциональное уравнение на производящую функцию, рекуррентное соотношение для числа деревьев.
Литература. Ф.Харари, Э.Палмер. Перечисление графов, гл.2,3.

Лекция 15, 27.04. Корневые помеченные леса, многочлены Абеля, биномиальные последовательности..
Литература. С. К. Ландо. Введение в дискретную математику, гл. 5,8.

Лекция 15, 18.05. Принцип включения-исключения, числа беспорядков. Производящие функции Дирихле.
Литература. Р. Стенли, Перечислительная комбинаторика, гл. 2.
С.К.Ландо, Введение в дискретную математику, гл 7.
Р. Грэхем, Д. Кнут, О. Паташник "Конкретная математика: основание информатики", гл. 4.9, 7.

Лекция 16, 25.05. Производящие функции Дирихле, мультипликативные последовательности,
формула обращения Мёбиуса. Дзета функция, функция Мёбиуса, эйлерова фи-функция.
Литература. С.К.Ландо, Введение в дискретную математику, гл 7.
Р. Грэхем, Д. Кнут, О. Паташник "Конкретная математика: основание информатики", гл. 4.9, 7.

Лекция 17, 01.06. Дискретная вероятность, случайные величины, математическое ожидание, дисперсия.
Литература. Р. Грэхем, Д. Кнут, О. Паташник "Конкретная математика: основание информатики", гл. 8

Лекция 18, 08.06. Ковариация и коэффициент корреляции случайных величин. Производящие функции случайных величин и старшие моменты.
Литература. Р. Грэхем, Д. Кнут, О. Паташник "Конкретная математика: основание информатики", гл. 8
________________________________________________________________________________
3 модуль

Объявления:

Оценки за 3 модуль (PDF, 43 Кб)

Итоговая оценка в столбце ИТОГ, полный балл за экзамен ставился за 4 задачи

Автоматы за 3 модуль (PDF, 38 Кб)

Срок сдачи Листка 3 продлён до 10.03.
Выложен Листок 4, срок сдачи 17.03.
Во вторник, 24 февраля, вместо приёма задач и десятиминутки состоится контрольная работа по темам:
биномиальные и мультиномиальные коэффициенты, многочлены Гаусса, формальные степенные ряды и
операции с ними, рекуррентные последовательности, рациональные производящие функции, квазимногочлены.

Литература:

Р. Грэхем, Д. Кнут, О. Паташник "Конкретная математика: основание информатики".
С. К. Ландо "Введение в дискретную математику".
С. К. Ландо "Лекции о производящих функциях".
Р. Стенли "Перечислительная комбинаторика".
Е. Ю.Смирнов "Диаграммы Юнга, плоские разбиения и знакочередующиеся матрицы"
Д.Эндрюс "Теория разбиений"

Листки:

Листок 1 (PDF, 149 Кб)

Листок 2 (PDF, 148 Кб)

Листок 3 (PDF, 160 Кб)

Листок 4 (PDF, 149 Кб)

Семинары:

Семинар 1 (PDF, 122 Кб)

Семинар 2 (PDF, 126 Кб)

Семинар 3 (PDF, 114 Кб)

Семинар 4 (PDF, 124 Кб)

Семинар 5 (PDF, 109 Кб)

Семинар 6 (PDF, 115 Кб)

Семинар 7 (PDF, 100 Кб)

Семинар 8 (PDF, 237 Кб)

Семинар 9 (PDF, 67 Кб)

Семинар 10 (PDF, 82 Кб)

Десятиминутки:

10min_1_var1 (PDF, 69 Кб)

10min_1_var2 (PDF, 65 Кб)

10min_2_var1 (PDF, 97 Кб)

10min_2_var2 (PDF, 79 Кб)

10min_3_var1 (PDF, 87 Кб)

10min_3_var2 (PDF, 95 Кб)

10min_4_var1 (PDF, 56 Кб)

10min_4_var2 (PDF, 56 Кб)

10min_5_var1 (PDF, 89 Кб)

10min_5_var2 (PDF, 89 Кб)

10min_6_var1 (PDF, 88 Кб)

10min_6_var2 (PDF, 50 Кб)

10min_7_var1 (PDF, 71 Кб)

10min_7_var2 (PDF, 64 Кб)

10min_8_var1 (PDF, 77 Кб)

10min_8_var2 (PDF, 85 Кб)

Лекции:

Лекция 1, 15.01. Множества и мультимножества. Биномиальные коэффициенты и разложения.
Литература: Р. Стенли, Перечислительная комбинаторика, том 1, гл. 1.

Лекция 2, 22.01. Мультиномиальные коэффициенты, перестановки мультимножеств.
Статистики на группе перестановок, статистические суммы, циклическая структура.
q-биномиальные коэффициенты - многочлены Гаусса..
Литература: Р. Стенли, Перечислительная комбинаторика, том 1, гл. 1.

Лекция 3, 29.01. q-мультиномиальные коэффициенты и перестановки мультимножеств. Алгебра формальных степенных рядов.
Литература:
Р. Стенли, Перечислительная комбинаторика, том 1, гл. 1.
С.К.Ландо, Введение в дискретную математику, гл. 1

Лекция 4, 05.02. Формальные степенные ряды, теорема существования и единственности обратного ряда.
Дифференциальное и интегральное исчисления формальных степенных рядов. Разложение
в ряд Тейлора, формула для производной композиции двух рядов. Экспонента и логарифм.
Литература. С.К.Ландо, Введение в дискретную математику, гл. 1.
А.Л.Городенцев, Лекции по алгебре, http://vyshka.math.ru/pspdf/1011/algebra-2/lec_04.pdf

Лекция 5, 12.02. Логарифм и экспонента, бином Ньютона. Векторные производящие функции,
рекуррентные последовательности и рациональные производящие функции.
Литература. С.К.Ландо, Введение в дискретную математику, гл. 2.
А.Л.Городенцев, Лекции по алгебре, http://vyshka.math.ru/pspdf/1011/algebra-2/lec_04.pdf

Лекция 6, 19.02. Рекуррентные последовательности, рациональные производящие функции, разложение
на простейшие дроби и квазимногочлены. Неоднородные рекуррентные соотношения.
Литература. С.К.Ландо, Введение в дискретную математику, гл. 2.

Лекция 7, 26.02. Числа Каталана: неассоциативное умножение, скобочные структуры, рекуррентное соотношение, производящая функция, явная формула. Пути Дика и лемма Рени о циклических сдвигах. Триангуляция многоугольников.
Литература. Р. Грэхем, Д. Кнут, О. Паташник "Конкретная математика: основание информатики", гл. 7.5.
Р. Стенли "Перечислительная комбинаторика т.2", гл.6, упраженения.
С.К.Ландо, Введение в дискретную математику, гл. 2,3.

Лекция 8, 05.03. Числа разбиений, диаграммы Юнга, производящая функция. Разбиения на различные и нечётные слагаемые. Пятиугольные числа, теорема Эйлера и рекуррентная формула.
Литература: С.К.Ландо, Введение в дискретную математику, гл 6
Е. Ю.Смирнов "Диаграммы Юнга, плоские разбиения и знакочередующиеся матрицы", гл. 1

Лекция 9, 12.03. Перечисление путей в графах. Графы Дика и Паскаля. Производящие функции от двух переменных. Треугольник Бернулли-Эйлера.
Литература: С.К.Ландо, Введение в дискретную математику, гл 3-4.

Лекция 10, 19.03. Треугольник Бернулли-Эйлера, пилообразные перестановки, рекуррентные соотношения.
Экспоненциальные производящие функции чисел Бернулли-Эйлера от одной и двух переменных.
Литература: С.К.Ландо, Введение в дискретную математику, гл. 4