забелязани грешки и проблеми в решенията на изпита на студентите от МГ
1. Във варианта на Инф, задача 2 не се решава с алг. на Kadane. Алг. на Kadane e за максимална сума на подмасив. Тук се иска нещо несравнимо по-просто. -2 т за твърдение, че този елементарен алг. е алг. на Kadane.
2. Пак в зад 2 на Инф: предлага се решение, което първо построява масив на максимумите до момента и след това с втори цикъл намира неговия максимум. За суперпрецизен отговор би трябвало да се докаже с инварианта и коректността на втория цикъл. Да, очевидно е, но то всичко е очевидно от някаква гледна точка. -2 точки за това.
3. В същата работа, зад 3, се твърди, че ({1,2,3}, {(1,2)}) има точно един източник 1 и точно един източник 2. Това не е вярно. Връх 3 е и източник, и сифон. Това е груба грешка. Нула точки на първа подточка.
В същата работа, зад 3, втора подточка се твърди, че G има точно едно топосортировка, ако # ребрата е n(n-1)/2 и е свързан. Понятието "свързан" е приложимо само за неориентирани графи. Още: ако даг има n(n-1)/2 ребра, той има точно една топосортировка, но може да има точно една топосортировка и да има много по-малко ребра, чак до n-1 (един Хам. път и нищо повече). Така че това е далече от НДУ.
4. В същата работа, зад 3, трета подточка правилно е разгледан празен граф като контрапример, правилно е забелязано, че всяка пермутация на върховете му е топосортиране, но грешно се твърди, че задачата за генерирането на всички пермутации е NP-пълна. Понеже на лекции не стигнахме до NP-пълнота, тук си затварям очите, но FYI това просто не е вярно. NP задачите са задачи за разпознане, които има къс (полиномиален в дължината на входа) сертификат. NP-пълна задаче е задача от NP, за която е вярно, че всяка друга задача от NP се свежда бързо до нея.
Задачата за генериране на всички пермутации на n обекта НЕ Е задача за разпознаване. За сертификат при нея и дума не може да става -- няма какво да се отгатва. Алгоритмично, това е супертежка задача със сложност Omega(n!), при положение, че n е записано унарно във входа (като върховете), но не е в NP изобщо, да не говорим за NP-c.
5. Това решение на зад 2 на Инф не е вярно
...
len = 1
max = 1
for (i = 1; i < n; i ++)
if (a[i] < a[i+1])
len ++
else
<нещо>
return max
Очевиден контрапример е всеки нарастващ масив. else няма да задейства никога и алгоритъмът ще върне единица.
Тук се изкушавам да дам общ съвет за професионалната ориентация, но ще замълча.
6. Опит за решение на зад 1 на вариант Инф строи пълно (кореново) дърво на възможните ходове. Това е ефективно, но изключително неефикасно. Опитайте да играете шах с построяване на пълно дърво на позициите. Нула точки.
7. По зад 3 на вариант КН. Идеята да се вземат или само четните, или само нечетните нива не работи. Това дава антиклика, но непременно максимална. Контрапример има в лекционните записки.
8. В решение на зад 3, вариант КН, се дава почти вярна рекурсивна декомпозиция, но се казва, че r+ = 1, r- = 0, където r е коренът. Това е много груба грешка, издаваща фундаментално неразбиране. u+ = 1, u- = 0 е за ЛИСТАТА. Ако за корена r е вярно, че r+ = 1, r- = 0, то излиза, че отговорът винаги е 1. Нула точки.
9. В зад 2, вариант КН, не е достатъчно да включите t в инвариантата. Инвариантата трябва да казва нещо и за B, инак не можете да докажете това, което твърдите за t, понеже t се смята чрез B[i-1].
10. Решение на зад 3, вариант КН, казва, че понеже Големия Началник няма шеф, той задължително ще участва в решението. Това е груба грешка -- представете си йерархия от ГН и 100 негови директно подчинени. Ако той участва, никой от тях няма да участва и това е решение с големина 1. А има решение с големина 100. Нула точки.
11. Има опити за решение на зад 1, вариант КН, които механично следват описанието, без разбиране, и казват неща като "За всеки два върха, за които се пита, противникът ги слага в различни дялове на разбиването". При положение, че дяловете са два, това може да е невъзможно. Ето пример: първо се пита за 1 и 2, те отиват в различни дялове, после за 2 и 3, те отиват в различни дялове, което означва, че 3 влиза в дяла, в който е 1, после се пита за 1 и 3 и ... какво правим?
В предложеното решение разбиването става в самото начало. Противникът отговаря спрямо него, но не мести върхове между дяловете.
12. В решение на зад 2, вариант КН, се казва "При всяко достигане на ред 9 нека е изпълнено, че t = max{ A[p] + A[q] + (p-q) } като 1 <= p <= q <= n."
Това е сбъркано по много начини. Първо, "нека" няма място тук. Изречение с "нека" е заповедно и не е съждение. Инвариантата казва какво е състоянието на нещата, а не дава заповеди. Второ, set constructor notation изисква неравенствата да са вътре във фигурните скоби, но отделени от израза вляво с "|" или ":". Трето, p-q може да е отрицателно; трябва да е q-p; това е дреболия. Най-съществената грешка е, че i не участва в този израз. Това не е предикат на i. Написано чрез n, това е нищо. Симулация на доказателство. Нула точки
13. Има решение на зад 1, вариант КН, което разглежда случая, в който не сме задали въпрос за поне една двойка от различни дялове. Това е добре и може да доведе до успех. Но това решение казва, че в такъв случай врагът ще ни даде несвързан граф. Не непременно! Стратегията на врага е съобразена с това, което отговаря нашият алгоритъм. А какво връща алгоритъма, ние НЕ ЗНАЕМ. В това д-во не правим никакви допускания за алгоритъма, освен че е коректен и че пропуска двойка (и показваме как това води до противоречие). Отново: не знаем дали алгоритъмът, бидейки пропуснал двойка от различни дялове, ще върне ДА или НЕ. И стратегията на противника трябва да работи и в двата случая: ако алг върне ДА, противникът показва несвързан граф, консистентен с отговорите му, и обратно. 20 точки, все пак има нещо.
14. В същата работа се предлага да се докаже коректността в зад 2 с индукция по дължината на масива. Това не е добра идея. Добрата идея е с индукция по изпълението. Нищо чудно, че д-во не е показано.
15. Задача 2 на вариант КН. Предлага се инварианта "B[i] съдържа максимума на обходените елементи на A[1 .. i] минус съответното разстояние до тях". Това е безсмислица. Съответното разстояние между КОЕ и всеки от тях? За разстояние трябват два обекта. Нула.
16. Задача 2 на вариант КН. Предлага се инварианта "При всяко достигане на ред 5, B[i-1] съдържа макс между разликата A[i-1] - (i-1+1) и предходния такъв максимум; t_{i-1} съдържа максималната сума на два различни елемента и разликата между тях в A[1 .. i-1]".
Това, че инвариантата говори както за B, така и за t, е правилно, но друго добро нещо не мога да кажа. В този вид, инвариантата е безсмислица. Какво значи "максимум между"? Максимум е на множество (може да е празното множество) и предлогът е "на" или "върху" или "от", въпреки че това звучи странно. "между" винаги се отнася за две неща. Кой е предходният такъв максимум? B[i-2]? Ако няма предходен? Защо t е индексирано? "разликата между тях" и "разстоянието между тях" са абсолютно различни неща! Формулирането чрез ред 5, а не ред 9, е странно, но не е фатално. Фатална е формалната безсмисленост. Не мога да дам точки за доказателство на твърдение, което е изразено по такъв начин.
Вижте, формалната страна е супер важна. Компютърът е изключително формален в смисъл, че за него фОрмата е всичко. Той не се и опитва да отгатне "какво е искал да каже авторът". Компютърът прави това, което му се укаже. Буквално. Ако сте си избрали поприще, което включва програмиране на компютър, трябва на някакво ниво на формалност да се изразявате безукорно.
17. Същата работа съдържа второ решение на задача 2, което е различно от първото. СамО по себе си това е недопустимо. Две различни решения на една задача не може, също както не може да предложите съществено различни (даващи несъвместими отговори) решения на клиент и да му кажете той да си избере; за някаква сложна система това може да е ОК, но за проста конкретна задача изобщо не е ОК. Ако вашият софтуер смята, да кажем, md5sum, и предлагате две реализации, даващи различни хешсуми върху един и същи вход ... нали ме разбирате?
18. Същата работа, задача 3. Задачата за максимална антиклика е РАЗЛИЧНА от задачата за двуоцветяване.
19. Задача 2, КН, инварианта "При всяко влизане в while цикъла, B[i-1] съдържа макс. разлика м-у A[i-1] и i-2 в подмасива A[1 .. i-1]". Това е безсмислено. Разликата A[i-1] - (i-2) е ЕДНО НЕЩО. Какъв максимум?
max{ A[k] - (k-1) : 1 <= k <= i-1 } от примерните решения е съвсем друго. Може да сте имали предвид точно това, но аз оценявам написаното.
20. Задача 3, КН. Казва се "Общо n служители. За всеки служител има шеф ==> шефовете = n/2". Не е вярно. Единият екстремален пример е граф-звезда, вкоренен в центъра си -- има само един шеф. Другият екстремален пример е граф-път, вкоренен в единия си край -- има n-1 шефа. Това невярно твърдение струва 10 точки.
По-лошо: няма кохерентно описание на алгоритъм. Нула.