ДАА Инф, пролет 2025

1) В зад 4,  ако алгоритъмът е изграден по алчната схема, което е очевидното решение, д-вото за коректност **е** д-во за оптималност.  Което не е лесно да се направи с инвариант.  Със сигурност може да стане и с инвариант, но инвариантът и негово д-во не са просто прилагане на шаблона за инвариант, който сме виждали.

Д-вото с допускане на противното е по-просто.  Виждали сме подобно на лекции при алчния алгоритъм за намиране на макс независимо подмножество интервали.

2)  В зад 2 някои решения казват, че има log n долна гр. за търсене и оттук следва, че алгоритъмът на професорът е некоректен.  Тази долна гр за търсене е валидна, ако търсенето става със сравнения.  Ако обаче числата в в дв. пирамида от тип макс, то максимумът е в корена и намирането му става в константно време.  lg n при Extract-Max идва по "поправянето" на пирамидалността след махането на корена -- за това не сме доказвали долна гр. на лекции.

3) В зад 4, някои алгоритмични решения ползват масив n x n .  Това е квадратична памет.  Квадратична памет означава (поне) квадратично време, което е недопустимо за тази суперлесна задача.

4) В задача 1, някои решения разглеждат неориентирани графи.  Задачата е за ориентирани графи. 

5)  Има решения на зад 3, които правят тази редукция (на VC към SC) : A = V, F = { N[v] : v \in V }, l = k.  Това не работи.  Ако графът има поне един универсален връх, то генерираната фамилия F съдържа V като елемент и тогава има покриване на фамилията от само един елемент.  Докато граф с универсален връх може да има колкото искате голямо върхово покриване -- като екстремен пример, в K_n всеки връх е универсален, а мин върхово покриване е с мощност n-1.