ДС, пролет 2021

1.  Задача 1 се решава чрез факти/дефиниции/разсъждения по теория на множествата.  Записът "p --> q /\ r" е само кратък запис на съждение, но това съждение трябва да се докаже.  Задача 1 не е задача от съждителна логика. p,q,r не са просто кутийки, които могат да са T или F; те имат конкретно съдържание и то трябва да се отчита.  За разлика от задачи от вида "докажете еквивалентността на съставните съждения ... и ...", при която променливите (простите съждения) са само кутийки.

U S е унарно обединение, приложимо само ако S е м-во от м-ва. Може да мислите синтактично за него: то маха скобите около елементите.  Примерно, U { {a}, {b} {a,b} } = { a, b, a, b } = {a,b}

U U S е приложимо само ако S е м-во от м-ва от м-ва.  Аналогично,    U { { {a,b} , {c} }, { {a}, {b}, {d} } } = {a, b, c, a, b, d} = {a,b,c,d}

2. В задача 6 съм направил грешка при писането.  Имал съм предвид G=(V,E), написал съм G=(U,V).  Нормално давам 5% бонус за открита грешка в условията.  Аз това не го обявих, но всеки, който го е забелязал, има 5% бонус отгоре към задачата.  Това обаче не е решението.  Решението е, че "да изтрием e' от c" е пълна безсмислица, понеже e' може да не е ребро от c, и това е причината д-вото да е невалидно.

3.  Има "решение" на зад 4, което изразява Sn чрез Sn-1, 3^(n-1) и 3^(n-4).  Решението е грешно.  За n=5 дава -36.  Някак е нагласено да работи за n=3, но това не стига.  Извеждането е нечетима каша, така че и частични точки не може да се дадат.  Нула.

4.  Има опит за решение на зад 4:

T(0) = 1, T(1) = 3, T(2) = 8, T(n) = T(n-1) + 3T(n-2) + 3T(n-3)

Не работи.  За T(4) дава 20 + 3*8 + 3*3 = 53, а истинският отговор е 50.

Пробвайте в скрипт test

#! /bin/bash

printf "%s\n" {a,b,c}{a,b,c}{a,b,c}{a,b,c}

и

./test | egrep -v 'ac|cab' | wc -l

10 точки.  Грешката е в разсъжденията за това, какво става, когато водещата буква е c

5.  Обединение се пише с "о", не с "у"

6. В едно решение на зад. 2 се казва ,че броят на частичните наредби без ограничения за това A е 2^10.  Твърдението е без обосновка.
Това не е вярно, разбира се.  За бройките на част наредби не е известна затворена формула, но за малки n стойностите се знаят:

https://oeis.org/A001035

За n=5 е  4231

7.  Има опит за решение на зад 5 чрез разглеждане на конкретен пример.  Това е груба грешка.

8.  Има опит за решение на зад 5, който пропуска да покаже три прости пътя без общи вътрешни върхове, които имат общи краища, но правилно отбелязва, че измежду три различни пътя, поне два имат една и съща четност на дължините си.  Това е нула точки.  Това е опит за възползване от упътването, който пропуска същината на доказателството. 

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

9.  Има опит за решение на зад 2, при който се разглеждат диаграми на Hasse (правилно!), но има огромно неразбиране на диаграмите.  В началото е показана диаграма от един връх горе, три върха на едно ниво по средата и един връх долу.  Без никакви линии между върхове от съседни нивА.  Това е доста груба грешка.  Единственоста на максималния си личи не от това, че е нарисуван високо горе (само той), а от това, че за всеки друг елемент u има елемент v над него и има линия между u и v.

10.  Тази фраза "Няма релация от никой елемент към никой друг" директно дава нула точки на цялата задача 2.

11.  В решение за зад 3 се твърди, че понеже графът е ацикличен, макс брой на ребра в него е n-1.  Това е грешка.  По условие, графът е ориентиран.  Ориентиран граф може да има n(n-1)/2 ребра и да е ацикличен

12.  За да бъде уравнение рекурентно, вдясно от = трябва да се появява функц. символ поне веднъж (върху по-малък аргумент).

13.  Функц. символ вдясно трябва да е същият като този вляво.  Това НЕ Е рекурентно уравнение

Sn = an-1 + an-3

14. Стринг и множество са принципно различни неща.  Стринг е редица, или вектор, или подредено мултимножество.  Типично, стринговете се пишат без нищо около себе си, например a, aba и т.н  Празният стринг НЕ Е същото нещо като празното множество.  Ерго, такива означени в зад 4 са неприемливи

S0 = { }

S1 = {a}; {b}; {c}

S2 = { {a,b}, ...

15.  В зад 1, не е вярно, че "U S" е същото като "U U S".

16. В решение на зад 3 се твърди, че щом матрицата има нулев ред (съответен на сифон), при i-тото повдигане на степен в нея има точно i нулеви реда, така че при i>= n тя се нулира.

Това, че матрицата ще се нулира при повдигане на n-та степен е вярно, но не по тази причина.  Не е вярно, че матрица с нулев ред се нулира непременно при повдигане на достатъчно голяма степен.  Ето пример

[ [0,1,1], [1,0,1], [0,0,0] ]

Повдигайте на каквато искате степен и вижте дали става нулева матрица

Научете алгебрата

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

Вие обаче разполагате с теоретичен резултат от лекции, който директно ви казва какъв смисъл имат елементите на матрицата^n.  Учете теория, тя е сила!

18.  В "решение" на зад 6 се казва "допускаме, че e не е в нито едно МПД, а после казваме , че го добавяме към произволно МПД, и това прави д-вото невалидно".

Нищо подобно.  "Добавяне" има смисъла от лекции: ако произволното МПД е T= (V,E), то конструираме графа D = (V, E U {e} ).

19.  В решение на зад 3 се започва подробно и формално д-во по инд-я на твърдението, в индуктивната стъпка формализмът се зарязва и просто се отбелязва, че броят на единиците строго намалява.  Това си остава недоказано, а само наблюдение, освен това не е достатъчно силно. ДАГ може да има до n(n-1)/2 единици, така че при n намалявания може броят да не падне до нула (или до sqrt(n) ).  10 точки, все пак нещо.

20.  В задачи като зад 5 е абсолютно безсмислено да разглеждате примери като част от д-вото.  Твърдението е за безброй много графи и не можете да разгледате всеки от тях.  Отделен пример не доказва НИЩО.

21.  Такова изречение "Ако в свързан претеглен неор. граф G съществува произволен срез {U,W}, следователно произволно най-леко ребро преминаващо през {U,W} принадлежи на поне едно МПД" води автоматично до нула точки.  Това е некохерентно. 

22.  Има интересен опит да се реши зад 5, като се направи индуктивна деф на въпросното м-во графи (с мин степен на връх 3) и се докаже със структурна индукция.  Аз не знам каква е индуктивната деф на това м-во, но не може да е толкова просто, колкото се предлага.  И трябва да се докаже, че тази индуктивна деф е еквивалентна на другата, а за това не е направен и опит.  Давам 10 т за изобретателност (на фона на цялостното представяне, това е нещо).

23.  В зад 4, следният запис дава автоматично нула точки

|S1| = { a, b, c } = 3

Бърка се множество с мощност на множество

24.  В решение на зад 5 се казва

"Най-дългия [sic] път (прост) е цикъл с дължина |V|."

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