• Home|
• Kontakty

Jirka Setnička

„Politici by měli číst science-fiction, ne detektivky a westerny.“ _{Arthur C. Clarke}

Cvičení z předmětu Algoritmy a datové struktury I (NTIN060) k přednáška Ondřeje Čepka (stránky přednášky) a Luďka Kučery.

Kontakt:

Pro účely cvičení mě můžete kontaktovat na emailu setnicka+ads@kam.mff.cuni.cz (usnadní mi to třídění pošty a zrychlí čas na odpověď), nebo můžete použít jinou metodu ze stránky s kontakty. Nebo mě někdy prostě odchyťte na chodbě :-)

Kdy a kde:

Cvičení se konají každé pondělí od 14:00 v učebně S6.

Počátkem semestru bohužel nejsem v ČR, tedy první tři cvika budou se záskokem (vracím se v pondělí večer po třetím cviku). Pokusím se ale být průběžně v dosahu emailem, ale odpovědi mohou pár dní trvat.

Zápočet:

Od druhého cvika dál se začnou objevovat (hlavně) teoretické domácí úkoly, za které bude potřeba získat alespoň 100 bodů. Úloh bude vypsáno alespoň za 150 bodů, možná i více. Další body navíc půjde získat i za hezký zápočtový program nebo aktivitu během cvik.

Druhou podmínkou je vypracování zápočtového programu, který bude nějak implementovat či používat některou z technik odpřednesených na přednášce. Téma se mnou nejdřív konzultujte, abyste nedělali něco moc těžkého, nebo naopak něco, co nepůjde uznat za zápočet. Detaily k zápočťákům domluvíme asi koncem března.

Získané body:

