Rozšiřující seminář Algoritmy a datové struktury 1 - NTIN107

• Anglický název: Extension seminar Algorithms and Data Structures 1
• Zajišťuje: Katedra aplikované matematiky (32-KAM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2020
• Semestr: letní
• E-Kredity: 2
• Rozsah, examinace: letní 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í
• Garant: prof. RNDr. Luděk Kučera, DrSc.
• Vyučující: prof. RNDr. Luděk Kučera, DrSc.
• Třída: Informatika Bc.
• Kategorizace předmětu: Informatika > Teoretická informatika

Anotace

čeština

Předmět navazuje na NTIN060 Algoritmy a datové struktury I, algoritmy vyučované v rámci ADS I ukazuje pod jiným úhlem pohledu a přináší některé další a pokročilejší metody. Algoritmy jsou presentovány pomoci vizualizací, které jsou vytvářeny tak, aby názorně osvětlily základní myšlenky, na kterých jsou algoritmy založeny. 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 způsobem.

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

angličtina

The course is a continuation of NTIN060 Algorithms and Data Structures I; algorithms taught in ADS I are shown under a different point of view and other and more advanced methods are introduced. Algorithms are presented using visualizations that are created so that illustrate basic ideas on which the algorithms are based. 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.

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

Podmínky zakončení předmětu

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

Poslední úprava: Kučera Luděk, prof. RNDr., DrSc. (13.06.2019)

Literatura

čeština

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. Literatura doporučená pro ADS I

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

angličtina

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

2. Cormen, Leiserson, Rivest, Stein : Introduction to algorithms (2nd Edition), Mc Graw Hill 2001

3. 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/

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

Sylabus

čeština

Stromové datové struktury s vyhledáváním: binární vyhledávací stromy (BVS), vyvažované BVS (AVL-stromy a červeno-černé stromy), B-stromy

Haldy: Standardní halda, binomiální (slučovatelná) halda, Fibonacciova halda.

Standardní algoritmy pro třídění: bubblesort, mergesort, quicksort, heapsort.

Algoritmy související s tříděním: vyhledávání mediánu (a k-tého prvku); obvody pro třídění a přepínání: bitonický obvod.

Základní grafové algoritmy: vyhledávání v grafu a stromu (do hlouby, do šířky), nejkratší a extremální cesty (CPM, Dijkstra, Bellman-Ford), minimální kostry grafu (obecné schéma, implementace Jarník-Prim a Kruskal)

Rozpis na jednotlivé lekce:

1. Binární vyhledávací stromy.

2. AVL-stromy.

3. Červeno-černé stromy.

4. B-stromy.

5. Standardní halda a heapsort, binomická halda.

6. Fibonacciova halda.

7. Bubblesort, mergesort, quicksort, vyhledávání mediánu a k-tého prvku.

8. Bitonické třídění.

9. Vyhledávání v grafu.

10. Nejkratší a extremální cesty - CPM, Dijkstra.

11. Nejkratší a extremální cesty - Bellman-Ford.

12. Minimální kostry grafu (obecné schéma, implementace Jarník-Prim a Kruskal).

13. Spektrální heuristika pro min-cut.

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

angličtina

Tree data structures with the search operation: binary search trees (BST), balanced BST (AVL-trees and red-black trees), B-trees

Heaps: The standard heap, binomial (mergeable) heap, Fibonacci heap.

Standard sorting algorithms: bubblesort, mergesort, quicksort, heapsort.

Algorithms connected to sorting: median (and k-th element) search; sorting and switching networks: bitonic sorter.

Basic graph algorithms: graph and tree searching (depth and breadth search), shortest and extremal paths (CPM, Dijkstra, Bellman-Ford), minimum spanning tree (general scheme, Jarnik-Prim and Kruskal implementations), spectral heuristics for min-cut.

Detailed syllabus:

1. Binary search trees.

2. AVL-trees.

3. Red-black trees.

4. B-stromy.

5. Standard heap, binomial (mergeable) heap.

6. Fibonacci heap.

7. Bubblesort, mergesort, quicksort, median (and k-th element) search.

8. Bitonic sorter.

9. Graph and tree searching.

10. Shortest and extremal paths - CPM, Dijkstra.

11. Shortest and extremal paths - Bellman-Ford.

12. Minimum spanning tree (general scheme, Jarnik-Prim and Kruskal implementations).

13. Spectral heuristics for min-cut.

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