Компания
459,86
рейтинг
11 января 2014 в 16:10

Разработка → Алгоритмы и структуры данных поиска. Лекции и курсы от Яндекса tutorial

Сегодня мы завершаем новогоднюю серию постов, посвященных лекциям Школы анализа данных. Последний по порядку, но никак не по важности курс — «Алгоритмы и структуры данных поиска».

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

Мы учли то, о чём нас просили в комментариях к прошлым курсам — теперь при желании можно не только смотреть/скачивать лекции по отдельности, но и загрузить всё разом в виде открытой папки на Яндекс.Диске. Кстати — в предыдущих постах тоже появились такие же апдейты (вот ссылки для удобства: «машинное обучение», «дискретный анализ и теория вероятностей», «параллельные и распределённые вычисления»).



Лекции читает Максим Александрович Бабенко, заместитель директора отделения computer science, ассистент кафедры математической логики и теории алгоритмов механико-математического факультета МГУ им. М. В. Ломоносова, кандидат физико-математических наук.


Полный курс в виде папки на Яндекс.Диске



Лекция 1. Сложность и модели вычислений. Анализ учетных стоимостей (начало)


Основные ресурсы: память и время. О-символика. Примеры моделей вычисления: машина Тьюринга, RAM-машина. Сложность в среднем и худшем случаях. Пример: задача сортировки. Сортировка выбором. Теоретико-информационная нижняя оценка сложности. Разрешающие деревья. Нижняя оценка сложности в модели разрешающих деревьев. Массивы переменного размера: аддитивная и мультипликативная схемы реаллокации. Анализ мультипликативной схемы для массива переменного размера с помощью банковского метода.

Лекция 2. Анализ учетных стоимостей (окончание)


Анализ учетных стоимостей операций: функция потенциала, истинные и учетные стоимости. Стеки и очереди. Реализация на основе массива переменного размера и на основе связанного списка. Моделирование очереди с помощью двух стеков. Задача о поддержании динамического максимума в стеке и очереди. Изменяемые (mutable) и неизменяемые (immutable) структуры данных. Структуры данных с хранением истории (persistent). Immutable-стек и immutable-очередь. Проблема множественного будущего при анализе учетных стоимостей в persistent-структурах.

Лекция 3. Функции быстрой сортировки и сортировки слиянием


Понятие о методе «разделяй и властвуй». Алгоритм Merge-Sort. Слияние двух упорядоченных списков. Оценка сложности. K-way Merge-Sort для работы во внешней памяти. Сортировка слиянием без использования дополнительной памяти. Общая схема алгоритма Quick-Sort. Два варианта реализации Partition. Примеры неудачного выбора опорных элементов. Рандомизированный выбор опорного элемента. Сложность Quick-Sort в худшем и среднем случаях. Глубина рекурсии в худшем и среднем случаях. Элиминация хвостовой рекурсии. Задача об оптимальном дереве слияний. Коды Хаффмана. Слияние двух упорядоченных последовательностей различной длины. Теоретико-информационная нижняя оценка. Бинарный поиск «от края» (galloping).

Лекция 4. Порядковые статистики. Кучи (начало)


Нахождение порядковых статистик с помощью рандомизированной модификации алгоритма Quick-Sort. Линейность матожидания времени работы. Приближенные медианы. Выбор k-й порядковой статистики за линейное в худшем случае. Деревья со свойствами кучи. Почти полные бинарные деревья: нумерация вершин, навигация. Двоичная куча. Операция просеивания вниз и вверх. Реализация операций вставки, удаления и поиска минимума. Преобразование произвольного массива ключей в кучу (операция Make-Heap), линейность времени работы. Алгоритм сортировки Heap-Sort.

Лекция 5. Кучи (начало). Хэширование (начало)


k-ичные кучи, зависимость сложности операций от выбора k. Биномиальные (binomial), левацкие (leftlist) и косые (skew) кучи.

Лекция 6. Хэширование


Хеш-функции. Коллизии. Разрешение коллизий методом цепочек, методом последовательных проб и методом двойного хеширования. Гипотеза простого равномерного хеширования, оценка средней длины цепочки. Универсальные семейства хеш-функций, оценка средней длины цепочки. Построение универсального семейства для целочисленных ключей. Совершенные хеш-функции. Построение совершенной хеш-функции с помощью универсального семейства. Интерфейс множества с ошибками. Фильтр Блюма (Bloom filter). Оценка вероятности ложноположительного срабатывания. Интерфейс словаря с ошибками. Модификация фильтра Блюма (bloomier filter).

Лекция 7. Деревья поиска (начало)


Определение дерева поиска. Вставка и удаление элементов. Inorder-обход дерева. Красно черные деревья: определение и основные свойства. Реализация операций вставки для красно-черного дерева. Splay-деревья. Операция splay: zig, zig-zig и zig-zag шаги. Реализация операций вставки, удаления, слияния и разделения для splay-деревьев.

Лекция 8. Деревья поиска (окончание). Декартовы деревья


Декартовы деревья (дучи). Единственность декартова дерева для заданного набора различных ключей и приоритетов. Логарифмическая оценка матожидания высоты дучи.Операции слияния и разделения для дуч. Операции вставки и удаления элементов для дуч. Построение декартового дерева за линейное время при условии предварительной сортировки ключей.

