• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Algorithms and Data Structures

2021/2022
Учебный год
ENG
Обучение ведется на английском языке
3
Кредиты

Преподаватель

Course Syllabus

Abstract

The course "Algorithms and Data Structures" introduces students to basic algorithms, complexity theories, and data structures. The course covers the issues of data search, data storage, construction, analysis of algorithms and their use for the effective solution of various tasks.
Learning Objectives

Learning Objectives

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

Expected Learning Outcomes

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

Course Contents

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

Assessment Elements

  • non-blocking Домашние задания
  • non-blocking Итоговый проект
Interim Assessment

Interim Assessment

  • Interim assessment (4 module)
    0.6 * Домашние задания + 0.4 * Итоговый проект
Bibliography

Bibliography

Recommended Core Bibliography

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

Recommended Additional Bibliography

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