PředmětyPředměty(verze: 845)
Předmět, akademický rok 2018/2019
   Přihlásit přes CAS
Třídění - NTIN058
Anglický název: Sorting
Zajišťuje: Katedra distribuovaných a spolehlivých systémů (32-KDSS)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2014
Semestr: zimní
E-Kredity: 3
Rozsah, examinace: zimní s.:2/0 Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: čeština
Způsob výuky: prezenční
Další informace: http://d3s.mff.cuni.cz/teaching/ntin058
Garant: RNDr. Alena Koubková, CSc.
Třída: Informatika Mgr. - volitelný
Kategorizace předmětu: Informatika > Teoretická informatika
Anotace -
Poslední úprava: ()
Přehled známých i méně známých třídicích algoritmů a jejich analýza. Algoritmy pro sekvenční a paralelní třídění, třídění souborů v interní paměti, externí třídění.
Literatura
Poslední úprava: RNDr. Alena Koubková, CSc. (27.04.2005)

Akl, S. G.: Parallel sorting algorithms. Academic Press, 1985.

Knuth, D. E.: The art of computer programming. Sorting and searching. Addison-Wesley, 1973.

Sedgewick, R.: Algorithms in C. Addison-Wesley, 1998 (česky SoftPress, 2003).

Požadavky ke zkoušce
Poslední úprava: RNDr. Alena Koubková, CSc. (10.10.2017)

Zkouška má pouze ústní část. Požadavky odpovídají sylabu přednášky.

Sylabus -
Poslední úprava: RNDr. Alena Koubková, CSc. (28.04.2005)

Sekvenční algoritmy pro vnitřní třídění. Algoritmy založené na porovnávání, přihrádkové třídění, odhady složitosti. Přehled známých třídicích algoritmů (bubblesort, insertsort, quicksort, mergesort, ...) a jejich modifikace. Méně známé třídicí algoritmy (Shellsort, shakersort, hybridsort, ...).

Paralelní třídění. Paralelní modely výpočtu, míry složitosti paralelních algoritmů. Speciální paralelní architektury pro třídění (třídicí sítě). Třídění na víceúčelových paralelních strojích s různými způsoby propojení procesorů (lineární propojení, stromy, ..., sdílená paměť). Synchronní a asynchronní třídění.

Externí třídění souborů uložených na páskách a na discích. Míry složitosti externího třídění.

 
Univerzita Karlova | Informační systém UK