Über diesen Kurs
9,835 recent views

100 % online

Beginnen Sie sofort und lernen Sie in Ihrem eigenen Tempo.

Flexible Fristen

Setzen Sie Fristen gemäß Ihrem Zeitplan zurück.

Ca. 22 Stunden zum Abschließen

Empfohlen: 5 hours/week...

Russisch

Untertitel: Russisch

100 % online

Beginnen Sie sofort und lernen Sie in Ihrem eigenen Tempo.

Flexible Fristen

Setzen Sie Fristen gemäß Ihrem Zeitplan zurück.

Ca. 22 Stunden zum Abschließen

Empfohlen: 5 hours/week...

Russisch

Untertitel: Russisch

Lehrplan - Was Sie in diesem Kurs lernen werden

Woche
1
3 Stunden zum Abschließen

Введение. Базовые понятия теории графов

В первую неделю курса мы познакомимся с понятием графа, научимся отличать граф от его изображения, поговорим о разных видах графов. Мы вспомним, с чего началась теория графов, научимся представлять в виде графа структуру интернета. Мы обсудим такие важные понятия, как маршруты в графах, степень вершины, связность, а также начнем говорить про важный класс графов - деревья....
17 Videos (Gesamt 104 min), 6 Lektüren, 1 Quiz
17 Videos
МФТИ1m
Примеры графов. Граф и его изображение10m
Ориентированные графы4m
Кёнигсбергские мосты. Мультиграфы5m
Граф интернета. Псевдографы4m
Определение графа5m
Маршруты в графах10m
Связность, подграфы7m
Степень вершины3m
Деревья, эквивалентные определения дерева5m
Знакомства6m
Число мультиграфов4m
Путь в графе5m
Перенумерация цикла8m
Последовательности степеней9m
Замкнутый маршрут9m
6 Lektüren
МФТИ10m
Теоретический материал к семинару10m
Задачи к семинару10m
Решение задач10m
Дополнительные задачи к неделе 110m
Конспект лекции 110m
1 praktische Übung
Задание к неделе 118m
Woche
2
3 Stunden zum Abschließen

Эквивалентные определения дерева. Планарные графы

На этой неделе мы научимся определять деревья четырьмя различными способами, и поговорим о том, как правильно раскрашивать географические карты. Мы вспомним знаменитую теорему о четырех красках, а также критерий Куратовского о том, как определить, можно ли нарисовать данный граф на плоскости без пересечений ребер. В последней части лекции мы обсудим формулу Эйлера для планарных графов и некоторые из её множественных следствий....
17 Videos (Gesamt 147 min), 4 Lektüren, 1 Quiz
17 Videos
Доказательство второй импликации13m
Доказательство третьей импликации9m
Доказательство четвертой импликации6m
Планарность. Гипотеза о четырех красках10m
Примеры непланарных графов5m
Критерий Куратовского7m
Плоские графы, грани и теорема Жордана8m
Формула Эйлера10m
Следствие для числа ребер13m
Хроматическое число планарных графов8m
Доказательство оценки хроматического числа13m
Минимальное число ребер2m
Число пересечений в полном графе2m
Число ребер в планарном графе и формула Эйлера4m
Характеризация двудольных графов15m
Двудольные планарные графы9m
4 Lektüren
Теоретический материал к семинару10m
Задачи к семинару10m
Решения задач10m
Дополнительные задачи к неделе 210m
1 praktische Übung
Задание к неделе 218m
Woche
3
3 Stunden zum Abschließen

Формула Кэли. Унициклические графы. Эйлеровы циклы

На этой неделе мы перечислим все деревья. Для этого нам потребуется перенять опыт древних по подсчету баранов (или козлов). Не остановившись на этом, перечислим и все леса и унициклические графы. Затем мы вернемся к задаче о Кёнигсбергских мостах и получим полное решение этого вопроса....
15 Videos (Gesamt 115 min), 4 Lektüren, 1 Quiz
15 Videos
Доказательство формулы. Кодирование деревьев5m
Построение кодов Прюфера5m
Взаимно однозначное соответствие кодов и деревьев. Декодирование8m
Формула для числа унициклических графов6m
Доказательство формулы14m
Эйлеровы циклы5m
Критерий эйлеровости3m
Первая часть доказательства критерия11m
Вторая часть доказательства критерия12m
Центр дерева6m
Деревья с заданной последовательностью степеней11m
Код Прюфера из различных чисел3m
Число неизоморфных деревьев6m
Ориентация графа4m
4 Lektüren
Теоретический материал к семинару10m
Задачи к семинару10m
Решения задач10m
Дополнительные задачи к неделе 310m
1 praktische Übung
Задание к неделе 316m
Woche
4
4 Stunden zum Abschließen

