забелязани грешки
Вчера съставих списък от 20+ забелязани грешки/проблеми, но някак муудъл го изтри при проверка на съобщение :( Не мога да го възстановя, без да мина през > 1/2 работи на КН2, което би било часове отгоре. Само по памет:
1. Основна грешка в задача 1 е фокусирането върху работата на алгоритъма. В тази задача трябва да обясните какво прави противникът. Алгоритмите са безброй много и няма шанс да опишете всеки възможен алгоритъм за тази задача. Да описвате един конкр. алг. или дори конкр. идея е безсмислено. Трябва да опишете детайлно какво прави противникът. За него, алгоритъмът е черна кутия. Той (врагът) няма представа как работи алгоритъма. Единственото, което врагът знае е, че алгоритъмът връща или ДА, или НЕ. Ако алг. пропусне поне една двойка върхове от двата дяла, противникът трябва да може да опровергае алгоритъма и в ДВАТА случая. Това е всичко. А защо алгоритъмът е дал този отговор няма никакво значение.
2. В задача 3, всички опити за решение с разбиване на върховете в нивА съгласно четността на разстоянието от корена са обречени. Тази задача не се решава с 2-оцветимост. Защо -- вижте примера в записките.
3. имаше поне едно решение на зад 3, което е експоненциален алг. Нула.
-- -- -- --
от днешната проверка:
4. фразата "на всяко к-то достигане на ред едикойси" е безмислица. к-тото достигане е САМО ЕДНО. Не е грешка, но е изключително дразнещо.
5. Решение на зад 1 започва със "За да разбере дали граф е свързан, алгоритъмът трябва да провери дали между всеки два върха има ребро".
Това е директно нула точки за цялата задача.