SubjectsSubjects(version: 942)
Course, academic year 2023/2024
   Login via CAS
Parallel Algorithms - NTIN017
Title: Paralelní algoritmy
Guaranteed by: Department of Software and Computer Science Education (32-KSVI)
Faculty: Faculty of Mathematics and Physics
Actual: from 2023
Semester: summer
E-Credits: 3
Hours per week, examination: summer s.:2/0, Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
4EU+: no
Virtual mobility / capacity: no
State of the course: taught
Language: Czech
Teaching methods: full-time
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 -
Last update: RNDr. František Mráz, CSc. (17.02.2020)

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

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 |