ДАА, пролет 2021

-- Обикновено има оплаквания от този курс, че е прекалено теоретичен и откъснат от практиката.  Сега има пример за обратното: курсът е станал прекалено практично ориентиран.   Има писмена работа, в която се казва, че не знаем нищо за функцията floor. ?!?!

Ако сте учили C, би трябвало да я знаете.  Тя е част от C стандарта поне от 20 години.  Декларирана е в math.h и за нея се линква с "-lm" в gcc.  floor(x) е най-голямото цяло число, ненадхвърлящо от x, където x e double.  Дуалната е ceil(x).

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

-- решение на задача 1 започва с "База:  k = mid".  Това е някакъв абсурд.  База на КАКВО?  Какво е твърдението, което ще доказвате?  Без формулиране на твърдение няма доказателство.  Искам пълни отговори, а не отговори-опорни точки, от които сам да си направя решение.  Нула точки.

-- в задача 2 има доказателство с дърво на рекурсията на а).  Наистина, в условието е казано, че може да се ползват и неформални методи, но точно а) с дърво е изключително трудно да се реши, понеже имате 4 викания с n-1 и 3 викания с n-2.  Трябва доста да се потрудите, за да направите правилна оценка на асимптотиката (2 + sqrt(7))^n.  Предвидимо, въпросното решение бърка жестоко, казвайки, че решението е Тита-от-n.  Само събираемото вдясно 4T(n-1) дава поне Тита-от-4^n.  Да пропуснете факта, че решението е експоненциално (каква е основата е друг въпрос) и да твърдите, че е линейно, е груба грешка.

-- пак в същата работа, решението P(n) = Theta(lg lg n) е написано директно, без никакво обяснение.  Това води до -3 точки.  Поне един ред от сорта на "Съгласно изучаваното на лекции" или нещо такова е добре да има.  Няма да изгубите фатално много време, ако напишете кратка обосновка

-- пак в същата работа, има опит за решение на уравнението на Q(n) чрез метода на Akra-Bazzi.  Хубаво е, че сте запознати с него, но го ползвайте правилно, ако ще го ползвате.  В тази работа се казва, че p = -2, откъдето нещата отиват в канавката и се стига до извод, че асимптотиката е 1/n^4, след което пише "==> T(n) = Theta(n^4)".  Това е нещо като опит за измама: ако стигаш до извод 1/n^4, който очевидно е грешен, трябва да се върнеш и да си намериш грешката, а не да го променяш на n^4.  То не е и вярно, че е n^4.  Въпросното p всъщност е 2, понеже

  2 (1/2)^2 + 8 (1/4)^ = 2/4 + 8/16 = 1/2 + 1/2 = 1

-- има героичен опит за решение по индукция на задача 2, T(n).  Защо?  Имате метода с характеристичното уравнение, който е приложим, той е формален и каквото ви даде, няма нужда да доказвате по индукция.  С него решението излиза на няколко реда.  Опитът по индукция е за 4^n, което не е вярната асимптотика и нищо чудно, че голямото-О не излиза.  Тъй като долната граница 4^n е доказана, макар че тя не е точна, давам 2 точки за усилието.

-- в същата работа, на задача 2, S(n), се казва, че log_2 (6) приблизително е 2.4.  Всъщност с точност до втория знак след десетичната точка е 2.58, но точната стойност е без значение.  Важното е, че е по-голямо от 2.5, което може да се докаже без ползване на калкулатор, само от факта, че sqrt(2) < 1.5.  Нула точки тук.

-- в същата работа, и Q(n), и P(n) са решени по индукция, като решението за P(n) е грешно: доказателството за горна граница О-голямо пропуска факта, че има и нехомогенна част +1.  За Q(n) пълен брой 6 точки, за P(n) само две точки.  Не правете всичко по индукция.  Затова учим и формални методи -- за да може, когато са приложими, да ги ползваме и да ни е по-лесно.

-- в друга работа, задача 2, Q(n) се решава с Akra-Bazzi.  Правилно се намира, че p=2, после при решаването на интеграла някак ln n изчезва и "решението" става само n^2.  Давам 3 точки, понеже това е труден метод и явно се владее в основни линии, но все пак трябва да умеете да ползвате ученото по ДИС.

-- в едно решение на задача 2, T(n), се казва, че sqrt(28) = 5 sqrt(3).  Това е доста груба грешка, която не ми прилича на грешка при писане.  Изглежда да е липса на математически фундамент.  Нула точки на ЦЯЛАТА задача 2.

