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

2020/2021

Учебный год

RUS

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

8

Кредиты

Кто читает:

Департамент программной инженерии

Статус:

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

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

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

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

Бессмертный Александр Игоревич

Бузулуков Алексей Максимович

Варгулёв Александр Сергоевич

Горденко Мария Константиновна

Рахмановский Андрей Дмитриевич

Родригес Залепинос Рамон Антонио

Терлыч Никита Андреевич

Топтунов Александр Алексеевич

Ульянов Михаил Васильевич

Чуйкин Николай Константинович

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

Аннотация

Алгоритмы и структуры данных являются основой для любой программной системы: распределенной системы, мобильного приложения, базы данных, web приложения. В данном курсе студент освоит основные структуры данных и алгоритмы, которые послужат фундаментом для всех дальнейших знаний в области компьютерных наук и программной инженерии.

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

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

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

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

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

• Основные понятия
  Определение структуры данных. АТД (абстрактный тип данных). Аналогия с математическими объектами (множество, отображение, отношение и другие объекты). Цели и причины разработки различных структур данных (для чего они нужны и почему их много?): типы данных (data types), нагрузки (workload), архитектура устройств хранения данных (architecture), параллельный доступ (parallel access), тип носителя информации (storage type). Области и примеры использования структур данных (базы данных, операционные системы, и другие области). Подходы к оценке структур данных (стоимость операций/время выполнения, объем занимаемой памяти). Рост функций, асимптотические обозначения, стандартные функции и обозначения, сравнение функций. Общепринятые соглашения по определению алгоритмов (вход, выход, обозначения, псевдокод). Размер входа; худшее, среднее и лучшее время работы алгоритма; порядок роста (линейный, квадратичный, экспоненциальный и другие стандартные определения). О пользе быстрых алгоритмов, примеры асимптотического анализа алгоритмов. Эффективность алгоритмов и целесообразность их выбора в зависимости от размера входных данных. Организация курса, формы контроля и оценки знаний. Список рекомендованной литературы по курсу.
• Элементарные структуры данных и С++
  Стек (stack), очередь (queue), "дек" (очередь с двумя концами / Deque) и операции над ними. Списки (односвязный, двусвязный), голова и хвост списка. Приоритетная очередь. Поиск в списке, добавление и удаление элементов. Особенности реализации указанных структур данных. Объектно-ориентированное программирование и С++. Классы, шаблоны. Стек как пример контейнера, Динамически выделяемая память, указатели. Выделение и освобождение памяти. Стандартная библиотека шаблонов (STL) – введение. Контейнер std::vector (модель динамического массива). Шаблонные классы std::array, std::list и std::forward_list. Шаблонный класс std::deque и адаптер std::stack.
• Битовые карты (маски)
  Практическое использование битовых карт/масок (bitmaps): invisible join, database indexing, и другие примеры. Битовые карты (bitmaps): BBC, WAH, EWAH, PLWAH, CONCISE, VALWAH, SBH, Roaring и другие. Операции над bitmaps, преимущества bitmaps.
• Хэш таблицы
  Хэш функции, хэш значения, коллизии, прямая адресация (open hashing), сцепление элементов (chaining). Коэффициент заполнения (load coefficient), равномерное хеширование (simple uniform hashing). Свойства хорошей хэш функции, способы построения хеш функций, двойное хэширование, примеры хэш функций. Фильтр Блума (Bloom Filter), Cuckoo filter и их разновидности. Хэш таблицы в стандартной библиотеке C++. Шаблонный класс std::unordered_map.
• Деревья
  Формальное определение множества, пары и дерева (краткая математическая справка). Деревья и их представление. Двоичные деревья, деревья с произвольным ветвлением. Преобразование дерева в двоичное дерево. Двоичное дерево поиска. Свойство упорядоченности. Способы обхода двоичного дерева поиска. Поиск заданного элемента в двоичном дереве поиска, поиск минимума и максимума, поиск следующего и предыдущего элемента. Добавление и удаление элементов в двоичном дереве поиска. Динамические множества с сохранением предыдущих версий. Устройство жесткого диска. B-деревья, R-деревья, деревья отрезков (промежутков): определение, предназначение, основные операции, разновидности этих деревьев.
• Растровые структуры данных
• Пространственные структуры данных
  Особенности, обзор пространственных структур данных, R-дерево, кривые пространства, k2-tree и другие.
• Параллельные структуры данных
  Параллельные алгоритмы и их особенности. Список с пропусками (skip list). Параллельный список с пропусками. Parallel RB-Tree, BWTree.
• Распределенные структуры данных
  DHT, Distributed Hash Tables. Распределенные алгоритмы и их особенности. Chord. Chubby и другие структуры.
• Современные тенденции в разработке структур данных
  Машинное обучение для построения структур данных. Learned data structures. Новые структуры данных для новых типов памяти (e.g., NVM). BW-дерево (Buzzword Tree). Распределенные структуры данных. Гибридные структуры данных.
