Компьютерные науки

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

В курсе рассматриваются базовые алгоритмы и структуры данных, включая хеширование, сложность и модели вычислений, деревья поиска, B-деревья, задачи геометрического поиска, динамическую связность в графах и другое.
Студентов 1510 Выпускников 105 Для всех
Бесплатно
или любая сумма на ваше усмотрение
Вы можете оплатить любую сумму, чтобы поддержать наш проект и авторов программы. Объем услуг не зависит от размера вашей оплаты.
Объем
72 час.
Длительность
30 дней
Нагрузка в неделю
17 час.
Формат обучения
Дистанционно (самостоятельно)
Описание Учебный курс посвящен классическим алгоритмам и структурам данных для поиска и обработки информации. В материалах рассматриваются модели вычислений, хеширование, различные виды деревьев поиска, включая B-деревья, а также решение задач геометрического поиска и оценка динамической связности в графах. Курс будет полезен разработчикам и программистам, желающим повысить эффективность своего кода за счет грамотного применения структур данных.
Цели
  • Сформировать понимание принципов работы базовых алгоритмов и структур данных.
  • Развить умение оценивать сложность вычислений.
  • Помочь анализировать применимость различных структур данных для решения конкретных задач поиска.
Чему я научусь?
  • Применять хеширование для эффективного поиска данных.
  • Использовать различные деревья поиска при проектировании программных решений.
  • Оценивать сложность алгоритмов и оптимизировать вычислительные процессы.

Авторы

Бабенко Максим Александрович
Бабенко Максим Александрович
Чему я научусь?
  • Применять хеширование для эффективного поиска данных.
  • Использовать различные деревья поиска при проектировании программных решений.
  • Оценивать сложность алгоритмов и оптимизировать вычислительные процессы.

Учебный план