Jméno	Úkoly	Bonusy	Bodů	Zápočťák	Zápočet
Anastasia	median(2), inverze(5), treeDiam(2), intervalTree(5), sroubky(12)		26	--	NE
Bydža	median(5), inverze(3), treeDiam(5), intervalTree(10), vazeni(5), mergesort(10), sroubky(12), bilaPani(10), cyklus(5)		65	Dijkstrův algoritmus s haldou	NE
Flower	median(5), inverze(10), treeDiam(5), intervalTree(10), vazeni(7), sroubky(12), bilaPani(10), odtrhavani(10), zataceni(10), cyklus(5), banditi(15), anketa(5)		104	Intervalové stromy	OK
Hanka	median(5), inverze(10), treeDiam(5), intervalTree(10), vazeni(5), mergesort(10), sroubky(12), odtrhavani(10), bilaPani(10), cyklus(5), banditi(15)	Aktivita na cviku: 3 (3)	100	Plánovač procesů CFS	OK
KKK	median(5), inverze(10), treeDiam(5), intervalTree(10), vazeni(7), mergesort(10), sroubky(12), bilaPani(10), odtrhavani(10), zataceni(10), cyklus(5), 4cyklus(8)		102	Knihovna na červeno-černé stromy	OK
knezi	median(5), inverze(10), treeDiam(5), intervalTree(10), vazeni(5), mergesort(10), sroubky(12), bilaPani(10), odtrhavani(10), zataceni(10), cyklus(5), banditi(15)		107	Dijkstrův algoritmus s více datovými strukturami	OK
Lucka	median(5), inverze(10), treeDiam(5), intervalTree(5), vazeni(5), mergesort(10), cyklus(5), odtrhavani(10), zataceni(10), banditi(15), cesty(10), trie(10), anketa(5)		105	Trie	OK
Matěj	median(5), inverze(10), treeDiam(5), intervalTree(10), vazeni(7), mergesort(10), sroubky(12), bilaPani(10), odtrhavani(10), zataceni(10), cyklus(5), banditi(15)	Hezký zápočťák: 15	124	Splay stromy	OK
Michal	median(5), inverze(5), treeDiam(5), intervalTree(10), vazeni(7), mergesort(10), sroubky(12), odtrhavani(10), cyklus(5), banditi(15), 4cyklus(8), cesty(10), medianPos(10)		112	Knihovna pro práci s AVL stromy	OK
PetoK	median(5), inverze(10), treeDiam(5), intervalTree(10), vazeni(7), mergesort(10), sroubky(12), bilaPani(10), odtrhavani(10), cesty(10), banditi(15)		104	Maticová knihovna	OK
Petr	median(5), inverze(10), treeDiam(5), intervalTree(10), vazeni(7), mergesort(10), sroubky(12), odtrhavani(10), zataceni(10), cyklus(5), medianPos(10), anketa(5)	Aktivita na cviku: 3 (3)	102	Dijkstrův algoritmus	OK
Samuel	treeDiam(5), intervalTree(10), vazeni(5), mergesort(10), sroubky(12), bilaPani(10), zataceni(10), odtrhavani(10), cyklus(5), banditi(15), cesty(10), anketa(5)	Hezký zápočťák: 15	122	Doplňování diakritiky	OK
Shinji	median(2), treeDiam(5), intervalTree(10), vazeni(7), mergesort(10), sroubky(12), bilaPani(10), zataceni(10), odtrhavani(10), cyklus(5), banditi(15), medianPos(10)		106	B stromy	OK
swaco	median(5), inverze(5), treeDiam(5), intervalTree(10), vazeni(7), mergesort(10), sroubky(12), bilaPani(6), odtrhavani(10), cyklus(5), banditi(15), cesty(10), medianPos(10)		110	Fibonacciho haldy	OK
Tarina	median(5), inverze(10), treeDiam(5), intervalTree(10), vazeni(7), mergesort(10), sroubky(12), bilaPani(10), zataceni(10), odtrhavani(10), cyklus(5), banditi(15), cesty(10)	Hezký zápočťák: 25	144	Porovnání třídících algoritmů	OK
Vašek	median(5), inverze(10), treeDiam(5), intervalTree(10), vazeni(7), mergesort(10), sroubky(12), bilaPani(10), odtrhavani(10), zataceni(10), cyklus(5), cesty(10)	Aktivita na cviku: 3 (3)	107	Jarníkův algoritmus na minimální kostry	OK
Vašek R.	inverze(10), treeDiam(5), intervalTree(10), vazeni(5), mergesort(10), sroubky(12), zataceni(10), odtrhavani(10), cyklus(5), banditi(15), anketa(5)	Aktivita na cviku: 3 (3)	100	Hledání pomocí hashování	OK
Viki	median(5), inverze(10), treeDiam(5), intervalTree(10), vazeni(7), mergesort(10), sroubky(12), bilaPani(10), odtrhavani(10), zataceni(10), cyklus(5)	Aktivita na cviku: 6 (3+3)	100	Hledání silně souvislých komponent	OK
Zelí	median(5), inverze(10), treeDiam(5), intervalTree(10), vazeni(5), mergesort(10), sroubky(12), odtrhavani(10), zataceni(10), cyklus(5)	Aktivita na cviku: 3 (3) Hezký zápočťák: 25	110	Implemetace řazení, map a set	OK
Zuzka D.	median(5), inverze(10), treeDiam(5), intervalTree(10), vazeni(5), mergesort(10), sroubky(12), bilaPani(10), odtrhavani(10), zataceni(10), banditi(15)		102	Knihovna pro práci s haldou	OK
Zuzka Š.	median(5), inverze(10), treeDiam(5), intervalTree(10), vazeni(7), mergesort(10), sroubky(12), bilaPani(10), odtrhavani(10), zataceni(10), cyklus(5), banditi(15)	Hezký zápočťák: 15	124	Suffixové stromy	OK

Studijní materiály

• (ADS)Skripta k ADS od Martina Mareše – Skvělý studijní materiál pokrývající dobře skoro celou látku
• (KSP)Programátorské kuchařky Korespondenčního semináře z programování – dobře pokrytá některá témata, mělo by být pochopitelné i středoškoláky. Je dobré k pochopení probírané látky, ale nejsou zde příliš formální důkazy.
• Videozáznamy ADS I z minulého roku (2014/2015) přednášené Martinem Marešem – pokud jste třeba na přednášce tento rok něco nepochytili nebo nestihli. Jsou dostupné po přihlášení loginem do SISu.

