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 [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
• Způsob výuky: prezenční
• 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

čeština

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í.

angličtina

Poslední úprava: RNDr. Filip Zavoral, Ph.D. (03.04.2001)

A survey on sorting algorithms and their analysis. Sequential and parallel sorting algorithms, internal and external sorting.

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

čeština

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í.

angličtina

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

Sequential algorithms for internal sorting. Algorithms based on comparisons, bucket sorting, estimates of their complexity. A survey on well-known sorting algorithms (Bubblesort, Insertionsort, Quicksort, Mergesort,...) and their modifications. Some little-known sorting algorithms.

Parallel sorting. Parallel models of computation, measures of complexity of parallel algorithms. Special parallel architectures for sorting (sorting networks). Sorting on multi-purpose parallel machines with various types of processor interconnection ( linear, tree, ...), shared memory computers. Synchronous and asynchronous sorting.

Sorting of external files on tapes and discs. Complexity measures for external sorting.