Paralelní algoritmy - NTIN017

• Anglický název: Parallel Algorithms
• Zajišťuje: Katedra softwaru a výuky informatiky (32-KSVI)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2024
• Semestr: letní
• E-Kredity: 3
• Rozsah, examinace: letní 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í
• Garant: RNDr. František Mráz, CSc.
• Třída: Informatika Mgr. - Teoretická informatika; Informatika Mgr. - Diskrétní modely a algoritmy
• Kategorizace předmětu: Informatika > Teoretická informatika

Anotace

čeština

Úvodní přednáška z paralelizmu věnovaná teoretickým modelům tzv. masivně paralelních výpočtů a jejich vztahu k sekvenčním modelům, základním technikám používaným v paralelních algoritmech a těžko paralelizovatelným úlohám. Předpokládají se znalosti v rozsahu bakalářského kursu NTIN061 Algoritmy a datové struktury II.

Poslední úprava: T_KSVI (30.04.2015)

angličtina

An introductory course on parallelism devoted to theoretical models of the so-called massively parallel computations and their relation to sequential computations, basic techniques used in parallel algorithm design and hard parallelisable problems.

Poslední úprava: T_KSVI (05.05.2004)

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

čeština

Prednáška Paralelné algoritmy nemá cvičenie, ale pre prehĺbenie znalostí absolventov bude doplnená o riešenie 3 úloh. Úlohy budú zadávané prostredníctvom systému Moodle. Každá úloha má stanovené dátum odovzdania. Riešenie sa dá do systému vkladať postupne a priebežne ho upravovať. Časom odovzdania je čas kliknutia na tlačítko "Odeslat řešení k oznámkování". Po kliknutí na toto tlačítko už riešenie nejde opravovať, ale je možné požiadať e-mailom učiteľa o vrátenie do stavu rozpracovania. Každá úloha bude učiteľom oznámkovaná pridelením 0-10 bodov. Za celý semester sa takto dá získať až 30 bodov. Body získané za celý semester budú skúšajúcím započítané do celkovej známky za predmet tak, že budú tvoriť 40% výsledného bodového hodnotenia, z ktorého bude odvodená známka pri skúške.

Typické riešenie úlohy sa skladá z textu – zápisu algoritmu, prípadne dôkazu. Texty odovzdávajte vo formáte PDF, prípadne RTF. Texty môžu býť v jazyku českom, slovenskom anebo anglickom. Mali by mať rozumnú úpravu. Za texty bez diakritiky prípadne iným spôsobom neprehľadné bude znižované ich bodové hodnotenie!

Upozornenie: V prípade zistenia, že N≥2 poslucháčov odovzdalo riešenia, ktoré se nápadne podobajú alebo sú úplne totožné, budú všetky tieto riešenia považované za jedno riešenie. Toto riešenie bude ohodnotené B bodmi podľa jeho kvality, ale každý z týchto N riešiteľov získa iba dolnú celú časť z B/N bodov.

Samotná skúška na konci semestru se započíta 60% do výsledného hodnotenia. Poslucháč získa známku na základe celkového hodnotenia podľa nasledujúcej tabuľky

známka 1	známka 2	známka 3	nevyhovel
100%–86%	85%–71%	70%–56%	ménej než 56%

Poslední úprava: Mráz František, RNDr., CSc. (19.02.2018)

angličtina

This course is taught in Czech/Slovak only. The requirements to complete the course can be found on the Czech site equivalent.

Poslední úprava: Mráz František, RNDr., CSc. (17.02.2020)

Literatura

čeština

I. Parberry: Parallel complexity theory, Pitman Publishing, 1987, (John Wiley & Sons)

A. Gibbons, W. Rytter: Efficient parallel algorithms, Cambridge University Press, 1988

J. JáJá: An introduction to parallel algorithms, Addison Wesley, 1992

Poslední úprava: Mráz František, RNDr., CSc. (30.04.2015)

Sylabus

čeština

Tato přednáška je úvodem do problematiky paralelních algoritmů pro tzv. masivně paralelní modely počítačů (počet procesorů je funkcí velikosti vstupu) se společnou pamětí.

1. Model paralelních strojů PRAM, měření složitosti paralelních výpočtů, paralelní teze.
2. Techniky paralelních algoritmů (balancované stromy, metoda rozděl a panuj, rozdělení úlohy, kaskádovité zrychlení).
3. Paralelní algoritmy pro grafové úlohy - Eulerova věž, určování souvislosti, hledání kostry, nejkratších cest.
4. Optimální třídící algoritmus, paralelní mergování (slévání), hledání nejmenšího prvku.
5. Dolní odhady složitosti pro paralelní algoritmy, výpočet funkce OR, sčítání.
6. Polylog-třídy složitosti, P-úplnost.

Poslední úprava: Mráz František, RNDr., CSc. (30.04.2015)

angličtina

This lecture is an introduction into parallel algorithms for the so-called massively parallel models of computers (the number of processors is a function of the input size) with shared memory.

1. Parallel RAM, complexity measures for parallel computations, parallel thesis.
2. Techniques of parallel algorithms (balanced binary trees, divide-and-conquer method, tasks splitting, cascade acceleration).
3. Parallel algorithms for graphs - Euler tour technique, connected components, minimal spanning tree, shortest paths.
4. Optimal parallel sorting, parallel merging, minimal element.
5. Lower bounds for parallel computations, computing OR, summation.
6. Polylog-complexity classes P-complete problems.

Poslední úprava: Mráz František, RNDr., CSc. (30.04.2015)