Вводный курс по алгоритмам: от сортировок до машины Тьюринга
Если вы плохо знакомы с теоретическими основами computer science, загляните сюда – мы нашли для вас хороший вводный курс по алгоритмам.
Если хочешь подтянуть свои знания, загляни на наш курс «Алгоритмы и структуры данных», на котором ты:
- углубишься в решение практических задач;
- узнаешь все про сложные алгоритмы, сортировки, сжатие данных и многое другое.
Ты также будешь на связи с преподавателем и другими студентами.
В итоге будешь браться за сложные проекты и повысишь чек за свою работу 🙂
10 видеоуроков от Рахима Давлеткалиева всего за 2,5 часа введут вас в курс дела и дадут наводку, что изучать дальше.
Урок 1. Что такое алгоритмы?
Начинается курс с самых основ: понятия алгоритма и краткой истории происхождения. Лектор расскажет, откуда алгоритмы взялись и зачем нужны, какое отношение к ним имеют Аль-Хорезми (самое прямое), Чарльз Бэббидж и лорд Байрон (очень косвенное).
Теперь вы знаете:
- кто "изобрел" алгоритмы;
- чем алгоритм отличается от программы;
- что произошло в 1834 году;
- зачем аналитической машине нужна была ручка;
- как входные данные могут влиять на эффективность алгоритма.
Урок 2. Пример простого алгоритма
Знаете, какое слово в информатике и программировании самое важное? Нет, не алгоритм :) Обязательно посмотрите второй урок: там об этом подробно рассказывают. А еще демонстрируют пример простейшего алгоритма, после которого вы точно поймете, что это такое.
Теперь вы знаете:
- что такое псевдокод и зачем он нужен.
Углубляемся в тему:
- Изучаем алгоритмы: полезные книги, веб-сайты, онлайн-курсы и видеоматериалы
- 6 бесплатных книг по алгоритмам в программировании
Урок 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-полных задач.