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

Това са някои нередности в решенията на контролното

-- В първата задача се говори за база и потдръжка [sic], без да е дадена инварианта.  Това е 0 точки.  Няма как да бъде доказано твърдение, което не е формулирано.

-- зад. 2. f8 е ограничена отгоре и отдолу от константа.  f8 = Theta(1).  Но f8 не е равна на константа.

-- В задача 1, алгоритъмът е рекурсивен.  Формалното д-во за коректност на рекурсивен алгоритъм 1) разглежда базовия случай /базовите случаи/, демек спирачката на рекурсията, и показва, че в него /тях/ алгоритъмът връща това, което се очаква 2) допуска, че рекурсивното викане /рекурсивните викания/ връща/т/ коректно и въз основа на това допускане доказва, че началното викане връща това, което се очаква. Преразказването на кода на алгоритъма не е доказателство за коректност.

-- В задача 1, управляващият параметър е разликата h-l.  Доказателството по индукция трябва да е направено спрямо тази разлика.  Няма доказателство при допускания от вида "MAX(A, 1, m) връща коректно" за някакво m < n.  Трябва да не фиксирате l = 1!  Това е груба грешка.

-- В задача 1, индукцията трябва да е силна.  Не е достатъчно едно инд. предположение.  Няма лошо да допуснем за ВСИЧКИ дължини, по-малки от h-l+1.

-- В едно решение на зад 2 има следната изключително ГРУБА грешка (в LaTeX нотация):

  f_7(n) = \sum_{k=1}^{n!} \frac{k}{2^k} = \sum_{k=1}^{(n-1)!} k \cdot \sum_{k=1}^n \frac{1}{2^k} \asymp (n-1)!

Нула точки на цялата задача.  Студент от ФМИ не може да греши така!  Това не е грешка на ръката, това е катастрофална липса на математически фундамент.

-- В решение на зад 1 се казва "... макс елемент на масива A[1 .. n] е на позиция k или k+1 ...".  Това е безсмислица, понеже в условието k е с екзистенциален квантор.  Не е грешка, но казва (почти) нищо.

-- За зад 2: казах ви да пишете ясно и да обособявате ясно отделните сравнения.  Има решение, в което от някаква нахвърляна каша, подходяща за чернова, но не и за белова, се извежда крайната наредба.  Нула точки.  Искам пълни ясни решения, а не hint-ове, от които да си съставя сам решение.

-- За зад 4: правилен псевдокод е само 5 т.  Основното в тази задача е умението да се изложи формално, макар и непълно (поради липса на време) доказателство за коректност.  Искам да се убедя, че умеете да ползвате аргументация с инварианта.  Доказателства без инварианта, а с "ръкомахане" и общи приказки, дават нула точки, така че при коректен код и ръкомахащи доказателства, общата оценка е 5 т.

-- Едно решение на задача 2 казва, че щом границата на k / 2^k е 0 при k --> безкрайност, то f7 е ограничена отгоре от константа.  Студенти от ФМИ не би трябвало да правят такива грешки.  Това, че общият член на реда клони към нула не влече, че редът е сходящ.  Преди столетия хората са установили, че хармоничният ред е РАЗХОДЯЩ, въпреки че общият член 1/k клони към нула.  Неслучайно учите по ДИС условия за сходимост на редове.  Тази грешка дава -5 точки.

-- Пак задача 2.  Слагане на безсмислени символи за импликация е формална грешка.  Импликацията е логически съюз и е приложима само когато нещата, които свързва, имат булева интерпретация.  Безсмислен запис е "f8(n) = 11 + sin(n!) --> (огр. отгоре) ==> \Theta(1)".  \Theta(1) не е съждение.  То няма глагол.  Това е или безкрайно м-во ф-ии, или анонимна ф-я от него, но и в двата случая не е нещо, което има булева интепретация.  Да има булева интепретация означава да е или истина, или лъжа.

-- Наличието на повече от едно решение на една задача не е разрешено и автоматично анулира тази задача.  Може да има колкото искате чернова за една задача, това е ОК, но беловата трябва да е само една.  Причината е, че съм имал горчив опит с две решения на една задача, в някаква степен различни, при което студентът опитва post factum, след публикуването на примерните решения, да иска да му/ѝ се признае решение, което в някакъв смисъл е максимумът на двете: от всяко решение да се вземе по-добрата част.  Това е опит за измама, с който е трудно да се спори.  Най-лесно, и най-правилно, е да се анулират множествени различни решения на една и съща задача.

-- Има решение на задача 1, което започва "Ще го докажа с индукция по n".  Това е много лош изказ.  Ще докажа КАКВО ТОЧНО?  И защо с индукция по n?  По-добре е да се каже "с индукция по разликата h-l". Следва "На всяко достигане на ред 3, ... ".  Това вече е груба грешка.  Ред 3 съдържа return и достигането му е еднократно.  0 точки.

