Какие алгоритмы используют социальные сети, чтобы осуществлять поиск по графу друзей? Как телекомпании выбирают, какую рекламу показывать, чтобы максимизировать прибыль? Как собрать геном из миллионов фрагментов? Как вычислить кратчайший путь из Нью-Йорка в Маунтин Вью в тысячи раз быстрее, чем это делают классические алгоритмы?

На Coursera появилась еще одна полезная специализация, созданная при участии Яндекса, — «Алгоритмы и структуры данных». Среди преподавателей не только представители Яндекса, Вышки, петербургского Computer Science Center, но и лекторы Калифорнийского университета в Сан-Диего, поэтому на этот раз все курсы специализации англоязычные.



Всего их пять, в конце слушателей ждет финальный проект. Один из них связан с биоинформатикой, второй — с поиском кратчайших путей в настоящих дорожных сетях и графах. В формате специализации все материалы доступны бесплатно. Оплата понадобится только в том случае, если вы захотите отправлять домашние задания на проверку и получить сертификат. Тогда вам нужно будет запрограммировать и сдать около 100 задач в тестирующую систему. Сделать это можно на C, C++, C#, Haskell, Java, JavaScript, Python2, Python3, Ruby и Scala.

Сегодня начинается первый курс — Algorithmic Toolbox. Под катом — программа специализации, информация о преподавателях и их мнение о том, кому она будет полезна и почему.

Преподаватели

Михаил Левин. Яндекс, факультет компьютерных наук ВШЭ. Руководитель службы анализа больших данных Yandex Data Factory. Ведет курс «Алгоритмы и структуры данных» в Школе анализа данных, участвует в создании программы обучения на факультете Computer Science Вышки и Яндекса. Дважды завоевывал медали на ACM ICPC в составе команды МГУ им. М.В. Ломоносова. Многие на Хабре помнят лекцию Миши о том, как математика помогает Яндексу зарабатывать на рекламе.

Алгоритмы и структуры данных — основы computer science, поэтому это обязательный курс в любой программе по компьютерным наукам. Их нужно знать не только для того, чтобы создавать самим базы данных, распределенные системы и хранилища, но и делать такие сервисы, как, например, поиск или навигатор. Алгоритмы используются в data science, существенный кусок машинного обучения — алгоритмы машинного обучения.

От курса в ШАДе наша специализация отличается существенно меньшим порогом входа, меньшим количеством доказательств (они есть, но многие опциональны), набором тем, более сильным упором на практические примеры и современные приложения, наличием Capstone Project.

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

Дэниэл Кейн, Калифорнийский университет в Сан-Диего. Доцент кафедры CSE и кафедры математики. Дэниэл преподает введение в алгоритмы. Cреди его научных интересов различные области математики и теории компьютерных наук, а большая часть работ касается теории чисел, вычислительной сложности и комбинаторики. Дэниэл Кейн окончил Гарвард, получил степень PhD в MIT.

Алгоритмы сейчас применяются повсеместно: в разработке софта, анализе генома, предсказании пробок, рекомендательных системах. Вы сталкиваетесь с алгоритмами, просто пользуясь интернетом. Их используют в любой области Computer Science, поэтому курс по алгоритмам и структурам данных — базовая часть любой программы по CS.

Павел Певзнер, Калифорнийский университет в Сан-Диего, Лаборатория алгоритмической биологии СПбАУ. Павел окончил Физтех, сейчас является профессором кафедры CSE в Сан-Диего, где в течение 12 лет преподает алгоритмы в биоинформатике. В 2011 году участвовал в основании Лаборатории алгоритмической биологии в Санкт-Петербурге, которая разработала платформу Rosalind. В знак признания его научных работ Павел получил звание действительного члена ACM и ISCB.

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

Нил Родс, Калифорнийский университет в Сан-Диего, Google. Окончил UCSD, изучал Computer Science. В то время, когда он уже получал Ph.D., решил покинуть университет и заняться развитием собственной компании Palomar Software. Более десяти лет Нил Родс ведет в Сан-Диего курсы по алгоритмам, машинному обучению, дискретной математике, теории вычислимости. Он разрабатывал программы обучения для сотрудников Apple и Palm. Последние семь лет был разработчиком в Google.

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

