Полная программа
Продвинутый уровень
Курс «Алгоритмы и структуры данных»

Содержание курса
— Фундаментальные структуры данных и алгоритмы работы с ними
— Примерный состав стандартной библиотеки языков программирования
В результате обучения слушатель будет:
Процесс обучения
На каждом уроке будут рассмотрены необходимые теоретические вопросы и множество практических примеров. На каждом уроке будет получать практические задания для закрепления материала.
Знать:
— Применять их при разработке программ
Уметь:
Соответствует односеместровому университетскому курсу по алгоритмам и структурам данных.
Список уроков
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
— Длинные числа.
— Обзор изученного материала. Литература и дополнительные материалы.
Слушатель понимает, в каком направлении двигаться дальше.
Результат
16
Сортировки
~ 2 - 3 урока
— Шелла, быстрая, поразрядная.
Результат
Слушатель понимает принципы и способен реализовать данные алгоритмы.
17
Строки
~ 2 - 4 урока
— Сложные алгоритмы поиска строк.
— Редакционное расстояние
Результат
Сложные алгоритмы поиска строк Редакционное расстояние.
18
Деревья
~ 2 - 4 урока
— Балансированные деревья.
— В-деревья.
Результат
Слушатель знает устройство балансированных деревьев (в том числе RB-tree), понимает работу алгоритмов, может реализовать некоторые.
19
Графы
4 урока
— Остовные деревья, пути, раскраски…
— Интернет и графы
Результат
Слушатель понимает схемы работы, умеет реализовать многие алгоритмы (в том числе жадные алгоритмы поиска остовного дерева).
20
Сжатие данных
2-3 урока
— Хаффмен, Лемпель-Зив
Результат
Слушатель знает схемы работы и умеет реализовать некоторые алгоритмы.
21
Динамическое программирование
— 1-2 типичные практические задачи (связь с графами)
Результат
Слушатель понимает принцип динамического программирования и знает схемы реализации задач ДП.
22
NP-трудные задачи
— Задача коммивояжера (связь с графами)
Результат
Слушатель понимает разницу между Р и NP, умеет реализовать алгоритмы полного перебора (исчерпывающего поиска).
1-2 урока
23
Эвристические алгоритмы ИИ
— Поиск в пространстве состояний, эвристические функции, сокращение перебора, генетические алгоритмы…
Результат
Слушатель понимает схемы работы эвристических алгоритмов, способен реализовать многие эвристические алгоритмы.
2-3 урока
24
Общие итоги
— Общий обзор изученного материала.
Результат
Слушатель понимает, в каком направлении двигаться дальше.
1 урок
Если у вас остались вопросы, и вы не знаете, подходит ли курс лично вам, заполните форму, мы свяжемся с вами и ответим на все ваши вопросы.
Поможем с выбором
Отправляя заявку, я соглашаюсь на обработку персональных данных