• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Algorithms and Data Structures

2019/2020
Academic Year
RUS
Instruction in Russian
6
ECTS credits
Delivered at:
Department of Information Systems and Technologies (Faculty of Informatics, Mathematics, and Computer Science (HSE Nizhny Novgorod))
Course type:
Elective course
When:
2 year, 3, 4 module

Instructor

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

Аннотация

Дисциплина предназначена для приобретения студентами навыков проектирования и применения различных структур данных и алгоритмов работы с ними. Изучение дисциплины «Алгоритмы и структуры данных» базируется на следующих дисциплинах: - Программирование; - Теоретические основы информатики.
Цель освоения дисциплины

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

  • Углубленное изучение основ алгоритмизации и структур данных
  • Овладение методами разработки и описания различных алгоритмов, связанных с управлением данными и применение полученных знаний для работы в избранной сфере деятельности
Планируемые результаты обучения

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

  • Способен создавать и преобразовывать различные структуры данных
  • Способен создавать динамические структуры данных (списки, массивы, классы, структуры и пр.) и преобразовывать их между собой
  • Способен реализовать внутреннюю сортировку несколькими методам (пузырьковая, быстрая и пр.)
  • Способен оценить сложность алгоритма внутренней сортировки на основе O-функций
  • Способен оценить сложность алгоритма сортировки на внешней памяти на основе O-функций
  • Реализует несколько алгоритмов сортировки на внешней памяти
  • Способен реализовать структуру дерева
  • Способен реализовать алгоритм обхода дерева
  • Способен реализовать структуру хэш-таблицы
  • Способен реализовать основные операции, связанные с поиском на основе хэш-таблиц (добавление, удаление, редактирование, поиск)
  • Реализует алгоритмы Хаффмана и LZW на текстовых данных
  • Способен реализовать одну из процедур поиска решения конкурсной задачи
Содержание учебной дисциплины

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

  • Тема 1: Введение, базовые структуры данных
    Разложение действия на элементарные части (структура действия). Порождение структуры операндов структурой действия. Рекурсия как средство повышения эффективности программирования и определяемая ею собственная структура операндов (векторы, матрицы и др., примеры структур). Структура алгоритмов и структура данных. Связь с математическим понятием структуры. Графический образ структуры. Переменные величины и схемы структур. Значения переменных структур и экземпляры схем. Элементы структуры, имена, значения. Основные и вспомогательные базисные множества и отношения в структуре. Структура машинной памяти. Примеры структур хранения данных. Вектор памяти. Массивы. Адресная арифметика как средство задания отношений в структуре хранения. Структуры хранения, операции над структурами и типы
  • Тема 2: Динамические структуры данных
    Переработка информации как преобразование структур данных. Преобразования, приводящие к рекурсивным отношениям исходных и результирующих структур. Динамические структуры - класс структур с частичным упорядочением (по включению) структур данных, примеры динамических структур (стеки, очереди, списки). Массивы. Динамические структуры и распределение памяти; средства поддержания динамической структуры. Выражение отношений программными средствами. Пример: структура типа стека и ее структура хранения. Сравнение структур хранения и хранения динамических структур. Статическое и динамическое распределение памяти. Управление памятью.
  • Тема 3: Внутренние сортировки
    Алгоритмы сортировок данных для внутренней памяти. Типы сортировок, анализ скорости работы сортировок, используемая память. Сравнение различных сортировок.
  • Тема 4: Внешние сортировки
    Алгоритмы сортировок данных для внешней памяти. Типы сортировок, анализ скорости работы сортировок, используемая память. Сравнение различных сортировок.
  • Тема 5: Алгоритмы поиска во внутренней памяти
    Понятие дерева поиска. Выполнение операций поиска, включения и исключения записей. Возможность выполнения операций без перепаковки памяти. Оценка эффективности выполнения операций. Анализ балансировки деревьев (возможность вырождения дерева поиска в линейный упорядоченный список). Сбалансированные и идеально сбалансированные деревья. Алгоритм вставки с сохранением балансировки дерева поиска. Красно-черные деревья, цифровые деревья поиска. Хэш-таблицы
  • Тема 6: Алгоритмы поиска во внешней памяти
    Понятие таблицы (ключ, тело, запись). Таблицы имен и адресов. Операции над таблицей: поиск, включение и исключение записей. Таблица как динамическая структура данных. Применение хэш-таблиц для поиска во внешней памяти. Применение деревьев для поиска во внешней памяти
  • Тема 7: Алгоритмы сжатия без потерь
    Применение сжатия данных, классификация алгоритмов. Алгоритмы Хаффмана и LZW.
  • Тема 8: Примеры конкурсных задач
    Анализ задач связанных со структурами данных и алгоритмами, применяемых на различных конкурсах и экзаменах.
Элементы контроля

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

  • неблокирующий Аудиторная работа
  • неблокирующий Самостоятельная работа
  • неблокирующий Экзамен
    Экзамен проводится в письменной форме с использованием асинхронного прокторинга. Экзамен проводится на платформе MS Teams (https://teams.microsoft.com), прокторинг на платформе Экзамус (https://hse.student.examus.net). К экзамену необходимо подключиться за 15 минут. На платформе Экзамус доступно тестирование системы. Компьютер студента должен удовлетворять следующим требованиям: https://elearning.hse.ru/data/2020/05/07/1544135594/Технические%20требования%20к%20ПК%20студента.pdf) Для участия в экзамене студент обязан: заранее зайти на платформу прокторинга, провести тест системы, включить камеру и микрофон, подтвердить личность. Во время экзамена студентам запрещено: общаться (в социальных сетях, с людьми в комнате), списывать. Кратковременным нарушением связи во время экзамена считается прерывание связи до 10 минут. Долговременным нарушением связи во время экзамена считается прерывание связи 10 минут и более. При долговременном нарушении связи студент не может продолжить участие в экзамене. Процедура пересдачи аналогична процедуре сдачи.
Промежуточная аттестация

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

  • Промежуточная аттестация (4 модуль)
    0.24 * Аудиторная работа + 0.36 * Самостоятельная работа + 0.4 * Экзамен
Список литературы

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

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

  • Алгоритмы и структуры данных: Учебник / Белов В.В., Чистякова В.И. - М.:КУРС, НИЦ ИНФРА-М, 2019. - 240 с.: - (Бакалавриат) - Режим доступа: http://znanium.com/catalog/product/978314

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

  • Апанасевич С.А. - Структуры и алгоритмы обработки данных. Линейные структуры: учебное пособие - Издательство "Лань" - 2019 - 136с. - ISBN: 978-5-8114-3366-7 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/113934