Персистентные структуры данных

Воскресенье, 05 октября 2014, 13:00–14:35
ПОМИ РАН

Описание

  • Pointer Machine model

  • Структуры данных. Операции на запрос (query) и изменение (update)

  • Персистентность. Частичная и полная

  • Функциональные структуры данных

  • Функциональный стек, BST

  • Общий метод для частично персистентных с дополнительным \(\log V\) на операцию

  • Частично персистентный связный список за O(1)

  • Частично персистентное дерево за O(1)

  • Общий метод построения частично персистентных структур

  • Общий метод построения полностью персистентных структур