ДАА, пролет 2021

1.  Има решение на зад 1 с динамично, което обаче не е динамично

def solve(arr[1 .. n])

  return max(arr[1 .. n])

def maximize(arr[1 .. n])

 if n == 1

    return arr[1]

  return maximize( arr[1] + minimize(arr[2 .. n],

                arr[n] + minimize(arr[1 .. n]) )

def minimize(arr[1 .. n])

 if n == 1

  return arr[1]

return min( maximize(arr[2 .. n]), maximize(arr[1 .. n-1])

Има няколко проблема с този код, въпреки основната идея е добра (минимаксно решение).  Това не прилича на решение с динамично -- къде е таблицата?  Ние за мемоизация не сме говорили, нито това решение споменава мемоизация, така че допускам, че се има предвид обикновена рекурсия.  Рекурсията е лошо написана -- входът трябва да е arr[i .. j] или нещо такова, и да се каже, че началното викане е с i=1, j=n.  Ако оставим това настрана, обикновената рекурсия без помнене на решения на подзадачи ще даде хубав експоненциален алгоритъм.  Освен това, дъното на рекурсията е за двуелементните подредици, а не едноелементните.  Нещо повече (това не го описах добре в решенията): на таблицата на динамичното ще се ползват около половината клетки над гл. диагонал, защото правим таблица за Албена и строим решения само за подредици с ЧЕТНИ дължини.  Останалите клетки на таблицата остават празни и не се ползват в изчислението.

20 точки на това решение.  Все пак има нещо здраво и смислено.

2.  В същата работа, в задача 2 липсва твърдението се доказва.  Пише "Инварианта: винаги на ред 8 за array[1 .. j] е изпълнено условието."  КОЕ условие?  Няма как да проверя д-во на твърдение, което не е изказано.

По-лошо, в кода има добавен ред "j ++", но по такъв начин, че не е ясно в от вложените цикли се намира.  Трябвало е със скоби { и } да се означи обхвата на вътрешния цикъл и тогава щеше да е ясно дали j++ е  в него, или не.

Повече от 5 точки не мога да дам.

3.  Груба грешка в решение на задача 2.  Първата стъпка е сортиране на масива.  Това напълно обезсмисля задачата: тогава максималният растящ подмасив става самият масив.  Нула

4.  Решение на зад 2 е с for цикъл, който изглежда добре, но има формална грешка.  Последната инструкция е i++, и това се изпълнява винаги.  На Pascal не е разрешено да се променя индексната променлива в тялото на цикъла.  На C е разрешено.  Тъй като е използван синтаксис на C, приемам, че конвенциите на C са в сила.  Тогава това "i ++" е бъг, който чупи програмата.  Нула точки.

5.  Има решение на зад 2, което е излишно усложнено, със задраскваници, сякаш е чернова, и на ред 14, добавен впоследствие, пише "същата проверка като ред 7 извън фор". 

Пишете ясен код.  Не съм длъжен да гадая какво имате предвид.  Задачата е много проста и се решава с код, по-къс от 10 реда.

Нула

6.  В същата работа, в задача 3, няма ясен отговор на а).  Отново, не съм длъжен да гадая и да сглобявам сам отговори от написани хинтове.  Нула на а)

Предложен е алгоритъм за б) с едниствена обосновка "в момента който [sic] видим черен сифон, значи има друг път значи разл. сортиране".  Интерпретацията ми е, че има > 1 топосортиране т.с.т.к. има сифон със степен на входа > 1.  Това не е вярно.  Може да има единствен сифон със степен на входа 1 и пак да има повече от една топосортировки.  Нула.

7.  Решение на зад 2 има правилен, кратък и ясен код, но инвариантата е формулирана ужасно.  "Всяка проверка за край на цикъла е изпълнено, че maxcount връща макс. дължина на подмасив A[i, i+1, ..., j], такъв че A[i] < A[i+1] < ... < A[j]".  maxcount е променлива и тя може да съдържа (или да не не съдържа) нещо, а не да връща.  Алгоритъмът е този, който връща.  По-лошо: цикълът е for с променлива i, така че при проверката за край на цикъла, maxcount съдържа дължина на подмасив в A[1 ..i] (или A[1 .. i-1], ако трябва да сме точни), а не в A[i .. j] за j>=i.  В края на работата, i става n, така че нарастващ масив A[i .. j] би бил само A[n] с дължина 1.

5 точки на задачата.  Основното в тази задача е да се демонстрира умение за формално д-во на коректност.  Самият алгоритъм е елементарен.