-- още едно решение на задача 2, Q(n), чрез Akra-Bazzi, което коректно намира p=2 и после оплесква решаването на интеграла: ln n изобщо не се появява.  3 точки, защото все пак метода на A-B се владее в основи.  Вижте, ДИС е важно нещо, което се ползва чат-пат в курса по алгоритми.  Както виждате, понякога се налага да се решават интеграли.  Ако ще ползвате A-B, трябва да умеете да решавате интеграли.

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

-- има странно решение на зад 3, което завършва с коректното Theta(n lg n), обаче извеждането е нула.  Това може да е преписано или да налучкано случайно.  Сложността се получава чрез сума (което е ок), която е двойна сума в началото, като над Сигмата има "1", а под Сигма-та е записано на един ред "i = n" и на втори ред "i --".  Формално, това не става, въпреки че виждам какво се има предвид.  ПРИЕТО е отдолу да има "i = a", отгоре "b", като, ако a>b, сумата е нула, защото i взема стойности от празното множество.  Дообяснението "i --" е формално нищо.  По-лошо.  Във вътрешната сума отново индексната променлива е i (лошо!), като излиза, според това решение, че \sum_{i = 1}^{floor(n/m)} 1 = log n.  Формално, това е пълна безсмислица.  m не може да не участва в резултата от това сумиране, ако то е написано така.  Нула точки.  Пак казвам, това може и да е преписано като краен резултат и после с някакви нагласявания, които са формално безсмислени, да се "стига" до верен извод.

-- в същата работа, зад 1, има коректно формулирана инварианта, в поддръжката коректно се казва да разгледаме достигане, което не е последно, но после се разглежда случая A[mid] = mid, което не е ок.  Ако онова достигане не е последно, то няма как A[mid]=mid, понеже в такъв случай алгоритъмът би терминирал и следващо достигане не би имало.  Този случай е за фазата Терминиране от доказателството. -5 точки.

--  Има решение на втора задача, T(n), което казва, че корените са (3 +- sqrt(28))/8.  Това е грешно, но има много по-голям проблем.  Общото решение при тези корени е дадено коректно, след което се твърди, че асимптотиката е Theta(n^2).  Това вече е груба грешка.  (3+sqrt(28))/8 е по-голямо от 1, поради което експонентата с тази основа доминира, асимптотична, n^2.  Това е много груба грешка.  Едно от нещата, които трябва да останат от този курс е, че всяка експонента доминира всеки полином.  Нула точка на цялата задача 2.

-- в същата работа, като решение на зад 3 се предлага Theta( floor(n/m)).  Решението трябва да е ф-я на n.  Променливата m е вътрешна.  0 точки

-- има странно д-во на асимптотиката в задача 3, в което се казва

\sum_{i = n, i /= 2}^{i=1} n/i = 2n -1 , а нашата ф-я нараства с i+1 вместо с 2i ==> има log(n) повече стъпки ==> ... = Theta( n log n)

Асимптотиката е такава, но извеждането не струва.  Първо, при нотацията с голямо-Сигма не е прието да се пише изменението на индекса по този начин.  Индексът е прието да нараства от стойността под Сигма до стойността над нея.  Коректно би било, примерно,

n + n/2 + n/4 + ... + 1 =Theta(n)

Второ, и по-лошо, резултатът не е доказан.  Такава импликация няма.  Факт е, че ако в знаменателите не са поредни естествени числа, а поредни естествени числа, всяко на степен, по-голяма от 1, редът става сходящ.  Вижте например https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&ved=2ahUKEwi0ndam9NfwAhXLFXcKHY2pB6kQFjALegQIHhAD&url=https%3A%2F%2Flink.springer.com%2Fcontent%2Fpdf%2Fbbm%253A978-0-387-27561-1%252F1.pdf

-- в едва работа се казва, че в задача 3 може да изразим алгоритъма (каквото и да означава това) с рек. уравнение T(m) = T(m-1) + A(m), където A(m) = A(n/m) + 1, а последното било решимо с МТ.  Първо, алгоритъмът е итеративен и естественото е да оценим сложността чрез сума, не чрез рек. у-ние.  Второ, "A(m) = A(n/m) + 1" не  е решимо с МТ.  Още по-лошо, на тази задача е написано още едно решение, явно в белова.  Всяко от тези самО по себе си е нула точки.  Повече от едно решение в белова на една и съща задача е автоматично нула точки.

-- в същата работа, зад 2, T(n): намира се правилно общото решение и се оставя така.  Нула точки по очевидни причини.

