Представяне по теми

  • Тема 1

    Въведение в абстрактните типове данни.


    Темата съдържа описание на основните абстрактни типове данни. Ще бъде обърнато само на необходимите операции, без да се конкретизира реализацията им.

    Учебни материали: Абстрактни типове данни

    • Тема 2

      Анализ на структури от данни.


      Темата съдържа техники за анализиране на структури от данни. Ще бъдат разгледани подробно различни методи за амортизационен анализ:
      • Aggregate analysis.
      • The accounting method.
      • The potential method.
      Учебни материали: Introduction to Algorithms - chapter 18.

      • Тема 3

        Червено черни дървета.


        Темата съдържа основните операции на червено чернитее дървета, както и примери за тяхното приложение.

        Учебни материали: Introduction to Algorithms - chapter 14.

      • Тема 4

        AVL дървета.


        Тема ще съдържа:
        1. Техники за разширяване на структури от данни (Augmenting Data Structures). Ще бъдат разгледани Dynamic Ordered Statistics и Interval trees, като за основа ще бъде използвано червено-черно дърво (от минала лекция). Ще се разгледат няколко задачи в решенията на, които се използват разширените структури от данни.

        Учебни материали: Introduction to Algorithms - chapter 15.

        2. AVL дърво. Ще бъдат разгледани основните операции на AVL дърветата и тяхната ефективност спрямо червено черните дървета.

        Учебни материали:
        Лекция за AVL дървета

        Визуално представяне на няколко вида балансирани дървета (Red-Black, AVL, Splay)
        • Тема 5

          Splay дървета.

          Темата съдържа описание на този вид самобалансиращи се дървета. Ще бъдат разгледани основните операции над Splay дървета, както и тяхното приложение.

          Учебни материали:

          * Материалът не влиза в теста.


          • Тема 6

            B дървета.


            Темата съдържа описание и реализация на Б-дърветата. Обрънато е внимание на брой дискови операции при резлизацията на структурата.

            Учебни материали: Introduction to Algorithms - chapter 19

          • Тема 7

            Trie.

            • Тема 8

              Суфиксно дърво и суфиксен масив.

            • Тема 9

              Патриции.

              • Тема 10

                Декартово дърво.

                • Тема 11

                  Двоична пирамида.

                • Тема 12

                  Биномна пирамида.


                  Темата съдържа описание на биномни дървета и биномна пирамида.

                  Учебни материали: Introduction to Algorithms - chapter 20

                  • Тема 13

                    Фибоначиева пирамида.

                    Учебни материали: Introduction to Algorithms - chapter 21

                    • Тема 14

                      Tiered вектор.

                      Учебни материали: http://debian.fmi.uni-sofia.bg/~dobrev/tiered-vector.pdf

                      • Тема 16

                        Хеш таблици.

                        На http://en.wikipedia.org/wiki/Hash_table има достатъчно материали по темата. Разгледайте самата статия и следните препратки от See Also:
                        Bloom filter
                        Hash function
                        Hash list
                        Hash tree
                        За тези на които им е интересно може и Rabin-Karp string search algorithm
                      • Тема 17

                        Представяне на графи.

                        • Тема 18

                          Представяне на дървета.

                          • Тема 19

                            Представяне на други комбинаторни конфигурации.

                            • Тема 20

                              Структури от данни за представяне на непресичащи се множества.

                              Учебни материали: Introduction to Algorithms, Chapter 22: "Data Structures for Disjoint Sets"
                              • Тази тема

                                Тема 21

                                Една задача от международната олимпиада по информатика за ученици.

                                Учебни материали: IOI2001 Competition Book (страница 38, задача Mobiles).