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

  • Главна

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

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

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

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

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

  • 12 октомври — 18 октомври
    •   Коректност на алгоритми

  • 19 октомври — 25 октомври
    •   Разделяне на масив.
        Сортиране и търсене

  • 26 октомври — 1 ноември

  • 2 ноември — 8 ноември
    •   Алгоритми върху графи
        (лекция в електронна среда,
        5 ноември 2020 г., 12–15 ч.)
    •   Разрешено е записването на лекцията
        само за лична употреба от участниците
        в курса по дизайн и анализ на алгоритми
        за целите на обучението!
    •   Представяния на графи.
        Обхождане в ширина
        и неговите приложения

  • 9 ноември — 15 ноември
    •   Алчни алгоритми
        (упражнение в електронна среда,
        10 ноември 2020 г., 19–21 ч.)
        _______________________________
    •   Алгоритми върху графи
        (лекция в електронна среда,
        12 ноември 2020 г., 12–15 ч.)

    •   Обхождане в дълбочина
        и неговите приложения.

        Динамично програмиране върху
        ориентирани ациклични графи.

  • 16 ноември — 22 ноември

  • 23 ноември — 29 ноември
    •   Алгоритми върху тегловни графи
        (упражнение в електронна среда,
        24 ноември 2020 г., 19–21 ч.)
        __________________________________
       
    •   Второ контролно — 26 ноември 2020 г.,
        в зала 229 на ФМИ, от 12:15 ч.
       
        Задължително е представянето
        на документ за самоличност —
        лична карта от МВР.
       
        Задължително е носенето на маска.
       
    • Файл icon
      Задачите от второто контролно Файл
    •   __________________________________
       
        Динамично програмиране
        (лекция в електронна среда,
        28 ноември 2020 г., 11–14 ч.):
        — задача за раницата;
        — подмножество от числа с даден сбор;
        и др.

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

  • 7 декември — 13 декември
    •  Комбинаторни задачи за броя на редиците,
       всеки два съседни члена на които
       удовлетворяват дадено изискване
       
       Такива задачи могат да се решават
       както чрез динамично програмиране,
       така и чрез преброяване на пътищата
       в подходящ граф.

  • 14 декември — 20 декември
    •  Сложност на алгоритмични задачи

  • 21 декември — 27 декември
    •   NP-пълни задачи
       
        Теория има в лекционните записки
        на страницата с учебни материали.
       
    • Файл icon
      Някои NP-пълни задачи Файл
      (доказателства с помощта
      на полиномиална редукция)

  • 28 декември — 3 януари

  • 4 януари — 10 януари

  • 11 януари — 17 януари

  • 18 януари — 24 януари

  • Текущ контрол
    •   Първо контролно — 15. X. 2020 г.:
        анализ на времевата сложност
        на итеративни и рекурсивни алгоритми.
    •   Първо домашно — 1. XI. 2020 г.:
        сортиране и търсене.
    •   Второ контролно — 26. XI. 2020 г.:
        инварианти, сортиране и търсене,
        алгоритми върху графи.
    •   Второ домашно — 7. XII. 2020 г.:
        алгоритми върху графи.
    •   Малък проект — 20. XII. 2020 г.:
        комбинаторни задачи, решими с графи
        и с динамично програмиране.
    •   Трето контролно — в края на семестъра:
        — комбинаторни задачи, решими с графи
        и с динамично програмиране;
        — долни граници на времевата сложност
        на алгоритмични задачи;
        — синтактичен анализ.
    • Файл icon
      Задачите от третото контролно Файл

  • Подготовка за изпит
    •   Изпитът е насрочен за 10 февруари 2021 г.,
        в зала 200 на ФМИ, от 13:00 ч.
       
        Задължително е представянето
        на документ за самоличност —
        лична карта от МВР.
       
        Задължително е носенето на маска.
       

  • Изпит — 10 февруари 2021 г.

  • Поправка — 27 август 2021 г.
    •  Задачите и резултатите са налични тук.