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

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

    Главна

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

    •   Учебни материали:
    • Българска терминология в информатиката URL
      Най-важни са страниците от главата
      "Грешки и трудности при превод",
      но и другите глави от справочника
      съдържат полезни съвети.
    • Учебни материали от Д. Кралчев URL
      по различни предмети
    •  
  • Разгъване Разширяване

    22 февруари — 28 февруари
    •  Асимптотични сравнения.
       Интегрален метод за сумиране

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

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

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

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

    8 март — 14 март
    •   Търсене:
        последователно, двоично,
        търсене на екстремални елементи,
        търсене на k-ти най-малък елемент
        _______________________________
       
        Сортиране чрез сравняване:
        елементарни сортировки,
        ефективни сортировки
  • Разгъване Разширяване

    15 март — 21 март
    •   Други видове сортировки:
        сортиране чрез броене,
        метод на бройните системи.
        Сортиране с линейна времева сложност
  • Разгъване Разширяване

    22 март — 28 март
    •   Алгоритми върху нетегловни графи
       
        Представяния на графи.
        Обхождане в ширина,
        обхождане в дълбочина
        и техните приложения
  • Разгъване Разширяване

    29 март — 4 април
    • Алгоритми върху тегловни графи URL

    •   Минимално покриващо дърво:
        — алгоритъм на Крускал
             (структура Union-Find);
        — алгоритъм на Прим—Ярник.

        Търсене на най-къси пътища:
        — алгоритъм на Дейкстра;
        — алгоритъм на Белман—Форд;
        — алгоритъм на Флойд—Уоршал.

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

    5 април — 11 април
    •   Моделиране на практически задачи
        с помощта на графи
  • Разгъване Разширяване

    12 април — 18 април
    •   Алчни алгоритми
  • Разгъване Разширяване

    19 април — 25 април
    •   Долни граници за времевата сложност
        на алгоритмични задачи
  • Разгъване Разширяване

    26 април — 2 май
    •   NP-пълни задачи
  • Разгъване Разширяване

    3 май — 9 май
    •   Динамично програмиране:
        — задача за раницата;
        — подмножество от числа с даден сбор.
       
  • Разгъване Разширяване

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

    17 май — 23 май
    •   Комбинаторни задачи за броя на редиците,
        всеки два съседни члена на които
        удовлетворяват дадено изискване
       
        Такива задачи могат да се решават
        както чрез динамично програмиране,
        така и чрез преброяване на пътищата
        в подходящ граф.
       
        Примерни задачи:
    • — застрояване на парцели; Файл
    • — брой мелодии; URL
    • — задача за 16-те царя. Файл
  • Разгъване Разширяване

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

    31 май — 6 юни
  • Разгъване Разширяване

    7 юни — 13 юни
    •   Подготовка за изпит
  • Разгъване Разширяване

    Текущ контрол и изпит
  • Разгъване Разширяване

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