このコースについて
11,402 最近の表示

100%オンライン

自分のスケジュールですぐに学習を始めてください。

柔軟性のある期限

スケジュールに従って期限をリセットします。

約22時間で修了

推奨:5 hours/week...

ロシア語

字幕:ロシア語

100%オンライン

自分のスケジュールですぐに学習を始めてください。

柔軟性のある期限

スケジュールに従って期限をリセットします。

約22時間で修了

推奨:5 hours/week...

ロシア語

字幕:ロシア語

シラバス - 本コースの学習内容

1
3時間で修了

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

В первую неделю курса мы познакомимся с понятием графа, научимся отличать граф от его изображения, поговорим о разных видах графов. Мы вспомним, с чего началась теория графов, научимся представлять в виде графа структуру интернета. Мы обсудим такие важные понятия, как маршруты в графах, степень вершины, связность, а также начнем говорить про важный класс графов - деревья.

...
17件のビデオ (合計104分), 6 readings, 1 quiz
17件のビデオ
МФТИ1 分
Примеры графов. Граф и его изображение10 分
Ориентированные графы4 分
Кёнигсбергские мосты. Мультиграфы5 分
Граф интернета. Псевдографы4 分
Определение графа5 分
Маршруты в графах10 分
Связность, подграфы7 分
Степень вершины3 分
Деревья, эквивалентные определения дерева5 分
Знакомства6 分
Число мультиграфов4 分
Путь в графе5 分
Перенумерация цикла8 分
Последовательности степеней9 分
Замкнутый маршрут9 分
6件の学習用教材
МФТИ10 分
Теоретический материал к семинару10 分
Задачи к семинару10 分
Решение задач10 分
Дополнительные задачи к неделе 110 分
Конспект лекции 110 分
1の練習問題
Задание к неделе 118 分
2
3時間で修了

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

На этой неделе мы научимся определять деревья четырьмя различными способами, и поговорим о том, как правильно раскрашивать географические карты. Мы вспомним знаменитую теорему о четырех красках, а также критерий Куратовского о том, как определить, можно ли нарисовать данный граф на плоскости без пересечений ребер. В последней части лекции мы обсудим формулу Эйлера для планарных графов и некоторые из её множественных следствий.

...
17件のビデオ (合計147分), 4 readings, 1 quiz
17件のビデオ
Доказательство второй импликации13 分
Доказательство третьей импликации9 分
Доказательство четвертой импликации6 分
Планарность. Гипотеза о четырех красках10 分
Примеры непланарных графов5 分
Критерий Куратовского7 分
Плоские графы, грани и теорема Жордана8 分
Формула Эйлера10 分
Следствие для числа ребер13 分
Хроматическое число планарных графов8 分
Доказательство оценки хроматического числа13 分
Минимальное число ребер2 分
Число пересечений в полном графе2 分
Число ребер в планарном графе и формула Эйлера4 分
Характеризация двудольных графов15 分
Двудольные планарные графы9 分
4件の学習用教材
Теоретический материал к семинару10 分
Задачи к семинару10 分
Решения задач10 分
Дополнительные задачи к неделе 210 分
1の練習問題
Задание к неделе 218 分
3
3時間で修了

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

На этой неделе мы перечислим все деревья. Для этого нам потребуется перенять опыт древних по подсчету баранов (или козлов). Не остановившись на этом, перечислим и все леса и унициклические графы. Затем мы вернемся к задаче о Кёнигсбергских мостах и получим полное решение этого вопроса.

...
15件のビデオ (合計115分), 4 readings, 1 quiz
15件のビデオ
Доказательство формулы. Кодирование деревьев5 分
Построение кодов Прюфера5 分
Взаимно однозначное соответствие кодов и деревьев. Декодирование8 分
Формула для числа унициклических графов6 分
Доказательство формулы14 分
Эйлеровы циклы5 分
Критерий эйлеровости3 分
Первая часть доказательства критерия11 分
Вторая часть доказательства критерия12 分
Центр дерева6 分
Деревья с заданной последовательностью степеней11 分
Код Прюфера из различных чисел3 分
Число неизоморфных деревьев6 分
Ориентация графа4 分
4件の学習用教材
Теоретический материал к семинару10 分
Задачи к семинару10 分
Решения задач10 分
Дополнительные задачи к неделе 310 分
1の練習問題
Задание к неделе 316 分
4
4時間で修了

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

На этой неделе мы продолжим обсуждать циклы, проходящие через весь граф. На этот раз мы поговорим про циклы, проходящие через все вершины графа. В отличие от эйлеровых циклов, здесь нет необходимого и достаточного критерия наличия такого цикла. Есть только достаточные условия, и мы обсудим два таких условия, довольно разных по своей природе. По пути мы обсудим такие важные характеристики графа, как независимое число и k-связность. В качестве дополнения, мы расскажем об одном очень интересном классе графов, для которого один из критериев работает, а другой - нет.

...
21件のビデオ (合計166分), 6 readings, 1 quiz
21件のビデオ
Множества соседей концов максимального пути9 分
Завершение доказательства теоремы Дирака9 分
Независимые множества5 分
Вершинная связность. Критерий Хватала4 分
Доказательство. В графе есть циклы6 分
Подграф без максимального цикла5 分
Соседи связной компоненты5 分
Соседи компоненты и максимальный цикл7 分
Число соседей больше связности7 分
Завершение доказательства9 分
Число гамильтоновых циклов в полном двудольном графе3 分
Число независимости, связность10 分
Непересекающиеся гамильтоновы циклы12 分
Сравнение двух признаков гамильтоновости на конкретном графе. Определение графа6 分
Работает ли признак Дирака?6 分
Признак Хватала. Оценка связности через общих соседей6 分
Число общих соседей8 分
Примеры независимых множеств, теорема о числе независимости11 分
Доказательство теоремы10 分
Связь с теорией кодирования6 分
6件の学習用教材
Пример гамильтонова графа10 分
Теоретический материал к семинару10 分
Задачи к семинару10 分
Комментарий к лекции10 分
Решения задач10 分
Дополнительные задачи к неделе 410 分
1の練習問題
Задание к неделе 418 分
5
3時間で修了

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

