Често срещани грешки във вариант Б на поправителния изпит
=========================================================

1.  Посоката на редукцията е важна.

    Трябва да бъде от задача, за която е известно, че е трудна,

    към задачата, за която искаме да покажем, че е трудна.

    Редукция в обратната посока --- от неизвестната към известната задача --- не доказва нищо!

    Например лесната задача за търсене в несоритран масив (с линейна времева сложност)

    може да се сведе до кошмарно трудната задача за спирането (нерешима алгоритмично)

    чрез следната полиномиална редукция:

    Search(A[1...n], key)
    
    1) for k <- 1 to n do

    2)    if A[k] = key

    3)       return k

    4) while true do // безкраен цикъл

    Масивът A[1...n] съдържа не ключа key <=> програмата Search работи безкрайно.

    Какво следва от това за трудността на задачата за търсене?  Абсолютно нищо.


2.  Във втората задача сортирането по началните моменти е лоша идея.

    Пример за това има в лекционните записки.


3.  Втората задача може да се реши за време Theta(n^2) с граф:

    върховете са лекциите, ориентираните ребра са предшестванията без застъпване.

    Ключово за решението е, че този граф е ориентиран и ацикличен.

    Търсим най-дълъг път в този граф, за което съществува бърз алгоритъм.

    Същинското търсене изразходва линейно време;

    квадратично време е нужно за построяването на графа.

    Ако не е казано, че графът е ориентиран и ацикличен или че се търси най-дълъг път,

    решението не носи точки.