Na některé materiály se budu odkazovat u jednotlivých cvičení – ADS nebo KSP v závorce značí, kam materiály odkazují.

Rozvrh cvičení (aneb co jsme dělali a co se chystá):

22.2.	Záskok Karel Tesař Pár problémů na rozcvičení: Úvodní motivace Podúsek s maximálním součtem Házení vajíček z mrakodrapu Hledání největší nulové podmatice v matici (se složitostí $\O(N^2M)$ – ale existuje lepší) Studijní materiály: Základní algoritmy(KSP), Pár příkladů na úvod(ADS)
29.2.	Záskok Pavel Veselý Časová složitost a binární vyhledávací stromy (BVS): Časová složitost a "óčkové" notace ($\O$, $\Omega$ a $\Theta$) Půlení intervalů a zavedení BVS k-tý nejmenší prvek v BVS Úkoly: median Studijní materiály: Časová a paměťová složitost(ADS), Složitost(KSP)
7.3.	Záskok Pavel Veselý Trochu do hlubin zkoumání algoritmů: Zavedení modelu RAM Bubblesort a Eratosthenovo síto na RAMu (včetně důkazu složitosti Eratosthenova síta $\O(N \log N)$) Kódování n čísel do jednoho libovolně velkého čísla Intervaly: Pole čísel a dotazy na součet intervalů Intervalové stromy (a pro ty, kdo už intervalové stromy znají: Fenwickovy stromy v dolní části kuchařky) Úkoly: inverze Studijní materiály: Počítání na RAMu(trochu pokročilejší skripta ke Grafovým algoritmům)
14.3.	Konečně dorazím osobně :-) Další stromy, tentokrát i vyvažované: Konstrukce vyváženého BVS ze seřazených hodnot v čase $\O(N)$ Další vyvážený BVS: Operace jako nevyvážený BVS, jen když jeden z podstromů má více než dvojnásobek vrcholů druhého, tak celý podstrom rozebereme a postavíme znovu (dokázali jsme amortizovaně $\O(\log N)$ na operaci) Vyhledávací strom pamatující si dvojice (klíč;hodnota) zvládající odpovídat na dotazy typu "Maximum z hodnot na intervalu klíčů" Úkoly: treeDiam Studijní materiály: Vyhledávací stromy(KSP), Vyhledávací stromy(ADS)
21.3.	Intervalové a (a,b)-stromy: Povídání k zápočťákům Intervalový strom: složení intervalu z nejvýše $2\log N$ vrcholů, update na intervalu Dokončení vyhledávacího stromu pamatujícího si dvojice (klíč;hodnota) z minule (a,b)-stromy jako alternativa vyvažovaným stromům: definice, FIND, INSERT a DELETE, spodní a horní odhad na hloubku Úkoly: intervalTree Studijní materiály: Intervalové stromy(KSP)
28.3.	Velikonoční pondělí – cvika nejsou
4.4.	Třídění: Přehled třídících algoritmů: QuickSort, TreeSort, MergeSort, HeapSort Vážení kuliček na vahách, náznak důkazu o nemožnosti třídit lépe než v $\O(N \log N)$ Rozděl a panuj: Hanojské věže Třídění v malém rozsahu v čase $\O(N)$ – CountingSort, přihrádkové třídění Víceúrovňové přihrádkové třídění Úkoly: vazeni, sroubky, mergesort Studijní materiály: Třídění(ADS), Třídění(KSP)
11.4.	Úvodní nakousnutí grafů: Reprezentace grafů v počítači (matice sousednosti, seznam sousedů) Poznávání grafu stromu a bipartitního grafu Strážníci ve městě aneb vrcholové pokrytí stromu Eulerovské tahy Úkoly: odtrhavani, cyklus Studijní materiály: Procházky po grafech(KSP)
18.4.	Záskok Jan Bok Pokračování v úvodu do grafů: Hledání centra grafu Hledání zdroje v matici sousednosti Hledání mostů v grafu (zahájení) Studijní materiály: Grafy(KSP)
25.4.	Použití DFS a BFS na grafech: Hledání mostů a artikulací Tarjanův algoritmus na hledání silně souvislých komponent Bludiště se dveřmi a klíči – nafouknutí stavového prostoru Bludiště s bílou paní (nebo krumpáčem) Úkoly: bilaPani, zataceni Studijní materiály: Základní grafové algoritmy(ADS)
2.5.	Hledání cest v grafu: Hledání nejkratších cest v grafu s "krátkými" vzdálenostmi Obecné hledání nejkratších cest – relaxační algoritmus Dijkstrův algoritmus s různými datovými strukturami Cesta pro nejvyšší jeřáb, cesta s mýtným i ve městech Úkoly: banditi, 4cyklus, cesty Studijní materiály: Halda, heapsort a Dijkstrův algoritmus(KSP)
9.5.	Pokračování v hledání cest: Dijkstra se zápornými hranami – kdy funguje a kdy ne Hledání cest se zápornými hranami – Bellman-Fordův algoritmus Vydělávání ve směnárně (tabulka kurzů měn) Studijní materiály: Nejkratší cesty(ADS)
16.5.	Hešování a písmenkové stromy (trie): Principy hešování a univerzálního hešování Různé typy hešovacích funkcí Řešení kolizí Písmenkové stromy a hledání nejlepšího rýmu Tiskařský šotek aneb hledání podobných slov s jedním překlepem Úkoly: presmycky, trie, medianPos Studijní materiály: Hešování(KSP), okrajově Vyhledávání v textu(ADS)
23.5.	Poslední cviko Minimální kostry: Úvod do minimálních koster – Jarník, Borůvka a Kruskal Minimální kostry v grafech s neunikátními váhami hran Drak a doupata se zlatem (chceme, aby označené vrcholy v minimální kostře byly listy) Úkoly: anketa :-) Studijní materiály: Minimální kostry(ADS), Minimální kostra(KSP)
A to je tento semestr vše, přeji hodně zdaru u zkoušek a získávání zápočtů :-)