-- има решение на задача 1, което показва разбиране и би могло да стане коректно решение за пълен брой точки, но, за съжаление, е лошо формулирано и получава 0 точки.  Казва се "Инварианта: на всяка проверка ... на ред 2 нямаме намерен елемент k, такъв че A[k] = k".  Какво означава "нямаме намерен"?  Аз виждам какво се има предвид, но това е неформален изказ.  При преподаване е ОК да се изразим така.  При верификиция не е ОК.  Инвариантата трябва да казва неща за променливите на алгоритъма, а не да говори за нас ("нямаме").  Нула точки...

-- в същата работа, Heapsort е написан чрез n викания на ExtractMin "A[i] <-- ExtractMin(h)".  Става, обаче няма д-во за коректност.  Искам да видя, че умеете да правите формални д-ва за коректност, а не че просто разбирате интуитивно нещата.  5 точки за коректен код без д-во.

--  има решение, в което задача 2, T(n), се намира мултим-вото от корените и нещата остават така.  Нула точки по очевидни причини.  В същата работа, опит за решение на Q(n) чрез дърво, в което се отбелязва, че височината е логаритмична, а на всяко ниво се прави n^2 работа.  Това не е достатъчно, понеже дървото е "криво".  Пример за това има в лекционните записки и сборника.  Тук няма да го пиша пак.  Нула точки.

-- в същата работа има коректно формулирана инварианта, при доказването на поддръжката на която обаче се казва "нека сме на ред 2 и предстои още едно изпълнение" и после се разглежда възможността на ред 4 условието да е истина.  Ако на ред 4 е истина, следващо достигане на ред 2 няма.  -3 точки заради това.

-- има опит за решение на зад 2, Q(n), по индукция за n^2.  Истинската асимптотика не е n^2 и за О-голямо не би трябвало да излезе д-вото.  За Омега-голямо може да стане, ако се прави внимателно, и това заслужава някакви точки, макар и доста под максимума от 25, защото все пак е получено някакво ограничение отдолу.  За съжаление, в тази работа д-вото за Омега не е коректно, понеже неравенството е объркано и е в грешната посока.  Нула.

-- има решение със сериозна грешка в зад 2, T(n).  Корените се намират правилно и после в общото решение експоненциалните ф-ии са записани като e^( (2+sqrt(7))^ n) и т.н.  Моля, научете как работи метода с характеристичното.  Нула.

-- в същата работа има любопитно, не напълно грешно, решение на зад 1.  Инвариантата е формулирана странно "след p итерации на цикъла, или сме намерили k, т.ч. A[k] = k, или сме отхвърлили floor(n/ 2^p) елементи".  Както вече писах, инвариантата трябва да казва неща за променливите, а не за нас -- че сме "намерили", "отхвърлили" и т.н.  В тази писмена работа инвариантата е по-близо до формално коректна и все пак би могло да се даде, да кажем, 5 точки, но д-вото не става.  Д-вото се прави с разбиване на случаи, като първият случай игнорира инвариантата и казва само " ако не същ. е-нт с търсеното св-во, то редове 5,11,13 са недостижими ... така while терминира, когато h-l <= 1 ........ на ред 15 алг. връща -1".  Това не е лъжа, но не е д-во с инварианта.  Нула точки.

-- в едно решение на зад 4, което е коректно като цяло, се е промъкнала напълно ненужно нещо, което не е истина "Приемаме, че BuildMaxHeap коректно ... . Т.е., че A[1] е най-големия (sic) елемент в A".  Това да направим пирамида от A е много повече от това да сложим максималния елемент на първа позиция.  Наличието на "тоест" е проблемът.  Ако беше писано "което влече, че A[1] е максималния елемент", нямаше да има проблем.  Сега -3 точки.

-- в същата работа, решението на зад 1 казва "Инварианта: mid, l, h са винаги <= A.len".  Какво значи "винаги"?  И от тази инварианта не следва нищо полезно.  Нула точки.

-- решение на зад 1 казва "Инварианта: Ако A[mid] != mid и l+1 <= h, то ако A[mid] \in A[1 .. n], то A[mid] \in A[l .. h]".  От това би могло да стане чудесна инварианта, обаче в този вид не е приемлива по чисто формални причини.  При първото достигане на ред 2 (което ми напомня: инвариантата трябва да казва за кой ред се отнася!), променливата mid не е дефинирана, откъдето базата на индукцията не е  доказуема.  Без база няма д-во.  Нула точки.

