Fórum studentů MFF UK

[quote="LnK"]Ja jen dodam, ze tentokrat ustni cast zacinala hned po pisemce. S kazdym si prosel jeho reseni a pripadne se na nej poptal. Dalo se tak i ustne doplnit celkem dost veci, ktere jste do pisemky nenapsali a take tak ukazat, ze v dane problematice mate nejaky prehled (treba i nacerpany z poznamek behem cekani :wink: )
Zakladni bodove hranice mel napsane u sebe na stole na papire: z onech 20 bodu nad 12 dvojka, nad 16 jednicka. Kdyz byl nekdo blizko (vyssi) hranici jeste se ho na neco poptal ustne (v mem pripade popsat, jakou slozitost ma Strassenuv algoritmus jako ukazku pouziti Master Theoremu). Vsechno probihalo s typickym usmevem a evidentni snahou rozdavat znamky co nejlepsi...[/quote]

Presne tak. A kdyz jste nahodou odpoved na dodatecnou otazku nevedeli, tak jste dostali cas na to, abyste ji v klidu vymysleli, zatimco se zkouselo dal. Ja mel napr. uplne okno v tom, jak rychle umocnit matici na n-tou (mel jsem zjistovat vzajemnou dostupnost vrcholu v orientovanem grafu). Tak jsem sel ven, tam me teda musel nekdo trosku nakopnout, protoze proste v tu chvili mi opravdu nedochazelo, jak spocitat A^4 pomoci mene nez tri nasobeni :-), ale pak uz jsem se chytil a i s 15b a timhle oknem dostal jednicku.

Ja jen dodam, ze tentokrat ustni cast zacinala hned po pisemce. S kazdym si prosel jeho reseni a pripadne se na nej poptal. Dalo se tak i ustne doplnit celkem dost veci, ktere jste do pisemky nenapsali a take tak ukazat, ze v dane problematice mate nejaky prehled (treba i nacerpany z poznamek behem cekani :wink: )
Zakladni bodove hranice mel napsane u sebe na stole na papire: z onech 20 bodu nad 12 dvojka, nad 16 jednicka. Kdyz byl nekdo blizko (vyssi) hranici jeste se ho na neco poptal ustne (v mem pripade popsat, jakou slozitost ma Strassenuv algoritmus jako ukazku pouziti Master Theoremu). Vsechno probihalo s typickym usmevem a evidentni snahou rozdavat znamky co nejlepsi...

[b]Příklad A1 (5 bodů):[/b] Definujte (a,b)-strom a dokažte, že má hloubku O(log n).

[b]Příklad A2 (5 bodů):[/b] Popište algoritmus pro hledání k-tého nejmenšího prvku v lineárním čase. Dokažte, že funguje, a rozeberte časovou a paměťovou složitost.

[b]Příklad B1 (5 bodů):[/b] Je dán neorientovaný graf s hranami ohodnocenými přirozenými čísly 1, 2,..., K. Navrhněte co nejefektivnější algoritmus pro nalezení minimální kostry takového grafu.

[b]Příklad B2 (5 bodů):[/b] Je dána posloupnost reálných čísel a1, a2,..., an. Navrhněte co nejefektivnější algoritmus, který spočítá, kolik má tato posloupnost inverzí, čili kolik existuje dvojic (i, j) takových, že i<j a ai>aj.

[b]Příklad C (5 bodů, bonus):[/b] Fibonacciho číselná soustava funguje tak, že čísla zapisujeme pomocí nul a jedniček a zápis <cn...c2> odpovídá číslu Suma(ci×Fi), kde Fi je i-té Fibonacciho číslo. Zápisu, v němž se nevyskytují dvě jedničky za sebou, budeme říkat hezký. Platí, že každé přirozené číslo má právě jeden hezký zápis. Vymyslete algoritmus, který v lepším než kvadratickém čase sečte dvě čísla zadaná hezkými Fibonacciho zápisy a vydá hezký zápis výsledku.