Основы дискретной математики

Общая информация
ЛекторА. В. Пастор
Семестросень 2013
Дата начала10.09.2013
Количество пар12
Язык курсарусский
Аннотация Целью курса является знакомство слушателей с основными понятиями и методами дискретной математики.
Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

1. Элементарная комбинаторика
(10.09.2013 - 18:30 - 19:50)

Основные комбинаторные величины и простейшие комбинаторные формулы. Числа размещения и сочетания (с повторениями и без повторений). Бином Ньютона и биномиальные коэффициенты. Простейшие соотношения на биномиальные коэффициенты. Треугольник Паскаля. Обобщение бинома Ньютона и мультиномиальные коэффициенты. Семейства подмножеств конечного множества.
2. Практика
(10.09.2013 - 20:00 - 21:20)

Соотношения на биномиальные коэффициенты, сочетания с повторениями, число сюрьективных отображений.
3. Принцип включений-исключений
(17.09.2013 - 18:30 - 19:50)

Формула включений-исключений. Субфакториалы (задача о беспорядках). Формула обращения Мебиуса
4. Практика
(17.09.2013 - 20:00 - 21:20)

Формула включения-исключения. Применение формулы обращения Мёбиуса к задаче перечисления циклических строк.
5. Частично упорядоченные множества
(24.09.2013 - 18:30 - 19:50)

Понятие частично упорядоченного множества. Функция Мебиуса для частично упорядоченного множества. Цепи и антицепи. Теорема Дилуорса (б/д). Теорема Мирского.
6. Практика
(24.09.2013 - 20:00 - 21:20)

Частично упорядоченные множества; цепи и антицепи. Применения теоремы Дилуорса и двойственной к ней.
7. Группа перестановок
(01.10.2013 - 18:30 - 19:50)

Четность перестановки, разложение в произведение транспозиций, разбиение на циклы, четность цикла, классы сопряженных и циклический тип перестановки.
8. Практика
(01.10.2013 - 20:00 - 21:20)

Формулы для чисел Стирлинга 1-го рода. Цикловая запись перестановки. Количество перестановок с ограничениями на структуру циклов.
9. Разбиения числа в сумму слагаемых
(08.10.2013 - 18:30 - 19:50)

Задачи о разбиениях чисел на слагаемые. Упорядоченные и неупорядоченные разбиения. Диаграммы Юнга. Рекуррентные соотношения для функций разбиения. Теоремы Харди- Рамануджана (б/д).
10. Практика
(08.10.2013 - 20:00 - 21:20)

11. Рекуррентные соотношения. Числа Каталана и числа Белла
(15.10.2013 - 18:30 - 19:50)

Рекуррентные соотношения. Числа Каталана и числа Белла. Различные интерпретации чисел Каталана.
12. Практика
(15.10.2013 - 20:00 - 21:20)

13. Методы линейной алгебры в комбинаторике
(22.10.2013 - 18:30 - 19:50)

Использование линейной алгебры для доказательства комбинаторных результатов. Различные примеры использования этого метода (неравенство Фишера, (n,k)-плотные множества, множества с двумя расстояниями и т.д.).
14. Практика
(22.10.2013 - 20:00 - 21:20)

15. Контрольная работа
(29.10.2013 - 19:00 - 21:20)

16. Основы теории графов
(12.11.2013 - 18:30 - 19:50)

Графы и орграфы. Основные определения. Матрицы смежности и инцидентности. Маршруты, пути и циклы. Связность, компоненты связности. Деревья и их свойства. Двусвязные графы и блоки. Дерево блоков и точек сочленения.
17. Ориентированные графы
(12.11.2013 - 20:00 - 21:20)

Связность орграфов: различные виды связности, компоненты сильной связности, граф компонент. Турнирные графы. Гамильтоновы пути в турнирном графе. Теорема Редеи (б/д). Циклы в сильно связных турнирах. Теорема Муна.
18. Раскраски графов
(19.11.2013 - 18:30 - 19:50)

Двудольные графы, критерий двудольности. Вершинные и реберные раскраски графа. Простейшие свойства раскрасок. Теорема Брукса. Теоремы Визинга и Гупты (б/д). Совершенные графы. Слабая и сильная гипотезы Бержа: доказательство слабой гипотезы.
19. Паросочетания и покрытия
(19.11.2013 - 20:00 - 21:20)

Независимые множества и покрытия. Связь между ними. Паросочетания в двудольном графе: теоремы Холла и Кенига. Вывод теоремы Дилуорса из теоремы Кенига.
20. Практика
(26.11.2013 - 18:30 - 19:50)

21. Практика
(26.11.2013 - 20:00 - 21:20)

22. Практика
(03.12.2013 - 18:30 - 19:50)

23. Контрольная работа
(03.12.2013 - 20:00 - 21:20)

24. Планарные графы
(10.12.2013 - 18:30 - 19:50)

Планарные и плоские графы. Формула Эйлера и следствия из нее. Понятие двойственного графа. Критерий раскрашиваемости стран в 2 цвета. Раскраска вершин планарного графа в 5 цветов. Гипотеза о четырех красках: формулировка, эквивалентность Тейта (б/д), обсуждение компьютерного доказательсва. Теорема Куратовского (б/д).
25. Практика
(10.12.2013 - 20:00 - 21:20)

Ваша оценка: Пусто Средняя: 4.7 (7 votes)
Share |