Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Структуры данных, основанные на указателях


Мы поговорим о структурах данных, основанных на указателях.

Допустим у нас есть массив чисел, и мы хотим эффективно выполнять поиск в нем, добавлять и удалять элементы. В этом нам помогут деревья поиска, которых существует много разновидностей. Мы обсудим некоторые из них. Как сравнить эффективность разных деревьев? Что такое динамическая оптимальность и какие деревья самые конкурентные по отношению к последовательностям запросов?

А если у нас вместо исходного массива чисел дано дерево, лес, граф? Мы обсудим структуры данных для этих случаев.

Во второй части курса мы посмотрим на общие вопросы о структурах данных основанных на указателях: Если у нас есть статическая такая структура, как сделать ее динамической, и сколько придется за это заплатить? Если у нас есть динамическая структура, можем ли мы так ее модифицировать, чтобы научиться смотреть на ее версии в прошлые моменты времени? Изменять эти версии?

В данном мини-курсе прозвучат ответы на эти и другие вопросы, а также новые вопросы, на которые мы пока не знаем ответа.

Прочтения курсов

Семестр
осень 2019