Computer Science

Учебник Структуры данных и алгоритмы для начинающих

28 уроков · 5 разделов · бесплатно, без регистрации

Начать с первого урока

Фундамент эффективного кода: как хранить данные и как быстро их обрабатывать. Изучим массивы, списки, деревья, хеш-таблицы, сортировки и оценку сложности.

Курс «Структуры данных и алгоритмы» состоит из 5 разделов и 28 уроков: Сортировки, Поиск, Рекурсия и динамическое программирование, Структуры данных и Введение в алгоритмы. Уроки идут по порядку — от основ к более сложным темам, в каждом есть объяснение с примерами, а в конце — вопросы для самопроверки. К урокам привязаны задачи с автоматической проверкой: прочитали тему — сразу закрепили её кодом.

Программа курса

  1. 1 Сортировки

    1. Сортировка пузырьком

      Сортировка пузырьком (Bubble Sort): идея алгоритма, пошаговый разбор прохода по массиву, код на Python, сложность O(n²) и оптимизация.

    2. Сортировка выбором

      Сортировка выбором (Selection Sort): поиск минимума, пошаговый разбор, код на Python, сложность O(n²), O(n) перестановок и когда применять.

    3. Сортировка вставками

      Сортировка вставками (Insertion Sort): идея, пошаговый разбор, код на Python, сложность O(n²)/O(n), применение в Timsort.

    4. Сортировка слиянием

      Сортировка слиянием (Merge Sort): разделяй и властвуй, рекурсия, слияние половин, код на Python, гарантированная сложность O(n log n).

    5. Быстрая сортировка

      Быстрая сортировка (Quick Sort): pivot, разбиение Lomuto, рекурсия, код на Python, O(n log n) в среднем и O(n²) в худшем случае.

  2. 2 Поиск

    1. Линейный поиск

      Линейный поиск (Linear Search): последовательный просмотр, код на Python, O(n), применение на неотсортированных данных.

    2. Бинарный поиск

      Бинарный поиск (Binary Search): итеративно и рекурсивно, пошаговый разбор, код на Python, O(log n) и требование сортировки.

  3. 3 Рекурсия и динамическое программирование

    1. Рекурсия: база, шаг, стек вызовов

      Рекурсия в Python: базовый случай и рекурсивный шаг, стек вызовов, факториал, числа Фибоначчи, задача о Ханойских башнях с пошаговым разбором.

    2. Динамическое программирование: мемоизация и табуляция

      DP: мемоизация (сверху вниз) и табуляция (снизу вверх) на примере чисел Фибоначчи — кэш подзадач, сравнение по скорости и памяти.

    3. DP на практике: лестница и задача о рюкзаке

      Динамическое программирование на практике: задача о лестнице (подъём на 1-2 ступени) и задача о рюкзаке (0/1 Knapsack) — формулировка подзадачи, таблица dp, сложность.

  4. 4 Структуры данных

    1. Стек
    2. Очередь
    3. Виды очередей
    4. Круговая очередь
    5. Очередь с приоритетом
    6. Двухсторонняя очередь
    7. Деревья
    8. Связные списки
    9. Двоичное дерево
    10. Дерево двоичного поиска
    11. B-дерево
    12. Хеш-таблицы
    13. Куча (структура данных)

  5. 5 Введение в алгоритмы

    1. Зачем изучать структуры данных и алгоритмы
    2. Что такое алгоритм
    3. Асимптотический анализ
    4. Основная теорема о рекуррентных соотношениях
    5. Алгоритм «Разделяй и властвуй»