SubjectsSubjects(version: 821)
Course, academic year 2017/2018
   Login via CAS
Parallel Algorithms - NTIN017
English title: Paralelní algoritmy
Guaranteed by: Department of Software and Computer Science Education (32-KSVI)
Faculty: Faculty of Mathematics and Physics
Actual: from 2011
Semester: summer
E-Credits: 3
Hours per week, examination: summer s.:2/0 Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: Czech
Teaching methods: full-time
Guarantor: RNDr. František Mráz, CSc.
Class: Informatika Mgr. - Teoretická informatika
Informatika Mgr. - Diskrétní modely a algoritmy
Classification: Informatics > Theoretical Computer Science
Annotation -
Last update: T_KSVI (05.05.2004)

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.
Course completion requirements - Czech
Last update: RNDr. František Mráz, CSc. (19.02.2018)

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%

Literature -
Last update: RNDr. František Mráz, CSc. (30.04.2015)

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

Syllabus -
Last update: RNDr. František Mráz, CSc. (30.04.2015)

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.

 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html