Лекция 9. B-деревья. Система непересекающихся множеств


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

Лекция 10. Задачи RMQ и LCA


Задачи RMQ (range minimum query) и LCA (least common ancestor). Сведение от задачи RMQ к задаче LCA, декартово дерево. Алгоритм Таржана для offline-версии задачи LCA. Простейшие алгоритмы для online-версии задачи LCA: полная и разреженная таблицы ответов. Алгоритм Фарах-Колтона-Бендера для к задаче ±1-RMQ. Сведение задачи LCA к задаче ±1-RMQ: эйлеров обход дерева.

Лекция 11. Задачи геометрического поиска


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).
Автор: @anton
Яндекс
рейтинг 459,86

Комментарии (18)

  • +2
    А я сегодня только на эту тему экзамен сдавал.

    Спасибо, повторю теорию!
  • +4
    Однако вы радуете. Спасибо.

    P.S. Вы, кстати, перечень выложенных материалов расширять не планируете?
    • +2
      Планируем в будущем, конечно.
  • +4
    Спасибо за труды! Всегда полезно такое слушать, читать, смотреть и писать местами.
  • 0
  • 0
    Простите пожалуйста за возможно глупый вопрос: Но Ваши вложения в подобные вещи хоть как-то к Вам возвращаются?
    • +5
      Конечно. Мы находимся в России, и нам нужно, чтобы здесь были квалифицированные люди и интерес к важным для нас темам. И то и другое мы получаем.
      • +1
        Ок. Еще след. вопрос. У Вас очень многое делается для студентов. Но почему именно они? Есть же громадное кол-во людей старше 25-лет и достаточно не глупых! Просто чуть ли ни каждый ивент по обучению чему-либо у Вас именно для студентов. Я вот 32-летний и есть чему по учиться. Ежедневно прихожу к мысли, что сколь не изучай, а все равно есть что еще изучать.
        • 0
          Почему вам так показалось? Разные наши мероприятия нацелены совсем не только на студентов.
          Смотрите, например: tech.yandex.ru/events/
          Да и здесь: tech.yandex.ru/education/

          Вы могли бы сформулировать, чего именно на Ваш взгляд не хватает?
          • +3
            Ну к примеру есть две темы:

            1) Сейчас очень появляется много языков для работы с очень большим объемом данных. К примеру Go, Rust и др. Об этом ничего пока у Вас нету. Более-того не слышал мнение Ваших специалистов на этот счет, может пропустил мимо ушей\глаз\сознания?

            2) Также сейчас все больше и больше набирает популярность «функциональщина» т.е. язык Haskel и др. Каково Ваше мнение по этому направлению компьютерной лингвистики и если применяется то где, как и насколько хорошо стало? Возможно опять проворонил мимо сознания и Вы это уже где-то рассказали?!
            • 0
              Добавлю еще один:
              п.3: Разработка компиляторов.
              Это весьма интересно + полезно. К примеру задача. Нужно написать тулзу, которая берет файл с исходным кодом на C++ с декларацией базового класса и создает скелет потомочного класса в виде двух файлов children.hpp, children.cpp. Это как пример что людям хочется знать подобное, т.к. задачи из этой темы пусть редко, но все-таки бывают!
    • +1
      Хорошее publicity и небольшое улучшение уровня разработчиков возвращаются косвенно, но возвращаются.
  • +3
    1) PR. Не так уж много компаний у нас делают проекты в области обучения Computer Science
    2) ШАД же это источник кадров и для Яндекс
    3) Общий рост грамотности ИТшников у нас это полезно и Яндексу, так как эффективнее пользуются его сервисами разработчики, плотнее к ним привязка у пользователей, ПРОФИТ Яндексу
    • +1
      Разработчики всё равно пользуются гуглом, даже в яндексе. У яндекса плохо с поиском технических вещей. У яндекса очень большой штат, он всё время расширяется и остро встаёт проблема поиска кадров. Её они и стараются решить, попутные приятный бонус — pr. То есть это холодный рассчёт, что нисколько не умаляет их вклада и пользы для общественности.
      • 0
        Как ни парадоксально, но это так. Был на ruBSD и пообщавшись с ребятами еще больше поразился этому факту )
  • +2
    Ого. Крута! Вот за этот материал действительно спасибо, гораздо лучше википедии.
  • 0
    В седьмой лекции рассмотрена реализация операции вставки для красно-черного дерева, но не реализация удаления. Интересно, что и в книге Роберта Лафоре «Структуры данных и алгоритмы в Java» со всеми подробностями изложена балансировка при вставке, а вот удаление упоминается вскользь со словами «это сложно, читайте Кормена». Балансировку при удалении действительно настолько сложно реализовать, что ее почти никто не рассматривает?
    P.S. Кормена я пробежал глазами, отметив, что там при балансировке при удалении используется ссылка на родительский узел, что снижало для меня ценность алгоритма — в моей реализации класса Node использовались только ссылки на левое и правое поддеревья.
  • 0
    А можно как-то выложить эти видео на iTunesU?

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Самое читаемое Разработка