Rozšiřující seminář Algoritmy a datové struktury 2 - NTIN108

• Anglický název: Extension seminar Algorithms and Data Structures 2
• Zajišťuje: Katedra aplikované matematiky (32-KAM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2020
• Semestr: zimní
• E-Kredity: 2
• Rozsah, examinace: zimní s.:0/2, Z [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: čeština, angličtina
• Způsob výuky: prezenční
• 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

čeština

Poslední úprava: doc. 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.

angličtina

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

The course is a continuation of NTIN061 Algorithms and Data Structures II; algorithms taught in ADS II are shown under a different point of view and the course is directed to a detailed illustration of underlzing algorithmic ideas. Algorithms are presented using visualizations that are created so that the ideas are presented visually and algorithm invariants are visualized. The goal is to present algorithms as a creative part of the computer science and to teach students to think about the behavior and properties of algorithms in an exact way.

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 [e-mail] - 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

čeština

Poslední úprava: doc. 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/

angličtina

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

1. Visualizations are available at www.algovision.org, a web browser (Chrome, Mozilla) and pdf reader (e.g., Adobe Acrobat) suffice

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

čeština

Poslední úprava: doc. 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í

angličtina

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

Network flows: Fast implementations of Ford-Fulkerson algorithm (Dinitz a 3 Indiens) a Goldberg algorithm.

Arithmetic a algebraic algorithms: binary number addition (general method a implementations Kogge-Stone, Brent-Kung, Ladner-Fisher, Han-Carlson), Discrete Fourier transform (motivation and FFT algorithm).

Geometric algorithms: convex hull and Voronoi diagram (both in the plane)

String matching: Algorithm Knuth-Morris-Pratt and its generalization Aho-Corasick.

Simplex algorithm of linear programmming.

Detailed syllabus

1. Network flows - Dinitz algorithm.

2. Network flows - 3 Indien algorithm.

3. Network flows - Goldberg algorithm.

4. Binary number addition (general method a implementations Kogge-Stone, Brent-Kung, Ladner-Fisher, Han-Carlson).

5. Discrete Fourier transform - motivation.

6. Discrete Fourier transform - FFT algorithm.

7. Convex hull of a finite subset of the plane.

8. Voronoi diagram in the plane.

9. Voronoi diagram in the plane - cont'd.

10 String matching: Algorithm Knuth-Morris-Pratt.

11.String matching: Algorithm Aho-Corasick.

12. Simplex algorithm of linear programmming.