Всем привет. Сегодня я бы хотел представить некоторую подборку материалов, которые помогут вам изучить основы Графов, как раздела математики.
Многие из нас, людей из IT-сферы, учились в инженерных университетах. Почти во всех институтах есть небольшой вводный курс по графам, который рассказывает некоторые основы. Там обычно вводятся базовые определения и понятия, а также доказываются базисные теоремы.
Что было у меня? У меня был курс Дискретная математика, один из разделов которого был посвящён графам. То есть, полноценного курса по графам у меня не было. Дискретная математика в моём институте читалась, если я правильно помню, на 2-м семестре.
К сожалению, до поступления в университет, я не занимался программированием, а также не развивался в IT-сфере (первый код был написан мной в 11-м классе). Поэтому, всё, что я знал до начала курса по дискретной математике о графах — это то, что эта тема широко используется в олимпиадном программировании.
Прослушав 1-ю лекцию по дискретной математике (а начали мы сразу с графом), я вообще не понял, что это, и с чем его едят. Нам было сказано, что графы имеют большое практическое применение, но чего-то конкретного я не услышал. На такой ноте и прошёл весь модуль Графы. Из этого курса я вынес только базовые определения, а также несколько теорем.
Время шло, я пытался расти в качестве разработчика. Иногда я посещал интервью, иногда — решал не совсем стандартные задачи. Кроме того, вечерами баловался на сайте онлайн чемпионата по программированию http://codeforces.com/. Всё это время от времени требовало знания Графов. Поэтому, в один из зимних вечеров я решил подтянуть эту тему. Итак, какие же я использовал ресурсы для этого?
Первое, с чего я начал — это удивительный курс Графы и комбинаторика: от жемчужин теории к современным приложениям. Мне повезло: моё желание освоить эту тему как раз таки совпало с датой начала курса.
Чем хорош этот курс? Наверное, главное — это лектор. Настолько талантливого преподавателя я не видел ранее. Харизма, глубокое знание темы, юмор — в нём было всё. Также нельзя ни отметить замечательную структуру курса. Всё начинается с базовых определений, а заканчивается — работой с динамическими графами. Также немного рассказывается о, наверное, самом популярном графе — Интернет графе.
Этот курс является больше теоретическим. В нём есть и доказательства теорем, и задачи, и прочие вещи, классические для математики. Тут вам не придётся кодить алгоритмы. То есть, вы в течение курса не напишите ни одной строчки кода. Зато получите хорошую теоретическую базу по основам графов.
Теория — это очень замечательно. Однако нам, разработчикам, нужна и практика. Первое, что поможет нам познакомится с графами с точки зрения программирования — это книжка Ф.А. Новиков. Дискретная математика для программистов. Тут вы найдете описание основных алгоритмов на графах, а также их псевдокод. Эта книжка поможет вам закрепить знания, полученные из онлайн-курса.
Если вы хотите углубиться в изучении Графов, то далее вы должны познакомится с творением Кормена — Кормен, Риверст, Лейзерсон. Алгоритмы: построение и анализ. Кстати, не так давно вышло 3-е издание на русском языке. Эта книжка — кладезь знаний по алгоритмам. Это и более подробный разбор алгоритмов, это и описание асимптотической сложности, это и приятный стиль изложения материала.
Вместо Кормена могу вам посоветовать свежий перевод книги — Алгоритмы. Перевод с английского А. С. Куликова под редакцией А. Шеня.. Тут вы найдете несколько глав, посвящённых базовым понятием графа, а также классическим алгоритмам на графах (поиск в глубину, поиск кратчайшего пути и т.д.).
Всё, что было описано выше — это источники знаний для изучения Графов. Однако иногда нам нужно найти какое-то понятие или алгоритм. В этом случае нам помогут такие замечательные сайты, как:
Надеюсь, что эти материалы помогут вам освоить азы графов.
Категории: Программирование