Delivered at:: Department of Information Systems and Technologies (Faculty of Informatics, Mathematics, and Computer Science (HSE Nizhny Novgorod))

Course type:: Compulsory course

When:: 2 year, 3 module

Instructor

Shutov, Alexey A.

Полная версия программы учебной дисциплины Задать вопрос

Аннотация

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

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

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

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

Способен создавать и преобразовывать различные структуры данных
Способен создавать динамические структуры данных (списки, массивы, классы, структуры и пр.) и преобразовывать их между собой
Способен реализовать внутреннюю сортировку несколькими методам (пузырьковая, быстрая и пр.)
Способен оценить сложность алгоритма внутренней сортировки на основе 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 минут и более. При долговременном нарушении связи студент не может продолжить участие в экзамене. Процедура пересдачи аналогична процедуре сдачи.
Аудиторная работа
Самостоятельная работа
Экзамен
Экзамен проводится в письменной форме с использованием асинхронного прокторинга. Экзамен проводится на платформе 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 минут и более. При долговременном нарушении связи студент не может продолжить участие в экзамене. Процедура пересдачи аналогична процедуре сдачи.

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

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

Bachelor’s Programme 'Business Informatics'

Algorithms and Data Structures

Instructor

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

Аннотация

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

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

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

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

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

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

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

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