Алгоритмы и структуры данных

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

Ознакомьтесь с программой курса «Алгоритмы и структуры данных» от Proglib Academy - proglib.academy

1. Введение. Производительность алгоритмов. Знакомство с программой курса и алгоритмами. Способы измерения времени выполнения алгоритмов. О-нотация.
2. Работа с числами. Числовые алгоритмы: алгоритм Эвклида, возведения в целую степень, схема Горнера, проверка простоты, решето Эратосфена.
3. Массивы. Массивы. Указатели. Доступ к элементам. Линейный поиск. Двумерные массивы. Динамический массив.
4. Алгоритмы на массивах. Бинарный поиск. Вставка и удаление элемента. Удаление нескольких элементов.
5. Списки. Стек, очередь, дек. Понятие об АТД, интерфейсе. Односвязные, двусвязные списки. Основные операции. Реализации на массиве. Реализация на списке. Применение.
6. Очередь с приоритетом. Понятие о пирамиде (куче), построение пирамиды. Извлечение максимума, добавление элемента. std::priority_queue.
7. Сортировки. Квадратичные сортировки. Сортировка слиянием. Быстрая сортировка. Пирамидальная сортировка. std::sort. Сортировка подсчетом.
8. Порядковые статистики. Поиск медианы и порядковых статистик методом QuickSelect.
9. Деревья. Виды деревьев. Обходы в глубину и в ширину. Двоичные деревья поиска. Необходимость балансировки. АВЛ-деревья и т.д.
10. Хеш-таблицы. Хеш-таблицы и ассоциативный доступ. Методы разрешения коллизий. std::unordered_set, std::unordered_map.
11. Жадные алгоритмы. Динамическое программирование. Примеры жадных алгоритмов, их корректность. Задача о рюкзаке. Одномерная и двумерная динамика.
12. Графы. Виды графов. Представление графов. Связность. Обходы в глубину и в ширину. Сильная связность, конденсация. Поиск кратчайших путей, алгоритм Дейкстры.
13. Строки. Символы, кодировки, юникод. Поиск в строках – алгоритмы Рабина-Карпа и Кнута-Морриса-Пратта. Бор.
14. Криптография. CRC-коды, MD5, SHA.
15. Длинные числа. Итоги. Подводим итоги первого этапа обучения и переходим к углубленному изучению тем.

Чему вы научитесь

• Научитесь уверенно работать с темой: работа с числами. числовые алгоритмы алгоритм эвклида, возведения в целую степень, схема горнера, проверка простоты, решето эратосфена.
• Освоите и сможете применять: графы. виды графов. представление графов. связность. обходы в глубину и в ширину. сильная связность, конденсация. поиск кратчайших путей, алгоритм дейкстры.
• Освоите и сможете применять: жадные алгоритмы. динамическое программирование. примеры жадных алгоритмов, их корректность. задача о рюкзаке. одномерная и двумерная динамика.
• Освоите и сможете применять: сортировки. квадратичные сортировки. сортировка слиянием. быстрая сортировка. пирамидальная сортировка. std sort. сортировка подсчетом.
• Освоите и сможете применять: очередь с приоритетом. понятие о пирамиде (куче), построение пирамиды. извлечение максимума, добавление элемента. std priority_queue.