-- в едно решение на зад 3 се стига до T(n) = \sum_{k=1}^n floor( n/k ).  Това не е приемливо, въпреки че е вярно.  Искам по-прост и по-информативен израз в отговора.  Само 2 точки.

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

-- в едно решение се твърди, че при достигане (не е ясно кое -- някое, всяко?) на ред 3 "се намира медианата на A".  Това е неформално изказване.  Формално коректното би било "A[mid] съдържа медианата".  По-лошо, няма формално коректно доказателство, а само неформално обяснение.  Нула точки.

-- има решение на зад 1, което като цяло е коректно, но съдържа пример за работата на алгоритъма.  Примери не трябват!  Писането на примери е загуба на време.  Единствено ме интересува формалното д-во.  Има наблюдение, че числата трябва да са уникални -- това е добре!  Инвариантата е напълно ок.  Обаче в д-вото ѝ се разглежда и случая, в който mid е точното число.  Това е за терминацията.  Ако това е така, алгоритъмът не достига ред 2 повече. 20 точки.

-- за коректен псевдокод в зад 4, без формално д-во, само 5 точки.

-- има непълно решение на зад 1, което разглежда случаи.  В първия случай, такова k съществува.  Това разбиване на д-вото е ненужно.  Може в едно д-во да се свърши цялата работа (дори такова k да няма).  По-лошо.  Това е писано като "1 сл." .  Няма съответен "2 сл." -- може би време не е стигнало?  Има следващо разбиване на случаи, първият от които пак е наречен "1 сл.".  Това никак не е добре, формално говорейки.  Вече сме на ново ниво  в д-вото и трябва имената на подслучаите да са различни от тези на случаите.  Липсва терминация.  Времето не е стигнало?  Не е трябвало да преписвате псевдокода, това е изяло доста време за нищо.  Само 10 точки.

-- в решение на зад 2, S(n), коректно се установява, че log_2 (6) > 2.5, но в решението стойността му се апроксимира с 2.7.  Това не е добре.   Каквато и крайна апроксимация да вземете, ен-на-тази-степен или е о-малко, или е омега-малко от истинското решение.  Формално, трябва да остане с логаритъма.  На практика, естестено, ще вземем някаква апроксимация, но, теоретично говорейки, по този начин имаме или само горна, или само долна асимпт. траница.  -2 точки.

-- в същата работа, зад 2, P(n), се минава в друга променлива m, като n = 2^2^n, и решението се намира коректно в m.  Да, но началната променлива беше n и решението трябва да е ф-я на n.  -2 точки

-- в същата работа, зад 2, Q(n), се ползва Akra-Bazzi и някак се стига до извода, че е Тета от n^3 lg n.  Тук е сгерешен порядъкът сериозно. 0 точки.  A-B е тежък метод!  Има по-прости формални начини да се намери асимптотиката.

-- в същата работа е сбъркан кодът на Heapsort.  Има

for i = 1 to n

  BuildHeap(A)

n пъти да правим пирамида?? 0 точки

-- в същата работа инвариантата в зад 1 не става. И тук се говори в човешки термини "... не е намерен ел. A[k] = k". 0 точки.

-- има решение на зад 1, което е безукорно с изключение на това, че в инвариантата се говори за нашето знание "При всяко достигане на ред 2 знаем, че ...".  Това вкарва някакъв субективизъм в доказателството.  Оставете какво знаем ние.  Въпросът е какво е вярно, независимо от това дали го знаем или не.  Не вземам точки, само казвам.

-- на зад 1 само инварианта, смислено формулирана, без д-во (само начало): 5 точки.  Времето не е стигнало?

-- има решение на зад 2, T(n), което бърка с характеристичното уравнение, слагайки + пред 3. Дори при тази грешка се получава корен 3, откъдето веднага следва, че асимптотиката е поне 3^n.  Решението твърди, че е Тита от n.  Ако намаляването е -1 и -2 и коефициентите пред T вдясно са +4 и +3, трябва да е очевидно, че асимптотиката е експоненциална и остава да се намери основата, която е >1.  Това е сериозна грешка.

-- в същата работа е сбъркано сравнението на 2.5 с log_2 (6), асимптотиката на P(n) е намерена като n, а за Q(n) се твърди, че е Тита от 1/2^n.  Всичко това говори за сериозни пропуски в математическия фундамент.  Ф-ята 1/2^n е НАМАЛЯВАЩА.

