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


При проверката на работите от експресната поръчка от вариант А 

забелязах тези често срещани грешки:


1.  За първата задача -- опит за решение с някакъв алгоритъм от тип "разделяй и владей",

    при който използваме двоично търсене по главния диагонал например.

    Ако не намерим търсената стойност, продължаваме неясно как

    и оттам правим извод, че сложността е Theta( (lg n)(lg m)).

    На лекции видяхме, че при m = n тази идея води

    до алгоритъм с времева сложност Theta(n), като анализът е много сложен.

    При изключително опростяващото допускане за перфектна дихотомия

    върху главния диагонал на всяко ниво на рекурсията,

    рекурентното уравнение е T(n) = 2T(n/2) + lg n

    с решение T(n) = Theta(n), получено чрез мастър-теоремата.

    Решението в никакъв случай не е логаритмично спрямо n.

    Доказателство по метода "игра срещу противник" доказва долна граница 2n-1.

    Не е невъзможно да се получи по-ниска долна граница, например Omega(lg n), с дърво,

    но тази долна граница не е точна.  Няма противоречие между двете долни граници,

    просто по-високата е по-интересна, а най-интересна е точната долна граница 2n-1.


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

    и вземане на по-голямото подмножество върхове от един цвят.

    Със сигурност това дава антиклика, но не непременно максимална.

    Това е все едно да изберем произволен връх на дървото за корен

    и да разгледаме върховете по равнища, вземайки или четните, или нечетните равнища.

    Контрапример е граф "гъсеница", който се състои от един път (тялото на гъсеницата)

    и към всеки връх от тялото са закачени много висящи върхове (крачетата на гъсеницата).

    Оптималното решение е множеството от върховете на крачетата,

    но разбиването по равнища и вземане на равнищата през едно

    ще ни даде горе-долу половината от максимума,

    защото част от крачетата ще са в единия цвят, а останалите --- в другия цвят.

    Тези решения получават по 5 точки, защото все пак има някаква идея.


3.  В третата задача: да вземем просто множеството от висящите върхове.

    Това е буквално преписване на упътването без никаква мисъл и се оценява с 0 точки.

    Ако дървото е път, това "решение" ще вземе само двата му края,

    а максимумът е горе-долу половината от върховете.