Zkouška 27.5. MJ

Úvodní přednáška o základních typech algoritmů a datových strukturách potřebných pro jejich implementaci.
Drakoii
Matfyz(ák|ačka) level I
Příspěvky: 5
Registrován: 12. 10. 2008 23:47
Typ studia: Informatika Bc.

Zkouška 27.5. MJ

Příspěvek od Drakoii »

Pro budoucí generace
Na zkoušce nás bylo "jak psů", takže jsme byli rozděleni do dvou skupin
skupina alfa:

A1. Je dáno N celých čísel v rozsahu 0...N^4 - 1. Popsat třídící algoritmus pracující v čase O(N)
A2. Červenočerné stromy - definice, důkaz logaritmické hloubky, a popsat insert (masochisti mohli i delete)

B1. Na vstupu donstaneme plán bludiště složený ze čtverečků (prázdné nebo zeď) a souřadnice dvou robotů v bludišti. Vymyslet algoritmus, který bude oboum robotům vždy v jednu chvíli dávat tentýž příkaz (jdi na sever, jih, západ, východ) a vyvede je co nejkratším počtem kroků z bludiště (za libovolný okraj). Pokud je před robotem zeď a má jít tím směrem, tak stojí na místě.
B2.V knihovně máme dlouhou řadu N knih seřazenou podle unikátních názvů. Někdo však K knih vyndal a vrátil na špatná místa. Popsat algoritmus, který řadu knih setřídí v co nejlepším čase. N>>K

C. Dokázat, že když máme algoritmus na invertování trojůleníkových matic, tak v tom samém čase umíme taky matice násobit (nebo něco na ten způsob :))

skupina beta měla cosi jako:

A1. Master Theorem, formulovat, dokázat.
A2. už nevím

B1.Najít v neorientovaném ohodnoceném grafu nejdražší čtyřcyklus
B2.Máme kabel plný vodičů a nevíme, které konce na jedné straně odpovídají těm na druhé a pomocí přivádění napětí na jedné straně a měření na druhé co nejmenším počtem operací (připojit na vodič, odpojit, změřit na druhé straně) přiřadit k sobě správně konce vodičů.

Celá zkouška probíhala ve velmi příjemné atmosféře, času jsme měli v podstatě, kolik jsme chtěli. Martin Mareš nás postupně obcházel a konzultoval řešení, takže většina lidí pak spíš už jen čekala, kdy na ně přijde řada.

možné řešení pro alfu:
a1- RadixSort na jehož začátku si převedu čisla do soustavy o základu N.

b1- prohledávání do šířky, roboti smějí jít daným směrem, pokud se alespoň jeden z nich pohne a pokud oba nevstoupí na políčko, na kterém již byli a zároveň tehdy stáli vzájemně na stejných pozicích.
b2- vyhodit ven knihy, které jsou špatně zařazené, setřídit zvlášť a provést Merge O(n+klogk).
peci1
Matfyz(ák|ačka) level II
Příspěvky: 86
Registrován: 21. 1. 2009 20:08
Typ studia: Informatika Bc.

Re: Zkouška 27.5. MJ

Příspěvek od peci1 »

Ahoj, jen doplnim k B2 - nestaci vyhodit jen knihu, ktera ti vyboci z poradi. To proto, ze nevis, jestli je spatne ona a nebo byla spravne a mezi ni a predchozi nekdo strcil knizku s "vyssim ID". Na cvikach jsme to resili tak, ze vyhodis pro jistotu obe :) Asymptoticky ti to neublizi...
Odpovědět

Zpět na „TIN060 Algoritmy a datové struktury I“