Гамильтоновы циклы

На этой неделе мы продолжим обсуждать циклы, проходящие через весь граф. На этот раз мы поговорим про циклы, проходящие через все вершины графа. В отличие от эйлеровых циклов, здесь нет необходимого и достаточного критерия наличия такого цикла. Есть только достаточные условия, и мы обсудим два таких условия, довольно разных по своей природе. По пути мы обсудим такие важные характеристики графа, как независимое число и k-связность. В качестве дополнения, мы расскажем об одном очень интересном классе графов, для которого один из критериев работает, а другой - нет....
21 Videos (Gesamt 166 min), 6 Lektüren, 1 Quiz
21 Videos
Множества соседей концов максимального пути9m
Завершение доказательства теоремы Дирака9m
Независимые множества5m
Вершинная связность. Критерий Хватала4m
Доказательство. В графе есть циклы6m
Подграф без максимального цикла5m
Соседи связной компоненты5m
Соседи компоненты и максимальный цикл7m
Число соседей больше связности7m
Завершение доказательства9m
Число гамильтоновых циклов в полном двудольном графе3m
Число независимости, связность10m
Непересекающиеся гамильтоновы циклы12m
Сравнение двух признаков гамильтоновости на конкретном графе. Определение графа6m
Работает ли признак Дирака?6m
Признак Хватала. Оценка связности через общих соседей6m
Число общих соседей8m
Примеры независимых множеств, теорема о числе независимости11m
Доказательство теоремы10m
Связь с теорией кодирования6m
6 Lektüren
Пример гамильтонова графа10m
Теоретический материал к семинару10m
Задачи к семинару10m
Комментарий к лекции10m
Решения задач10m
Дополнительные задачи к неделе 410m
1 praktische Übung
Задание к неделе 418m
Woche
5
3 Stunden zum Abschließen

Паросочетания. Теоремы Холла и Кёнига

На этой неделе мы поговорим про паросочетания. Мы узнаем, что нужно, чтобы переженить всех юношей и девушек по любви. Мы обсудим две классических теоремы, у одной из которых очень изящное доказательство по индукции, а у другой не менее изящное доказательство алгоритмическое. А на семинаре мы узнаем, что эти две теоремы эквивалентны....
15 Videos (Gesamt 150 min), 4 Lektüren, 1 Quiz
15 Videos
Необходимое условие существования паросочетания. Теорема Холла8m
Доказательство теоремы Холла. Два случая6m
Разбор случая 110m
Разбор случая 212m
Вершинное покрытие, теорема Кёнига6m
Первая часть доказательства. Чередующиеся цепи12m
Вторая часть доказательства. Разбиение множества вершин8m
Третья часть доказательства. Построение вершинного покрытия10m
Завершение доказательства. Вершинное покрытие работает10m
Теорема Холла из теоремы Кёнига9m
Теорема Кёнига из теоремы Холла11m
Паросочетания и степени вершин10m
Паросочетания в деревьях5m
К-регулярный двудольный граф15m
4 Lektüren
Теоретический материал к семинару10m
Задачи к семинару10m
Решения задач10m
Дополнительные задачи к неделе 510m
1 praktische Übung
Задание к неделе 518m
Woche
6
3 Stunden zum Abschließen

Экстремальная теория графов. Теорема Турана

На этой неделе мы начнем разговор про экстремальную теорию графов, которая ставит вопросы про то, с какого момента графы начинают обладать тем или иным свойством. В частности, мы выясним, сколько ребер должен иметь граф, чтобы он гарантированно содержал треугольник. В конце лекции мы узнаем, что графы на плоскости в экстремальных задачах ведут себя несколько по-другому, нежели графы абстрактные. ...
13 Videos (Gesamt 123 min), 4 Lektüren, 1 Quiz
13 Videos
Теорема Турана6m
Доказательство теоремы Турана16m
Пример графа, на котором оценка Турана достигается7m
Теорема Турана в терминах кликового числа7m
Задача про графы на плоскости9m
Решение задачи15m
Двудольный подграф13m
Вершинное покрытие для графа без треугольников4m
Граф без четных циклов10m
Хроматическое число и число независимости6m
Хроматическое число и максимальная степень7m
Хроматическое число графа и его дополнения11m
4 Lektüren
Теоретический материал к семинару10m
Задачи к семинару10m
Решения задач10m
Дополнительные задачи к неделе 610m
1 praktische Übung
Задание к неделе 618m
Woche
7
3 Stunden zum Abschließen

