City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Персистентные структуры данных
Advanced chapters of algorithms, часть 1

What: Lecture
When: Sunday, 05 October 2014, 13:00–14:35
Where: ПОМИ РАН

Description

  • Pointer Machine model

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

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

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

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

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

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

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

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

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

Video