Алгоритмы: теория и практика. Методы
В ноябре мы запускаем онлайн-курс «Алгоритмы: теория и практика. Методы» от Computer Science центра. Курс бесплатный, приглашаются все желающие. В курсе будут подробно разобраны базовые алгоритмические методы: жадные алгоритмы, метод «разделяй и властвуй», динамическое программирование. Для всех алгоритмов будут математически строго доказаны корректность и оценки на время работы. Мы постарались изложить материал так, чтобы были понятны и сами алгоритмы, и то, как можно было бы догадаться до их основных идей. Помимо теоретических основ, будут рассказаны тонкости реализации алгоритмов на языках программирования C++, Java и Python. В частности, будет рассказано, какие есть общие практики написания кода, позволяющие минимизировать вероятность ошибки, как писать и тестировать код, где стоит использовать стандартные методы, а не изобретать колесо.
Мы тщательно подобрали задачи для закрепления материала. Большинство алгоритмов, которые вы узнаете, вам нужно будет запрограммировать. Это лучший способ убедиться, что вы разобрались во всех деталях. Решая такие задачи, вы получите ценный опыт написания и отладки эффективных и надёжных программ. Задачи на программирование помогут вам почувствовать разницу между плохим (медленным) и хорошим (быстрым) алгоритмом. Вас также ждут тесты (где нужно выбрать правильные ответы из предложенных) и теоретические задачи (в них нужно доказать математическое утверждение). Наконец, в курсе есть также задачи повышенной сложности — менее стандартные задачи, которые не являются обязательными для прохождения курса. Получить удовольствие от решения этих задач смогут и те, кто уже знаком с базовыми алгоритмами.
Несколько примеров (частей) уроков:
Сергей Лебедев (исследователь в области биоинформатики и машинного обучение в JetBrains; преподаватель курса по Python в Computer Science центре)
Реализация алгоритма Евклида для вычисления наибольшего общего делителя на Python
Алексей Левин (разработчик Telegram; несколько лет проводит code review решений студентов Computer Science центра по алгоритмам; золотая медаль (2011) и серебряная медаль (2010) на финале чемпионата мира по программированию ACM ICPC)
Реализация алгоритма для задачи о непрерывном рюкзаке на C++
Павел Маврин (преподаватель курса «Алгоритмы и структуры данных» в Университете ИТМО и Computer Science центре; преподаватель школьного кружка олимпиадной информатики ИТМО; чемпион мира ACM ICPC 2004)
Реализация алгоритма вычисления числа инверсий в массиве на Java
