• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Бакалавриат 2019/2020

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

Статус: Курс обязательный (Программная инженерия)
Направление: 09.03.04. Программная инженерия
Когда читается: 2-й курс, 1-4 модуль
Формат изучения: без онлайн-курса
Преподаватели: Варгулёв Александр Сергоевич, Родригес Залепинос Рамон Антонио, Ульянов Михаил Васильевич, Шершаков Сергей Андреевич
Язык: русский
Кредиты: 8
Контактные часы: 132

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

Аннотация

Алгоритмы и структуры данных являются основой для любой программной системы: распределенной системы, мобильного приложения, базы данных, 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.
  • Хэш таблицы
    Хэш функции, хэш значения, коллизии, прямая адресация (open hashing), сцепление элементов (chaining). Коэффициент заполнения (load coefficient), равномерное хеширование (simple uniform hashing). Свойства хорошей хэш функции, способы построения хеш функций, двойное хэширование, примеры хэш функций. Фильтр Блума (Bloom Filter), Cuckoo filter и их разновидности. Хэш таблицы в стандартной библиотеке C++. Шаблонный класс std::unordered_map.
  • Деревья
    Формальное определение множества, пары и дерева (краткая математическая справка). Деревья и их представление. Двоичные деревья, деревья с произвольным ветвлением. Преобразование дерева в двоичное дерево. Двоичное дерево поиска. Свойство упорядоченности. Способы обхода двоичного дерева поиска. Поиск заданного элемента в двоичном дереве поиска, поиск минимума и максимума, поиск следующего и предыдущего элемента. Добавление и удаление элементов в двоичном дереве поиска. Динамические множества с сохранением предыдущих версий. Устройство жесткого диска. B-деревья, R-деревья, деревья отрезков (промежутков): определение, предназначение, основные операции, разновидности этих деревьев.
  • Современные тенденции в разработке структур данных
    Машинное обучение для построения структур данных. 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).
  • Задачи умножения длинных целых чисел и умножения матриц
    Задача умножения длинных целых чисел. Гипотеза Колмогорова. Алгоритм умножения в столбик. Алгоритм Карацубы. Классический алгоритм умножения матриц. Алгоритм Штрассена.
  • Динамическое программирование. Задача оптимальной упаковки (задача о рюкзаке)
    Основы метода динамического программирования. Пошаговая оптимизация. Классическая задача упаковки и основное уравнение Беллмана для точного решения задачи упаковки — табличная реализация функционального уравнения.
  • Рекурсивный алгоритм метода динамического программирования для задачи упаковки
    Рекурсивная реализация алгоритма Беллмана для задачи упаковки. Параметризация задачи упаковки по среднему объёму грузов. Структура рекурсивного дерева и подсчет количества вершин порождённого дерева рекурсии. Оценка сложности алгоритма. Сравнительный анализ табличного и рекурсивного алгоритмов. Варианты построения комбинированного алгоритма.