Теория Рамсея

На заключительной лекции мы поговорим про теорию Рамсея. Вы узнаете много нового о знакомствах, о том, сколько раз можно в одном доказательстве применить принцип Дирихле и о том, что доказать существование графа и привести пример такого графа - это зачастую совсем разные по сложности задачи....
20 Videos (Gesamt 148 min), 4 Lektüren, 1 Quiz
20 Videos
Начало доказательства. Применение принципа Дирихле4m
Завершение доказательства6m
Формулировка в терминах независимых множеств и раскрасок5m
Пяти вершин недостаточно2m
Определение чисел Рамсея4m
Значения R(s,t) для малых s13m
Верхняя оценка чисел Рамсея с помощью рекурсии2m
Доказательство. Принцип Дирихле7m
Завершение доказательства10m
Численные верхние оценки чисел Рамсея12m
Нижняя оценка числа Рамсея. Что требуется доказать?3m
Подсчет графов с большими полными подграфами12m
Вычисления. Завершение доказательства теоремы4m
Обсуждение нижних оценок4m
Число Рамсея для звезды5m
Число Рамсея для дерева и полного графа13m
Раскраска плоскости6m
Монотонные последовательности9m
Пути или звезды13m
4 Lektüren
Теоретический материал к семинару10m
Задачи к семинару10m
Решение задач10m
Дополнительные задачи к неделе 710m
1 praktische Übung
Задание к неделе 714m
Woche
8
18 Minuten zum Abschließen

Экзамен

Заключительная работа по материалу всего курса...
1 Quiz
1 praktische Übung
Экзамен. Один граф18m
4.9
41 BewertungenChevron Right

20%

ziehen Sie für Ihren Beruf greifbaren Nutzen aus diesem Kurs

25%

erhalten Sie eine Gehaltserhöhung oder Beförderung

Top-Bewertungen

von DDOct 30th 2016

Очень интересный курс. Проходил его просто из любопытства и открыл для себя много нового в теории графов. Задачки средней сложности. Некоторые можно просто решить запрограммировав перебор.

von DMNov 8th 2016

Отличный курс, правда местами задания сложные, но зато есть над чем поломать голову) Это тот курс, который даст хорошие знания и для окончания которого действительно стоит постараться.

Dozenten

Avatar

Андрей Райгородский

профессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Avatar

Андрей Купавский

кандидат физико-математических наук
Кафедра дискретной математики ФИВТ МФТИ

Über Moscow Institute of Physics and Technology

Московский физико-технический институт (неофициально известный как МФТИ или Физтех) является одним из самых престижных в мире учебных и научно-исследовательских институтов. Он готовит высококвалифицированных специалистов в области теоретической и прикладной физики, прикладной математики, информатики, биотехнологии и смежных дисциплин. Физтех был основан в 1951 году Нобелевской премии лауреатами Петром Капицей, Николаем Семеновым, Львом Ландау и Сергеем Христиановичем. Основой образования в МФТИ является уникальная «система Физтеха»: кропотливое воспитание и отбор самых талантливых абитуриентов, фундаментальное образование высшего класса и раннее вовлечение студентов в реальную научно-исследовательскую работу. Среди выпускников МФТИ есть Нобелевские лауреаты, основатели всемирно известных компаний, известные космонавты, изобретатели, инженеры....

Häufig gestellte Fragen

  • Sobald Sie sich für ein Zertifikat angemeldet haben, haben Sie Zugriff auf alle Videos, Quizspiele und Programmieraufgaben (falls zutreffend). Aufgaben, die von anderen Kursteilnehmern bewertet werden, können erst dann eingereicht und überprüft werden, wenn Ihr Unterricht begonnen hat. Wenn Sie sich den Kurs anschauen möchten, ohne ihn zu kaufen, können Sie womöglich auf bestimmte Aufgaben nicht zugreifen.

  • Wenn Sie ein Zertifikat erwerben, erhalten Sie Zugriff auf alle Kursmaterialien, einschließlich bewerteter Aufgaben. Nach Abschluss des Kurses wird Ihr elektronisches Zertifikat zu Ihrer Seite „Errungenschaften“ hinzugefügt – von dort können Sie Ihr Zertifikat ausdrucken oder es zu Ihrem LinkedIn Profil hinzufügen. Wenn Sie nur lesen und den Inhalt des Kurses anzeigen möchten, können Sie kostenlos als Gast an dem Kurs teilnehmen.

Haben Sie weitere Fragen? Besuchen Sie das Hilfe-Center für Teiln..