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 I - NTIN107
Anglický název: Extension seminar Algorithms and Data Structures I
Zajišťuje: Katedra aplikované matematiky (32-KAM)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2018 do 2019
Semestr: letní
E-Kredity: 3
Rozsah, examinace: letní 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 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.
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. Literatura doporučená pro ADS I

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

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.

 
Univerzita Karlova | Informační systém UK