8. В решение на зад 3 се казва, че даг има единствено топосортиране тстк при рекурсивното обхождане (Tarjan) за всеки връх откриваме <= 1 бели деца.

Това не е вярно.  Най-прост пример е празният граф, в който обхождането не открива никакви деца и в частност за всеки връх открива нула, което е не повече от едно, бели деца.

Дори да добавим условието да има единствен източник и единствен сифон, твърдението пак остава невярно.  Разгледайте ({a,b,c}, { (a,b), (b,c), (a,c)} ).  Очевидно има Хамилтонов път a,b,c и единствено топосортиране <a,b,c>.  От друга страна, ако DFS започне в a, открие c като бяло дете, после ще открие връх b като друго бяло дете (на a).  Ерго, a има две бели деца, а топосортирането е единствено.

9.  Същата работа има почти решение на задача 3:

albena(A, l , r)

  if l = r return A[l]

  left := A[l] + boris(A, l+1, r)

  right := A[r] + boris(A, l, r-1)

  return max(left, right)

boris(A, l, r)

  if l = r return A[l]

  left := A[l] + boris(A, l+1, r)

  right := A[r] + boris(A, l, r-1)

  return min(left, right)

Това решение е същото---по дух!---като решението от отговорите.   Ако във функцията albena се заменят двете викания на boris с кода на boris, ще се получи нещо близко.  Сбъркано е началното условие за Албена, което е по-малкият проблем.  Големият проблем е, че това не е динамично, а е разделяй и владей (никъде не е спомената мемоизация, която не сме учили така или иначе) и експоненциален алгоритъм.  Забележете разликата с отговорите, в които ясно се разграничава входния масив от таблицата на динамичното.

25 точки.  На фона на цялостното представяне на тази задача, тук има нещо.

10.  Едно решение на зад 3-б има стряскаща грешка.

T1[1 .. n] := Tsort(G = (V,E), V = {1 .. n})

T2[1 .. n] := Tsort(G = (V,E), V = {1 .. n})

if T1 = T2

  print "ДА"

else

  print "НЕ"

Оставяйки настрана странната нотация във викането, на първите два реда се вика ЕДНА И СЪЩА функция върху ЕДИН И СЪЩИ вход.  Тъй като ние разглеждаме само детерминистични алгоритми, и двете викания ще върнат едно и също.

Тук има някакво фундаментално неразбиране.  Нула.

11.  В същата работа е предложено тромаво решение на зад 2, в което входният A се сканира и в работен масив Len[1 .. n] се записват случванията на A[i] > A[i+1].  Формално погледнато, в условието не се иска паметта да е O(1), но е грехота толкова проста задача да се решава с линейна работна памет.  По-лошото е, че масивът Len не се инициализира и ако се случи A[1] < A[2] < ... < A[n], само една клетка на Len ще получи стойност, а именно Len[1].  Алгоритъмът завършва с for i = 2 to n цикъл, в който се правят обръщения към Len[i].  При нито един от тези достъпи, Len[i] не е дефиниран.  Което означава, че поведението на алгоритъма е недефинирано.  Нула.

12.  В решение на зад 3 се казва "на лекции сме показвали, че ако граф е даг, то след топосортиране той винаги има точно един сифон и точно един източник".  Това е изключително груба грешка, показваща фундаментално неразбиране по много начини.  Нула.

13.  Решение на зад 2 е алгоритъм, който не връща нищо.  Псевдокодът не съдържа инструкция, която показва какво се връща.  Нула точки.

14.  Решение на зад 2 съдържа нещо нередно

algX( arr[1 .. n] : int)

  prev = arr[0]

Тъй като arr[0] няма, резултатът от това присвояване е недефиниран.  После  prev  се ползва в сравнения с елементи на масива, но резултатът от тези сравнения е недефиниран, понеже prev не е дефиниран.  Нула.

15.  Решение на зад 3 започва така:

start := i, end := i, l := 0, arr[j - i +1]

И накрая няма връщане на нищо.

Това е грешно по много начини.  i не е дефинирано никъде и се ползва за инициализация на две променливи, което означава, че те остават недефинирани.  Вижте, това, че в условието се ползват i и j , не ги прави дефинирани.  Обхватът на онези i и j е само до края на изречението/параграфа, в който са използвани. Освен това, "arr[j - i + 1]" не е инструкция и няма място в алгоритъм.   Нула

16.  В задача 1 се иска пример за това, че алчната стратегия не е непременно печеливша.  Следният пример е странно предложение

  2, 10, 5, 6, 7, 4, 1, 2

