====== ZIMNÍ SEMESTR 2011 ======
**Anyone can make the simple complicated. \\
Creativity is making the complicated simple.**\\
\\
[[http://en.wikipedia.org/wiki/Charles_Mingus|Charles Mingus]]\\
----
=== Organizace a zápočet ===
Seminář probíhá každé ponděli v 9:00-10:30 v G102A nebo G205 nebo E205 na Karlově náměstí.\\
Klasifikovanou součástí jsou samostatné domácí programovací úlohy zadávané v průběhu semestru, které musí být akceptovány systémem [[http://uva.onlinejudge.org/| UVA Online Judge]] .\\
Klasifikace je uvedena dole na stránce pod tabulkou úloh a řešitelů. \\
Seminář vedou\\
[[mailto:jacerny@gmail.com | Jakub Černý ]]\\
[[mailto:berezovs@fel.cvut.cz| Marko Genyk-Berezovskyj ]]\\
\\
[[http://www.fel.cvut.cz/education/bk/predmety/19/70/p1970806.html| Sylabus]]
----
=== Odkazy ===
* Algoritmické úlohy spolu s odevzdávacím/vyhodnocovacím systémem na University of Valladolid: [[http://uva.onlinejudge.org/| UVA Online Judge]]
* Soutěžní stránky ACM na FEL: [[http://contest.felk.cvut.cz/|ACM International Collegiate Programming Contest]]
* Sbírka typických úloh s dobře vysvětlenými základy a komentáři: Steven S. Skiena, Miguel A. Revilla: [[http://www.acmsolver.org/books/Programming_Challenges_Miguel_Skiena.pdf|Programming Challenges]]
* Loňské stránky předmětu [[http://acm.algoritmy.eu/|zde]].
----
=== Seminář 1 (10.10.) ===
**Téma** \\
Úvodní přehled témat semináře, jednoduché intuitivní postupy při řešení konkrétních úloh.
**Příklady k rozmyšlení** \\
Délka ulice a čísla domů: Najděte dvě čísla menší než dané N splňující dodatečnou podmínku, pokud možno v čase úměrném N nebo i rychleji.
[[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=74| zde ]]. \\
Silueta marakodrapů na obzoru [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=41|zde]]. \\
Zjistěte, jaký maximální počet krabic lze vložit do sebe navzájem.
[[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=39| zde]].
----
=== Seminář 2 (17.10.) ===
**Rozcvička** \\
Petr sečetl čísla všech stran kapitoly knihy, kterou právě četl. Nepamatuje si už ale, jestli mu vyšlo 412 nebo 512. Zjistěte, na které stránce kapitola začíná a na které končí.\\
Komentář: Zcela jistě to jde v čase úměrném odmocnině z většího předpokládaného součtu. Šlo by to rychleji?
**Téma** \\
Orientované a neorientované grafy, jejich reprezentace v počítači. Obarvení grafu dvěma barvami.
**Příklad k rozmyšlení** \\
Obarvení grafu dvěma barvami, kopíruje doslovně probrané téma, vyzkoušejte si reprezentaci grafu ve vašem oblíbeném jazyce.
[[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=37&page=show_problem&problem=945 | zde ]].
----
=== Seminář 3 (24.10.) ===
**Rozcvička** \\
Jak máme rozdělit číslo 20 na součet několika kladných celých sčítanců, aby součin všech těchto sčítanců byl co největší? \\
Komentář: Zkuste si úlohu vyřešit pro případ, že sčítance nemusí být celé, ale libovolné reálné kladné (asi i větší než 1).
**Téma** \\
Nejdelší cesta v orientovaném acyklickém grafu, topologické uspořádání.
**Příklady k rozmyšlení** \\
Změňte co nejrychleji konfiguraci čísel na ciferném bezpečnostním zámku
a vyhněte se přitom dalším zakázaným konfiguracím:
[[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=37&page=show_problem&problem=1008| zde ]]. \\
Naskládejte co nejvíce disků na více Hanojských věží s pozměněnými pravidly. Uvažte, že tentokrát pracujeme vlastně s nekonečným grafem.
[[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=37&page=show_problem&problem=1217| zde ]]. \\
**Domácí programovací úloha** \\
Zjistěte, jaký maximální počet krabic lze vložit do sebe navzájem (ze semináře 1).
[[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=39| zde]].
----
=== Seminář 4 (31.10.) ===
**Rozcvička** \\
Ve skříni je 15 červených a 6 černých ponožek. Náhodně vybereme dvě z nich. Jaká je pravděpodobnost, že vybereme červený pár? \\
Komentář: Úloha je vlastně grafová, máme spočítat hrany v určitém grafu. Jako jednodušší variantu lze vyzkoušet 3 červené a 1 černou ponožku ve skříni.
**Téma** \\
Procházení do šířky a Dijkstrův algoritmus.
**Domácí programovací úloha** \\
Převoz turistů autobusy v co nejmenším počtu skupin.
[[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=37&page=show_problem&problem=1040 | zde]].
**K zamyšlení na příště ** \\
Pravděpodobnost, že Vilém porazí profesionálně hrajícího Lukáše, je 1:5. Pravděpodobnost, že porazí svého staršího bratra, je 1:2. Vilém získá putovní cenu, pokud vyhraje ze tří zapasů alespoň dva zápasy za sebou, a může si vybrat, zda pořadí protivníků v těchto třech zápasech bude Lukáš, bratr, Lukáš nebo bratr, Lukáš, bratr. Které pořadí si má vybrat a proč?\\
Komentář: Úloha je vlastně grafová, jde o různě ohodnocené průchody konkrétním nevelkým binárním stromem.
----
=== Seminář 5 (7.11.) ===
Rychlé zopakování/připomenutí, co je to časová složitost.
Úlohy s pěknými triky, jak rychle a efektivně řešit úlohy. Předpočítání si výsledků, rychlé vyhodnocování polynomu, rychlé vypsání posloupnosti cisel tvaru 2^i*3^j*5^k podle velikosti, hledání největší jedničkové podmatice.
Zadání viz [[http://acm.algoritmy.eu/wp-content/uploads/casova_sloz_a_zakladni_triky.pdf|pdf]].
Jako úlohy na doma jsme vybrali jednoduché
* [[http://www.programming-challenges.com/pg.php?page=downloadproblem&probid=110301&format=html |WERTYU]]
* [[http://www.programming-challenges.com/pg.php?page=downloadproblem&probid=110203&format=html |HARTALS]]
* [[http://www.programming-challenges.com/pg.php?page=downloadproblem&probid=110403&format=html |BRIDGE]]
* [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2092 |Longest palindrom in string]] (Těžší úloha, její řešení nahrazuje libovolné 2 do té doby, než si na jednom z příštích seminářů ukážeme řešení. To je pro ty, co si chtějí trochu zapřemýšlet.)
=== Seminář 6 (14.11.) ===
Na tento seminář si doneste notebooky, zkusíme si minisoutěž!
Zadání úloh
Tréningovové úlohy z "practice session" z CERC2011 (každý si kontroluje vstupy x výstupy přes diff). -- rozdáno na semináři.
Pro pokročilejší tu máme v záloze úlohy, které si mohou zkusit vymyslet, naprogramovat a submitnout na online server
* 3n+1 problem [[http://www.programming-challenges.com/pg.php?page=downloadproblem&probid=110101&format=html | (prog. challenges]] |[[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=36 | online judge)]]
* Minesweeper [[http://www.programming-challenges.com/pg.php?page=downloadproblem&probid=110102&format=html | (prog. challenges]] |[[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1130 | online judge)]]
* LCDisplay [[http://www.programming-challenges.com/pg.php?page=downloadproblem&probid=110104&format=html | (prog. challenges]] |[[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=29&page=show_problem&problem=647 | online judge)]]
=== Seminář 7 (21.11.) ===
Nepřesná aritmetika
Největší společný dělitel, nejmenší společný násobek
[[http://acm.algoritmy.eu/wp-content/uploads/cisla.pdf | zadani-cisla.pdf]]
=== Seminář 8 (28.11.) ===
Geometrie - základy, geometrický význam determinantu, plocha nekonvexního mnohoúhelníka v O(n), plocha sjednocení obdélníků v O(n log n).
Úloha na naprogramování: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2510| Cranes]] - jednoduchá geometrická úloha.
=== Seminář 9 (5.12.) ===
Dynamické programování (Jakub)
Příklady ze semináře [[http://acm.algoritmy.eu/wp-content/uploads/dynprog_priklady.pdf | dynamicke_programovani.pdf]]
Úloha na doma: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=39&page=show_problem&problem=944 | Cutting Sticks]]
=== Seminář 10 (12.12.) ===
Minimální kostra v grafu, zopakováno. Využití Union-Find struktury. S ohledem na odpadající příští sseminář ještě kódování binárních stromů a to 2N nebo jen N bity, podle toho, zda jsou regulární. \\
Domácí úloha: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=38&page=show_problem&problem=975 | Freckles]], přímočará aplikace min. kostry.
=== Seminář 11 (19.12.) ===
**Odpadá díky přesunu výuky v tomto týdnu z pátku na pondělí.**
Binární stromy a aplikace (Marko)
===== Výsledky domácích úkolů =====
| Uloha | Lída Pabalavets |
|[[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=39 | stacking boxes]] | 1 |
|[[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=37&page=show_problem&problem=945 | bicoloring]] | 1/2 |
|[[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=37&page=show_problem&problem=1040 | the tourist guide]] | 1 |
|[[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=31&page=show_problem&problem=1023 | WERTYU]] nebo [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=30&page=show_problem&problem=991 | Hartals]] nebo [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=32&page=show_problem&problem=978 | Bridge]] | |
|[[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=36 | 3n+1]] nebo [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1130 | minesweeper]] nebo [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=29&page=show_problem&problem=647 | LCDisplay]] | 2 |
|[[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2510 | cranes]] | |
|[[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=39&page=show_problem&problem=944 | Cutting Sticks]] | |
|[[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=38&page=show_problem&problem=975 | Freckles]] | |
==== Klasifikace ====
V uvedené tabulce je nutno mít správně vyřešenu **alespoň polovinu** řádků, tj. čtyři. \\
Klasifikace je: 4 řádky - **C**, 5 nebo 6 řádků - **B**, 7 nebo 8 řádků - **A**. \\
Úlohy nutno vyřešit do **10.2.2012**.
==== Problémy s Javou na OnlineJudge.org ====
* [[http://online-judge.uva.es/board/viewforum.php?f=16 | Diskuse k Javě při řešení úloh]] (tady se můžete zeptat, co vám pálí).
* [[http://acm.uva.es/board/viewtopic.php?f=31&t=7429| How to write Java solution ]].