Acerca de este Curso
4.9
63 calificaciones
7 revisiones
100 % en línea

100 % en línea

Comienza de inmediato y aprende a tu propio ritmo.
Fechas límite flexibles

Fechas límite flexibles

Restablece las fechas límite en función de tus horarios.
Horas para completar

Aprox. 23 horas para completar

Sugerido: 6 недель исследования, 1-2 часов / неделю...
Idiomas disponibles

Ruso (Russian)

Subtítulos: Ruso (Russian)
100 % en línea

100 % en línea

Comienza de inmediato y aprende a tu propio ritmo.
Fechas límite flexibles

Fechas límite flexibles

Restablece las fechas límite en función de tus horarios.
Horas para completar

Aprox. 23 horas para completar

Sugerido: 6 недель исследования, 1-2 часов / неделю...
Idiomas disponibles

Ruso (Russian)

Subtítulos: Ruso (Russian)

Programa - Qué aprenderás en este curso

Semana
1
Horas para completar
3 horas para completar

Две модели случайного графа

Случайный граф Эрдеша-Реньи: биномиальная модель и равномерная модель. Свойства случайного графа. Свойство связности. Пороговая вероятность для свойства связности. Пороговая вероятность для свойства связности. Возникновение гигантской компоненты в случайном графе....
Reading
15 videos (Total 94 minutos), 4 readings, 2 quizzes
Video15 videos
Биномиальная модель случайного графа12m
Связность случайного графа на четырех вершинах3m
Эволюция случайного графа6m
Равномерная модель случайного графа3m
МФТИ1m
Пороговая вероятность для свойства связности: формулировка теоремы14m
Нижняя оценка вероятности связности: формулировка теоремы12m
Теорема о появлении гигантской компоненты в случайном графе10m
Задача о монотонности вероятности4m
Задача о промежуточных значениях вероятности5m
Задача о дополнительных ребрах3m
Задача об одном ребре2m
Задача о дереве4m
Задача о простом цикле3m
Reading4 lecturas
Комментарий к лекции10m
МФТИ10m
Дополнительные задачи10m
Конспект лекции10m
Quiz2 ejercicios de práctica
Задачи к семинару 112m
Итоговые задания по неделе 120m
Semana
2
Horas para completar
3 horas para completar

Теорема о пороговой вероятности для свойства связности

Неравенство Маркова и Чебышева. Доказательство теоремы о пороговой вероятности для свойства связности случайного графа....
Reading
16 videos (Total 132 minutos), 3 readings, 2 quizzes
Video16 videos
Напоминание теоремы о пороговой вероятности для свойства связности2m
Применение неравенства Чебышева9m
Оценивание математического ожидания10m
Оценивание дисперсии10m
Вероятность существования изолированной вершины5m
Разложение случайного графа на компоненты связности2m
Оценивание математического ожидания числа компонент связности15m
Представление оценки в виде суммы двух слагаемых5m
Предел первого слагаемого10m
Предел второго слагаемого9m
Задача о количестве изолированных вершин в случайном двудольном графе8m
Задача о существовании изолированной вершины в случайном двудольном графе17m
Задача об одной изолированной вершине4m
Задача о количестве вершин степени 14m
Задача о связности случайного графа при большой вероятности проведения ребра8m
Reading3 lecturas
Комментарий к задаче о существовании изолированной вершины в случайном двудольном графе10m
Дополнительные задачи10m
Конспект лекции10m
Quiz2 ejercicios de práctica
Задачи к семинару 210m
Итоговые задания по неделе 218m
Semana
3
Horas para completar
3 horas para completar

Вероятностный метод

Хроматическое число, число независимости и кликовое число. Обхват графа. Теорема о существовании графа с большим обхватом и большим хроматическим числом....
Reading
15 videos (Total 102 minutos), 3 readings, 2 quizzes
Video15 videos
Обхват графа2m
Теорема о графе с большим обхватом и большим хроматическим числом: формулировка теоремы и идея доказательства5m
Введение случайности5m
Оценка математического ожидания числа циклов15m
Применение неравенства Маркова для оценивания обхвата3m
Оценка математического ожидания числа независимых множеств7m
Применение неравенства Маркова для оценивания числа независимости6m
Существование графа с большим хроматическим числом и малым количеством циклов1m
Модификация графа6m
Задача о количестве 4-циклов в случайном двудольном графе15m
Задача об отсутствии циклов в равномерной модели1m
Задача о хроматическом числе случайного графа в равномерной модели4m
Задача об оценке числа независимости7m
Задача о хроматическом числе случайного графа с 5 ребрами7m
Reading3 lecturas
Замечание: существование длинных циклов10m
Дополнительные задачи10m
Конспект лекции10m
Quiz2 ejercicios de práctica
Задачи к семинару 310m
Итоговые задания по неделе 318m
Semana
4
Horas para completar
3 horas para completar

Хроматическое число случайного графа

Оценки хроматического числа случайного графа G(n,p) при различных p=p(n)....
Reading
14 videos (Total 113 minutos), 3 readings, 2 quizzes
Video14 videos
Доказательство теоремы11m
Хроматическое число случайного графа без ребер5m
Хроматическое число сильно разреженного случайного графа4m
Доказательство того, что в случайном разреженном графе отсутствуют циклы6m
Хроматическое число случайного графа G(n,c/n)10m
Хроматическое число слабо разреженного графа9m
Точная асимптотика хроматического числа G(n,0.5)5m
Идея доказательства теоремы Боллобаша7m
Алгоритм покраски10m
Задача о хроматическом числе и обхвате случайного двудольного графа10m
Задача о хроматическом числа графа G(6,5)5m
Задача о древесных компонентах случайного графа14m
Задача об оценке хроматического числа случайного графа специального вида3m
Reading3 lecturas
Комментарий к лекции: тройка вместо двойки10m
Дополнительные задачи10m
Конспект лекции10m
Quiz2 ejercicios de práctica
Задачи к семинару 48m
Итоговые задания по неделе 414m

Instructores

Avatar

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

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

Максим Жуковский

преподаватель
кафедра дискретной математики МФТИ

Acerca de Moscow Institute of Physics and Technology

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

Preguntas Frecuentes

  • Una vez que te inscribes para obtener un Certificado, tendrás acceso a todos los videos, cuestionarios y tareas de programación (si corresponde). Las tareas calificadas por compañeros solo pueden enviarse y revisarse una vez que haya comenzado tu sesión. Si eliges explorar el curso sin comprarlo, es posible que no puedas acceder a determinadas tareas.

  • Cuando compras un Certificado, obtienes acceso a todos los materiales del curso, incluidas las tareas calificadas. Una vez que completes el curso, se añadirá tu Certificado electrónico a la página Logros. Desde allí, puedes imprimir tu Certificado o añadirlo a tu perfil de LinkedIn. Si solo quieres leer y visualizar el contenido del curso, puedes participar del curso como oyente sin costo.

¿Tienes más preguntas? Visita el Centro de Ayuda al Alumno.