• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Бакалавриат 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
Элементы контроля

Элементы контроля

  • неблокирующий Накопленная оценка за 1 модуль
  • неблокирующий Накопленная оценка за курс
Промежуточная аттестация

Промежуточная аттестация

  • 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 - количество заработанных "бонусных" баллов (дополнительные домашние задания в системе Я.Контест, активность на лекциях).
Список литературы

Список литературы

Рекомендуемая основная литература

  • Алгоритмы. Построение и анализ : пер. с англ., Кормен Т., Лейзерсон Ч., 2012

Рекомендуемая дополнительная литература

  • Введение в теорию автоматов, языков и вычислений, Хопкрофт, Д. Э., 2016

Авторы

  • Меликян Алиса Валерьевна
  • Нестеров Роман Александрович
  • Петрухина Анастасия Сергеевна
  • Родригес Залепинос Рамон Антонио -