ZIMNÍ SEMESTR 2011

Anyone can make the simple complicated.
Creativity is making the complicated simple.


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 UVA Online Judge .

Klasifikace je uvedena dole na stránce pod tabulkou úloh a řešitelů.

Seminář vedou
Jakub Černý
Marko Genyk-Berezovskyj

Sylabus


Odkazy

  • Algoritmické úlohy spolu s odevzdávacím/vyhodnocovacím systémem na University of Valladolid: UVA Online Judge
  • Sbírka typických úloh s dobře vysvětlenými základy a komentáři: Steven S. Skiena, Miguel A. Revilla: Programming Challenges
  • Loňské stránky předmětu 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. zde .

Silueta marakodrapů na obzoru zde.

Zjistěte, jaký maximální počet krabic lze vložit do sebe navzájem. 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. 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: 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.


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. 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 pdf.

Jako úlohy na doma jsme vybrali jednoduché

  • 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

Seminář 7 (21.11.)

Nepřesná aritmetika

Největší společný dělitel, nejmenší společný násobek

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í: Cranes - jednoduchá geometrická úloha.

Seminář 9 (5.12.)

Dynamické programování (Jakub)

Příklady ze semináře dynamicke_programovani.pdf

Úloha na doma: 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: 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ů

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

courses/a4b36acm2/2011_zs/main.txt · Last modified: 2018/10/03 03:51 (external edit)