• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Магистратура 2022/2023

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

Статус: Курс по выбору (Современные компьютерные науки)
Направление: 01.04.02. Прикладная математика и информатика
Когда читается: 1-й курс, 1, 2 модуль
Формат изучения: без онлайн-курса
Охват аудитории: для всех кампусов НИУ ВШЭ
Прогр. обучения: Современные компьютерные науки
Язык: русский
Кредиты: 6
Контактные часы: 56

Программа дисциплины

Аннотация

"Курс дает базовые знания в области алгоритмов и структур данных. В явном виде они, может быть, не пригодятся, но очень важны для понимания работы библиотек, алгоритмов и языков программирования. Домашние задания по курсу закрепляют полученные знания и воспитывают хороший стиль написания кода, который позволяет избежать стандартных, но от этого ничуть не менее распространенных даже у опытных разработчиков, ошибок."
Цель освоения дисциплины

Цель освоения дисциплины

  • Цель курса — обучить основам алгоритмического программирования, привить практические навыки решения задач с помощью базовых алгоритмов и структур данных, сформировать правильное представление о времени работы и эффективности различных алгоритмов и структур данных.
Планируемые результаты обучения

Планируемые результаты обучения

  • Иметь представление о быстрых методах поиска k-й порядковой статистики
  • Иметь представление о задачах LCA и RMQ и об связи между ними
  • Иметь представление о кучах. Уметь использовать кучи для решения практических задач
  • Иметь представление о персистентных структурах данных
  • Иметь представление об основных алгоритмах сортировки. Понимать их преимущества и недостатки.
  • Иметь представление об основных структурах данных
  • Иметь представления о хэш-функциях и их свойствах. Уметь выбирать хэш-функцию для работы с заданным типом данных.
  • Уметь интерпретировать практические задачи в терминах теории графах, решать эти задачи с использованием графовых алгоритмах
  • Уметь находить кратчайшие пути в графах
  • Уметь обходить графы в ширину и в глубину
  • Уметь строить и эффективно использовать деревья поиска, выбирать правильную стратегию балансировки
  • Уметь строить остовные деревья для графов.
  • Уметь устранять коллизии при использовании хэш-таблиц
  • Уметь эффективно реализовывать структуры данных в виде структур на языке С++
  • Понимать устройство массивов переменного размера.
  • Уметь оценивать сложность алгоритмов и объём дополнительной памяти.
Содержание учебной дисциплины

Содержание учебной дисциплины

  • Введение
  • Введение в структуры данных
  • Сортировки
  • Кучи
  • Хэширование
  • Графы
  • Деревья поиска
  • Кратчайшие пути в графах
  • LCA & RMQ
  • Графы: продвинутые темы
Элементы контроля

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

  • неблокирующий Домашняя работа 1
  • неблокирующий Домашняя работа 2
  • неблокирующий Экзамен
Промежуточная аттестация

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

  • 2022/2023 учебный год 2 модуль
    0.3 * Домашняя работа 1 + 0.3 * Домашняя работа 2 + 0.4 * Экзамен
Список литературы

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

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

  • Комбинаторика и теория графов : учеб. пособие, Кочетков, Ю. Ю., 2009

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

  • Теория графов : учеб. пособие для втузов, Белов, В. В., 1976
  • Язык С#. Базовый курс : учеб. пособие для вузов, Подбельский, В. В., 2013
  • Язык С#. Решение задач : учеб. пособие для вузов, Подбельский, В. В., 2014