На этой неделе мы поговорим про паросочетания. Мы узнаем, что нужно, чтобы переженить всех юношей и девушек по любви. Мы обсудим две классических теоремы, у одной из которых очень изящное доказательство по индукции, а у другой не менее изящное доказательство алгоритмическое. А на семинаре мы узнаем, что эти две теоремы эквивалентны.

...
15件のビデオ (合計150分), 4 readings, 1 quiz
15件のビデオ
Необходимое условие существования паросочетания. Теорема Холла8 分
Доказательство теоремы Холла. Два случая6 分
Разбор случая 110 分
Разбор случая 212 分
Вершинное покрытие, теорема Кёнига6 分
Первая часть доказательства. Чередующиеся цепи12 分
Вторая часть доказательства. Разбиение множества вершин8 分
Третья часть доказательства. Построение вершинного покрытия10 分
Завершение доказательства. Вершинное покрытие работает10 分
Теорема Холла из теоремы Кёнига9 分
Теорема Кёнига из теоремы Холла11 分
Паросочетания и степени вершин10 分
Паросочетания в деревьях5 分
К-регулярный двудольный граф15 分
4件の学習用教材
Теоретический материал к семинару10 分
Задачи к семинару10 分
Решения задач10 分
Дополнительные задачи к неделе 510 分
1の練習問題
Задание к неделе 518 分
6
3時間で修了

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

На этой неделе мы начнем разговор про экстремальную теорию графов, которая ставит вопросы про то, с какого момента графы начинают обладать тем или иным свойством. В частности, мы выясним, сколько ребер должен иметь граф, чтобы он гарантированно содержал треугольник. В конце лекции мы узнаем, что графы на плоскости в экстремальных задачах ведут себя несколько по-другому, нежели графы абстрактные.

...
13件のビデオ (合計123分), 4 readings, 1 quiz
13件のビデオ
Теорема Турана6 分
Доказательство теоремы Турана16 分
Пример графа, на котором оценка Турана достигается7 分
Теорема Турана в терминах кликового числа7 分
Задача про графы на плоскости9 分
Решение задачи15 分
Двудольный подграф13 分
Вершинное покрытие для графа без треугольников4 分
Граф без четных циклов10 分
Хроматическое число и число независимости6 分
Хроматическое число и максимальная степень7 分
Хроматическое число графа и его дополнения11 分
4件の学習用教材
Теоретический материал к семинару10 分
Задачи к семинару10 分
Решения задач10 分
Дополнительные задачи к неделе 610 分
1の練習問題
Задание к неделе 618 分
7
3時間で修了

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

На заключительной лекции мы поговорим про теорию Рамсея. Вы узнаете много нового о знакомствах, о том, сколько раз можно в одном доказательстве применить принцип Дирихле и о том, что доказать существование графа и привести пример такого графа - это зачастую совсем разные по сложности задачи.

...
20件のビデオ (合計148分), 4 readings, 1 quiz
20件のビデオ
Начало доказательства. Применение принципа Дирихле4 分
Завершение доказательства6 分
Формулировка в терминах независимых множеств и раскрасок5 分
Пяти вершин недостаточно2 分
Определение чисел Рамсея4 分
Значения R(s,t) для малых s13 分
Верхняя оценка чисел Рамсея с помощью рекурсии2 分
Доказательство. Принцип Дирихле7 分
Завершение доказательства10 分
Численные верхние оценки чисел Рамсея12 分
Нижняя оценка числа Рамсея. Что требуется доказать?3 分
Подсчет графов с большими полными подграфами12 分
Вычисления. Завершение доказательства теоремы4 分
Обсуждение нижних оценок4 分
Число Рамсея для звезды5 分
Число Рамсея для дерева и полного графа13 分
Раскраска плоскости6 分
Монотонные последовательности9 分
Пути или звезды13 分
4件の学習用教材
Теоретический материал к семинару10 分
Задачи к семинару10 分
Решение задач10 分
Дополнительные задачи к неделе 710 分
1の練習問題
Задание к неделе 714 分
8
18分で修了

Экзамен

Заключительная работа по материалу всего курса

...
1 quiz
1の練習問題
Экзамен. Один граф18 分
4.9
41件のレビューChevron Right

20%

コースが具体的なキャリアアップにつながった

25%

昇給や昇進につながった

Теория графов からの人気レビュー

by DDOct 30th 2016

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

by DMNov 8th 2016

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

講師

Avatar

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

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

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

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

モスクワ物理工科大学(Moscow Institute of Physics and Technology)について

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

よくある質問

  • 修了証に登録すると、すべてのビデオ、テスト、およびプログラミング課題(該当する場合)にアクセスできます。ピアレビュー課題は、セッションが開始してからのみ、提出およびレビューできます。購入せずにコースを検討することを選択する場合、特定の課題にアクセスすることはできません。

  • 修了証を購入する際、コースのすべての教材(採点課題を含む)にアクセスできます。コースを完了すると、電子修了証が成果のページに追加されます。そこから修了証を印刷したり、LinkedInのプロフィールに追加したりできます。コースの内容の閲覧のみを希望する場合は、無料でコースを聴講できます。

さらに質問がある場合は、受講者向けヘルプセンターにアクセスしてください。