danilx8/algo-school

Алгоритмы и структуры данных Высшей Школы Программирования Сергея Бобровского

Пройденный курс включал в себя следующие темы:

• Основные ресурсы: память и время. О-символика.
• Асимптотический анализ. Сложность в среднем и худшем случаях. Теоретико-информационная нижняя оценка сложности.
• Связанные списки.
  • Связанные двунаправленные списки.
• Массивы переменного размера: аддитивная и мультипликативная схемы реаллокации. Анализ мультипликативной схемы для массива переменного размера с помощью банковского метода.
• Стеки. Реализация на основе массива переменного размера и на основе связанного списка. Анализ учетных стоимостей операций: функция потенциала, истинные и учетные стоимости.
• Очереди. Моделирование очереди с помощью двух стеков.
  • Двусторонние очереди.
• Упорядоченные списки.
• Хэширование. Хеш-функции. Коллизии. Разрешение коллизий методом цепочек, методом последовательных проб и методом двойного хеширования.
• Универсальное кэширование. Гипотеза простого равномерного хеширования, оценка средней длины цепочки. Универсальные семейства хеш-функций, оценка средней длины цепочки. Построение универсального семейства для целочисленных ключей.
• Совершенные хеш-функции. Построение совершенной хеш-функции с помощью универсального семейства.
• Ассоциативные массивы (словари).
• Множества.
• Кэши.
• Интерфейс множества с ошибками. Фильтр Блюма (Bloom filter).
• Оценка вероятности ложноположительного срабатывания.
• Интерфейс словаря с ошибками. Модификация фильтра Блюма (bloomier filter).
• Деревья.
  • Обходы дерева.
  • Двоичные деревья поиска (1). Определение дерева поиска. Вставка и удаление элементов.
  • Двоичные деревья поиска (2).
  • Строим сбалансированные двоичные деревья поиска (1).
• Понятие о методе «разделяй и властвуй».
• Двоичные деревья поиска (2).
• Пирамиды. Деревья со свойствами кучи. Почти полные бинарные деревья: нумерация вершин, навигация. Двоичная куча. Операция просеивания вниз и вверх. Реализация операций вставки, удаления и поиска минимума.
• Преобразование произвольного массива ключей в кучу (операция Make-Heap), линейность времени работы.
• Красно-чёрные деревья (ознакомительное) Определение и основные свойства. Реализация операций вставки для красно-черного дерева.
• B-деревья (ознакомительное): определения и основные свойства. Операции поиска, вставки и удаления для B+ деревьев.
• Графы.
  • Графы (поиск в глубину).
  • Графы (поиск в ширину).