ДАА, КН2, пролет 2022

1) зад 1: не може да има валидно доказателство, ако не е изказано твърдение.  В няколко работи на зад 1 се започва направо с "База: ...".  База на КАКВО?

2) зад 1: мнозина са пропуснали, че се иска да се докаже конюнкция от три твърдения.  Такова е условието на задачата.  За пропускане на p >= 0  и q >= 0 съм вземал половината точки.

3) зад 5: алчният подход не работи.  Всяко решение, което взема минималната стойност за боядисване на h1 (или hn)  и за продължава върху останалите въз основа на това, без да дава възможност да бъде променено решението за h1 (или hn), получава нула точки.  Тривиално е да се измисли пример, в който локален избор за h1 ни прецаква глобално.

4) зад 5: имаше решения с графи, но нито едно не беше формулирано пълно и изчерпателно.  Ако ще е с граф, добре е да е ориентиран -- никъде не се казва, че цените за боядисването са положителни.

5) зад 2: има само едно пълно решение, което е удивително.  Функциите са 12 на брой, така че очаквам 11 експлицитни коректни сравнения на функции, които са СЪСЕДИ в окончателната наредба.  Нали отбелязахме на лекции, и от много пъти, че непосредственото съседство не може да се изведе косвено от транзитивността?

6) зад 5: всяко експоненциално решение се оценява с нула точки.

7) зад 3: иска се аргумент за ДОЛНА ГРАНИЦА, а не алгоритъм, който решава задачата с указания брой сравнения.  За алгоритъм се дават 10 т само ако е доказана долната граница.  То това го и пише в условието.

8) зад 4: най-чистото и бързо решение е с контрапример.  Имаше доста решения, които не дават контпрапример, а обясняват надълго защо алгоритъмът на професора не е непременно коректен.  Това щеше да "бЕре мед", ако беше дадено доказателство за коректност на алгоритъма и трябваше да се посочи слабо място в аргументацията.  Но случаят не е такъв -- не се знае защо той мисли така.  Нали разбирате -- това, че сте отхвърлили някои възможни пътища за доказване на коректност не означава, че сте показали, че алг е некоректен.