Вводный курс по алгоритмам: от сортировок до машины Тьюринга

0
22706
Добавить в избранное

Если вы плохо знакомы с теоретическими основами computer science, загляните сюда – мы нашли для вас хороший вводный курс по алгоритмам.

Вводный курс по алгоритмам: от сортировок до машины Тьюринга

10 видеоуроков от Рахима Давлеткалиева всего за 2,5 часа введут вас в курс дела и дадут наводку, что изучать дальше.

Урок 1. Что такое алгоритмы?

Начинается курс с самых основ: понятия алгоритма и краткой истории происхождения. Лектор расскажет, откуда алгоритмы взялись и зачем нужны, какое отношение к ним имеют Аль-Хорезми (самое прямое), Чарльз Бэббидж и лорд Байрон (очень косвенное).

Теперь вы знаете:

  • кто «изобрел» алгоритмы;
  • чем алгоритм отличается от программы;
  • что произошло в 1834 году;
  • зачем аналитической машине нужна была ручка;
  • как входные данные могут влиять на эффективность алгоритма.

Урок 2. Пример простого алгоритма

Знаете, какое слово в информатике и программировании самое важное? Нет, не алгоритм 🙂 Обязательно посмотрите второй урок: там об этом подробно рассказывают. А еще демонстрируют пример простейшего алгоритма, после которого вы точно поймете, что это такое.

Теперь вы знаете:

  • что такое псевдокод и зачем он нужен.

Углубляемся в тему:

Урок 3. Знакомство с алгоритмами сортировки

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

Кроме непосредственно сортировок, в этом уроке затрагивается очень важная концепция – сложность алгоритмов и способы ее оценки.

Теперь вы знаете:

  • о каких пузырьках идет речь в алгоритме bubble sort;
  • что и куда вставляется при сортировке вставками;
  • почему bogosort – это неудачная идея для сортировки;
  • что бывают худшие и лучшие случаи входных данных;
  • как абстрагироваться от физической реализации вычислительных устройств при оценке эффективности алгоритма.

Еще немного о сортировках:

Урок 4. Разделяй и властвуй

Переходим к одной из самых эффективных алгоритмических концепций. В четвертом уроке лектор расскажет о сортировке слиянием и о ее преимуществах перед уже рассмотренными видами сортировок.

Теперь вы знаете:

  • почему искать в отсортированном массиве проще, чем в неотсортированном;
  • как объединить два маленьких упорядоченных массива в один большой, но тоже упорядоченный;
  • что значит «логарифмический рост алгоритма».

Урок 5. Сложность алгоритмов и Big O

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

Теперь вы знаете:

  • как математически описать масштабируемость алгоритмов;
  • что такое асимптотическая нотация и зачем она нужна;
  • чем O отличается от Ω;
  • почему для оценки быстродействия можно отбросить все степени аргумента, кроме самой большой.

Подробнее о нотациях здесь:

Урок 6. Графы

Вы знакомы с легендой о семи мостах Кёнигсберга? Если нет, то обязательно посмотрите шестой урок курса по алгоритмам – это историческая задача, которую должен знать каждый программист. А заодно вы познакомитесь с особой структурой данных – графами.

Теперь вы знаете:

  • как абстракции (да-да, вот оно главное слово из второго урока) помогают решать реальные проблемы;
  • почему не любой граф можно обвести одним росчерком;
  • как найти самый короткий путь из точки A в точку B;
  • кто такой Дейкстра.

Графы – это очень интересно:

Урок 7. Структуры данных

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

Теперь вы знаете:

  • зачем нужна хеш-функция;
  • что такое кластеризация;
  • чем хороши хеш-таблицы;
  • какие проблемы массивов решают связные списки;
  • какие проблемы, в свою очередь, есть у связных списков и как их решать.

Полезные курсы:

Урок 8. Деревья и двоичные деревья

В восьмом уроке курса по алгоритмам лектор разбирается с рекурсивными деревьями, растущими сверху вниз. Оказывается, они бывают разными.

Теперь вы знаете:

  • чем глубина узла отличается от его высоты;
  • как устроено двоичное дерево поиска;
  • формулу расчета высоты дерева;
  • можно ли хранить деревья в массивах;
  • почему с низкими деревьями проще работать;
  • какова эффективность операций с деревьями;
  • в чем особенность red-black tree.

Еще немного о структурах данных:

Урок 9. Машина Тьюринга

Еще одна крутая абстрактная концепция computer science – машина Тьюринга, придуманная, как можно догадаться, Аланом Тьюрингом. Что это за штука – смотрите в девятом уроке.

Теперь вы знаете:

  • что Алан Тьюринг сделал для развития компьютерной науки;
  • из каких частей состоит легендарная машина Тьюринга;
  • в чем ее детерминированность.

Урок 10. P vs. NP

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

Теперь вы знаете:

  • что такое задачи P- и NP-класса;
  • какую роль здесь играет машина Тьюринга;
  • можно ли быстро решить проблему, если ее решение можно быстро проверить;
  • какие задачи до сих пор не решены и почему;
  • в чем магия NP-полных задач.

Супер! Вы прошли этот небольшой курс по алгоритмам. В награду за усердие вот вам еще пара интересных статей:

Интересуетесь алгоритмами?

Подпишитесь на нашу рассылку, чтобы получать больше интересных материалов:

И не беспокойтесь, мы тоже не любим спам. Отписаться можно в любое время.




Добавить комментарий