• Дополнительные главы
  Кэш, алгоритмы кэширования. Красно-черные деревья, 2-3 деревья, 2-3-4 деревья, LSM дерево (Log-structured merge-tree).
• Понятие алгоритма. Формализм Э.Л. Поста. Алгоритм как финитный 1-процесс
  История теории алгоритмов. Понятие алгоритма. Формализация понятия алгоритма. Формализм Э.Л. Поста. Пространство символов и примитивные операции в машине Поста, алгоритм как финитный 1-процесс, доставляющий решение общей проблемы, гипотеза Поста.
• Основная терминология и обозначения в анализе ресурсной эффективности алгоритмов
  Вход как эквивалент конкретной проблемы по Посту. Длина входа как функция от мощности множества входных данных. Оценки качества алгоритма. Понятие трудоёмкости. Трудоёмкость в лучшем, худшем и среднем случаях. Ёмкостная эффективность.
• Классификация алгоритмов по трудоёмкости
  Влияние длины входа и значений на трудоёмкость. Классификация алгоритмов по характеристическим особенностям множества исходных данных, определяющим вид функции трудоемкости. Классы N, PR, NPR. Примеры алгоритмов в рамках классификации. Дополнительная детализация классов. Особенности анализа алгоритмов по классам.
• Анализ NPR алгоритмов методом классов входных данных
  Метод классов входных данных. Особенности его применения. Задача сортировки трёх чисел по месту. Классы входных данных, порождаемые этой задачей. Алгоритмы и их анализ методом классов входных данных.
• Метод вероятностного анализа для получения трудоёмкости в среднем
  Собственно метод вероятностного анализа. Алгоритм сортировки вставками и анализ его трудоёмкости в среднем. Замечания об экспериментальном анализе алгоритмов по трудоёмкости. Выборочное среднее и математическое ожидание. Определение необходимого числа экспериментов.
• Сравнительный анализ алгоритмов по трудоёмкости и решение задачи рационального выбора
  Методика сравнительного анализа алгоритмов и определение границ применимости по характеристикам исходных данных. Простейшие примеры сравнительного анализа для задачи сортировки — алгоритм сортировки вставками и сортировки методом индексов. Рациональный выбор в параметрическом пространстве.
• Сложность алгоритмов. Теоретическая нижняя граница сложности задачи
  Асимптотический анализ функций и основные обозначения. Сложность как асимптотическая оценка трудоёмкости в худшем случае. Теоретическая нижняя граница сложности задачи. Доказательство теоретической нижней границы для задачи сортировки сравнениями.
• Введение в теорию сложности вычислений. Основные сложностные классы задач
  Исторический очерк теории сложности вычислений. Сложностные классы задач. Определение и взаимосвязь классов P и NP. Определение и примеры NP-полных задач.
• Временная эффективность и особенности перехода к временным оценкам
  Переход к пооперационному анализу трудоёмкости алгоритмов. Построение временных оценок. Методы перехода к временным оценкам на основе функции трудоемкости. Особенности измерения времени выполнения программной реализации алгоритма.
• Рекурсивные алгоритмы — Особенности реализации и анализа
  Рекурсивные функции и рекурсивные алгоритмы. Рекурсивная реализация алгоритмов. Анализ механизма рекурсивного вызова. Дерево рекурсивных вызовов. Простейшие примеры рекурсивных алгоритмов.
• Разработка алгоритмов методом декомпозиции и особенности его применения
  Собственно метод декомпозиции. Рекурсивные алгоритмы как реализация метода декомпозиции. Методы анализа рекурсивных алгоритмов. Теорема Бентли-Хакен-Сакса и её применение для получения сложностных оценок алгоритмов. разработанных методом декомпозиции. Анализ рекурсивных алгоритмов методом прямого подсчета вершин рекурсивного дерева. Пример анализа — алгоритм сортировки слиянием.
• Анализ рекурсивных алгоритмов методом подсчёта вершин дерева рекурсии
  Анализ рекурсивных алгоритмов методом прямого подсчета вершин рекурсивного дерева. Пример анализа — алгоритм сортировки слиянием. Отличие детального анализа от асимптотического — граница применимости алгоритма сортировки вставками.
• Рекурсивный алгоритм возведения в степень
  Метод повторного возведения в квадрат. Функция beta1(n). Рекурсивный и итерационный алгоритм быстрого возведения в степень и их анализ с использованием функции beta1(n).
• Задачи умножения длинных целых чисел и умножения матриц
  Задача умножения длинных целых чисел. Гипотеза Колмогорова. Алгоритм умножения в столбик. Алгоритм Карацубы. Классический алгоритм умножения матриц. Алгоритм Штрассена.
• Динамическое программирование. Задача оптимальной упаковки (задача о рюкзаке)
  Основы метода динамического программирования. Пошаговая оптимизация. Классическая задача упаковки и основное уравнение Беллмана для точного решения задачи упаковки — табличная реализация функционального уравнения.
