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

◄8 май - 14 май
►22 май - 28 май
  • Теми от лекцията на 17.05:

    Динамично оптимиране
    • Въведение
      • Условия за прилагане
      • Свеждане към под-задачи
      • Зависимост между задачите
      • Граф на задачите
      • Рекурсивна реализация
      • Итеративна реализация
      • Редуциране на използваната памет
    • Задача за раницата при многократно вземане на елемент
      • Еднуаргументни задачи
      • Възстановяване на оптималното решение
    • Задача за раницата при еднократно вземане на елемент
      • Допълнително параметризиране на задачите
      • Запомняне в матрица
      • Предимства и недостатъци на итеративните и рекурсивните реализации
      • Редуциране на заетата памет за сметка на времето
    • Обобщение
      • Кеширане с map
    Задачи за упражнения:
    • Най-дълга нарастваща подредица (само решението с O(N*N))
    • Най-дълга обща подредица на две редици
    • Най-дълъг общ отрез на два масива (отрез е като подниз, но не само за низове)
    • *Edit distance на два низа (колко операции insert, delete и replace са необходими за да се достигне от един низ до другия).
    Забележки:
    Явно много често се получава така че студентите не успяват да разберат нещата в упражненията. За това моля и студентите и преподавателите да проявят малко инициатива за решаване на този проблем:
    • Студентите да питат повече конструктувни въпроси и да показват когато нещата не са им ясни.
    • Преподавателите да следят по-често дали студентите разбират това което се говори, като задават подходящи въпроси.

◄8 май - 14 май
►22 май - 28 май