# Zkouška 27.5. MJ

<{ForumPost(poster="Drakoii", timestamp=2009-05-28 13:30:17)}>
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).
<{/ForumPost}>

<{ForumPost(poster="peci1", timestamp=2009-06-16 23:22:57)}>
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...
<{/ForumPost}>