PředmětyPředměty(verze: 845)
Předmět, akademický rok 2018/2019
   Přihlásit přes CAS
Rozšiřující seminář Algoritmy a datové struktury II - NTIN108
Anglický název: Extension seminar Algorithms and Data Structures II
Zajišťuje: Katedra aplikované matematiky (32-KAM)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2018 do 2019
Semestr: zimní
E-Kredity: 3
Rozsah, examinace: zimní s.:0/2 Z [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Garant: prof. RNDr. Luděk Kučera, DrSc.
Třída: Informatika Bc.
Kategorizace předmětu: Informatika > Teoretická informatika
Anotace -
Poslední úprava: Mgr. Jan Kynčl, Ph.D. (21.05.2018)
Předmět navazuje na předmět NTIN061 Algoritmy a datové struktury II, algoritmy vyučované v rámci ADS II ukazuje pod jiným úhlem pohledu a zaměřuje se na detailní ilustraci algoritmických myšlenek, na kterých jsou založeny. Algoritmy jsou presentovány pomoci vizualizací, které jsou vytvářeny tak, aby tyto myšlenky presentovaly graficky a ilustrovaly především invarianty algoritmů. Cílem předmětu je ukázat studentům algoritmy jako tvůrčí oblast informatiky a naučit je o chování a vlastnostech algoritmů přemýšlet exaktním matematickým způsobem.
Podmínky zakončení předmětu
Poslední úprava: prof. RNDr. Luděk Kučera, DrSc. (13.06.2019)

Zápočet bude udělen za aktivní účast na semináři, a to

za fyzickou přítomnost na semináři, provázenou přítomností duševní (prokázanou například samostatným řešením zadaných příkladů, týkajících se probíraných algoritmů, připomínkami a/nebo dotazy) a

zejména za aktivitu přes emailovou adresu algovize@gmail.com - zasílání výsledků testů, hodnocení systému Algovision po stránce obsahové i softwarové, návrhy dalšího rozvoje vizualizací algoritmů, hlášení chyb v rozsahu, který prokáže domácí přípravu na základě témat, probíraných na semináři

Literatura -
Poslední úprava: Mgr. Jan Kynčl, Ph.D. (21.05.2018)

1. Vizualizace jsou (nebo do začátku semestru budou) dostupné na www.algovision.org, k jejich prohlížení stačí libovolný webový prohlížeč (Chrome, Mozilla) a čtečka souborů pdf (např. Adobe Acrobat)

2. A.Koubková, J.Pavelka : Úvod do teoretické informatiky, Matfyzpress 1999

3. Aho, Hopcroft, Ullman : The design and analysis of computer algorithms, Addison-Wesley 1976

4. T.Cormen, Ch.Leiserson, R. Rivest, C. Stein : Introduction to Algorithms (2nd Edition), McGraw-Hill 2001

5. L.Kučera : Kombinatorické algoritmy, SNTL Praha 1983

6. L.Kučera, J. Nešetřil : Algebraické metody diskretní matematiky, SNTL Praha 1989

7. M.Mareš, T.Valla : Průvodce labyrintem algoritmů, CZ.NIC z.s.p.o. Praha 2017, 978-80-88168-19-5, http://pruvodce.ucw.cz/

Sylabus -
Poslední úprava: Mgr. Jan Kynčl, Ph.D. (21.05.2018)

Toky v sítích: Rychlé implementace Ford-Fulkersonova algoritmu (algoritmy Dinitzův a 3 Indů) a Goldbergův algoritmus.

Aritmetické a algebraické algoritmy: sčítání binárních čísel (obecná metoda a implementace Kogge-Stone, Brent-Kung, Ladner-Fisher, Han-Carlson), Diskrétní Fourierova transformace (motivace a algoritmus FFT).

Geometrické algoritmy: konvexní obal a Voroného diagram (obojí v rovině)

Vyhledávání řetězců: Algoritmus Knuth-Morris-Pratt a jeho zobecnění Aho-Corasick.

Simplexový algoritmus lineárního programování.

Rozpis na jednotlivé lekce:

1. Toky v sítích - Dinitzův algoritmus

2. Toky v sítích - algoritmus 3 Indů

3. Toky v sítích - Goldbergův algoritmus

4. Sčítání binárních čísel (obecná metoda a implementace Kogge-Stone, Brent-Kung, Ladner-Fisher, Han-Carlson)

5. Motivace diskrétní Fourierovy transformace

6. Algoritmus rychlé Fourierovy transformace (FFT - Fast Fourier Transform)

7. Konvexní obal konečné množiny v rovině

8. Voroného diagram

9. Voroného diagram - pokračování

10. Vyhledávání řetězců - algoritmus Knuth-Morris-Pratt

11. Vyhledávání řetězců - algoritmus Aho-Corasick

12. Simplexový algoritmus lineárního programování

 
Univerzita Karlova | Informační systém UK