Внасяне на оценки по ДАА от поправителния
Внасянето на оценките от поправката, както и разглеждането на писмените работи, ще е на 09 септември от 10:30 до 12 ч в стая 503 на ФМИ.
Няколко пояснения и съображения по изпита и оценяването:
1. 50% може да се изкара само от познаване на материала на лекции. Говоря за първата и четвъртата задача. За зад. 4 са достатъчни три изречения "Задачата е същата като DS. Известно е и е доказано на лекции, че DS е NP-пълна. Следователно, твърде невероятно е да има ефикасен алг. за задача 4.". Пълно решение на зад 1 иска повече писане, но при положение, че имате право на пищов, това не би трябвало да е проблем. Опорните точки от извеждането на средната сложност (решаването на онова засукано рек. уравнение) може да са в пищова.
И така, изпитът може да се изкара само със знаене на преподавания през семестъра материал. Ерго, твърдението, че човек се е явил добре подготвен(а) и не е изкарал(а) въпреки това, е неистина.
2. Зад. 3 се решава прецизно и пълно с доказване по инд-я на отговора 2^(n(n+1)/2). За коректно рек. уравнение и нищо повече съм давал по 5 точки. За изведен с развиване резултат, но без д-во по инд-я, 20. За прецизно изведен отговор с инд-я, 25. Всеки грешен отговор е 0.
Пълно вярно решение на зад 3, заедно с пълни решения на зад 1 и 4, е 75%, т.е. петица.
3. В зад 1 имаше доста (може би 1/4 или 1/3 от работите..) "решения" на въпроса за средната сложност на QSort чрез рекурентното уравнение T(n) = 2 T(n/2) + n. Тези решения са оценени с 0. От никъде не е ясно, че на всяко ниво на рекурсията QSort дели входа на две (приблизително) равни части. Ако смятате, че е така, докажете го.
QSort НЕ Е MergeSort.
4. Пак в зад 1 има учудващо много грешни определения на трите сложности по време. Да, тази подзадача е само 2 точки, но все пак... Дефиницията на сложност по време и асимптотичните нотации (O, Omega ..) са принципно различни неща. Асимптотичните нотации са понятия от анализа -- става дума за някаква еквивалентност на положителни ф-ии или квазинаредби върху положителните ф-ии. За дефиниране на сложност на алгоритъм те не са необходими. Сложност на алгоритъм е ф-я на големината на входа и очаквам да се започне с това, какво е големина на входа.
5. Оценките са окончателни.
-- ММ