Přibližně 10 minutová vystoupení

Obsah:
1. Abstraktní algoritmická formulace úlohy. (Např. Hledáme kostru neorientovaného grafu s tím omezením, že každý vrchol ve výsledné kostře musí mít stupeŇ nejvýše 3.) Pokud je 'pohádka' zajímavě vtipná, lze ji krátce zmínit.

2. Obrázek nebo obrázky s ilustrací dostatečně jednoduchého a přitom návodného případu dat.

3. Metoda řešení a její časová a paměťová složitost . (Např. použiju rekurzi, ke každé kostře vybudované pro n-1 vrcholů zkusím připojit n-tý vrchol, složitost exponenciální, paměťové nároky zanedbatelné, v řádu O(n^2)). Důvod, proč jsem použil právě tento postup, zmínka o jiných možných postupech, pokud existují.

4. Kód mého řešení s případnými vysvětlivkami a se zminěním zvlášť zajímavých/efektivních obratů.

5. Srovnání rychlosti mého řešení s jinými řešiteli na konkrétním Judge.


Vystupující:

Tomáš Hnídek, 8 queens problem, se zaměřením na efektivitu ( UVA judge problem 730 ).

Tomáš Altman, Pseudo-Random Numbers, ve skutečnosti jde o zjištění, kdy se daná posloupnost čísel začne opakovat nebo o detekci cyklu např. v spojovém seznamu, je to pěkný trik ( UVA judge problem 350).

Michal Polívka, Collecting Marbles, ( UVA judge problem 12087).

Jan Hadáček, Bridge, klasická úloha o přechodu mostu v noci s jednou baterkou, tentokrát pro neomezený počet lidí ( UVA judge problem 10037).

Vojtěch Šívr, Password Search, hledání opakujícího se podřetězce ve slově, hashtabulka nebo strom? ( UVA judge problem 902 ).
Případně Quadtrees, projděte stromem bez jeho konstruování (UVA judge problem 297 ).

courses/a4b36acm2/2013_ls/vystoupeni.txt · Last modified: 2018/10/03 03:51 (external edit)