Алгоритмы: дизайн и анализ

2018/2019

Учебный год

RUS

Обучение ведется на русском языке

3

Кредиты

Кто читает:

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

Статус:

Курс обязательный

Когда читается:

2-й курс, 4 модуль

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

Демкин Валерий Матвеевич

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

Аннотация

Настоящая дисциплина относится к циклу профессиональных дисциплин и блоку дисциплин по выбору. Изучается на 2-м курсе. Дисциплина представляет собой on-line курс: Алгоритмы: дизайн и анализ /Algorithms: Design and Analysis Платформа: coursera Ссылка: https://www.coursera.org/learn/algorithm-design-analysis Название высшего учебного заведения: Стэнфордский университет

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

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

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

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

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

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

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

• Экзамен
• Самостоятельная работа

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

• Промежуточная аттестация (4 модуль)
  0.3 * Самостоятельная работа + 0.7 * Экзамен

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

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

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

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

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