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

Бакалавриат 2020/2021

Статус: Курс обязательный (Бизнес-информатика)

Направление: 38.03.05. Бизнес-информатика

Кто читает: Кафедра информационных систем и технологий (Нижний Новгород)

Где читается: Факультет информатики, математики и компьютерных наук (Нижний Новгород)

Когда читается: 2-й курс, 3 модуль

Формат изучения: без онлайн-курса

Охват аудитории: для своего кампуса

Преподаватели: Шутов Алексей Александрович

Язык: русский

Кредиты: 3

Контактные часы: 32

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

Аннотация

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

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

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

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

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

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