Курс: Алгоритмы и структуры данных
Курс о том, как устроены стек, очередь, списки и деревья - и какие алгоритмы на них работают. Каждый урок: понятное объяснение, сравнение с Python, разбор реализации на C и задача для самопроверки.
Программа курса
1 Объекты и ссылки
- ✓ Статические и динамические объекты программ: компиляция против выполнения
- ✓ Ссылочный тип данных: как добраться до безымянного объекта
- ✓ Ссылочные типы в современных языках программирования: указатели C, ссылки C++, связывание Python
- ✓ Уровни описания структур данных: от математики до байтов
- ✓ Абстрактные типы данных: тип определяют операции
- ✓ Закрепление материала: Объекты и ссылки
- ✓ Задачи модуля "Объекты и ссылки": от указателей до утечек памяти
2 Файл и вектор
- ✓ Файл. Функциональная спецификация: последовательность, которая живет дольше программы
- ✓ Файл. Логическое описание. Физическое представление: буферная переменная, потоки и носители
- ✓ Вектор. Функциональная спецификация: восемь операций и главный компромисс
- ✓ Вектор. Логическое описание и физическое представление: указатель, размер и realloc
- ✓ Закрепление материала: Файл и вектор
- ✓ Задачи модуля "Файл и вектор": от реверса до слияния файлов
3 Стек
- ✓ Стек. Функциональная спецификация стека: LIFO и семь операций
- ✓ Стек. Логическое описание: рекурсия и обратная польская запись
- ✓ Стек. Аппаратурные аспекты: от команд процессора до встречных стеков
- ✓ Стек. Физическое представление (массив): одна переменная решает все
- ✓ Стек. Физическое представление (динамические объекты): связный список узлов
- ✓ Стек. Реализация рекурсии: что происходит при вызове функции
- ✓ Закрепление материала: Стек
- ✓ Задачи модуля "Стек": от скобок до пересечения
4 Очередь и дек
- ✓ Очередь. Функциональная спецификация очереди: FIFO и семь операций
- ✓ Очередь. Логическое описание и физическое представление (файл): долговременное хранение и его цена
- ✓ Очередь. Логическое описание и физическое представление (массив): кольцевой буфер
- ✓ Очередь. Логическое описание и физическое представление (динамические объекты): два указателя
- ✓ Дек. Сравнительное описание. Примеры задач: очередь с двумя открытыми концами
- ✓ Закрепление материала: Очередь и дек
- ✓ Задачи модуля "Очередь и дек": от двух стеков до транспонирования
5 Линейные списки
- ✓ Линейный список. Функциональная спецификация: операции в произвольном месте
- ✓ Линейный список. Логическое описание: голова и хвост
- ✓ Линейный список. Физическое представление (массив): индексный вектор
- ✓ Линейный список. Физическое представление (динамические объекты): указатели
- ✓ Линейный список. Физическое представление. Итераторы: безопасная навигация
- ✓ Списки общего вида. Примеры: ортосписки
- ✓ Разреженные матрицы
- ✓ Закрепление материала: Линейные списки
- ✓ Задачи модуля "Линейные списки": от сравнения до реверса
6 Деревья
- ✓ Деревья: основные понятия
- ✓ Двоичные деревья: виды и спецификация
- ✓ Эквивалентность деревьев общего вида и двоичных деревьев
- ✓ Двоичное дерево. Функциональная спецификация
- ✓ Двоичное дерево. Логическое описание
- ✓ Двоичное дерево: Построение и визуализация
- ✓ Двоичное дерево. Физическое представление. Прошивка
- ✓ Алгоритмы обхода двоичных деревьев
- ✓ Представление и обработка деревьев общего вида
- ✓ Закрепление материала: Деревья
- ✓ Задачи модуля "Деревья": от высоты до зеркального отражения
7 Графы
8 Выражения
9 Деревья поиска
- ✓ Деревья поиска. Организация: свойство упорядоченности и поиск за O(log N)
- ✓ Деревья поиска. Вставка и удаление: два простых случая и один хитрый
- ✓ Сбалансированные деревья поиска: АВЛ-деревья
- ✓ Сбалансированные деревья поиска. Включение: повороты и балансировка
- ✓ Сбалансированные деревья поиска. Исключение: балансировка после удаления
- ✓ Деревья оптимального поиска
- ✓ Закрепление материала: Деревья поиска
- ✓ Задачи модуля "Деревья поиска": от проверки дерева до общего предка
10 Поиск
11 Хеш-таблицы
12 Сортировки
- ✓ Задача сортировки. Классификация и свойства сортировок
- ✓ Сортировка вставкой (Insertion Sort)
- ✓ Сортировка выборкой (Selection Sort)
- ✓ Пузырьковые сортировки (Bubble Sort)
- ✓ Сортировка Шелла (Shell Sort)
- ✓ Турнирная сортировка (Tournament Sort)
- ✓ Пирамидальная сортировка (Heap Sort)
- ✓ Сортировка Хоара (Quick Sort): быстрая сортировка
- ✓ Сортировка слиянием (Merge Sort)
- ✓ Сортировка естественным слиянием (Natural Merge Sort)
- ✓ Сортировка строк
- ✓ Сортировка подсчетом (Counting Sort)
- ✓ Поразрядная сортировка (Radix Sort)
- ✓ Карманная сортировка (Bucket Sort)
- ✓ Сравнение алгоритмов сортировки
- ✓ Закрепление материала: Сортировки
- ✓ Задачи модуля "Сортировки": от пузырьковой сортировки до слияния