Бакалавриат
2018/2019
Алгоритмы: дизайн и анализ
Статус:
Курс обязательный (Бизнес-информатика)
Направление:
38.03.05. Бизнес-информатика
Когда читается:
2-й курс, 4 модуль
Формат изучения:
с онлайн-курсом
Преподаватели:
Демкин Валерий Матвеевич
Язык:
русский
Кредиты:
3
Программа дисциплины
Аннотация
Настоящая дисциплина относится к циклу профессиональных дисциплин и блоку дисциплин по выбору. Изучается на 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