Седмичен изглед

  • Главна

    Сгъване на всички Разгъване на всички

  • 21 февруари — 27 февруари

    •   Асимптотични сравнения.
        Интегрален метод за сумиране
       
        Сложност на алгоритъм.
        Анализ на времевата сложност
        на итеративни алгоритми
        чрез сумиране
       

  • 28 февруари — 6 март

    •   Рекурентни уравнения

  • 7 март — 13 март

    •   Анализ на рекурсивни алгоритми
        с помощта на рекурентни уравнения;
        алгоритми от тип "разделяй и владей"
        и анализ чрез мастър-теоремата

    •   Бързо умножение:
        — на числа;
        — на матрици.
       
        Бързо степенуване

    •   Коректност на алгоритми

  • 14 март — 20 март

    •   Амортизирана сложност:
        определение, приложения,
        агрегатен метод
       
        Търсене:
        последователно, двоично,
        търсене на екстремални елементи,
        търсене на k-ти най-малък елемент

  • 21 март — 27 март

    • Файл icon
      Контролно № 1 Файл
      (анализ на алгоритми)
    •  
        ————————————————
       
        Разделяне на масив:
        — по Ломуто;
        — по Хоор;
        — устойчиво разделяне.
       
        Елементарни сортировки:
        — метод на мехурчето;
        — сортиране чрез вмъкване;
        — сортиране чрез пряк избор.

  • 28 март — 3 април

    •   Ефективни сортировки:
        — сортиране чрез сливане;
        — пирамидално сортиране;
        — бързо сортиране.
       
        Бързо търсене:
        описание, анализ,
        съпоставка с алгоритъма PICK

  • 4 април — 10 април

    •   Други видове сортировки:
        сортиране чрез броене,
        метод на бройните системи.
        Сортиране с линейна времева сложност
       
    •   Приложения на сортирането:
        — в теоретични задачи;
        — в практически задачи
            (напр. производствени задачи).
       
    • Файл icon
      Задача за бутилиране Файл
      (оригиналът е публикуван
      в руското списание "Квант")
    •  
    • Файл icon
      Контролно № 2 Файл
      (приложения на сортирането)

  • 11 април — 17 април

    •   Динамично програмиране:
        — подмножество от числа с даден сбор;
        — разбиване на множество от числа
             на две подмножества с равни сборове;
        — задача за раницата.
       
         Алгоритъм CYK
        за синтактичен анализ
        на безконтекстни граматики
        в нормална форма на Чомски
       
    • URL (хипервръзка) icon
      Най-дълга обща подредица URL
    •   ___________________________________
       
        Понякога динамичното програмиране
        не води до най-бърз алгоритъм!
       
        Най-дълга растяща подредица
        се търси за квадратично време (n2)
        посредством динамично програмиране,
        но само за време  n log n
        с помощта на сортиране чрез пасианс.

  • 18 април — 24 април

  • 25 април — 1 май

    •   Синтактичен анализ
       
        Използвани средства:
        — крайни автомати (за регулярни езици);
        — алгоритъмът CYK (за безконтекстни езици).
    •  
       ——————————————————————
       
    •   Комбинаторни задачи за броя на редиците,
        всеки два съседни члена на които
        удовлетворяват дадено изискване
       
        Такива задачи могат да се решават
        както чрез динамично програмиране,
        така и чрез преброяване на пътищата
        в подходящ граф.
       
        Примерни задачи:
    • Файл icon
      — застрояване на парцели; Файл
    •   — брой мелодии.

  • 2 май — 8 май

  • 9 май — 15 май

    •   Сложност на алгоритмични задачи

  • 16 май — 22 май

  • 23 май — 29 май

    •   Алчни алгоритми
    •   Решават оптимизационни задачи,
        като на всяка стъпка избират
        действието, което изглежда
        най-добро за момента,
        без поглед напред.
        Винаги са бързи,
        но невинаги са коректни.
       
        NP-пълни задачи
    • Файл icon
      Доказателства за NP-пълнота Файл
      на някои алгоритмични задачи
      чрез полиномиална редукция

  • 30 май — 5 юни

  • 6 юни — 12 юни

  • Резултати
    от редовната лятна сесия
    (юни 2022 г.)
    •   Оценките са нанесени
        в изпитните протоколи.

  • Поправителна сесия
    28 август 2022 г.
    •  
        Задължително е представянето
        на официален документ за самоличност —
        валидна лична карта, издадена от МВР.
       
    •   Няма да има ликвидационна дата по ДАА !
       
    • Файл icon
      Изпитни задачи Файл