Warning
This page is located in archive.

Letní Algoritmické Soustředění LASO 2016

.

Začátečníci

Kde: Laboratoř KN:E-220

Situační plánek

Program

Den Dopoledne 9:00-12:15
teorie - výklady - ukázky
Odpoledne 13:30 – 17:00
praxe - programování - diskuse
Po
19.9.
Graf, grafové pojmy a grafové vlastnosti, reprezentace grafu v paměti.
Přehled hlavních grafových úloh.
Neformální výklad asymptotické složitosti, ukázky na kódech, O/Θ/Ω notace.
Úlohy k dopoledni, zpracovat programově co nejvíce grafů.
Bez BFS jen lokální vlastnosti, počet trojúhelníků apod.
Út
20.9.
BFS, DFS, fronta, zásobník
Prioritní fronta, halda.
Seznámení s Graphviz, úlohy k dopoledni,
jednoduché prohledávání grafu.
St
21.9.
Dijkstra s prioritní frontou.
Porovnání efektivity probraných postupů.
Přehled řešitelných a neřešitelných úloh
Úlohy k dopoledni
Celkem Napište nám své připomínky a komentáře: Reakce účastníků LASO ..

Pondělí

Slidy: Úvodní grafový přehled

Rychlost kódu: Najděte v poli obsahujícím kladná i záporná čísla souvislý úsek s maximálním součtem. Diskuse řešení kubického, kvadratického i lineárního.
Úloha 0: Naprogramujte si všechna tři řešení.

// Obsah pole: 
// V a[] jsou pomocne hodnoty, je to tzv. linearni kongruentni generator pseudonahodnych cisel. 
// Pozor, v a[] pracujeme s longy, tj. 64-bitovymi cisly. 
 
a[0] = 123456;  
a[i+1] = (a[i]*22695477+1) % 4294967296; 
 
NasePole[i] = a[i] - 1580030168;

Graf na vstupu – Formát dat Data Graf
První řádek vstupu obsahuje dvě celá kladná čísla N a M oddělená mezerou představující po řadě počet uzlů a počet hran grafu. Předpokládáme, že uzly grafu jsou číslovány 0, 1, 2, …, N−1.
Následuje M řádků, každý popisuje jednu hranu. Pokud graf není vážený, jsou na řádku dvě celá čísla oddělená mezerou – čísla krajních uzlů hrany. Pokud je graf vážený, jsou na řádku tři celá čísla oddělená mezerou – čísla krajních uzlů hrany a váha hrany.
Pořadí uzlů na řádku i pořadí hran na vstupu může být libovolné.
7 13
4 0
5 0
0 6
3 4
4 2
4 6
3 5
6 3
1 6
4 1
5 6
1 5
0 3

Úloha 1.

Načtěte nevážený graf ze souboru a vypište k každému uzlu jeho seznam hran. Stáhněte si data s obrázky.

Úloha 2.

Načtěte vážený graf ze souboru a vypište k každému uzlu jeho seznam hran. Stáhněte si data s obrázky.

Úloha 3.

V daném grafu zjistěte pro každý možný stupeň uzlu D, kolik je takových hran, jejichž oba koncové uzly mají tento stupeň D. Pro každý stupeň tento počet hran vypište. Porovnejte své výsledky s ukázkovými. Stáhněte si data s obrázky.

Úloha 4.

Jindra vyrazí z uzlu A, který má určitý stupeň D. Pak jde do některého jeho sousedního uzlu B a nezajímá se o stupeň uzlu B. Z uzlu B se přesune do uzlu C, který je sousedem B a není to A. Jindra trvá na tom, že stupeň D startovního uzlu A i stupeň cílového uzlu C musejí být stejné. Určete, kolik je v daném grafu možností procházek podle Jindrových pravidel. Vypište toto jediné číslo na výstup. Stáhněte si data s obrázky.

Úloha 5.

Řekneme, že hrana H je lokálně minimální, pokud její váha je striktně menší než váha kterékoli hrany, která s H sdíli jeden uzel. Najděte v daném váženém grafu všechny lokálně minimální hrany a vypište je v rostoucím lexikografickém pořadí jejich krajních uzlů. Stáhněte si data s obrázky.

Úloha 6.

Určete, kolik je trojúhelníků v každém grafu úlohy 4. Trojúhelník je trojice uzlů, v níž každý uzel sousedí se zbylými dvěma uzly.

Úloha 7.

Určete, kolik je kružnic délky 4 v každém grafu úlohy 4. Kružnice nesmí obsahovat příčku, tj. první a třetí uzel v kružnici nesmí spolu sousedit a druhý a čtvrtý uzel v kružnici spolu nesmí sousedit.

Úterý

Slidy: Prohledávání grafu, halda

Úlohy na odpoledne:

  1. Stáhněte soubor s daty, se kterými budete pracovat.
  2. Nalezněte výchozí implementaci zásobníku ve vašem oblíbeném jazyce. Poté načtěte soubor seq.txt. Na každém řádku máte jeden z příkazů insert <number> a remove. Příkaz insert <number> vloží číslo <number> do zásobníku. Příkaz remove odstraní prvek ze zásobníku a vypíše ho na standardní výstup.
  3. [Dobrovolné] Sami naimplementujte zásobník a zopakujte úkoly z bodu 2. s vaší implementací. Zkontrolujte, že se výsledky shodují.
  4. To samé jako 2., pouze použijte frontu.
  5. [Dobrovolné] To samé jako 3., pouze implementujte frontu.
  6. Načtěte graf graph.txt jako neorientovaný graf. Ten je definovaný ve stejném formátu jako včera.
  7. Určete jaké vrcholy lze navštívit z vrcholu 0. Kolik jich je?
  8. Jaká je délka nejkratší cesty z vrcholu 0 do vrcholu 7.
  9. Kolik je komponent souvislosti v grafu? Komponenta souvislosti je množina vrcholů, že mezi každou dvojicí z nich vede cesta. Přitom platí, že do komponenty souvislosti již nelze přidat žádný další vrchol grafu tak, aby tato vlastnost zůstala zachována. Více detailů zde a zde.
  10. Nyní načtěte graf graph.txt jako orientovaný graf.
  11. Zopakujte úkoly 7. a 8. (abychom zvládli 9. pro orientovaný graf, museli bychom umět buď Tarjanův algoritmus nebo Kosarajiho algoritmus)
  12. Zopakujte úkol 2., pouze místo zásobníku použijte haldu. Operaci remove chápejte jako extract-min.
  13. Zopakujte předchozí úkol, ale místo haldy použijte pole. Prvky přidávejte nakonec a při implementaci extract-min hledejte minimum naivně pomocí procházení celého pole.
  14. Porovnejte časy běhu z kroků 12. a 13.
  15. Naimplementujte Median Maintenance, o kterém jsme mluvili na přednášce. Jako vstup můžete použít čísla ze souboru seq.txt, operace remove ignorujte.
  16. Zkontrolujte výsledky. Můžete se podívat také na implementaci.

Úlohy na odpoledne (středně těžké):

Úlohy na odpoledne (většinou těžší):

Graphviz:

Středa

courses/laso2016/zacatecnici.txt · Last modified: 2017/09/18 00:36 by berezovs