Бакалавриат
2023/2024
Алгоритмы и структуры данных
Статус:
Курс обязательный (Прикладная математика и информатика)
Направление:
01.03.02. Прикладная математика и информатика
Когда читается:
2-й курс, 1, 2 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для своего кампуса
Преподаватели:
Пономаренко Александр Александрович
Язык:
русский
Кредиты:
4
Контактные часы:
56
Программа дисциплины
Аннотация
Ресурсы вычислительной техники конечны. Вместе с тем, существует масса способов, как можно запрограммировать компьютер на решение одной задачи. При этом один алгоритм может требовать меньшее число вычислительных ресурсов чем другой. Данный курс должен помочь студенту освоить подходы к построению эффективных алгоритмов для решения широкого спектра практических задач.
Цель освоения дисциплины
- знать основные структуры данных (список, дерево, хеш-таблицы, графы), базовые алгоритмы (поиск в глубину, поиск в ширину, принцип разделяй и властвуй, динамическое программирование, поиск с отсечением, генерирование комбинаторных объектов).
- развить алгоритмическое мышление
- овладеть навыками программирования на языке C++ в процессе реализации основных вычислительных алгоритмов и структур данных
Планируемые результаты обучения
- Владеет методом "поиск в глубину"
- Владеет методом "поиск в ширину"
- Знает различные формализации понятия алгоритма.
- Понимает и умеет реализовывать "двоичное дерево"
- Понимает и умеет реализовывать различные методы хэширования
- Понимает когда можно использовать "жадные" алгоритмы.
- Решает задачи методом динамического программирования
- Умеет использовать метод динамического программирования
- Умеет использовать нотацию большого О
- Умеет оценивать вычислительную сложность алгоритмов
- Умеет реализовывать алгоритмы поиска минимального остова, определения изоморфноти графов
- Умеет реализовывать алгоритмы построения выпуклой оболочки и вращения геометрических фигур
- Умеет реализовывать базовые алгоритмы на графах
- Умеет реализовывать различные комбинаторные объекты
- Умеет реализовывать рекурсивные алгоритмы
Содержание учебной дисциплины
- Понятие и свойство алгоритма. Способы записи алгоритма. Различные формализации понятия алгоритма.
- Сложность алгоритмов. Классы алгоритмов.
- Поиск в ширину. Поиск в глубину. Рекурсия.
- Двоичные деревья.
- Хеширование
- Построение различных комбинаторных объектов
- Жадные алгоритмы
- Динамическое программирование
- Динамическое программирование – разные задачи.
- Алгоритмы на графах
- Алгоритмы на графах – 2
- Геометрические задачи
Элементы контроля
- Задачи по теме "Поиск в ширину"Задачи в формате ICPC
- Задачи по теме "Хэш-таблицы"Задачи в формате ICPC
- Задачи по теме "Сортировки"Задачи в формате ICPC
- Задачи по теме "Динамическое программирование"
- Задачи по теме "Алгоритмы на графах"Задачи в формате ICPC
- Задачи по теме "Геометрические задачи"Задачи в формате ICPC
Промежуточная аттестация
- 2023/2024 учебный год 2 модуль0.166 * Задачи по теме "Алгоритмы на графах" + 0.166 * Задачи по теме "Геометрические задачи" + 0.166 * Задачи по теме "Динамическое программирование" + 0.166 * Задачи по теме "Поиск в ширину" + 0.17 * Задачи по теме "Сортировки" + 0.166 * Задачи по теме "Хэш-таблицы"
Список литературы
Рекомендуемая основная литература
- Алгоритмы : построение и анализ, 2-е изд., 1290 с., Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К., 2012
- Алгоритмы : построение и анализ, пер. с англ., 3-е изд., 1323 с., Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К., 2018
Рекомендуемая дополнительная литература
- Апанасевич С.А. - Структуры и алгоритмы обработки данных. Линейные структуры: учебное пособие - Издательство "Лань" - 2019 - ISBN: 978-5-8114-3366-7 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/113934