Бакалавриат
2022/2023
Алгоритмы и структуры данных
Статус:
Курс по выбору (Программная инженерия)
Направление:
09.03.04. Программная инженерия
Кто читает:
Департамент программной инженерии
Где читается:
Факультет компьютерных наук
Когда читается:
2-й курс, 1, 2 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для своего кампуса
Преподаватели:
Бессмертный Александр Игоревич,
Нестеров Роман Александрович,
Шершаков Сергей Андреевич
Язык:
русский
Кредиты:
4
Контактные часы:
60
Программа дисциплины
Аннотация
Учебный курс «Алгоритмы и структуры данных» предлагается студентам бакалавриата по направлению «Программная инженерия» (код 09.03.04) на факультете компьютерных наук Национального исследовательского университета — Высшая Школа экономики (НИУ ВШЭ). Курс относится к обязательным предметам (блок/базовый модуль Б.Пр.Б, Б.Пр – Профильные дисциплины рабочего учебного плана на 2022–2023 учебный год). Курс двухмодульный (модули 1 и 2).
Программа учебной дисциплины подготовлена для преподавателей, ответственных за курс (а также преподавателей смежных дисциплин), учебных ассистентов, слушателей курса (студентов), зачисленных на курс, а также экспертов и официальных лиц, осуществляющих аккредитацию.
Курс посвящен основам проектирования и анализа алгоритмов. Он также включает в себя обучение фундаментальным структуры данных, а так же их реализации на основе стандартной библиотеки C++ (STL). Курс включает блок тем, посвященных теории автоматов, регулярных языков и грамматик, а также основам теории сложности.
Лекции и практические занятия тесно взаимосвязаны. Лекции в первую очередь предназначены для знакомства с новыми темами, тогда как практические занятия предназначены для решения конкретных задач — аналитически, а также путем кодирования программы на языке С++.
Цель освоения дисциплины
- Изучить принципы построения алгоритмов
- Научиться анализировать сложность алгоритма с точки зрения времени (временная) и памяти (пространственная)
- Изучить принципы проектирования базовых, а также некоторых продвинутых структур данных
- Получить практический опыт в реализации алгоритмов и структур данных в виде C++-приложений, а также применять их для решения специализированных задач
- Изучить базовые концепции теории автоматов, регулярных языков и грамматик
- Получить практические навыки построения конечных автоматов и регулярных выражений
Планируемые результаты обучения
- Основные концепции и методы построения алгоритмов.
- Навыки проектирования структур данных с использованием C++.
- Подходы к анализу сложности алгоритмов по времени и памяти.
- Навыки построения модели программ и процессов в виде конечных автоматов и регулярных выражений.
- Навыки работы в команде с использованием инструментов совместной работы.
- Навыки презентации.
- Навыки написания отчетов и технической документации, в том числе быстро изменяющейся документации с использованием вики и других специальных инструментов.
- Навыки самоанализа и экспертной оценки.
Содержание учебной дисциплины
- Введение
- Асимптотический анализ сложности
- Анализ сложности рекурсивных алгоритмов
- Анализ сложности рекурсивных алгоритмов (продолжение)
- Рандомизированные алгоритмы
- Теорема о нижней оценке сортировки
- Бинарные деревья
- Сбалансированные бинарные деревья поиска
- Амортизационные анализ сложности алгоритмов
- Хеширование
- Вероятностные структуры данных
- Теория сложности-1
- Теория сложности-2
- Теория сложности-3
- Теория сложности-4
Промежуточная аттестация
- 2022/2023 учебный год 1 модульВ 1 модуле выставляется оценка по результатам накполенных баллов ОА. Накопленная оценка ОА рассчитывается следующим образом: OA = min[(10 * (RP + BP) / RPmax), 10], где RP - количество заработанных "обычных" баллов (домашние задания в системе Я.Контест, тесты на семинаре, контрольная работа) BP - количество заработанных "бонусных" баллов (дополнительные домашние задания в системе Я.Контест, активность на лекциях).
- 2022/2023 учебный год 2 модульНакопленная оценка ОА рассчитывается следующим образом: OA = min[(10 * (RP + BP) / RPmax), 10], где RP - количество заработанных "обычных" баллов (домашние задания в системе Я.Контест, тесты на семинаре, контрольная работа) BP - количество заработанных "бонусных" баллов (дополнительные домашние задания в системе Я.Контест, активность на лекциях).