-- в друга работа се казва, че P(n) = A . 1^(sqrt(n)).  Студенти от ФМИ не би трябвало да грешат така.  Едно-на-степен-каквото-и-да-е е единица.  Твърдите, че решението е константа?  Сега виждам, че до този извод се стига след субституция n --> k^2, като става P(k^2) = P(k) + 1.  Това не е решимо с метода с хар. у-ние.  Имате много сериозни пропуски.

-- в същата работа, в задача 1 се разглеждат случаи n=1,2,3 (защо??) и после направо "База: ..." без изказване на инварианта.  Нула точки.  Не може да има доказателство на твърдение, което отсъства.

-- във втора работа вече виждам коректно решение на зад 2, S(n), не чрез МТ, а субституция с 2^m и после с хар. у-ние.  МТ е по-проста.  Защо не я ползвате?  Научете МТ.  Ако нехомогенната част е много "дива", с минаване към хар. у-ние няма да стане, а МТ работи винаги (освен за наистина дива нехомогенна част). В същата работа и задача, за Q(n) е получено решение с 4^( log_2 n ).  Това е просто n^2.  Не вземам точки, но отговорът трябва да е максимално прост и прегледен.

-- в същата работа, в зад 4 има ок код и после инварианта "Всеки път ... A'[n+1-i .. n] се състои <една добре задраскана дума> елементи на входния масив A в сортиран вид".  Формално, това не казва нищо.  Какво е задраскано не виждам, но, дори и да виждах, то е задраскано и все едно го няма.  Д-вото е ок.  Давам 10 точки.  За пълен брой точки трябва формално коректна инварианта.  Тази трябва да се допълни с нещо.  Само така не става.

-- в същата работа, в реш. на зад. 1 се казва, че д-вото било полу-формално.  Лошо.  Искаме формални д-ва.  Инвариантата говори за "елемента, който търсим".   Пак се вкарва субективизъм.  Ако обяснявате, такива изрази са напълно на място, защото придават някаква живост на тази суха материя.  Ако доказвате коректност, те нямат място, също както нямат място, когато пишете компютърни програми.  Въпросът е какво е съдържанието на променливите.  Какво търсим ... може и нищичко да не търсим. Тук нещата не са толкова зле, колкото в другите "решения" със субективизъм, но д-вото и тук пропуска факта, че, ако има следващо изпълнение, няма как A[mid]=mid.  10 точки.

-- в решение на зад 1, инвар. е "... ако A[ (l+h)/2 ] = (l+h)/2, връщаме (l+h)/2".  Това просто не става.  Вярно е, но не ни дава желания резултат.  0 точки

<тук изтрих, без да искам, няколко коментара; firefox има лошо undo, съжалявам>

-- има странно решение на зад 3, което казва правилно, че асимпт. е n lg n, но без никаква аргументация (това може да е и преписано), а отделно се разглежда възможността n <= 0.  Защо?    Нула точки.

-- има странно решение на зад 1, което разбива на случаи n=1, n=2, n >= 3, които на свой ред се разбиват на n \in {3,4,5} и n >= 6.  никакъв опит за инварианта.  0 точки.

-- има решение на зад 2, S(n), което "доказва" по индукция, че S(n) е Тита от n^2 lg n.  Би трябвало да забележите, че само нехомогенната част расте по-бързо.  Тук не мога да дам точки дори за Омегата, въпреки че аргументацията там е ок.  При опита за О-голямо се "намира" константа, която е от интервала ( sqrt(n), + \infinity ).  Това е груба грешка, която нулира цялата задача.  Научете разликата между константа и променлива.  Ако n е променлива (която може да става колкото голяма искаме), няма как ПРЕДВАРИТЕЛНО избрана константа да е в интервал, долната граница на който е sqrt(n).

-- в едно решение на зад 1 се дава инварианта "за всяко достигане ... , ако:

1. A[k] = k

2. h - l > 1,

то ... k \in [l .. h]"

Без квантор за съществуване пред k, това е формално некоректно и не казва нищо.  Д-вото нататък е ок, така че давам 15 точки. 

-- в решение на зад 1 се казва "инварианта ... след всяка проверка за край на цикъла, алг връща k или -1".  След ВСЯКА проверка алгоритъмът връща?  Това е пълна безсмислица.

-- в едно решение на зад 4 се ползва помощен масив B, като дори не е казано, че е масив, а аз трябва да се сетя сам.  Пише

Let B, B.size = A.size

Формално, това обезсмисля кода, а неформално -- Heapsort може да се реализира прекрасно с O(1) допълнителна памет.  Нула точки.

-- В същата работа, решението на зад 1 е някаква надраскана каша, която може да е само чернова.  Нула точки.