На 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
Изучение базовых алгоритмов к этому времени будет завершено, и мы перейдем к продвинутым. Начнется курс с потоков в сетях и их применения — как очевидного (поиск оптимального соответствия, непересекающихся путей, составление расписаний), так и более неожиданного (сегментации изображений в компьютерном зрении, поиск плотных кластеров в графах). Следом мы займемся линейным программированием для решения задач создания оптимального бюджета, поиска самой дешевой диеты по заданным параметрам, маршрутизации звонков в телекоммуникациях и т.д.
После останутся сложные задачи, хорошее решение для которых не найдено и, скорее всего, найдено не будет. Слушатели узнают, как решать их на практике. В финале мы расскажем о применении алгоритмов в больших данных и машинном обучении.