• Рекурсивный алгоритм метода динамического программирования для задачи упаковки
  Рекурсивная реализация алгоритма Беллмана для задачи упаковки. Параметризация задачи упаковки по среднему объёму грузов. Структура рекурсивного дерева и подсчет количества вершин порождённого дерева рекурсии. Оценка сложности алгоритма. Сравнительный анализ табличного и рекурсивного алгоритмов. Варианты построения комбинированного алгоритма.

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

• Контрольная работа (CW)
• Домашнее задание (HW)
• Экзамен (EX)
• Инициативная тема (IT)
• Домашнее задание (ДЗ)
• Работа на семинаре (ПЗ)
• Экзамен (ЭКЗ)
  Часть 2 дисциплины (3-4 модули) Экзамен устный в Zoom без прокторинга. Экзамен проходит целый день, студенты выступают по очереди. Технические требования: web-камера, микрофон, наушники / колонки, Zoom.
• Мини тесты по темам семинаров. Реализация алгоритмов на семинаре
  Часть 2 дисциплины (3-4 модули)
• Самостоятельная работа - решение заданий контеста
  Часть 2 дисциплины (3-4 модули)
• Контрольное домашнее задание
  Часть 2 дисциплины (3-4 модули)

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

• Промежуточная аттестация (2 модуль)
  Вклад
  CW 20% HW 60% EX 20% HW – средняя оценка за домашние работы CW – оценка за контрольную работу EX – оценка за экзамен Накопленная оценка O_A вычисляется следующим образом: O_A=min((CW+HW)×10/80, 10), CW и HW - проценты Оценка за курс вычисляется следующим образом: O_C=O_A×0.8+EX×0.2 Во время лекций студентам допускается выступать с небольшими презентациями (такая возможность, тема и время согласуются с лектором заранее), которые дают дополнительные баллы выступающему (до 0.5 от накопленной оценки). Сайт курса edu.gis.land/ds2020 является неотъемлемой частью данной программы для 1-2 модулей. На сайте курса могут уточняться и дополняться программа курса, темы, литература, правила курса, домашние задания и любые другие материалы курса. Актуальная информация содержится на сайте курса. В случае расхождения с информацией в ЛМС, предпочтение следует отдавать сайту курса. При вычислении процентов, значения остаются в своей изначальной форме. При вычислении оценок (0..10), происходит стандартное математическое округление. Таким образом, на определенных этапах округляются только O_A, EX, и O_C. Студенты, которые получат O_A>=8, по своему желанию могут быть освобождены от экзамена и получить O_A в качестве оценки за курс. К программному коду применяются здравые критерии оценки такого вида задания, которые во многим общи для дисциплин, в которых необходимо программировать. За творческий подход к выполнению задания могут начисляться баллы. По желанию студент может выбрать индивидуальную образовательную траекторию, в которую входит научная либо проектная работа, участие в конференциях, конкурсах и другие виды деятельности. Индивидуальная образовательная траектория должна заранее согласовываться с преподавателем. Сроки и объемы работ должны заранее обговариваться и согласовываться с преподавателем. Оценивание работы индивидуальной образовательной траектории выполняется по правилам, обговариваемым со студентом. В таком случае, формула O_C и/или O_A может быть изменена с добавлением IT, вес которого обговаривается со студентом заранее. Преподаватели/ассистенты оставляют за собой право задавать вопросы во время защиты работ, чтобы обеспечить понимание материала студентом, написанного исходного кода, подлинность исходного кода. Вопросы также могут основываться на материалах, которые были освещены на лекциях/семинарах. Преподаватель/ассистент оценивает работы в соответствии с процентом отвеченных вопросов, количеством выполненной работы, точностью исходного кода и приложением в целом, правильностью приложения и другими здравыми критериями, применимыми к данным видам работы. Студент имеет только 3 попытки дать правильный ответ на поставленный преподавателем вопрос, включая первый ответ студента. Остальные детали оценивания сообщаются на лекциях/семинарах/по почте в зависимости от задания. Отсутствие у студента бумаги, пишущего предмета, ноутбука, зарядки от ноутбука или других необходимых принадлежностей не является причиной освобождения студента от задания и может привести к оценке в 0 баллов за задание.
• Промежуточная аттестация (4 модуль)
  0.5 * Самостоятельная работа - решение заданий контеста + 0.5 * Экзамен (ЭКЗ)

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

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

• Информационная чувствительность компьютерных алгоритмов, Петрушин, В. Н., 2010
• Искусство программирования. Т.1: Основные алгоритмы, Кнут, Д. Э., 2011
• Искусство программирования. Т.2: Получисленные алгоритмы, Кнут, Д. Э., 2012
• Искусство программирования. Т.3: Сортировка и поиск, Кнут, Д. Э., 2012
• Ресурсно - эффективные компьютерные алгоритмы. Разработка и анализ : учеб. пособие для вузов, Ульянов, М. В., 2008
• С#. Программирование на языке высокого уровня : учебник для вузов, Павловская, Т. А., 2009
• Теория рекурсии для программистов, Головешкин, В. А., 2006

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

• Prabhu, C. S. R. (2019). Fog Computing, Deep Learning and Big Data Analytics-Research Directions. Singapore: Springer. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=1994845