Модули и структура курса
1 Основные понятия и классические задачи теории графов 7 лекций
Видеолекции 7
-
Введение 0:00
-
Задача о Кенигсбергских мостах 0:00
-
Определение графа 0:00
-
Примеры графов 0:00
-
Маршруты в графе 0:00
-
Эквивалентные определения дерева 0:00
-
Эйлеровские графы 0:00
Тест к модулю
2 Графы.Первые задачи 8 лекций
Видеолекции 8
-
Деревья Кэли 0:00
-
Как закодировать дерево 0:00
-
Как раскодировать граф 0:00
-
Проблема четырёх красок 0:00
-
Задача о рукопожатиях 0:00
-
Числа Рамсея 0:00
-
Кликовое число и число независимости 0:00
-
Раскраска плоскости 0:00
Тест к модулю
3 Вероятность и графы 9 лекций
Видеолекции 9
-
Классическое определение вероятности. 0:00
-
Совпадут ли дни рождения? 0:00
-
Независимые события и условная вероятность. 0:00
-
Испытания Бернулли. 0:00
-
Биноминальные коэффициенты. 0:00
-
Случайный граф - что это такое? 0:00
-
Случайная величина и её математическое ожидание. 0:00
-
Линейность математического ожидания. 0:00
-
Неравенства Маркова и Чебышёва. 0:00
Домашнее задание
Тест к модулю
4 Треугольники в случайном графе 6 лекций
Видеолекции 6
-
Есть ли у случайного графа треугольники? 0:00
-
Пределы 0:00
-
Когда треугольников почти наверное нет 0:00
-
Когда треугольники почти наверное есть. Начало 0:00
-
Когда треугольники почти наверное есть. Второй момент 0:00
-
Победа – треугольники всё-таки есть! 0:00
Тест к модулю
5 Числа Рамсея и связность графа 7 лекций
Видеолекции 7
-
Связен ли наш граф 0:00
-
О пользе железных дорог 0:00
-
Когда граф связен 0:00
-
Фазовый переход от связности к несвязности 0:00
-
Когда граф несвязен 0:00
-
Числа Рамсея - они быстро растут 0:00
-
Графы, которых никто не видел 0:00
Тест к модулю
6 Хроматическое число 6 лекций
Видеолекции 6
-
Какая оценка лучше? 0:00
-
Кто быстрее 0:00
-
Коротких циклов не слишком много 0:00
-
Девушки и ожерелья 0:00
-
Больших независимых множеств нет 0:00
-
Как удалить циклы? 0:00
7 Интернет-графы 6 лекций
Видеолекции 6
-
Как устроен веб-граф ? 0:00
-
Два удивительных наблюдения 0:00
-
Степенной закон распределения степеней вершин 0:00
-
Надо ли менять модель? 0:00
-
Каков закон распределения вершин в модели Эрдеша-Реньи? 0:00
-
Модель Боллобаша-Риордана 0:00
8 Выходим на приложения 3 лекции
Видеолекции 3
-
Теоремы на основе исследований Боллобаша и Риордана? 0:00
-
Работаем с оговоркаи и ограничениями 0:00
-
Приложение теории для поисковых систем 0:00
Цель изучения курса
Представленный курс позволит не только осовить основные понятия и определения теории графов, но и заложит основы её практического использования. Слушатели инженерных специализаций, получат реальный инструмент повышения своей профессиональной результативности, но в тоже время и поклонники фундаментальных наук смогут насладиться исключительным обаянием теории графов и её связью со смежными научными направлениями.
Необходимый уровень подготовки
Необходимо знать основы комбинаторики, т.е. числа сочетаний и бином Ньютона, а также полезно иметь представление о том, что такое квантор ("для любого", "существует"), что бывают взаимно однозначные соответствия между множествами.
Результаты изучения курса
Слушатель познакомится с некоторыми объектами теории графов, с несколькими наиболее яркими задачами теории, а также узнает о приложениях теории в современных информационных технологиях и не только в них.