-- Има решение на зад. 3, което започва директно с рекурентното уравнение.  Би трябвало да има аргументация защо това рекурентно уравнение описва сложността по време.  Без такава аргументация, решението е непълно.  Уравнението е почти коректно (липсва нехомогенната част) и е решено правилно, но решението остава непълно.  Пак да кажа, че решението не трябва да се състои от опорни точки, от които аз да си направя пълно решение.  Само 10 точки.

-- Има решение на задача 2, което е сякаш писано за чернова, въпреки че отгоре има "Белова".  Започва с половин страница преамбюл с асимптотични еквивалентности, без да става дума за сравнения на двойки ф-ии.  После има доста сравнения на ф-ии, които не са съседи в окончателната наредба, вкл. и доста грешни изводи.  Има две коректни сравнения на съседи и една еквивалентност, но за нея не е посочена аргументация.  Само 2 точки на цялата задача.  Няма да повтарям как трябва да изглежда смислено решение на задачата.  "Решение" като това показва хаотична мисъл, от която не се разбира почти нищо от човек, който не знае за какво става дума.  Дори да не бяха грешките при сравненията, такъв отговор е много далече от желаното.  Задачи като зад. 2 не са никак сложни.  Няма съмнение, че повечето студенти, ако видят две ф-ии като тези (изключвам сумата, тя е малко трикова), интуитивно разбират коя расте по-бързо.  Трябва да се види освен това, че умеят да комуникират идеята си по ясен, недвусмислен, изчерпателен, без да е досадно многословен, начин.

-- В решение на зад 1 се разглеждат случаи, което добре, но във формулировката на Случай 1 се дефинира k, което k се ползва и в Случай 2, но вече без деф.  Добрият стил изисква k да се дефинира извън случаите (по-точно, преди тях).  По този начин написано, формално, k е недефиниран символ в Случай 2.  Нещо като променлива в програма на С, която променлива е дефинирана в една ф-я и се ползва без деф. и в друга ф-я.

-- Отново решение на зад 1, което твърди, че (в LaTeX нотация)

\sum_{k=1}^{n!} \frac{k}{2^k} = \sum_{k=1}^{n!} \frac{1}{2^k} \cdot \sum_{k=1}^{n!} k

И тук нула точки на цялата задача.  Това показва тежки пропуски в математическата култура.  Не може да е моментен лапсус.

-- Има решение на зад 1, което започва с "За всяко достигане на ред 1, подмасивът изпълнява търсеното свойство: A[1] < ... < A[k] и A[k+1] > ... > A[n] и най-големият елемент е A[k] или A[k+1]".  Това се оценява директно с нула точки.  Всяко достигане на ред 1 е само едно, защото в едно рек. викане ред 1 се изпълнява веднъж (оставяме настрани това, че ред 1 е коментар).  По-лошо е, че k е недефинирана в това твърдение.  В условието на задачата, k е квантована променлива.  Извън обхвата на квантора, k  е недефинирана.

-- В решение на зад 1 се съдържа фразата "Щом А е особен ==> за произволно k в [1 .. n]: макс. елемент на A е или A[k], или A[k+1]".  Това е пълна безсмислица.

 -- Има решение на зад 3, което прави коректно рек. уравнение, но намира неправилни корени -1 (който е ОК) и 1/5.  На пръв поглед, това е дребна грешка от слагане на множител -5 в знаменателя на израза за корените.  На втори поглед, това показва механично папагалско прилагане на формализмите, защото достига до извода, че асимптотиката е Тита от (1/5)^n.  Това е много сериозно.  (1/5)^n е намаляваща, клоняща към нула отгоре, функция.  Студент(ка), който/която има базова алгоритмична култура, веднага трябва да забележи, че има нещо нередно с корена, по-малък от единица по абс. стойност.  Проверката дали това наистина са корените се прави за секунди. Нула точки.

-- Едно решение на зад 1 (по индукция) казва "поддръжка: допускаме, че на ред 2 в текущия масив се съдържа максимален елемент".  Формално, това е груба грешка, която нулира цялото решение.  Това, че текущият масив съдържа максимален елемент следва тривиално от това, че е масив от цели числа и релациите <= и >= са линейни наредби.  Всеки масив от цели или дори реални числа има поне един максимален елемент.  Това не е свойство на битоничните масиви, а на всички числени масиви.  Ерго, индуктивната хипотеза е безполезна и няма доказателство.  Нула точки.

-- Груба грешка в решението на зад 1.  Твърди се, че f8(n) е асимпт. еквивалентна на sin(n!).  sin(n!) не е положителна функция.  Дори не е асимптотично положителна, защото за всяко n0 има n > n0, такова че sin(n!) е отрицателна.  Това твърдение е очевидно при реално n (тогава n! се дефинира чрез гама функцията) и не е очевидно при цяло n, но не е моя работа да го доказвам.  Който ползва sin(n!) в Тита нотация трябва да покаже (ако може...), че функцията е положителна или поне асимптотично положителна.

