Често срещани грешки на изпита
Често срещани грешки в решенията:
1) В първата задача ясно е казано, че не може да се сравняват болт с болт, нито гайка с гайка. Да се каже "сортираме масива с болтовете" или "сортираме масива с гайките" като стъпка от решението е грешка. Ние не можем да сторим това директно, защото не можем да ги сравняваме.
2) Пак в първата задача, да се говори за масива от диаметрите няма никакъв смисъл. Те не са дадени. Ако те бяха дадени, задачата щеше да е изключително проста. Никъде в условието не се казва, че диаметрите са дадени, а и очевидно няма как да ги получим. Ерго, не можем да ги ползваме в решението си.
3) В третата задача (дага), всички решения, които акумулират желаното количество чрез инкрементации като "c ++", са невалидни. Ако изобщо този алгоритъм е коректен, то той е поне експоненциален като сложност, защото пътищата може да са експ. много в броя на върховете, така че, ако ги броим един по един, няма да приключим никога (в рамките на ограничения си живот) в най-лошия случай.
Същото е и за DFS-и, които не маркират върхове (за да избягват повторно влизане).
4) За задача 4, ако се опитваме да генерираме систематично всички стрингове с дължина не по-голяма от тази на дадения стринг, пак изпълняваме експоненциален алгоритъм, което е неприемливо. Алгоритъмът CYK е споменаван в час като идея.
5) В задача 5, редукция от KNAPSACK би била тегава. Общият пример на KNAPSACK е наредена петорка <м-во, тегла, цени, лимит на раницата, мин. обащ цена>. Ако трансформираме това към общия пример на SET COVER, трябва да кодираме числата ефикасно (бинарно), което би било супер тегаво. По принцип всяка NP-c задача се свежда до всяка друга с полин. редукция, но някои от тези свеждания са по-лесни, други, по-трудни. VC е подходяща, понеже числото в нейния общ пример е малко.
6) В задача 5, редукция от DOMINATING SET не е толкова очевидна, колкото от VC. VC и DS са различни задачи, макар да звучат подобно. Помислете така: графът на Petersen се доминира от 3 върха най-малко, но се покрива от най-малко 6. Следователно, <гр-Petersen, 4> е ДА-пример за DS, но е НЕ-пример за VC.
-- ММ