|
|
|
||
Last update: doc. Mgr. Jan Kynčl, Ph.D. (21.05.2018)
|
|
||
Last update: 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 |
|
||
Last update: 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/ |
|
||
Last update: 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. |