Chevron Left
Back to Теория графов

Теория графов, Moscow Institute of Physics and Technology

4.9
295 ratings
35 reviews

About this Course

Среди жителей Кёнигсберга была распространена такая практическая головоломка: можно ли пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды? В 1736 году выдающийся математик Леонард Эйлер заинтересовался задачей и в письме другу привел строгое доказательство того, что сделать это невозможно. В том же году он доказал замечательную формулу, которая связывает число вершин, граней и ребер многогранника в трехмерном пространстве. Формула таинственным образом верна и для графов, которые называются "планарными". Эти два результата заложили основу теории графов и неплохо иллюстрируют направление ее развития по сей день. Граф как математический объект оказался полезным во многих теоретических и практических задачах. Наверное, дело в том, что сложность его структуры хорошо отвечает возможностям нашего мозга: это структура наглядная и понятно устроенная, но, с другой стороны, достаточно богатая, чтобы улавливать многие нетривиальные явления. Если говорить о приложениях, то, конечно, сразу же на ум приходят большие сети: Интернет, карта дорог, покрытие мобильной связи и т.п. В основах поисковых машин, таких, как Yandex и Google, лежат алгоритмы на графах. Помимо computer science, графы активно используются в биоинформатике, химии, социологии. Этот курс служит введением в современную теорию графов. Мы, конечно, обсудим классические задачи, но и поговорим про более недавние результаты и тенденции, например, про экстремальную теорию графов. Материал изложен с самых основ и на доступном языке. Целью этого курса является не только познакомить вас с вопросами и методами теории графов, но и развить у неподготовленных слушателей культуру математического мышления. Поэтому курс доступен широкому кругу слушателей. Для освоения материала будет достаточно знания математики на хорошем школьном уровне и базовых знаний комбинаторики. Курс состоит из 7 учебных недель и экзамена. Для успешного решения большинства задач из тестов достаточно освоить материал, рассказанный на лекциях. На семинарах разбираются и более сложные задачи, которые смогут заинтересовать слушателя, уже знакомого с основами теории графов....
Filter by:

34 Reviews

By Василюк Антон Викторович

Nov 26, 2018

Хороший лектор, понятный курс, но хочется больше тем

By Dubovik Alexandra

Nov 07, 2018

thanks a lot!

By Братеньков Илья Викторович

Aug 03, 2018

Райгородский великолепный преподаватель! Материал без воды, отличная структура, шутки в тему, не позволяют заскучать

By Sevryukov Vladimir

Jun 18, 2018

Итоговый тест значительно легче недельных.

By Aleksei Krasikov

Mar 15, 2018

Очень хорошее введение в теорию графов, которое предполагает владение только основами комбинаторики. Подача и подбор лекционного материала выше всяких похвал. Этот курс не предполагает получения глубоких знаний в этой области, однако для быстрого обучения базовым навыкам вполне подойдет. Разбору задач уделяется значительно меньше времени, и овладеть способностью решать задачи по заданным материалам достаточно сложно, но его вполне хватает для закрепления пройденного материала. В конечном счете все зависит от ваших целей.

By Maxim Gubanov

Sep 29, 2017

Низкий поклон Андрею Райгородскому, очень живая подача материала. Всех формулировок словами несколько затягивает процесс.

Не совсем понятно было, как соотносить пройденный материал с заданиями недели -- на лекции разбираются оценки сверху или алгоритмы, а оцениваются знания по NP-полным задачам на графически заданных графах.

Я проходил курс для ознакомления с теорией графов, задачу выполнил

By Валерия Шелгунова

Sep 13, 2017

Курс в основном состоит из доказательств теорем, задач разбирается немного, и те задачи, которые разобрали на семинарах, мало имеют отношения к задачам в тесте. Тесты, правда, местами очень легкие, но если какая-то задача не получается, то узнать её решение неоткуда. Начиная со второй недели ответов и пояснений к тестам нет совсем. Вопросы по задачам на форуме преподавателями полностью игнорируются, максимум предлагают "хорошенько подумать". Я вот, к примеру, уже около месяца просыпаюсь и засыпаю с мыслями о задаче о треугольниках из шестой недели, но к решению меня это не приблизило). Получается из серии "если сам не додумался, то тебе и не надо, рожденный ползать летать не может".

Лектор, как всегда, читает замечательно, очень увлеченно, но иногда допускает "неточности" в формулировках, что потом выясняется при выполнении тестов и на форуме. Одна видеолекция пропущена, у нескольких лекций перепутаны субтитры.

Короче, такое ощущение, что создатели курса просто сделали видео-нарезку из того, что у них было, набрали рандомных задач по теме и дальше не запаривались. С тем же успехом можно смотреть ютуб и читать вики (что много раз приходилось делать, чтоб разобраться с тестовыми заданиями). Курс, конечно, очень интересный, но для изучающих теорию графов с нуля не советую совсем.

By Dmitry Grinko

Jul 25, 2017

Concise intro to graph theory. Very good

By Romaykin Alexey

Jul 11, 2017

Great!

By Valentyn Ponomarenko

Jul 08, 2017

Интересно - но сложно :))