Informações sobre o curso
10,018 visualizações recentes

100% online

Comece imediatamente e aprenda em seu próprio cronograma.

Prazos flexíveis

Redefinir os prazos de acordo com sua programação.

Aprox. 22 horas para completar

Sugerido: 5 hours/week...

Russo

Legendas: Russo

100% online

Comece imediatamente e aprenda em seu próprio cronograma.

Prazos flexíveis

Redefinir os prazos de acordo com sua programação.

Aprox. 22 horas para completar

Sugerido: 5 hours/week...

Russo

Legendas: Russo

Programa - O que você aprenderá com este curso

Semana
1
3 horas para concluir

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

В первую неделю курса мы познакомимся с понятием графа, научимся отличать граф от его изображения, поговорим о разных видах графов. Мы вспомним, с чего началась теория графов, научимся представлять в виде графа структуру интернета. Мы обсудим такие важные понятия, как маршруты в графах, степень вершины, связность, а также начнем говорить про важный класс графов - деревья....
17 vídeos (total de (Total 104 mín.) min), 6 leituras, 1 teste
17 videos
МФТИ1min
Примеры графов. Граф и его изображение10min
Ориентированные графы4min
Кёнигсбергские мосты. Мультиграфы5min
Граф интернета. Псевдографы4min
Определение графа5min
Маршруты в графах10min
Связность, подграфы7min
Степень вершины3min
Деревья, эквивалентные определения дерева5min
Знакомства6min
Число мультиграфов4min
Путь в графе5min
Перенумерация цикла8min
Последовательности степеней9min
Замкнутый маршрут9min
6 leituras
МФТИ10min
Теоретический материал к семинару10min
Задачи к семинару10min
Решение задач10min
Дополнительные задачи к неделе 110min
Конспект лекции 110min
1 exercício prático
Задание к неделе 118min
Semana
2
3 horas para concluir

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

На этой неделе мы научимся определять деревья четырьмя различными способами, и поговорим о том, как правильно раскрашивать географические карты. Мы вспомним знаменитую теорему о четырех красках, а также критерий Куратовского о том, как определить, можно ли нарисовать данный граф на плоскости без пересечений ребер. В последней части лекции мы обсудим формулу Эйлера для планарных графов и некоторые из её множественных следствий....
17 vídeos (total de (Total 147 mín.) min), 4 leituras, 1 teste
17 videos
Доказательство второй импликации13min
Доказательство третьей импликации9min
Доказательство четвертой импликации6min
Планарность. Гипотеза о четырех красках10min
Примеры непланарных графов5min
Критерий Куратовского7min
Плоские графы, грани и теорема Жордана8min
Формула Эйлера10min
Следствие для числа ребер13min
Хроматическое число планарных графов8min
Доказательство оценки хроматического числа13min
Минимальное число ребер2min
Число пересечений в полном графе2min
Число ребер в планарном графе и формула Эйлера4min
Характеризация двудольных графов15min
Двудольные планарные графы9min
4 leituras
Теоретический материал к семинару10min
Задачи к семинару10min
Решения задач10min
Дополнительные задачи к неделе 210min
1 exercício prático
Задание к неделе 218min
Semana
3
3 horas para concluir

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

На этой неделе мы перечислим все деревья. Для этого нам потребуется перенять опыт древних по подсчету баранов (или козлов). Не остановившись на этом, перечислим и все леса и унициклические графы. Затем мы вернемся к задаче о Кёнигсбергских мостах и получим полное решение этого вопроса....
15 vídeos (total de (Total 115 mín.) min), 4 leituras, 1 teste
15 videos
Доказательство формулы. Кодирование деревьев5min
Построение кодов Прюфера5min
Взаимно однозначное соответствие кодов и деревьев. Декодирование8min
Формула для числа унициклических графов6min
Доказательство формулы14min
Эйлеровы циклы5min
Критерий эйлеровости3min
Первая часть доказательства критерия11min
Вторая часть доказательства критерия12min
Центр дерева6min
Деревья с заданной последовательностью степеней11min
Код Прюфера из различных чисел3min
Число неизоморфных деревьев6min
Ориентация графа4min
4 leituras
Теоретический материал к семинару10min
Задачи к семинару10min
Решения задач10min
Дополнительные задачи к неделе 310min
1 exercício prático
Задание к неделе 316min
Semana
4
4 horas para concluir

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

На этой неделе мы продолжим обсуждать циклы, проходящие через весь граф. На этот раз мы поговорим про циклы, проходящие через все вершины графа. В отличие от эйлеровых циклов, здесь нет необходимого и достаточного критерия наличия такого цикла. Есть только достаточные условия, и мы обсудим два таких условия, довольно разных по своей природе. По пути мы обсудим такие важные характеристики графа, как независимое число и k-связность. В качестве дополнения, мы расскажем об одном очень интересном классе графов, для которого один из критериев работает, а другой - нет....
21 vídeos (total de (Total 166 mín.) min), 6 leituras, 1 teste
21 videos
Множества соседей концов максимального пути9min
Завершение доказательства теоремы Дирака9min
Независимые множества5min
Вершинная связность. Критерий Хватала4min
Доказательство. В графе есть циклы6min
Подграф без максимального цикла5min
Соседи связной компоненты5min
Соседи компоненты и максимальный цикл7min
Число соседей больше связности7min
Завершение доказательства9min
Число гамильтоновых циклов в полном двудольном графе3min
Число независимости, связность10min
Непересекающиеся гамильтоновы циклы12min
Сравнение двух признаков гамильтоновости на конкретном графе. Определение графа6min
Работает ли признак Дирака?6min
Признак Хватала. Оценка связности через общих соседей6min
Число общих соседей8min
Примеры независимых множеств, теорема о числе независимости11min
Доказательство теоремы10min
Связь с теорией кодирования6min
6 leituras
Пример гамильтонова графа10min
Теоретический материал к семинару10min
Задачи к семинару10min
Комментарий к лекции10min
Решения задач10min
Дополнительные задачи к неделе 410min
1 exercício prático
Задание к неделе 418min
Semana
5
3 horas para concluir

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