№ Занятия
Экзамен экстерном Внимание! Экзамен экстерном не обязательный для сдачи. При желании вы можете его пройти, если хотите подтвердить свои знания по данному курсу без его изучения или поверить свои знания по нему. Экзамен экстерном можно сдать только один раз. 90 мин
1 Сложность и модели вычислений. Анализ учетных стоимостей Основные ресурсы: память и время. О-символика. Примеры моделей вычисления: машина Тьюринга, RAM-машина. Сложность в среднем и... Основные ресурсы: память и время. О-символика. Примеры моделей вычисления: машина Тьюринга, RAM-машина. Сложность в среднем и худшем случаях. Пример: задача сортировки. Сортировка выбором. Теоретико-информационная нижняя оценка сложности. Разрешающие деревья. Нижняя оценка сложности в модели разрешающих деревьев. Массивы переменного размера: аддитивная и мультипликативная схемы реаллокации. Анализ мультипликативной схемы для массива переменного размера с помощью банковского метода. ещё
2 Анализ учетных стоимостей (окончание) Анализ учетных стоимостей операций: функция потенциала, истинные и учетные стоимости. Стеки и очереди. Реализация на основе... Анализ учетных стоимостей операций: функция потенциала, истинные и учетные стоимости. Стеки и очереди. Реализация на основе массива переменного размера и на основе связанного списка. Моделирование очереди с помощью двух стеков. Задача о поддержании динамического максимума в стеке и очереди. Изменяемые (mutable) и неизменяемые (immutable) структуры данных. Структуры данных с хранением истории (persistent). Immutable-стек и immutable-очередь. Проблема множественного будущего при анализе учетных стоимостей в persistent-структурах. ещё
Анализ учетных стоимостей (окончание) тест для курса Алгоритмы и структуры данных поиска 85 мин
3 Функции быстрой сортировки и сортировки слиянием "Понятие о методе ""разделяй и властвуй"". Алгоритм Merge-Sort. Слияние двух упорядоченных списков. Оценка сложности. K-way Merge-Sort... "Понятие о методе ""разделяй и властвуй"". Алгоритм Merge-Sort. Слияние двух упорядоченных списков. Оценка сложности. K-way Merge-Sort для работы во внешней памяти. Сортировка слиянием без использования дополнительной памяти. Общая схема алгоритма Quick-Sort. Два варианта реализации Partition. Примеры неудачного выбора опорных элементов. Рандомизированный выбор опорного элемента. Сложность Quick-Sort в худшем и среднем случаях. Глубина рекурсии в худшем и среднем случаях. Элиминация хвостовой рекурсии. Задача об оптимальном дереве слияний. Коды Хаффмана. Слияние двух упорядоченных последовательностей различной длины. Теоретико-информационная нижняя оценка. Бинарный поиск ""от края"" (galloping)." ещё
Функции быстрой сортировки и сортировки слиянием тест для курса Алгоритмы и структуры данных поиска 60 мин
4 Порядковые статистики. Кучи Нахождение порядковых статистик с помощью рандомизированной модификации алгоритма Quick-Sort. Линейность матожидания времени работы. Приближенные медианы. Выбор... Нахождение порядковых статистик с помощью рандомизированной модификации алгоритма Quick-Sort. Линейность матожидания времени работы. Приближенные медианы. Выбор k-й порядковой статистики за линейное в худшем случае. Деревья со свойствами кучи. Почти полные бинарные деревья: нумерация вершин, навигация. Двоичная куча. Операция просеивания вниз и вверх. Реализация операций вставки, удаления и поиска минимума. Преобразование произвольного массива ключей в кучу (операция Make-Heap), линейность времени работы. Алгоритм сортировки Heap-Sort. ещё
5 Кучи и хэширование k-ичные кучи, зависимость сложности операций от выбора k. Биномиальные (binomial), левацкие (leftlist) и косые (skew) кучи.
Кучи и хэширование тест для курса Алгоритмы и структуры данных поиска 85 мин
6 Хэширование Хеш-функции. Коллизии. Разрешение коллизий методом цепочек, методом последовательных проб и методом двойного хеширования. Гипотеза простого равномерного... Хеш-функции. Коллизии. Разрешение коллизий методом цепочек, методом последовательных проб и методом двойного хеширования. Гипотеза простого равномерного хеширования, оценка средней длины цепочки. Универсальные семейства хеш-функций, оценка средней длины цепочки. Построение универсального семейства для целочисленных ключей. Совершенные хеш-функции. Построение совершенной хеш-функции с помощью универсального семейства. Интерфейс множества с ошибками. Фильтр Блюма (Bloom filter). Оценка вероятности ложноположительного срабатывания. Интерфейс словаря с ошибками. Модификация фильтра Блюма (bloomier filter). ещё
Хэширование тест для курса Алгоритмы и структуры данных поиска 65 мин
7 Деревья поиска Определение дерева поиска. Вставка и удаление элементов. Inorder-обход дерева. Красно черные деревья: определение и основные свойства.... Определение дерева поиска. Вставка и удаление элементов. Inorder-обход дерева. Красно черные деревья: определение и основные свойства. Реализация операций вставки для красно-черного дерева. Splay-деревья. Операция splay: zig, zig-zig и zig-zag шаги. Реализация операций вставки, удаления, слияния и разделения для splay-деревьев. ещё
8 Деревья поиска и декартовы деревья Декартовы деревья (дучи). Единственность декартова дерева для заданного набора различных ключей и приоритетов. Логарифмическая оценка матожидания... Декартовы деревья (дучи). Единственность декартова дерева для заданного набора различных ключей и приоритетов. Логарифмическая оценка матожидания высоты дучи.Операции слияния и разделения для дуч. Операции вставки и удаления элементов для дуч. Построение декартового дерева за линейное время при условии предварительной сортировки ключей. ещё
9 B-деревья. Система непересекающихся множеств B+ деревья: определения и основные свойства. Операции поиска, вставки и удаления для B+ деревьев. Системы непересекающихся... B+ деревья: определения и основные свойства. Операции поиска, вставки и удаления для B+ деревьев. Системы непересекающихся множеств. Реализация с использованием леса. Ранги вершин, эвристика ранга. Логарифмическая оценка ранга через количество элементов. Рандомизированная ранговая эвристика. Эвристика сжатия путей. Оценка учетной стоимости операций (без доказательства). ещё
B-деревья. Система непересекающихся множеств тест для курса Алгоритмы и структуры данных поиска 75 мин
10 Задачи RMQ и LCA Задачи RMQ (range minimum query) и LCA (least common ancestor). Сведение от задачи RMQ к задаче... Задачи RMQ (range minimum query) и LCA (least common ancestor). Сведение от задачи RMQ к задаче LCA, декартово дерево. Алгоритм Таржана для offline-версии задачи LCA. Простейшие алгоритмы для online-версии задачи LCA: полная и разреженная таблицы ответов. Алгоритм Фарах-Колтона-Бендера для к задаче ±1-RMQ. Сведение задачи LCA к задаче ±1-RMQ: эйлеров обход дерева. ещё
Задачи RMQ и LCA тест для курса Алгоритмы и структуры данных поиска 60 мин
11 Задачи геометрического поиска Location problem, stabbing problem. Деревья интервалов. Сведение системы интервалов к двумерной задаче. Задача поиска точек в... Location problem, stabbing problem. Деревья интервалов. Сведение системы интервалов к двумерной задаче. Задача поиска точек в коридоре. Priority search tree. Задача поиска точек в прямоугольнике. Дерево отрезков по координате X, упорядоченные по Y списки точек в каждой вершине. Сложность O(n log n) для построения и O(log^2 n) для запроса. Уменьшение времени поиска до O(log n). Задача одновременного поиска в наборе упорядоченных списков. Fractional cascading. ещё
12 Динамическая связность в графах Задача о динамической связности: вставки и удаления ребер, запросы о связности. Частный случай задачи для случая... Задача о динамической связности: вставки и удаления ребер, запросы о связности. Частный случай задачи для случая лесов. Деревья эйлеровых обходов: слияние и разделение. Использование амортизации и набора остовных лесов для решения со сложностью O(log^2 n). ещё
Динамическая связность в графах тест для курса Алгоритмы и структуры данных поиска 75 мин
Тренировочный экзамен Внимание! Тренировочный экзамен экстерном не обязательный для сдачи. При желании вы можете его пройти, если хотите проверить свои знания курса перед сдачей экзамена. Тренировочный экзамен можно сдавать сколько угодно один раз. 90 мин
Экзамен 60 мин

Какой документ я получу?

Сертификат

Выдаётся автоматически после успешного завершения программы.

Удостоверение о повышении квалификации

Выдается при наличии среднего специального или высшего образования (необходимые документы).

Стоимость программы

Бесплатно
или любая сумма на ваше усмотрение
Вы можете оплатить любую сумму, чтобы поддержать наш проект и авторов программы. Объем услуг не зависит от размера вашей оплаты.
^