• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Контакты

Тиморин Владлен Анатольевич
декан

 

Артамкин Игорь Вадимович
заместитель декана

 

Кузнецова Вера Витальевна
заместитель декана

 

Фейгин Евгений Борисович
заместитель декана

 

Эстеров Александр Исаакович
заместитель декана

119048, Москва,
ул. Усачёва, 6
тел. (495) 772-95-90 *12725 (секретарь)
тел. (495) 772-95-90 *12726 (декан)
тел. (495) 624-26-16
e-mail: math@hse.ru

Учебный офис:
mathstudyoffice@hse.ru

Редакторы сайта факультета:
Коршунов Дмитрий Олегович
Кузнецова Вера Витальевна

Дискретная математика 1 курс 2013-2014 учебный год

лектор: доц. Е.Б.Фейгин


Объявления
Срок сдачи листка № 7 продлён до 4 июня включительно.

Листок № 8 выдаваться не будет (в связи с государственными праздниками 12 и 13 июня).

В пятницу, 23 мая, на третьей паре состоится контрольная по дискретной математике

Список студентов, получивших автомат за третий модуль: Автомат 3 модуль

Выложен листок 4.

В среду 5 марта на второй паре (начало в 10.30) состоится контрольная работа по пройденному с начала третьего модуля материалу.

В листке 3 исправлена опечатка в задаче 9: нужно рассматривать не все последовательности, а только перестановки
(т.е. последовательности без повторений). 

Выложена обновлённая версия листка 5.



Программа курса.

1.Биномиальные и мультиномиальные коэффициенты.
2. Перестановки, статистики и многочлены Гаусса.
3. Двенадцатеричный путь.
4. Формальные степенные ряды и производящие функции.
5. Рациональные производящие функции, рекуррентные соотношения.
6. Числа Каталана, пути Дика и пути Моцкина.
7. Производящие функции нескольких переменных. Числа Бернулли-Эйлера.
8. Принцип включения-исключения. Производящие функции Дирихле.
9. Производящие функции, пути и непрерывные дроби.
10. Разбиения, диаграммы Юнга и пентагональная теорема.
11. Перечисление графов и деревьев.
12. Частично упорядоченные множества и формула обращения Мебиуса.
13. Дискретная вероятность.
14. Производящие функции случайных величин



Литература:

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


Лекции:

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

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

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

Лекция 4, 05.02. Формальные степенные ряды, основные операции: сложение, умножение, композиция.
Теорема существования и единственности обратного ряда. Числа Фибоначчи, экспонента.
Литература. С.К.Ландо, Введение в дискретную математику, гл. 1

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

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

Лекция 7, 28.02. Рекуррентные соотношения, рациональные производящие функции, квазимногочлены и разложение на элементарные дроби. Числа Каталана: комбинаторные интерпретации, явная формула и производящая функция.
Литература. С.К.Ландо, Введение в дискретную математику, гл. 2, гл. 3.

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

Лекция 9, 19.03. Пятиугольные числа и теорема Эйлера. Рекуррентная формула для чисел разбиений. Тождество Якоби для тройного произведения.
Литература. С.К.Ландо, Введение в дискретную математику, гл 6.
Е.Ю.Смирнов "Диаграммы Юнга, плоские разбиения и знакочередующиеся матрицы", лекции 1 и 2.

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

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

Лекция 12, 18.04. Числа Эйлера, треугольники Дика с кратностями. Принцип включения-исключения и линейная алгебра.
Конечные множества и свойства элементов.
Литература. С.К.Ландо, Введение в дискретную математику, гл 4.
Р. Стенли, Перечислительная комбинаторика, гл. 2.

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

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

Лекция 15, 30.05.
Теорема Кэли и теорема Лагранжа. Дискретная вероятность, случайные величины, математическое ожидание, дисперсия.
Литература.
С.К.Ландо, Введение в дискретную математику, гл 8.
Р.Стенли, Перечислительная комбинаторика: деревья, том 2, гл. 5.
Р. Грэхем, Д. Кнут, О. Паташник "Конкретная математика: основание информатики", гл. 8

Лекция 16, 06.06.
Ковариация и коэффициент корреляции случайных величин. Неравенство Чебышёва. Производящие функции случайных величин.
Литература. Р. Грэхем, Д. Кнут, О. Паташник "Конкретная математика: основание информатики", гл. 8


Задачи для семинаров:   Семинар 1   Семинар 2  Семинар 3   Семинар 4  Семинар 5  Семинар 6  Семинар 7   
Семинар 8 (числа Каталана): Р.Стенли, Перечислительная комбинаторика. Деревья, производящие функции и симметрические функции, стр. 283-295. 
Семинар 9   Семинар 10  Семинар 11  Семинар 12   Семинар 13  Семинар 13  Семинар 14
Семинар 15   Семинар 16  Семинар 17   Семинар 18

Листки:   Листок 1   срок сдачи: до 07.02.2014
Листок 2  срок сдачи: до 21.02.2014 
Листок 3  срок сдачи: 06.03.2014 
Листок 4  срок сдачи 20.03.2014 
Листок 5  срок сдачи 24.04.14
Листок 6  срок сдачи 15.05.14
Листок 7  срок сдачи 29.05.14