Informações sobre o curso
4.9
287 classificações
34 avaliações
100% online

100% online

Comece imediatamente e aprenda em seu próprio cronograma.
Prazos flexíveis

Prazos flexíveis

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

Aprox. 23 horas para completar

Sugerido: 5 hours/week...
Idiomas disponíveis

Russo

Legendas: Russo...
100% online

100% online

Comece imediatamente e aprenda em seu próprio cronograma.
Prazos flexíveis

Prazos flexíveis

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

Aprox. 23 horas para completar

Sugerido: 5 hours/week...
Idiomas disponíveis

Russo

Legendas: Russo...

Programa - O que você aprenderá com este curso

Semana
1
Horas para completar
3 horas para concluir

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

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

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

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

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

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

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

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

Instrutores

Avatar

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

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

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

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

Sobre Moscow Institute of Physics and Technology

Московский физико-технический институт (неофициально известный как МФТИ или Физтех) является одним из самых престижных в мире учебных и научно-исследовательских институтов. Он готовит высококвалифицированных специалистов в области теоретической и прикладной физики, прикладной математики, информатики, биотехнологии и смежных дисциплин. Физтех был основан в 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.