Александр Куликов, Математический институт им. В.А. Стеклова, Computer Science Center, Яндекс. Окончил матмех СПбГУ, защитил степень кандидата физико-математических наук в Математическом институте Стеклова. Научные интересы — алгоритмы для NP-трудных задач и схемная сложность. Александр руководит Computer Science Center в Санкт-Петербурге, на базе которого работает филиал Школы анализа данных Яндекса. Организовывает в России конференции и студенческие школы, посвященные компьютерным наукам.

Алгоритмы нужны во всех разделах Computer Science, поэтому вопросы о них всегда есть в техническом интервью. На Курсере уже есть два отличных курса по алгоритмам: один от Тима Рафгардена из Стэнфорда, второй — от Роберта Сэджвика из Принстона. Наша специализация выгодно отличается от них тем, что
в ней большой акцент делается на практическую составляющую. Все
изученные алгоритмы слушателям нужно будет реализовать так, чтобы они работали очень быстро даже на больших объёмах данных. Это даст и более глубокое понимание алгоритмов, и ценный опыт написания и отладки быстрых и надёжных программ. Второе преимущество нашей специализации более банальное — в ней больше материала.

Чтобы к ней приступить, нужно иметь базовую математическую подготовку (доказательство по индукции, доказательство от противного), опыт программирования (C, C++, C#, Haskell, Java, JavaScript, Python2, Python3, Ruby или Scala), представлять, как работать со списками/массивами и как устроена рекурсия. Специализация будет полезна любому программисту, который хочет стать более востребованным и научиться решать более сложные задачи.

Программа

Специализация состоит из пяти курсов и финального проекта.

1. Algorithmic Toolbox

В первом курсе рассказано об алгоритмах, которые нельзя не знать, и задачах, которые часто возникают на практике: сортировка и поиск, подход «разделяй и властвуй», жадные алгоритмы, динамическое программирование. Слушатели узнают, когда имеет смысл использовать жадные алгоритмы и как динамическое программирование используется в изучении генома. Вы сможете потренироваться в создании новых алгоритмов и их эффективной реализации (чтобы они работали меньше чем за секунду).

2. Data Structures

Эффективные алгоритмы почти всегда используют эффективные структуры данных. В этом курсе будут рассмотрены основные из них, которые можно использовать для решения самых разных задач. Начнем с базовых структур: массивы, очереди, стеки, деревья; обсудим, в каких ситуациях их стоит использовать. Затем рассмотрим два способа реализации словарей — с помощью хеш-таблиц и бинарных деревьев поиска. Эти структуры повсеместно используют в языках программирования и базах данных. На практике почти любая нетривиальная программа каким-нибудь образом использует хеш-таблицы или деревья поиска. И хотя эти структуры обычно реализованы в библиотеках языка программирования, важно понимать их достоинства и недостатки, чтобы эффективно использовать в своих программах и уметь расширять существующие реализации.

Кроме того, в этом курсе вы узнаете о том, как Яндекс.Диску удается экономить много места и почему иногда загрузка большого файла в Dropbox происходит практически мгновенно; познакомитесь с принципами построения распределенных хеш-таблиц, используемых для хранения больших данных.

Наконец, в курсе будут рассмотрены структуры данных, которые позволяют выполнять запросы типа «извлечь минимальный элемент» или «проверить, принадлежат ли два элемента одному множеству».

3. Algorithms on Graphs

Если вы когда-нибудь запускали навигатор, чтобы построить маршрут или узнать примерное время пути, то пользовались алгоритмами на графах. Графы проявляются в самых разных реалиях: дорожных сетях, компьютерных сетях и в последнее время — в социальных сетях. Если вы ищете быстрый способ добраться до работы, самый дешевый вариант соединения нескольких компьютеров в сеть или эффективный способ нахождения популярных людей в фейсбуке, вам придется работать с алгоритмами на графах.

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

4. Algorithms on Strings

С точки зрения Computer Science, весь окружающий нас текст — это строки. Чтобы создать эффективный поиск по нему, разработчики активно используют алгоритмы на строках. Они же применяются в медицине: с их помощью исследователи находят мутации в человеческом геноме, вызывающие те или иные болезни. Алгоритмам на строках будет посвящен четвертый курс нашей специализации.

5. Advanced Algorithms and Complexity

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

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