1.       

Course title

Parallel computing and algorithms

2.       

Year of study, study programme

3,

1-31 03 09 Computer Mathematics and Systems Analysis

3.       

Semester of study

5

4.       

Number of credits

3

5.       

Lecturer

Lavrova Olga Anatolievna

6.       

Course Objective

Formation of theoretical knowledge and practical skills for solving optimization problems and constructing parallel algorithms for these problems.

As a result of studying the student should be able to

–         construct extremal problems on sets of finite-dimensional spaces;

–         analyze convex sets, convex functions, problems of convex and linear programming;

–         solve optimization problems by means of parallel computing and algorithms.

7.       

Prerequisites

Computer Mathematics. Calculus. Programming Methods and Informatics. Optimization Methods. Numerical Methods

8.       

Course content

1.  Theory of convex sets. The separation theorem for the point and the convex set. The separation theorem for two convex sets. Simplicial cone. Caratheodory theorem. Polyhedral cone. Farkas’ lemma for linear inequalities.

2.  Criterion of optimality for the problems of convex programming. Criterion of optimality for a differentiable convex function on a convex set. Regular problems. Karush-Kuhn-Tucker conditions.  Criterion of optimality for non-differentiable functions.

3.  Classification of convex programming problems and discrete programming problems.

4.  Parallel algorithms. Principles of constructing parallel algorithms and improving known serial algorithms for multithreaded execution. Evaluation of the efficiency of algorithms in parallel and distributed computing environments. Optimization problems on graphs.

9.       

Recommended Literature

1.  Materials to the course «Einfürung in die Mathematische Optimierung», Prof. Kaibel, Otto-von-Guericke University, Magdeburg, Germany 2013/14: video-lectures in German, slides for lectures, homework tasks.

2.  R. T. Rockafellar, Convex Analysis. Princeton University Press, 1970.

3.  A. Ruszcynski, Nonlinear Optimization. Princeton University Press, 2006.

4.    A. Gramma, A. Gupta, G. Karypis, V. Kumar Introduction to Parallel Computing, Addison Wesley, 2003.

5.    Дорошенко А.Е Математические модели и методы организаций высокопроизводительных вычислений Киев: Наукова думка, 2000.

10.   

Teaching Methods

Lectures, laboratory classes

11.   

Teaching language

Russian, German

12.   

Requirements, current control

Control of the student’s work takes place in the form of interviews, tests and reports on laboratory works with their oral defense. Credits are held either orally or in writing.

13.   

Method of certification

Credit