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

  • Главна

  • Тема 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

                      • Тема 15

                        Skip List.

                        Учебни материали: http://www.csee.umbc.edu/courses/undergraduate/341/fall01/Lectures/SkipLists/skip_lists/skip_lists.html

                        • Тема 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).