Странното е в това, че крайните монети са с еднаква стойност, при което А може да вземе коя да е от тях.  Естественият пример е с различни крайни монети, при което А няма избор.  В случая аргументацията трябва да разгледа два подслучая: А взема вляво или А взема вдясно, водещи съответно до

  2, 10, 5, 6, 7, 4, 1

и

   10, 5, 6, 7, 4, 1, 2

Това не е направено.  Нула точки за примера.

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

17.  Решение на зад 2 съдържа коректен алгоритъм, смислена инварианта, която е доказана, но няма терминация, което кара доказателството да "увисне".  Само 20 точки.

18.  Решение на зад 3 казва "Проф. Д. не е прав.  Нека даг G има точно един източник и точно един сифон.  Ако първо вземем източника и махнем ребрата му, броят на източници може да се увеличи.  В случая, в който той се увеличава, <коректни разсъждения и само това>".  Това е недостатъчно д-во.  А ако не се увеличава, какво правим? Ако след махането на първия източник остане точно един източник, няма гаранция, че на някое следващо махане няма да се появят повече източници.  

Че трябва винаги да има само един източник (в оставащата част на дага), за да има уникална топосортировка е вярно,  но това не е казано. 2 точки

19.  Решение на зад 2 има код

ред 4: if <нещо задраскано> и A[i] <= A[i+1]

Директно го игнорирам.  Отгоре пише "Белова" и щом е белова, трябва да е недвусмислено четимо.  Не е моя работа да се опитвам да отгатна какво е искал да каже авторът (дали логическият съюз присъства, или не).  Компютърът не се опитва да отгатне намерението на програмиста, а прави това, което е инструктиран.  Буквално.

Нула точки.

20.  Базата на д-вото на инвариантата НЕ Е "n = 1".  Индукцията е по изпълнението, а не по дължината на входния масив.

21.  Има решение на задача 2, в което се предлагат два алгоритъма, написани един след друг.  Алгоритмите са различни.  Това е нула точки.  Не може на една задача да се дават различни решения.  Ако се отказвате от едното, задраскайте го.  Тук нищо не е задраскано. 

22.  В същата работа се казва "ДАГ -- ациклично дърво, което е ориентирано".  Само това изказване дава нула точки.  Това е абсолютно невярно.  Освен това, първата подзадача е с положителен (а не контра-) пример, което не доказва нищо, а във втората се предлага код, който е нечетим.  Нула.

23.  Решение на зад 2 започва така

i := 1

while i < n

  if A[i] > A[i+1]

    swap( A[i], A[i+1] )

    i := i + 2

Това е некоректно, понеже размества елементи на входа, преди да започне каквото и да е броене.  Ако входът е [8, 9], това ще направи [9, 8], и нататък всякакво броене е безсмислено.

Вижте, това е задача за РЕДИЦА.  Подредбата на числата във входа е от ключово значение.  При разместване на елементи от входа, решението се променя.  За разлика от задачи като Сортиране или Най-Близки Елементи или Мода, които са за мултимножество; при тях решението не се променя от размествания във входа.

24.  Решение на задача 1 казва, че тази задача прилича най-много на SUBSET SUM.  Това не е вярно.  Задачата SUBSET SUM е много различна -- там се иска подмножество с определена сума.  В това подмножество можем да сложим които елементи искаме, стига всички те да се сумират до дадено число; ако ще да са всички елементи.  В настоящата задача НЕ МОЖЕМ да сложим които искаме.  А и Б могат да вземат само едната от двете крайни монети в даден момент.  Очевидно нито А, нито Б може да вземе всички монети.  SSUM е NP-c задача

https://en.wikipedia.org/wiki/Subset_sum_problem

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

Предложото решение е грешно.  То ползва работни масиви B[a .. n+1] (*какво е "a", не е казано*) и copyA[1 .. n] и после адресира B през A:

B[A[i]] := ....

Това е груба грешка.  Числата в A може да са колкото искате големи и в частност A[i] може да е извън B[ .. ].  Нула.

25.  Има решение на зад 2, което връща не число, а масив от числа.  Нула точки.  Формалните спецификации трябва да се съблюдават.  В условието се казва "... намира максималната дължина на ...".  Дължината е число.  Алгоритъмът трябва да връща число.  Ако връща масив от числа, от който може да бъде намерен желаният резултат, това е---формално---един некоректен алгоритъм.  Нула точки.

26.  В решение на зад 3 се казва, че ако алгоритъмът попадне на съседен връх, който е черен,  със сигурност има повече от 1 топосортиране.

Това не е вярно.  Апропо, би трябвало да е "дете", не "съседен връх", понеже графът е ориентиран.  И така, ето контрапример:

