Две често срещани грешки в отговорите на сем. контролно и още нещо
В доста писмени работи отговорът на задача 5 не говори за стратегията на противника У, а описва алгоритъма на Х (че е двоично търсене), което не се иска. Или говори за дърво на вземане на решения, а в условието ясно е казано да се опише стратегията на У.
======================================
В доста работи има една и съща грешка в задача 1, касаеща G(n). Прави се субституция n |--> 2^2^m, с което sqrt(n) става 2^2^(m-1). Дотук добре. После се преписва така
G(2^2^m) = G(2^2^(m-1)) + m
което НЕ Е добре. Нехомогенната страна става 2^2^m при тази субституция. Следва грешно решение G(n) = Theta( (lg n)^2 ). Доста очевидно това не може да е решението, понеже по условия G(n) е n-плюс-нещо-положително.
Този път не води до успех. Ако се напише правилното
G(2^2^m) = G(2^2^(m-1)) + 2^2^m
и се положи G(2^2^m) да е S(m), става
S(m) = S(m-1) + 2^2^m
и методът с хар у-ние не е приложим, понеже нехомог. част е двойна експонента.
Може да стане така. n |--> 2^m, при което
G(2^m) =G(2^(m/2)) + 2^m
Полагаме S(m) да е G(2^m) и получаваме
S(m) = S(m/2) + 2^m,
което е решимо с МТ. a=1, b=2, f(m) = 2^m, по третия случай S(m) = Theta(2^m), оттук G(n) = Theta(n).
------------------------------------------------------------------
2^2^n се интерпретира като 2^(2^n), а НЕ като (2^2)^n. Втората интерпретация е: експонента с основа 4. Първата е: двойна експонента. Разликата е грамадна. 2^(2^10) е 2^1024, което е много повече от броя на атомите във Вселената, поне по съвременните представи. (2^2)^10 е 2^20, което е по-малко от броя на жителите на България.