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 2024
• 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: nevyuč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

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

Poslední úprava: ()

angličtina

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

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

Literatura

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

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

Požadavky ke zkoušce

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

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

Sylabus

čeština

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

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

angličtina

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.

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