G = ( {a,b,c}, { (a,b), (b,c), (a,c) } ).  DFS тръгва от a, намира първо b, после c, после backtracking до a, намира отново c и този път c е черен (реброто (a,c) е ребро напред).  Но има точно едно топосортиране, понеже a,b,c е Хамилтонов път.

27.  В решение на зад 1 се казва

DP[i][j] <- максимално събрана сума с първите i монети.

Кои са "първите i монети"?  В някои задачи с динамично на лекции подредихме елементите на мултимножество от числа някак и спрямо тази наредба говорехме за "първите i числа".  В случая не е ясно кои са първите i числа.  Първите i отляво надясно в наредбата?  Първите i, които А събира?  Не  е едно и също.

После.  Изразът "максимално събрана сума с първите i монети" съдържа едно променлива, а именно i.  Тогава j какво е?  Ако се има предвид "дали има сума j с първите i монети, които и да са те" -- не би било добра идея.  Числата може да са грамадни и тогава алг. би бил псевдополиномиален.  Но тези неща трябва да се напишат експлицитно.  Проверяващият не трябва да гадае.

Нататък нотацията DP не се ползва, а се ползва едномерно динамично с f(n).  Нула точки.  Няма решение.

28.  В решение на зад 1 се казва

dp е матрица n x n, чиито е-нти са нар. двойки (i, j), като i отговаря на макс. сума за А, а j отговаря на макс сума за Б

Това няма как да е вярно.  Максималната сума КЪДЕ, в КОЯ подредица?  Нищо чудно, че няма смислена рек. декомпозиция.  Нула на втората подзадача.

29.  Има странно объркано решение на зад 2, в което "temp := 1" във for-a е написано с такъв отстъп (в края на тялото), че на всяко изпълнение този брояч ще става 1.  Това няма как да е вярно.

В тази работа има и нещо друго.  В беловата е писано с молив, като е и трито.  За цвета на мастилото не казвам нищо, стига да не пишете с червено.  Но не искам  да пишете с молив в беловата.  Молив е за чернова или чертеж.  Някой може да каже, че аз съм изтрил нещо от беловата.  Искам да пишете с мастило.

30.  Когато давате контрапримера в задача 1, трябва да кажете

1) колко взема А, следвайки алчната стратегия,

2) и колко най-много би взела А дори при оптимална игра на Б.  

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

31.  В същата работа, която визирах в 30., се казва за зад. 3-Б:

Пускаме DFS от източник и ако сме обходили всички върхове, връщаме ДА

Това не е коректно.  В контрапримера от зад 3-А ясно се вижда, че целият граф е достижим от единствения си източник.  А топоростирането не е единствено.

32. Решение на зад 3-Б казва (T[1 .. n] е топосортиране)

for i =1 to n

  for j = i to n

    foreach y \in adj[y]

      if T[j] = y

        swap T[i], T[j]

        return T

return "Уникален е"

Това y \in adj[y] няма смисъл, при положение, че y не е дефинирано преди това.  Не искам да гадая дали се има предвид y \in adj[i] или y \in adj[j].

33.  В същата работа се казва "Не вярвам на проф Факториелски, защото топосортиранията може да са n на брой плюс времето за сортиране".  Топосортировките може да са много повече от n.  Името на професора не е случайно!  Нула точки, тук няма аргументация.

34.  В същата работа има решение на зад 1-Б, което не е динамично, а е експоненциален алг.  Ползва се вход C, без грам обяснения (в условието няма "C", така че е редно да кажете какво е това), няма таблица за складиране на временни резултати, правят се две рек викания, всяко върху масив големина с единица по-малка.  Чист експ. алгоритъм.  Иначе е коректен.  20 точки

35. Решение на зад 3.Б твърди, че ако има ребро настрани в даг, то този даг има повече от една топосортировка.  Това не е вярно

Нека G = ( { a,b,c },  { (a,b), (b,c), (a,c) }).  Топосортирането е само едно: <a,b,c>.  От друга страна, има DFS изпълнение, което дава ребро настрани: от a към c, backtracking към a, после към b, и реброто (b,c) се оказва настрани, защото води към черен връх, а b и c не са отношение на предшествие в дървото на DFS; дървото е ребрата (a,b), (a,c).

36.  В задача 2 инварианта

При всяко достигане на проверката за край, A[1 .. i] има подмасив с макс. дължина според условието.

Това не може да е инварианта.  Твърдението е тривиално вярно -- да, има такъв подмасив.  И?  Въпросът е коя променлива съдържа дължината му.  Нула за д-вото, 5 точки за коректен код