Случайные графы от Coursera

От: Coursera

1,5 месяца изучения теории случайных графов от МФТИ. Курс содержит 6 модулей. Занятия 1–2 часа в неделю. Для освоения материала достаточно математики школьного уровня, базовых знаний комбинаторики и теории вероятностей. Студенты освоят две модели случайного графа, теорему о пороговой вероятности, вероятностный метод, хроматическое число, алгоритмы и малые подграфы. Эксперт даст обратную связь по заданиям. После сдачи экзамена выдаётся сертификат.

Сводка

Цена
0₽
Рассрочка
от 200₽
Статус
Идет набор
Длительность
28 дней
Язык
ru

Описание курса

Решать комбинаторные и алгоритмические задачи на случайных графах

- Воспринимать сложные системы как "случайные графы" – устройство интернета, социальные сети (Фейсбука, Вконтакте), биологические, межбанковские сети
- Разбираться в инструментарии теории графов

О школе

Coursera
Отзывы 0
Информация
Компания основана в 2012 году. Официальный сайт https://ru.coursera.org. Мы собрали и проверили более 17 отзывов об онлайн курсах Coursera.

Программа курса

Две модели случайного графа
Случайный граф Эрдеша-Реньи: биномиальная модель и равномерная модель. Свойства случайного графа. Свойство связности. Пороговая вероятность для свойства связности. Пороговая вероятность для свойства связности. Возникновение гигантской компоненты в случайном графе.
Теорема о пороговой вероятности для свойства связности
Неравенство Маркова и Чебышева. Доказательство теоремы о пороговой вероятности для свойства связности случайного графа.
Вероятностный метод
Хроматическое число, число независимости и кликовое число. Обхват графа. Теорема о существовании графа с большим обхватом и большим хроматическим числом.
Хроматическое число случайного графа
Оценки хроматического числа случайного графа G(n,p) при различных p=p(n).
Алгоритмы на случайном графе
Жадный алгоритм раскраски. Жадное хроматическое число, жадное число независимости и жадное кликовое число. Теорема о жадном хроматическом числе и жадном числе независимости случайного графа.
Итоговый тест
Заключительный экзамен, содержащий задачи по всем пройденным темам

Отзывы

Еще не добавили ни одного отзыва