В преддверии дня рождения ШАД стоит рассказать про, наверное, наиболее классический курс в линейке, обязательный для всех студентов, призванный развивать строгое алгоритмическое мышление – курс «Алгоритмы и структуры данных, часть 1».
Курс традиционно читается в осеннем семестре, наполнен практикой строгого решения алгоритмических задач и реализации построенных алгоритмов на С++. Курс можно сдавать только на С++, и это один из вызовов для большого числа студентов. Но команда курса уверена, и каждый год об этом рассказывает слушателям курса, что умение реализовывать алгоритмы с учетом специфики используемых структур данных важно и для специалистов в разработке больших распределенных систем, и для создания передовых моделей ИИ.
Некоторые особенности курса:
— 6 стандартных домашних заданий с 20-25 задачами
— 2 код-ревью по требованиям к итоговому решению с защитой алгоритма (теоретическая часть) и реализации (практическая часть)
— дополнительные задачи на построение эффективных алгоритмов с модификацией структур данных под требования интерфейса
Основные темы лекций и семинаров курса:
1. Модели вычислений. RAM-модель
2. Амортизационный анализ: метод монеток, метод потенциалов. Динамически расширяющийся массив
3. Сортировки: от быстрой сортировки до сортировки слиянием без дополнительной памяти. Алгоритмы поиска порядковой статистики. Бинарный поиск.
4. Кучи
5. Хеширование. Хеш-таблица на цепочках. Совершенное хеширование. Открытая адресация.
6. Бинарные поисковые деревья. Обходы дерева поиска.
7. Красно-черные деревья. Операция вставки и удаления.
8. Splay дерево. Операция splay. Функция потенциала для амортизированной оценки.
9. Декартово дерево. Линейное построение декартового дерева.
10. Графы. Хранение графов. DFS и лемма о белых путях. BFS.
11. Топологическая сортировка. Поиск компонент сильной связности. Мосты и точки сочленения.
12. Задача поиска кратчайшего пути. Алгоритм Дейкстры. Двусторонний алгоритм Дейкстры.
13. Остовные деревья. Минимальное остовное дерево. Задача о динамической связности.
Кроме стандартных задач, входящих в домашние задания, в курсе есть несколько задач-челленджей, которые стоят как целая домашка, но решают их несколько человек в год! Одна из таких задач как раз задача о динамической связности графа.
Пара слов о фото к посту. Преподаватели и студенты в ШАД с удовольствием встречаются вне аудитории, чтобы обсудить и сам курс, и путь, куда идет Школа, или куда идут наши студенты. Спасибо за открытый и всегда интересный разговор!
Ваш ШАД 🥳
#курсышад #алгоритмы