Онлайн-курс "Algorithmic Toolbox" на Coursera

Опубликовано:

Курс "Algorithmic Toolbox" - первый из 6 курсов специализации "Master Algorithmic Programming Techniques" от университета Калифорнийский университет в Сан-Диего & Высшая школа экономики на Coursera. На примере разбора реальных алгоритмов - рассказывается об алгоритмических приемах, используемых для эффективного решения вычислительных задач.

Теории в лекциях не много, только необходимый минимум, чтобы понять рассмотренные алгоритмические приемы. По большей части, для меня, это было повторение давно изученного, и во многом подзабытого, материала. Но после многолетнего практического опыта - было полезно, хотя бы для систематизации накопленного опыта :) Основной ценностью, оказались практические задания. Сложность заданий я бы назвал средней, но над некоторыми голову поломать пришлось. Задания можно выполнять на C, C++, C#, Haskell, Java, JavaScript, Python, Ruby, и Scala.

Рассмотренные темы

  • Вычислительная сложность алгоритмов:
    1. Асимптотическая сложность - порядок роста времени работы алгоритма от размера входных данных.
    2. Big O нотация - общепринятая нотация, с помощью которой выражают вычислительную сложность алгоритмов. Удобна для сравнения эффективности/производительности алгоритмов.
    3. Мастер теорема - полезна для нахождения асимптотической сложности некоторых рекурсивных алгоритмов (частный случай Akra-Bazzi method).
  • Жадный алгоритм - простой и эффективный способ решения задач: задача разбивается на шаги; на каждом шаге происходит 'жадный' выбор, после которого размер входных данные уменьшается; и алгоритм рекурсивно повторяется для меньшего набора данных. Алгоритм далеко не всегда приводит к верному решению, и поэтому требует обязательного доказательства что жадный выбор безопасен и соответствует корректному решению поставленной задачи.
  • Разделяй и властвуй - задача разбивается на несколько подзадач, каждая из которых решается независимо (и возможно рекурсивно), после чего, из комбинации результатов подзадач - формируется решение задачи. Наиболее известные алгоритмы из разобранных:
    1. Двоичный поиск
    2. Алгоритмы сортировок: сортировка выбором, сортировка слиянием, быстрая сортировка (Визуализация и описание алгоритмов).
  • Динамическое программирование - метод, при котором задача разбивается на подзадачи, каждая из которых решается независимо, и результат решения подзадачи может быть запомнен и переиспользован в той же подзадаче, но на другой итерации - что позволяет сократить кол-во итераций, если бы использовался метод, отличный от динамического программирования. Алгоритм полезен для оптимизации задач, когда при наивном подходе, требуется перебор всех возможных вариантов/комбинаций (к примеру, когда сложность O(n!)). Наиболее известные алгоритмы из разобранных:
    1. Дистанция редактирования/Расстояние Левенштейна
    2. Наибольшая общая подпоследовательность
    3. Задача о ранце
top

Комментарии

Комментарии остутствуют

Оставить комментарий


Комментарии перед публикацией проверяются