Дискретная математика (Е.Б. Фейгин)

АБB
АБB
АБB

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

ВЕСНА

Объявления:

NEW: Выложены итоговые результаты - файл Результат_весна.pdf.

Результаты (обновлено 22.06):

Результат_весна (PDF, 41 Кб)

15мин+контр_весна (PDF, 43 Кб)

Листок1_весна (PDF, 116 Кб)

Листок2_весна (PDF, 55 Кб)

Листок3_весна (PDF, 55 Кб)

Лекции:

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

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

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

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

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

Лекция 6, 11.05. Инварианты Татта.
Литература. С. К. Ландо. Введение в дискретную математику, гл. 10.

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

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

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

Лекция 10, 08.06. Треугольники в случайных графах. Связность случаного графа.
Литература. А.М.Райгородский "Модели случайных графов", гл. 2

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

Листки:

listok1 (PDF, 110 Кб)

listok2 (PDF, 148 Кб)

listok3 (PDF, 101 Кб)

Семинары:

seminar1 (PDF, 82 Кб)

seminar2 (PDF, 65 Кб)

seminar3 (PDF, 70 Кб)

seminar4 (PDF, 114 Кб)

seminar5 (PDF, 78 Кб)

seminar6 (PDF, 56 Кб)

seminar7 (PDF, 108 Кб)

seminar8 (PDF, 117 Кб)

Пятнадцатиминутки:

15min_1 (PDF, 34 Кб)

15min2_var1 (PDF, 48 Кб)

15min2_var2 (PDF, 48 Кб)

15min3 (PDF, 92 Кб)

15min4 (PDF, 67 Кб)

15min5 (PDF, 57 Кб)

15min6 (PDF, 52 Кб)

15min7 (PDF, 72 Кб)

15min8 (PDF, 41 Кб)

15min9 (PDF, 54 Кб)

ЗИМА

Объявления:
NEW: Выложены окончательные результаты (файл Результат). Полный балл за листочки ставился за 20 задач, за десятиминутки за 24 балла, за к/р за 20 баллов, за экзамен за 24 балла.
Итоговую оценку можно найти в столбце Итог.

Результаты:

Дискретная математика_19.02 (XLSX, 30 Кб)

Результат_24.02 (PDF, 47 Кб)

Литература:

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

Лекции:

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

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

Лекция 3, 09.12. Инверсии для мультимножеств, q-биномиальные коэффициенты (многочлены Гаусса), q-мультиномиальные коэффициенты и перестановки мультимножеств.
Литература: Р. Стенли, Перечислительная комбинаторика, том 1, гл. 1.

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

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

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

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

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

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

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

Листки:

listok1 (PDF, 96 Кб)

listok2 (PDF, 148 Кб)

Семинары:

seminar1 (PDF, 97 Кб)

seminar2 (PDF, 126 Кб)

seminar3 (PDF, 83 Кб)

seminar4 (PDF, 120 Кб)

seminar5 (PDF, 99 Кб)

seminar6 (PDF, 84 Кб)

seminar7_catalan (PDF, 237 Кб)

seminar8 (PDF, 111 Кб)

seminar9 (PDF, 127 Кб)

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

10min_1_var1 (PDF, 79 Кб)

10min_1_var2 (PDF, 65 Кб)

10min_2_var1 (PDF, 61 Кб)

10min_2_var2 (PDF, 57 Кб)

10min_3_var1 (PDF, 58 Кб)

10min_3_var2 (PDF, 58 Кб)

10min_4_var1 (PDF, 43 Кб)

10min_4_var2 (PDF, 51 Кб)

10min_5_var1 (PDF, 66 Кб)

10min_5_var2 (PDF, 75 Кб)

10min_6_var1 (PDF, 84 Кб)

10min_6_var2 (PDF, 84 Кб)

Выложен листок 2. Срок сдачи 1 июня. Ближайший ПЗ 1 июня.