Fórum studentů MFF UK

1) Složitost (A. Kučera) Savičova věta - Kučera v rychlosti důkaz proletěl a jen se zeptal jaká je jeho hlavní myšlenka 2) Datové struktury (Pangrác) Třídění vě vnitřní a vnější paměti - U třídění ve vnitřní paměti jsem tam vypsal jen názvy známých algoritmů, podrobněji jsem popsal jen HybridSort a ...

1) Vyslovit a dokázat tvrzení že na součet n čísel je potřeba aspoň log n času Ptal se na předpoklady, proč tahle věta plátí když jsme měli algoritmus na sčítání n čísel který byl rychlejší než log n, jak rychle a s jakým počtem procesorů umíme sčítat 2) Zjistit počet artikulací v grafu zadaném mati...

Dokázat že Chaitin-random a ML-random jsou totéž.

S dovolením doplním poslední přednášku;) Pro neprázdnou \Pi^0_1 třídu A která je podmnožinou (0,1)-DNR existuje x_0 t.ž. A \cap \{f : f(x_0) = i \} eq \emptyset pro i = 0,1 Pro neprázdnou \Pi^0_1 třídu A která je podmnožinou (0,1)-GNR existuje x_0 t.ž. A \cap \{f : f(<x_0, j>) = B(j)\ \forall j \} e...

04.02.2015: 1) Věta o nízké bázi 2) Výběr z: (a) Pod 1-generickou nejsou nerekurzivní množiny (b) 1-generická neobsahuje nekonečnou rekurzivně spočetnou podmnožinu U 2a jsem se trochu zamotal ale bez problémů mi to uznal s tím že myšlenka je správně ale za detaily neručí. Celkově ty papíry četl doce...

Program k přečtení (snad bez chyby): Program k napsání:
Na vstupu je infixový výraz s operátory +,- a * a s celými čísly. Vyhodnoťe ho.

Výsledek za 3.

Domácí úkoly byly postupně opravovány předešlou noc. Před zkouškou byly prezentace a nakonec z nich každý měl cca 12 - 15 bodů (15 bylo maximum). Zadání: 1) Restrikční mapování : definice, příklady (PDP, DDP, SPDP), důkaz NP-úplnosti DDP 2) Lokální alignment: definice, algoritmus, heslovitě možná vy...

Heapsort
Možnost výběru mezi tříděním na disku a na páskách
Doplňující: jen stručně říct o paralelním třídění

Zkouška pohodová, stejně jako přednáška (na které jsem byl sám :) ).

3.9.2014 1) Sufixový strom: efektivní konstrukce 2) Bitový paralelismus: vybrat si problém a vyřešit ho pomocí bitových operací + pseudokód 3) Konečná množina vzorků - časová složitost ad 1) Ukkonen + 4 triky. V algoritmu pro i-tou iteraci jsem měl napsáno že se řídím podle toho, zda návěští hrany j...

Písemka stejná jako příspěvek přede mnou. Doporučuju si pořádně přečíst zdůvodnění k bodu 3: poslední inkluze ve zdůvodnění je neostrá, měl jsem ji jako ostrou a hned to vygeneruje 4 chyby (a přišlo mi, že to byla častá chyba). Každopádně Čepek počítal stejné chyby jako jednu chybu takže zápočet dos...

1) Plánovaní v prostoru plánů: kaz, otevřený cíl, hrozba, PSP, PoP, heuristiky co se používají. 2) F2 || C_max - co to je, napsat jak se to řeší a dokázat větu co se k tomu používá Na začátku oznámil, že zkouška bude víc písemná než ústní (asi spěchal), četl to poctivě (ptal se pokud jsem tam měl ně...

1) IDS
2) Roboti na Marsu.

(na MAS jsem nechodil, byl jsem tam na zkoušce z EVY2, takže v té první otázce byla možná jiná třípísmenná zkratka ;) )

1) GP - čím divnější, tím lepší.
2) O čem jsme dělali referát na cvikách (pak jsme si o tom hromadně moc pěkně popovídali).

Bayesovská síť - definovat, popsat odvozování v ní - exaktní metody (enumerace, eliminace proměnných) a aproximační metody (zamítání, vážení, MCMC). Ptal se na: proč BS a ne jiné metody (např - úplná distribuční fce) : paměť Na co se vůbec ptáme: P(X|e) Jak zjistíme ze vzorků odpověď na to na co se ...

1) Limitní vyčíslitelnost 2) výběr a) konstrukce 1-generické b) low basis theorem U první otázky, první implikace - jak se tam definuje funkce f přes funkcionál Fí. Ptal se (všech), co bychom museli udělat kdyby nebyla totálni (nebo něco podobného). Což jsem nevěděl plus jsem nevěděl u druhé implika...