• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Algorithms and Data Structures

2019/2020
Academic Year
RUS
Instruction in Russian
5
ECTS credits
Course type:
Elective course
When:
1 year, 1, 2 module

Instructor

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

Аннотация

"Курс дает базовые знания в области алгоритмов и структур данных. В явном виде они, может быть, не пригодятся, но очень важны для понимания работы библиотек, алгоритмов и языков программирования. Домашние задания по курсу закрепляют полученные знания и воспитывают хороший стиль написания кода, который позволяет избежать стандартных, но от этого ничуть не менее распространенных даже у опытных разработчиков, ошибок."
Цель освоения дисциплины

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

  • Цель курса — обучить основам алгоритмического программирования, привить практические навыки решения задач с помощью базовых алгоритмов и структур данных, сформировать правильное представление о времени работы и эффективности различных алгоритмов и структур данных.
Планируемые результаты обучения

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

  • Уметь оценивать сложность алгоритмов и объём дополнительной памяти.
  • Понимать устройство массивов переменного размера.
  • Иметь представление об основных структурах данных
  • Иметь представление о персистентных структурах данных
  • Уметь эффективно реализовывать структуры данных в виде структур на языке С++
  • Иметь представление об основных алгоритмах сортировки. Понимать их преимущества и недостатки.
  • Иметь представление о быстрых методах поиска k-й порядковой статистики
  • Иметь представление о кучах. Уметь использовать кучи для решения практических задач
  • Иметь представления о хэш-функциях и их свойствах. Уметь выбирать хэш-функцию для работы с заданным типом данных.
  • Уметь устранять коллизии при использовании хэш-таблиц
  • Уметь обходить графы в ширину и в глубину
  • Уметь интерпретировать практические задачи в терминах теории графах, решать эти задачи с использованием графовых алгоритмах
  • Уметь строить и эффективно использовать деревья поиска, выбирать правильную стратегию балансировки
  • Уметь находить кратчайшие пути в графах
  • Иметь представление о задачах LCA и RMQ и об связи между ними
  • Уметь строить остовные деревья для графов.
Содержание учебной дисциплины

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

  • Введение
    Время и память как основные ресурсы. Модели вычислений: RAM, разрешающие деревья. Сложность на заданном входе, сложность в худшем случае, сложность в среднем случае, рандомизированная сложность. Нижняя оценка на число сравнений при сортировке в модели разрешающих деревьев.Учетная стоимость операций, метод потенциалов, банковский метод анализа сложности. Анализ двоичного счетчика. Массивы переменного размера.
  • Введение в структуры данных
    Реализация очереди на паре стеков с константной учетной сложностью. Динамические минимумы-максимумы в стеках и очередях. Персистентные структуры данных. Видны персистентности. Модель вычислений Pointer Machine. Персистентные стеки.
  • Сортировки
    "Сортировка слиянием (Merge-Sort). Inplace-разновидность. Galloping в бинарном поиске. Оптимальное по числу сравнений слияние двух упорядоченных последовательностей. Задача о длиннейшей возрастающей подпоследовательности. Быстрая сортировка (Quick-Sort). Способы выбора разделяющего элемента. Элиминация хвостовой рекурсии. Порядковые статистики. Рандомизированный алгоритм Quick-Select. Детермининированный алгоритм поиска (метод ""медианы медиан"")."
  • Кучи
    Кучи: основные определения и свойства. Операции Sift-Down и Sift-Up. Бинарные и k-ичные кучи. Построение кучи за линейное время. Алгоритмы сортировки Heap-Sort и Intro-Sort. Частичная сортировка с помощью кучи и поиска порядковой статистики.
  • Хэширование
    "Хеш-функции. Коллизии. Разрешение коллизий методом цепочек. Гипотеза простого равномерного хеширования, оценка средней длины цепочки. Универсальные семейства хеш-функций, оценка средней длины цепочки. Построение универсального семейства для целочисленных ключей. Совершенные хеш-функции. Построение совершенной хеш-функции методом двухуровненого хеширования. Построение совершенной хеш-функции методом ациклических графов. Фильтр Блюма (Bloom filter). Оценка вероятности ложноположительного срабатывания. Locality-sensitive hashing. Семейства locality-sensitive хеш-функций и общий алгоритм. Семейство для расстояния Хэмминга. Потоковые алгоритмы. Задача подсчета количества вхождений в потоке. Turnstile и cash-register модели. Count-min sketch. Алгоритм Misra-Gries. Locality-sensitive hashing. Семейства для углового расстояния, евклидова расстояния. Asymmetric LSH - приближенный поиск точки в множестве с максимальным скалярным произведением с точкой запроса."
  • Графы
    "Графы: основные определения и способы представления в алгоритмах. Обход в ширину. Обход в глубину. Лемма о белом пути. Проверка на ацикличность и топологическая сортировка. Сильно связные компоненты и топологическая сортировка конденсации. Классификация ребер при обходе в глубину в ориентированном и неориентированном графах. Точки сочленения: определение и нахождение с помощью обхода в глубину. Эйлеров обход: проверка существования и построение с помощью обхода в глубину."
  • Деревья поиска
    "Деревья поиска. Вставка и удаление элементов. Inorder-обход дерева. Обход Морриса для бинарных деревьев. Красно черные деревья: определение и основные свойства. Реализация операций вставки для красно-черного дерева. Splay-деревья. Операция splay: zig, zig-zig и zig-zag шаги. Реализация операций вставки, удаления, слияния и разделения для splay-деревьев. Дучи (treaps). Единственность дучи для заданного набора различных ключей и приоритетов. Логарифмическая оценка матожидания высоты дучи. Операции слияния и разделения для дуч. Операции вставки и удаления элементов для дуч."
  • Кратчайшие пути в графах
    "Кратчайшие пути в графах. Оценки расстояний и их релаксация. Алгоритмы БеллманаФорда, Флойда и Дийкстры. Потенциалы. Критерий консервативности длин. Алгоритм Флойда. Алгоритм Джонсона. Двухсторонний алгоритм Дийкстры. Алгоритм A*."
  • LCA & RMQ
    Задачи LCA и RMQ. Решение RMQ с помощью sparse table. Сведение LCA к RMQ (алгоритм Фарах-Колтона-Бендера). Сведение RMQ к LCA.
  • Графы: продвинутые темы
    Остовы минимального веса. Лемма о минимальном ребре в разрезе. Алгоритмы Краскала и Прима. Системы непересекающихся множеств. Реализация с использованием леса. Ранги вершин, эвристика ранга. Логарифмическая оценка ранга через количество элементов. Эвристика сжатия путей. Оценка учетной стоимости операций (без доказательства). Алгоритм Борувки. Комбинация алгоритма Борувки и алгоритма Прима. Алгоритм Таржана для задачи offline LCA. Алгоритм hub labels для задачи о кратчайших путях.
Элементы контроля

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

  • неблокирующий Домашняя работа
  • неблокирующий Домашняя работа 2
  • неблокирующий Экзамен
Промежуточная аттестация

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

  • Промежуточная аттестация (2 модуль)
    0.3 * Домашняя работа + 0.3 * Домашняя работа 2 + 0.4 * Экзамен
Список литературы

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

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

  • Комбинаторика и теория графов : учеб. пособие, Кочетков, Ю. Ю., 2009

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

  • Теория графов : учеб. пособие для втузов, Белов, В. В., 1976
  • Язык С#. Базовый курс : учеб. пособие для вузов, Подбельский, В. В., 2013
  • Язык С#. Решение задач : учеб. пособие для вузов, Подбельский, В. В., 2014