SubjectsSubjects(version: 806)
Course, academic year 2017/2018
   Login via CAS
Parallel Algorithms - NTIN017
Czech 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.
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 |