Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически во время прогулок. Доказать или опровергнуть возможность существования такого маршрута никто не мог до 1736 года, когда выдающийся математик Леонард Эйлер не написал письмо своему другу с решением. Ответ был «нельзя». Так и родилась теория графов. Но что будет, если процесс, который описывает граф – случаен?
Случайные графы
Instituto de Física e Tecnologia de MoscouInformações sobre o curso
2,372 visualizações recentes
Certificados compartilháveis
Tenha o certificado após a conclusão
100% on-line
Comece imediatamente e aprenda em seu próprio cronograma.
Prazos flexíveis
Redefinir os prazos de acordo com sua programação.
Aprox. 21 horas para completar
Russo
Legendas: Russo
Certificados compartilháveis
Tenha o certificado após a conclusão
100% on-line
Comece imediatamente e aprenda em seu próprio cronograma.
Prazos flexíveis
Redefinir os prazos de acordo com sua programação.
Aprox. 21 horas para completar
Russo
Legendas: Russo
oferecido por
Instituto de Física e Tecnologia de Moscou
Московский физико-технический институт (Физтех) является одним из ведущих вузов страны и входит в основные рейтинги лучших университетов мира. Институт обладает не только богатой историей – основателями и профессорами института были Нобелевские лауреаты Пётр Капица, Лев Ландау и Николай Семенов – но и большой научно-исследовательской базой.
Programa - O que você aprenderá com este curso
3 horas para concluir
Две модели случайного графа
Случайный граф Эрдеша-Реньи: биномиальная модель и равномерная модель. Свойства случайного графа. Свойство связности. Пороговая вероятность для свойства связности. Пороговая вероятность для свойства связности. Возникновение гигантской компоненты в случайном графе.
3 horas para concluir
15 vídeos (Total 94 mín.), 4 leituras, 2 testes
15 videos
МФТИ1min
История зарождения понятия случайного графа4min
Биномиальная модель случайного графа12min
Связность случайного графа на четырех вершинах3min
Эволюция случайного графа6min
Равномерная модель случайного графа3min
Пороговая вероятность для свойства связности: формулировка теоремы14min
Нижняя оценка вероятности связности: формулировка теоремы12min
Теорема о появлении гигантской компоненты в случайном графе10min
Задача о монотонности вероятности4min
Задача о промежуточных значениях вероятности5min
Задача о дополнительных ребрах3min
Задача об одном ребре2min
Задача о дереве4min
Задача о простом цикле3min
4 leituras
МФТИ10min
Комментарий к лекции10min
Дополнительные задачи10min
Конспект лекции10min
2 exercícios práticos
Задачи к семинару 130min
Итоговые задания по неделе 130min
4 horas para concluir
Теорема о пороговой вероятности для свойства связности
Неравенство Маркова и Чебышева. Доказательство теоремы о пороговой вероятности для свойства связности случайного графа.
4 horas para concluir
16 vídeos (Total 132 mín.), 3 leituras, 2 testes
16 videos
Напоминание теоремы о пороговой вероятности для свойства связности2min
Применение неравенства Чебышева9min
Оценивание математического ожидания10min
Оценивание дисперсии10min
Вероятность существования изолированной вершины5min
Разложение случайного графа на компоненты связности2min
Оценивание математического ожидания числа компонент связности15min
Представление оценки в виде суммы двух слагаемых5min
Предел первого слагаемого10min
Предел второго слагаемого9min
Задача о количестве изолированных вершин в случайном двудольном графе8min
Задача о существовании изолированной вершины в случайном двудольном графе17min
Задача об одной изолированной вершине4min
Задача о количестве вершин степени 14min
Задача о связности случайного графа при большой вероятности проведения ребра8min
3 leituras
Комментарий к задаче о существовании изолированной вершины в случайном двудольном графе10min
Дополнительные задачи10min
Конспект лекции10min
2 exercícios práticos
Задачи к семинару 230min
Итоговые задания по неделе 230min
3 horas para concluir
Вероятностный метод
Хроматическое число, число независимости и кликовое число. Обхват графа. Теорема о существовании графа с большим обхватом и большим хроматическим числом.
3 horas para concluir
15 vídeos (Total 102 mín.), 3 leituras, 2 testes
15 videos
Обхват графа2min
Теорема о графе с большим обхватом и большим хроматическим числом: формулировка теоремы и идея доказательства5min
Введение случайности5min
Оценка математического ожидания числа циклов15min
Применение неравенства Маркова для оценивания обхвата3min
Оценка математического ожидания числа независимых множеств7min
Применение неравенства Маркова для оценивания числа независимости6min
Существование графа с большим хроматическим числом и малым количеством циклов1min
Модификация графа6min
Задача о количестве 4-циклов в случайном двудольном графе15min
Задача об отсутствии циклов в равномерной модели1min
Задача о хроматическом числе случайного графа в равномерной модели4min
Задача об оценке числа независимости7min
Задача о хроматическом числе случайного графа с 5 ребрами7min
3 leituras
Замечание: существование длинных циклов10min
Дополнительные задачи10min
Конспект лекции10min
2 exercícios práticos
Задачи к семинару 330min
Итоговые задания по неделе 330min
3 horas para concluir
Хроматическое число случайного графа
Оценки хроматического числа случайного графа G(n,p) при различных p=p(n).
3 horas para concluir
14 vídeos (Total 113 mín.), 3 leituras, 2 testes
14 videos
Доказательство теоремы11min
Хроматическое число случайного графа без ребер5min
Хроматическое число сильно разреженного случайного графа4min
Доказательство того, что в случайном разреженном графе отсутствуют циклы6min
Хроматическое число случайного графа G(n,c/n)10min
Хроматическое число слабо разреженного графа9min
Точная асимптотика хроматического числа G(n,0.5)5min
Идея доказательства теоремы Боллобаша7min
Алгоритм покраски10min
Задача о хроматическом числе и обхвате случайного двудольного графа10min
Задача о хроматическом числа графа G(6,5)5min
Задача о древесных компонентах случайного графа14min
Задача об оценке хроматического числа случайного графа специального вида3min
3 leituras
Комментарий к лекции: тройка вместо двойки10min
Дополнительные задачи10min
Конспект лекции10min
2 exercícios práticos
Задачи к семинару 430min
Итоговые задания по неделе 430min
Avaliações
Principais avaliações do СЛУЧАЙНЫЕ ГРАФЫ
por VT17 de Out de 2016
Прошел курс исключительно из за лектора. Даже не знаю, пригодится ли мне на практике, но очень захватывающе изложено.
Perguntas Frequentes – FAQ
Quando terei acesso às palestras e às tarefas?
O que recebo ao adquirir o Certificado?
Is financial aid available?
Mais dúvidas? Visite o Central de Ajuda ao Aprendiz.
