Как стать автором
Обновить

Курс Algorithms от Coursera (1-3 недели обучения)

Время на прочтение 4 мин
Количество просмотров 57K
Месяц назад несколько раз на Хабре проскакивали статьи о замечательном ресурсе Coursera, где можно пройти курсы обучения по различным направлениям. Среди прочего меня очень заинтересовал курс «Алгоритмы» (часть 1), на который я подписался и начал его изучать. Сейчас курс приближается к завершению, а я решил написать небольшой отчет по первой части курса (надеюсь меня хватит и на описание второй части курса по его завершению), чтобы уважаемый %username% мог определить стоит ли записываться на следующую итерацию курса или нет.

Надо сказать, что незадолго до начала изучения курса я не очень хорошо себя проявил на собеседовании в Одноклассники по традиционному пункту всех девелоперских вакансий — «Уверенное/Хорошее/Отличное знание алгоритмов», это стало дополнительным стимулом к тому, чтобы начать изучение данного курса. Отмечу, что алгоритмы я до того изучал в рамках предмета «Структуры данных» в институте, а так позже эпизодически в рамках последующей 4 летней трудовой деятельности. В общем обрывки знаний: где-то хорошо, даже с углубленной подготовкой для собеседований, а где-то пробелы.

Итак, для начала немного о том как построен курс. Длительность курса 6 недель. Каждую неделю открываются лекции посвященные двум темам (по каждой теме 4-6 лекций по 10-20 минут). Прослушав лекции, для закрепления выполняются тесты по каждой из тем, а также одно практическое упражнение — программа на Java, на реализацию прикладной задачи. По каждому из указанных проверочных работ, выставляются баллы (пока не знаю куда они пойдут, подозреваю в конце курса будут как то обработаны в итоговую оценку). Дополнительно есть вопросы по изученной темы, которые могут быть заданы на собеседованиях (там оценок нет, просто для общего развития).

Теперь немного о том, какие темы будут рассмотрены в первые 3 недели курса (весь курс на английском и для некоторых тем я не уверен, что знаю адекватное русское название).

Неделя 1
  • Union-Find (поиск объединений): рассматривается проблема определения принадлежности элемента к определенному множеству элементов, а также операция объединения элементов. Фактически разговор идет о деревьях и поиске принадлежности элемента указанному поддереву и о добавлении элемента в указанное поддерево. Рассматриваются плюсы и минусы решения этой задачи на практике через массив и через связный список.
  • Analysis of Algorithms (анализ алгоритмов): рассматривают понятия сложности алгоритмов, лучший, худший и средний случай работы алгоритма, способы оценки времени работы алгоритма, а также способ подсчета затрачиваемой памяти структурами данных в Java.
  • В качестве практического задания предлагается реализовать решение Percolation task. К сожалению не знаю как правильно перевести данную задачу на русский (в комментариях подсказывают, что эта задача называется «Просачивание»), поэтому на пальцах изложу суть: дан двумерный массив ячеек, каждая из которых может быть включена/выключена, после активации очередной ячейки необходимо определить есть ли путь соединяющий верхнюю и нижнюю строки матрицы.

Неделя 2
  • Stacks and Queues (стеки и очереди): как понятно из названия рассматриваются указанные структуры данных и их практическая реализация на базе массивов и списков, а также оценка временной сложности выполнения основных операций при реализации на данных структурах данных. Отдельно время уделено таким вещам как итераторы и дженерики в Java.
  • Elementary Sorts (простейшие сортировки): рассматриваются сортировка выбором, сортировка Шелла и сортировка вставками, оценка их временной сложности. Дополнительно рассматривается проблема «перемешивания» элементов. Рассматривается задача построения выпуклого замкнутого многоугольника, охватывающего набор точек на плоскости (Convex Hull).
  • Для практики предложено реализовать структуры данных дек и «сумку» (bag).

Неделя 3
  • Mergesort (сортировка слиянием): много времени уделено сортировке слиянием, а точнее двум способам ее реализации и оценке их временной сложности. Бонусом рассматривается понятие «устойчивости сортировки», а также отдельно рассматриваются компараторы в Java.
  • Quicksort (быстрая сортировка): здесь все отталкивается от быстрой сортировки. Практическая реализация, оценка ее временной сложности. Дополнительно рассматривается проблема «выборки» элементов (например наибольшего элемента) из множества элементов, а также внимание уделено тому, как реализована встроенная сортировка в Java.
  • На практике попросят решить задачу нахождения коллинеарных точек на плоскости.


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

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

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

Ссылки:
Сайт Сoursera — www.coursera.org
Курс «Алгоримы. Часть 1» — www.coursera.org/course/algs4partI
Теги:
Хабы:
+14
Комментарии 41
Комментарии Комментарии 41

Публикации

Истории

Работа

Java разработчик
356 вакансий

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн
Геймтон «DatsEdenSpace» от DatsTeam
Дата 5 – 6 апреля
Время 17:00 – 20:00
Место
Онлайн