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

В доста писмени работи отговорът на задача 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, което е по-малко от броя на жителите на България.