Элементы контроля

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

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

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

  • Промежуточная аттестация (2 модуль)
    Вклад<br /> LP 10% PP 5% CW 10% HW1 55% HW2 16% EX 20% LP – процент выполненных самостоятельных работ (отводится время до 10 минут во время лекции) во время лекций. PP – процент посещения студентом семинаров соответственно (0% ничего не посетил, 100% посетил все занятия). CW, HW1 и HW2 - средние оценки за все контрольные и домашние работы соответственно EX - оценка за экзамен Накопленная оценка O_A вычисляется следующим образом: O_A=min((LP+PP+CW+HW1+HW2)×10/80, 10) Оценка за курс вычисляется следующим образом: O_C=O_A×0.8+EX×0.2 Домашние задания, которые оцениваются HW2 не обязательны к выполнению, они введены для повышения накопленной оценки и в основном содержат задачи повышенной сложности. Оценки LP. Каждая самостоятельная работа оценивается максимум в 1 балл. Отметим, что студент может посетить лекцию, но выполнить самостоятельную работу на 0 баллов. Студент должен -- иметь при себе белый лист А4 для принтера (не из блокнота) -- вверху необходимо печатными буквами от руки указать свои ФИО -- непосредственно под своим ФИО от руки указать дату контрольной работы -- вверху справа необходимо указать свой номер из списка (список размещается в LMS) -- иметь ручку (можно две запасные) Рекомендация: заранее подготовить листики (ФИО, дата, номер), чтобы не тратить время на самостоятельной работе (иначе придется потратить время на оформление во время работы, которое выделено на решение задания). Отсутствие должным образом оформленной бумаги либо пишущей ручки повлечет за собой оценку 0 за задание. Пустые листики (без решения задания), неполные либо неверные ответы на задания будут оценены в 0 баллов. Писать необходимо четко, аккуратно и разборчиво, крупными буквами, иначе неразобранные письмена будут считаться отсутствующими, и работа будет оценена без них. Во время лекций студентам допускается выступать с небольшими презентациями (такая возможность, тема и время согласуются с лектором заранее), которые дают дополнительные баллы выступающему (до 0.5 от накопленной оценки). При вычислении процентов, значения остаются в своей изначальной форме. При вычислении оценок (0..10), происходит стандартное математическое округление. Таким образом, на определенных этапах округляются только O_A, EX, и O_C. Студенты, которые получат O_A>=8, по своему желанию могут быть освобождены от экзамена и получить O_A в качестве оценки за курс. К программному коду применяются здравые критерии оценки такого вида задания, которые во многим общи для дисциплин, в которых необходимо программировать. За творческий подход к выполнению задания могут начисляться баллы. По желанию студент может выбрать индивидуальную образовательную траекторию, в которую входит научная либо проектная работа, участие в конференциях, конкурсах и другие виды деятельности. Индивидуальная образовательная траектория должна заранее согласовываться с преподавателем. Сроки и объемы работ должны заранее обговариваться и согласовываться с преподавателем. Оценивание работы индивидуальной образовательной траектории выполняется по правилам, обговариваемым со студентом. В таком случае, формула O_C и/или O_A может быть изменена с добавлением IT, вес которого обговаривается со студентом заранее. Преподаватели/ассистенты оставляют за собой право задавать вопросы во время защиты работ, чтобы обеспечить понимание материала студентом, написанного исходного кода, подлинность исходного кода. Вопросы также могут основываться на материалах, которые были освещены на лекциях/семинарах. Преподаватель/ассистент оценивает работы в соответствии с процентом отвеченных вопросов, количеством выполненной работы, точностью исходного кода и приложением в целом, правильностью приложения и другими здравыми критериями, применимыми к данным видам работы. Студент имеет только 3 попытки дать правильный ответ на поставленный преподавателем вопрос, включая первый ответ студента. Остальные детали оценивания сообщаются на лекциях/семинарах/по почте в зависимости от задания. Если студент опаздывает на лекцию/семинар более чем на 20 минут, он считается отсутствующим. Запрещается использовать компьютеры, мобильные телефоны, Интернет на лекциях, если это явно не предусмотрено текущим заданием преподавателя. Будут вычитаться баллы из LP в случае нарушения правил. За непристойное поведение могут вычитаться баллы из LP и PP (критерии устанавливаются преподавателем согласно здравым культурным нормам поведения студентов в высшем учебном заведении). Во время экзамена запрещается выходить из аудитории. Отсутствие у студента бумаги, пишущего предмета, ноутбука, зарядки от ноутбука или других необходимых принадлежностей не является причиной освобождения студента от задания и может привести к оценке в 0 баллов за задание.
  • Промежуточная аттестация (4 модуль)
    0.15 * Контрольное домашнее задание + 0.025 * Мини тесты по темам семинаров. Реализация алгоритмов на семинаре + 0.325 * Самостоятельная работа - решение заданий контеста + 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