Заявки
на голосование

Дискретные структуры

Проголосовать за курс:
Александр Дайняк
МФТИ
Курс ДС — основной курс по дискретной математике и её окрестностям, который читается студентам ФИВТ МФТИ потока ПМФ. Аналогичный (более продвинутый) курс для потока ПМИ читает А.М. Райгородский.

Урок: Демонстрационный урок 1 по дискретным структурам для конкурса

План курса:

Часть 1. Это должен знать каждый.

  1. Вспоминаем/изучаем школьную комбинаторику и некоторые полезные приёмы
    1. Вспоминаем язык: обозначения, которые будут нас преследовать до конца.
    2. Когда голубям тесно: принцип Дирихле.
    3. Принцип домино по-математически: доказательства по индукции.
    4. Когда не вредно изобретать велосипед: метод двойного подсчёта.
    5. Основной вопрос: сколько…?
    6. Сложение и умножение… по-комбинаторному.
    7. Размещаем и сочетаем, с повторениями и без.
    8. Раскрываем скобки: формула бинома и полиномиальная формула.
    9. Свойства биномиальных коэффициентов.
    10. Формула включений-исключений.
    11. Рекуррентные соотношения и метод выделенного элемента.
  2. Теория графов
    1. Откуда берутся графы.
    2. Звёзды, цепи, кактусы и другие графы: новые значения знакомых слов и важные определения.
    3. Одинаковые графы: общематематическая концепция изоморфизма.
    4. Графы и индукция. Теорема Рамсея.
    5. Деревья.
    6. Как нарисовать граф.
    7. Зачем и как раскрашивать графы.
    8. Графы и бракосочетания: всё могут короли, если они выполняют условия Холла.
    9. Когда поверхностное сходство обманчиво: эйлеровы и гамильтоновы циклы.
  3. Асимптотики
    1. Кто побеждает в битве на краю бесконечности: обозначения Кнута.
    2. Сложная асимптотика для «простого» факториала, и что из этого следует.
    3. Набиваем руку: суммы, быстро растущие функции, и другие насущные вещи.

Часть 2. Для тех, кто любит погорячее.

  1. Числа Рамсея
    1. Простые оценки чисел Рамсея.
    2. Вероятностный метод, один из мощнейших методов комбинаторики.
  2. Числа Заранкевича: один сюжет из экстремальной комбинаторики
    1. Вероятностный метод в нижней оценке чисел Заранкевича.
    2. Алгебраическая верхняя оценка.
    3. Алгебраическая нижняя оценка.
  3. Знакомимся с графами ближе
    1. Связность бывает разная: k-связность и теорема Менгера.
    2. Когда вычесть единицу из тривиальной оценки непросто: теорема Брукса.
    3. Обманчивые графы: вблизи как деревья, а раскашиваются тяжело: теорема Эрдёша.
    4. Паросочетания в недвудольных графах: теорема Татта.
    5. Две красивые теоремы о разложении графов: теоремы Анселя и Грэхема—Поллака.
comments powered by Disqus