14. 5. MJ

Zanatic
Matfyz(ák|ačka) level I
Příspěvky: 7
Registrován: 15. 1. 2007 16:16
Typ studia: Informatika Bc.
Bydliště: Prosek
Kontaktovat uživatele:

14. 5. MJ

Příspěvek od Zanatic »

(Doslovný přepis včetně formátování)

Příklad A1 (6 bodů). Popište algoritmus pro rozklad orientovaného grafu na komponenty silné souvislosti, dokažte jeho správnost a rozeberte časovou složitost.

Příklad A2 (4 body). Popište Euklidův algoritmus, dokažte jeho správnost a rozeberte časovou složitost.

Příklad B1 (5 bodů). Přišla zima<sup>1</sup> a některé silnice jsou pravděpodobně neprůjezdné. Mějme mapu města v podobě orientovaného grafu, jehož hrany odpovídají silnicím a jsou ohodnoceny pravděpodobnostmi toho, že silnice je průjezdná. Vymyslete algoritmus, který pro zadané dva vrcholy na této mapě najde nejpravděpodobnější
cestu, tj. takovou, že součin pravděpodobností hran této cesty je největší možný.

Příklad B2 (5 bodů). Byla-nebyla jedna knihovna, na počátku krásně abecedně seřazená, ale jak šel čas, čtenáři občas vraceli knížky na náhodná místa. Navrhněte co nejefektivnější algoritmus, který dostane posloupnost n prvků (které umíme pouze porovnávat) a tuto posloupnost setřídí, přičemž víte, že zadaná posloupnost vznikla ze setříděné posloupnosti vložením k prvků na libovolná místa. Můžete předpokládat, že k je mnohem menší než n.

Příklad C (5 bodů). Alfík a Betynka spolu hrají následující hru: Je dán strom a čtyři barevné pastelky. Na počátku jsou všechny vrcholy stromu neobarvené. Alfík a Betynka se střídají v tazích (Alfík začíná) a ten, kdo je zrovna na tahu, vybere jeden z neobarvených vrcholů a obarví ho některou z pastelek, ovšem nesmí použít barvu žádného ze sousedů tohoto vrcholu. Alfík vyhraje, pokud se podaří obarvit všechny vrcholy, v opačném případě vyhraje Betynka. Vymyslete algoritmus, který bude radit Alfíkovi, jak hrát, aby vždy vyhrál.

Poznámky:
Příklady jsou tří druhů: teoretické Ai, u kterých byste měli vše precizně formulovat a zdůvodnit, dále praktické Bi, kde se můžete odkazovat na algoritmy a věty z přednášky, aniž byste je museli odvozovat, a konečně nepovinný příklad C, jenž slouží jako lahůdka pro ty, kdo budou s písemkou dříve hotovi.
Ke každému algoritmu neodmyslitelně patří rozbor jeho správnosti (není-li zjevná) a časové a paměťové složitosti.
Při zkoušce je zapovězeno používat zápisky, kalkulačky, mobily, své kolegy, jakož i jiné pomůcky. Společně vyřešené úlohy budou obodovány taktéž společně.

Hodně štěstí!

<sup>1</sup> ladovská, samozřejmě :-)
KVÍK!
Odpovědět

Zpět na „2006“