На этой неделе мы поговорим про паросочетания. Мы узнаем, что нужно, чтобы переженить всех юношей и девушек по любви. Мы обсудим две классических теоремы, у одной из которых очень изящное доказательство по индукции, а у другой не менее изящное доказательство алгоритмическое. А на семинаре мы узнаем, что эти две теоремы эквивалентны....
15 vídeos (total de (Total 150 mín.) min), 4 leituras, 1 teste
15 videos
Необходимое условие существования паросочетания. Теорема Холла8min
Доказательство теоремы Холла. Два случая6min
Разбор случая 110min
Разбор случая 212min
Вершинное покрытие, теорема Кёнига6min
Первая часть доказательства. Чередующиеся цепи12min
Вторая часть доказательства. Разбиение множества вершин8min
Третья часть доказательства. Построение вершинного покрытия10min
Завершение доказательства. Вершинное покрытие работает10min
Теорема Холла из теоремы Кёнига9min
Теорема Кёнига из теоремы Холла11min
Паросочетания и степени вершин10min
Паросочетания в деревьях5min
К-регулярный двудольный граф15min
4 leituras
Теоретический материал к семинару10min
Задачи к семинару10min
Решения задач10min
Дополнительные задачи к неделе 510min
1 exercício prático
Задание к неделе 518min
Semana
6
3 horas para concluir

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

На этой неделе мы начнем разговор про экстремальную теорию графов, которая ставит вопросы про то, с какого момента графы начинают обладать тем или иным свойством. В частности, мы выясним, сколько ребер должен иметь граф, чтобы он гарантированно содержал треугольник. В конце лекции мы узнаем, что графы на плоскости в экстремальных задачах ведут себя несколько по-другому, нежели графы абстрактные. ...
13 vídeos (total de (Total 123 mín.) min), 4 leituras, 1 teste
13 videos
Теорема Турана6min
Доказательство теоремы Турана16min
Пример графа, на котором оценка Турана достигается7min
Теорема Турана в терминах кликового числа7min
Задача про графы на плоскости9min
Решение задачи15min
Двудольный подграф13min
Вершинное покрытие для графа без треугольников4min
Граф без четных циклов10min
Хроматическое число и число независимости6min
Хроматическое число и максимальная степень7min
Хроматическое число графа и его дополнения11min
4 leituras
Теоретический материал к семинару10min
Задачи к семинару10min
Решения задач10min
Дополнительные задачи к неделе 610min
1 exercício prático
Задание к неделе 618min
Semana
7
3 horas para concluir

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

На заключительной лекции мы поговорим про теорию Рамсея. Вы узнаете много нового о знакомствах, о том, сколько раз можно в одном доказательстве применить принцип Дирихле и о том, что доказать существование графа и привести пример такого графа - это зачастую совсем разные по сложности задачи....
20 vídeos (total de (Total 148 mín.) min), 4 leituras, 1 teste
20 videos
Начало доказательства. Применение принципа Дирихле4min
Завершение доказательства6min
Формулировка в терминах независимых множеств и раскрасок5min
Пяти вершин недостаточно2min
Определение чисел Рамсея4min
Значения R(s,t) для малых s13min
Верхняя оценка чисел Рамсея с помощью рекурсии2min
Доказательство. Принцип Дирихле7min
Завершение доказательства10min
Численные верхние оценки чисел Рамсея12min
Нижняя оценка числа Рамсея. Что требуется доказать?3min
Подсчет графов с большими полными подграфами12min
Вычисления. Завершение доказательства теоремы4min
Обсуждение нижних оценок4min
Число Рамсея для звезды5min
Число Рамсея для дерева и полного графа13min
Раскраска плоскости6min
Монотонные последовательности9min
Пути или звезды13min
4 leituras
Теоретический материал к семинару10min
Задачи к семинару10min
Решение задач10min
Дополнительные задачи к неделе 710min
1 exercício prático
Задание к неделе 714min
Semana
8
18 minutos para concluir

Экзамен

Заключительная работа по материалу всего курса...
1 teste
1 exercício prático
Экзамен. Один граф18min
4.9
41 avaliaçõesChevron Right

20%

consegui um benefício significativo de carreira com este curso

25%

recebi um aumento ou promoção

Melhores avaliações

por DDOct 30th 2016

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

por DMNov 8th 2016

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

Instrutores

Avatar

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

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

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

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

Sobre Instituto de Física e Tecnologia de Moscou

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

Perguntas Frequentes – FAQ

  • Ao se inscrever para um Certificado, você terá acesso a todos os vídeos, testes e tarefas de programação (se aplicável). Tarefas avaliadas pelos colegas apenas podem ser enviadas e avaliadas após o início da sessão. Caso escolha explorar o curso sem adquiri-lo, talvez você não consiga acessar certas tarefas.

  • Quando você adquire o Certificado, ganha acesso a todo o material do curso, incluindo avaliações com nota atribuída. Após concluir o curso, seu Certificado eletrônico será adicionado à sua página de Participações e você poderá imprimi-lo ou adicioná-lo ao seu perfil no LinkedIn. Se quiser apenas ler e assistir o conteúdo do curso, você poderá frequentá-lo como ouvinte sem custo.

Mais dúvidas? Visite o Central de Ajuda ao Aprendiz.