Схема на раздела

  • Разгъване Разширяване

    Главна

    Сгъване на всички Разгъване на всички
    • Обявления Форум
    •  
    • Конспект Файл
    • Схема за оценяване Файл
    •  
    • Виртуална класна стая URL
      за лекциите по ДАА
      в електронна среда
    •  Забранено е записването на лекциите,
       съхраняването и разпространяването
       на видеозаписи и/или аудиозаписи!
       
    • Виртуална класна стая URL
      за упражненията по ДАА
      в електронна среда
    •  
    • Транслатор за Си-плюс-плюс URL
       (транслаторът работи в Интернет
       без инсталиране на файлове
       на локалната машина)
    •  
    • Учебни материали от Д. Кралчев URL
    •  
    • Задачи за самоподготовка URL
    •  
  • Разгъване Разширяване

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

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

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

    •   Рекурентни уравнения
  • Разгъване Разширяване

    7 март — 13 март

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

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

    •   Коректност на алгоритми
  • Разгъване Разширяване

    14 март — 20 март

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

    21 март — 27 март

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

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

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

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

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

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

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

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

    •   Контролно № 3
        (динамично програмиране):
    • — условия; Файл
    • — решения. Файл
  • Разгъване Разширяване

    25 април — 1 май

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

    2 май — 8 май

  • Разгъване Разширяване

    9 май — 15 май

    •   Сложност на алгоритмични задачи
  • Разгъване Разширяване

    16 май — 22 май

  • Разгъване Разширяване

    23 май — 29 май

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

    30 май — 5 юни

  • Разгъване Разширяване

    6 юни — 12 юни
    •   Обобщения на понятието алгоритъм:
        рандомизирани алгоритми
        (типове Монте Карло и Лас Вегас),
        генетични / еволюционни алгоритми,
        евристични алгоритми и др.
       
        Апроксимиращи алгоритми:
        — върхово покритие;
        — задача за търговския пътник.
       
        Паралелни алгоритми:
        — сортиране чрез сливане;
        — алгоритъм на Борувка.
       
    • Квантови компютри Файл
    •  
        —————————————————
       
    • Контролно № 6 Файл
      (поправка на контролни)
    •  
        Предварителен изпит
  • Разгъване Разширяване

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

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