Полная программа

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


Содержание курса
Курс состоит из двух разделов:
а) основы – уроки по 2 академических часа
б) продвинутый – уроки 30 до 2 академических часов
— Фундаментальные структуры данных и алгоритмы работы с ними
— Примерный состав стандартной библиотеки языков программирования
— Применять их при разработке программ
Знать:
Уметь:
В результате обучения слушатель будет:
Процесс обучения
На каждом уроке будут рассмотрены необходимые теоретические вопросы и множество практических примеров. На каждом уроке будет получать практические задания для закрепления материала.
Соответствует односеместровому университетскому курсу по алгоритмам и структурам данных.
1 урок
Введение. Производительность алгоритмов
1
— Кто авторы курса, план курса.
— Определение алгоритма, примеры разных алгоритмов для решения одной задачи.
— Способы измерения времени выполнения алгоритмов (benchmarking).
— Теоретическая оценка производительности, О-нотация.
Слушатель знает, зачем ему изучать алгоритмы и что его ждет на курсе, знает и понимает теоретические оценки производительности алгоритмов.
Результат
1 урок
Работа с числами
2
— Числовые алгоритмы: алгоритм Евклида, возведения в целую степень, проверка простоты, решето Эратосфена.
Слушатель знает и понимает схему работы данных алгоритмов, способен самостоятельно реализовать.
Результат
2 урока
Массивы
3
— Массивы. Указатели. Доступ к элементам. Линейный поиск. Двумерные массивы. Динамический массив.
Слушатель понимает устройство массива и списка, знает виды списков, способы доступа к элементам.
Результат
1 урок
Алгоритмы на массивах
4
— Бинарный поиск. Вставка и удаление элемента. Удаление нескольких элементов.
Слушатель понимает устройство массива и списка, разбирается в работе с элементами массивов.
Результат
2 урока
Списки. Стек, очередь, дек
5
— Понятие об АТД, интерфейсе. Односвязные, двусвязные списки. Основные операции. std::forward_list, std::list.
— Стек, очередь, дек. std::stack, std::queue, std::deque.
— Реализации на массиве. Реализация на списке. Применение.
Слушатель знает типовые схемы циклов; понимает реализацию длинных целых чисел, знает, что такое АТД. Различает реализацию на массиве и на списке.
Результат
1 урок
Очередь с приоритетом
6
— Понятие о пирамиде (куче), построение пирамиды.
— Извлечение максимума, добавление элемента. std::priority_queue.
Слушатель знает понятие пирамиды (кучи), что такое АТД, извлекает максимум, работает с командами.
Результат
1 урок
Порядковые статистики
8
— Поиск медианы и порядковых статистик методом QuickSelect.
Слушатель умеет находить медиану и работать с помощью метода QuickSelect
Результат
2 урока
Сортировки
7
— Квадратичные сортировки. Сортировка слиянием. Быстрая сортировка. Пирамидальная сортировка. std::sort. Сортировка подсчетом.
Слушатель знает, что такое сортировки, понимает отличия реализаций на различных сортировках.
Результат
2 урока
Деревья
9
— Виды деревьев. Обходы в глубину и в ширину. Двоичные деревья поиска. Поиск, вставка, удаление, минимум/максимум. Необходимость балансировки. АВЛ-деревья. std::set, std::map.
Слушатель знает представление деревьев, двоичных деревьев, умеет реализовать обходы и другие алгоритмы.
Результат
2 урока
Хеш-таблицы
10
— Хеш-функции.
— Хеш-таблицы и ассоциативный доступ.
— Методы разрешения коллизий. std::unordered_set, std::unordered_map.
Слушатель понимает устройство хеш-таблиц, знает варианты разрешения коллизий.
Результат
2 урока
Жадные алгоритмы. Динамическое программирование
11
— Примеры жадных алгоритмов, их корректность.
—Задача о рюкзаке. Одномерная и двумерная динамика.
Слушатель знает представление жадных алгоритмов, умеет решать задачи с помощью динамического программирования.
Результат
3 урока
Графы
12
— Виды графов. Представление графов. Связность. Обходы в глубину и в ширину. Сильная связность, конденсация. Поиск кратчайших путей, алгоритм Дейкстры.
Слушатель знает представление графов, умеет реализовать обходы графов, знает виды задач на графах.
Результат
2 урока
Строки
13
— Символы, кодировки, юникод.
— Поиск в строках – алгоритмы Рабина-Карпа и Кнута-Морриса-Пратта. Бор.
Слушатель умеет реализовать алгоритмы работы со строками.
Результат
1 урок
Криптография
14
— CRC-коды, MD5, SHA.
Слушатель знает разные виды шифров и умеет реализовать алгоритмы шифрования и дешифрования.
Результат
1 урок
Длинные числа. Итоги
15
— Длинные числа.
— Обзор изученного материала. Литература и дополнительные материалы.
Слушатель понимает, в каком направлении двигаться дальше.
Результат
Список уроков – базовый уровень
~ 2 - 3 урока
Сортировки
16
— Шелла, быстрая, поразрядная.
Слушатель понимает принципы и способен реализовать данные алгоритмы.
Результат
~ 2 - 4 урока
Строки
17
— Сложные алгоритмы поиска строк.
— Редакционное расстояние
Сложные алгоритмы поиска строк Редакционное расстояние.
Результат
~ 2 - 4 урока
Деревья
18
— Балансированные деревья.
— В-деревья.
Слушатель знает устройство балансированных деревьев (в том числе RB-tree), понимает работу алгоритмов, может реализовать некоторые.
Результат
4 урока
Графы
19
— Остовные деревья, пути, раскраски…
— Интернет и графы
Слушатель понимает схемы работы, умеет реализовать многие алгоритмы (в том числе жадные алгоритмы поиска остовного дерева).
Результат
2-3 урока
Сжатие данных
20
— Хаффмен, Лемпель-Зив
Слушатель знает схемы работы и умеет реализовать некоторые алгоритмы.
Результат
Динамическое программирование
21
— 1-2 типичные практические задачи (связь с графами)
Слушатель понимает принцип динамического программирования и знает схемы реализации задач ДП.
Результат
NP-трудные задачи
1-2 урока
22
— Задача коммивояжера (связь с графами)
Слушатель понимает разницу между Р и NP, умеет реализовать алгоритмы полного перебора (исчерпывающего поиска).
Результат
Эвристические алгоритмы ИИ
2-3 урока
23
— Поиск в пространстве состояний, эвристические функции, сокращение перебора, генетические алгоритмы…
Слушатель понимает схемы работы эвристических алгоритмов, способен реализовать многие эвристические алгоритмы.
Результат
Общие итоги
1 урок
24
— Общий обзор изученного материала.
Слушатель понимает, в каком направлении двигаться дальше.
Результат
Список уроков — продвинутый уровень