====== 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 ]].