Domácí úkoly

Aby se podpořila práce během semestru, tak má každý úkol stanovený termín (typicky tři týdny, platí odevzdání do začátku cvičení) kdy je za plný počet bodů. Po termínu je ho možné odevzdat až do začátku zkouškového období za dolní celou část poloviny bodů.

Preferovaný způsob odevzdání je emailem (PDF, čistý text v UTF-8, čistý text v ASCII, …). Při prvním odevzdání úkolu si zvolte přezdívku, pod kterou chcete být uvedeni v tabulce bodů, nebo napište že na webu nechcete být uvedeni vůbec.

Datum	Úkol	Body	Zadání
12.03. Termín: 28.03.	median	5	Upravte binární vyhledávací strom tak, abyste vždy zvládli v čase $\O(\log N)$ najít medián (prostřední prvek).
	inverze	10	Inverze v permutaci je jakákoliv dvojice prvků, která se vyskytne v opačném pořadí (více viz Wikipedia). Navrhněte algoritmus počítající počet inverzí v zadané permutaci (nápověda: použijte binární vyhledávací stromy)
14.03. Termín: 04.04.	treeDiam	5	Na vstupu dostanete binární strom (obecně nevyvážený). Úkolem je vymyslet algorimus, který na tomto stromě najde nejdelší cestu mezi dvěma vrcholy.
	intervalTree	10	Naprogramujte (stačí sepsat v pseudokódu nebo jako zdroják v nějakém imperativním programovacím jazyce – Pascal, C, C#, Java, …) následující dvě operace na intervalovém stromě: Aktualizace hodnoty na indexu i Spočtení součtu hodnot na intervalu (a,b)
05.04. Termín: 25.04.	vazeni	5	Rozšíření příkladu ze cvika: Máme 12 kuliček a rovnoramenné váhy. Víme, že jedna kulička je lehčí nebo těžší (ale nevíme co z toho), než ostatní. Kolik nejméně vážení potřebuji, abych určil která to je a rozhodl, zdali je lehčí nebo těžší než ostatní.
	mergesort	10	Implementujte mergesort bez použití rekurze. Řešení můžete sepsat v pseudokódu nebo jako zdroják v nějakém imperativním programovacím jazyce – Pascal, C, C#, Java, …
	sroubky	12	Máme $N$ šroubků a $N$ matiček různých velikostí. Vždy právě jedna matička pasuje na právě jeden šroubek, o ostatních zjistíme jen, jestli je matička malá anebo velká, jinak jsou matičky i šrouky mezi sebou neporovnatelné (nezjistíme, jaký šroubek je ětší, nebo o kolik nesedí matička). Vymyslete jak s co nejmenším počtem pokusů spárovat všechny šroubečky a matičky dohromady.
27.04. Termín: 23.05.	bilaPani	10	Rozšíření příkladu ze cvika: Máme plán hradu zadaný jako čtvercovou síť, mezi některými políčky jsou zdi, pevné kamenné hradní zdi. Bílá paní může zdmi procházet, ale ráda by našla cestu ze startu do cíle (označená políčka), na které bude muset zdí projít co nejméněkrát. Ze všech možných cest s minimálním množstvím průchodů zdí najděte takovou, které je co nejkratší (tedy primárně optimalizujeme počet průchodů zdí, sekundárně délku cesty).
	odtrhavani	10	Mějme souvislý neorientovaný graf. V jakém pořadí postupně smazat všechny jeho vrcholy, aby byl v průběhu mazání graf stále souvislý?
	zataceni	10	Půjčili jste si v půjčovně auto a mapu města – město je čtvercová síť s nějakými políčky průjezdnými (silnice) a nějakými ne (domy). Jediná potíž je, že autu nefunguje levý blinkr a tak smíte zatáčet pouze doprava (otáčet se na místě také není povoleno, můžete prostě jet jen rovně nebo doprava). Vymyslete algoritmus na nalezení nejkratší cesty mezi zadaným startem a cílem.
	cyklus	5	Poznejte, jestli označený vrchol v neorientovaném grafu leží na cyklu
04.05. Termín: 06.06.	banditi	15	Jste v roli obchodníka za starých časů, který chce dopravit náklad mezi dvěma města a nenechat se přepadnout bandity. Máte mapu v podobě grafu, kde jsou vyznačeny dva vrcholy, start a cíl, a pro každou hranu grafu máte pravděpodobnost, že jí zvládnete projít bez přepadení (na královské cestě je šance bezpečného průchodu 0.95, v temné soutěsce třeba jen 0.25). Najděte nejspolehlivější cestu ze startu do cíle aneb cestu s největším součinem šancí na bezpečný průchod.
	4cyklus	8	Máme ohodnocený orientovaný graf. Najděte v něm nejkratší čtyřcyklus (cyklus ze 4 hran) a to v lepším čase než v $\O(N^4)$
	cesty	10	Mějme mapu města – orientovaný graf silnic a jeden označený vrchol jako radnici. Radní by pro všechny ostatní vrcholy zajímalo, kolik do nich z radnice vede různých nejkratších cest = cest s nejmenším možným počtem silnic. Dvě cesty považujeme za různé, pokud se liší alespoň v jedné hraně.
16.05. Termín: 30.09.	presmycky	10	Dostanete slovník a seznam hledaných slov. Ke každému hledanému slovu najděte ve slovníku všechny anagramy neboli přesmyčky, které z tohoto slova můžou vzniknout.
	trie	10	Naimplementujte (stačí v pseudokódu) trii (písmenkový strom) nad abecedou a-z. Měla by umět alespoň operace INSERT, FIND a DELETE.
	medianPos	10	Budete postupně dostávat čísla (neutříděná). Sestrojte datovou strukturu, která po každém přidání čísla zvládne vypsat, jaký je aktuální medián (prostřední prvek) této posloupnosti.
24.05. Termín: 30.09.	anketa	5	Budu rád, pokud mi napíšete, co se vám na cviku nelíbilo, co naopak líbilo, jak těžké vám přišlo získat zápočet a jaké vám přišly úlohy. Díky za feedback :-)
Celkem:		160