-- Има суперпестеливо решение на зад 1, което словесно обяснява коя функция расте по-бързо от коя друга.  Формално, това е празно решение.  Което получава нула точки.  Правилният израз е "по-бързо, в асимптотичния смисъл" или "асимптотично по-бързо".  Като пример, 2n^2 + n расте по-бързо от n^2, но не и в асимптотичния смисъл.  За да се избегне многословието се ползват асимптотичните нотации и/или релационни символи. Както вече писах, решенията трябва да са пълни и убедителни за човек, който не ги знае, но има достатъчно знания в областта.  Решения-опорни точки не се приемат.

-- Решение на зад 2, което казва

"... \sum_{k=1}^{n!} k \frac{1}{2^k} = n! \Theta(1) = n!"

съдържа неявно грубата грешка, за която писах горе.  НЕ МОЖЕ да разделяте сума от произведения на произведение от суми по този начин.  В някакъв смисъл, това е все едно да кажете, че a1.b1 + a2.b2 + a3.b3 = (a1+a2+a3)(b1+b2+b3)

-- решения на зад 2, ползващи обикновено по-малко "<", са невалидни.  Първо, не сме дефинирали какво означава "f(n)  < g(n)".  Първичната дефиниция на "<" е върху числа, не върху функции.  Ако допуснем, че "f(n) < g(n)" означава "за всяко n от домейна: f(n) < g(n)", това не върши работа за аргументация на асимптотична наредба.

-- в решение на зад 2 се казва "... формули = \Theta(1)".  Това е сериозна грешка.  Бърка се синтаксис със семантика.  Формула не може да е Тита от нещо.  Формулата е синтактичен обект, стринг над някаква азбука, построен съгласно някакви правила.  Ако този стринг е валидна формула, той има семантика, която е функция.  Функцията вече може да е, а може да не е, Тита от нещо си.

-- има иновативно решение на зад 1, което ползва смислено твърдение "нито един елементи на A вляво от l не е максимален и нито един елемент на A вдясно от h не е максимален".  Това е вярно и е доказуемо с индукция в дървото на рекурсията.  Наречено е "инварианта", което не е добра идея.  Инварианта традиционно е инварианта на цикъл.  Тук цикъл няма.  Дървото на рекурсията е изродено (в път, понеже повече от едно викане от едно ниво е невъзможно) и твърдението е доказуемо по разстоянието от корена, т.е. дълбочината.  Дълбочина 0 е базата: твърдението е вярно в празния смисъл, понеже подмасивите вляво от l=1 и вдясно от h=n са празни. 

Обаче иновативното решение е формално некоректно, защото след горе-долу добре формулираното твърдение прави опит за доказателство с инварианта.  Говори се за k-то и (k+1)-во достигане, не се казва на какво, но явно това имитира доказателствата с инварианта на итеративни алгоритми.  15 т. за това решение, в което има потенциал, но формално не е издържано.  Допълнително утежняващо е, че разбиването на случаи и подслучаи всъщност не е разбиване.

-- Има решение на зад 1, което би било чудесно обяснение за неформален курс, който не борави с понятия като индукция.  Започва с дефиниране на x като макс. елемент и коректно разбиване на подслучаи съгласно възможностите за x в A[l .. h].  Неформалното е в това, че се говори за "... (ако x е в лявата половина) алгоритъмът ще продължи търсенето в лявата част".  Така се изразява човек, неползващ индукция.  Човек, ползващ индукция, казва "съгласно индуктивното предположение, рекурсивното викане на ред едикойси връща коректен резултат".  Важна цел на курса ДАА е усвояване на формални методи за доказване на коректност.  Доказателството с алгоритъма-продължава-наляво дава нула точки.

-- има грешен код в зад 4: реализация чрез swap, но swap-ът е само един и е извън for-a.  Във for-а не се местят елементи от масива.  Това няма как да е вярно.

-- на първа задача, решение с индукция казва

"инд. предположение: Когато достигнем return, или връщаме максимален елемент, или връщаме MAX(A, x1, x2) ....".  Това не може да е индуктивно предположение.  Нула точки.

-- решение на зад 1 дава половин страница пример за работата на алгоритъма.  Това не е грешка, но е излишно.  Времето на контролно е ограничено и няма смисъл да се губи.  Примери се дават, когато има обучение.  Същото решение казва

"Инварианта: при всяко i-то достигане на ред 4, нека имаме li , hi, mid_i"

Това е сбъркано по няколко начина.  Нула точки.

-- има решение на зад 4, което е коректен сортиращ алгоритъм, само че е SelectionSort.  Съжалявам, но нула точки,  въпреки че кодът работи.  Общоприетите понятия, вкл. и имената на алгоритмите, трябва да се знаят.  Задачата говори за InsertionSort.