Search
Anyone can make the simple complicated. Creativity is making the complicated simple. Charles Mingus
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 UVA Online Judge .
Klasifikace je uvedena dole na stránce pod tabulkou úloh a řešitelů.
Seminář vedou Jakub Černý Marko Genyk-Berezovskyj Sylabus
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. zde .
Silueta marakodrapů na obzoru zde.
Zjistěte, jaký maximální počet krabic lze vložit do sebe navzájem. zde.
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. zde .
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: 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. zde .
Domácí programovací úloha Zjistěte, jaký maximální počet krabic lze vložit do sebe navzájem (ze semináře 1). zde.
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. 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.
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 pdf.
Jako úlohy na doma jsme vybrali jednoduché
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
Nepřesná aritmetika
Největší společný dělitel, nejmenší společný násobek
zadani-cisla.pdf
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í: Cranes - jednoduchá geometrická úloha.
Dynamické programování (Jakub)
Příklady ze semináře dynamicke_programovani.pdf
Úloha na doma: Cutting Sticks
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: Freckles, přímočará aplikace min. kostry.
Odpadá díky přesunu výuky v tomto týdnu z pátku na pondělí. Binární stromy a aplikace (Marko)
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.