Learning outcomes

This course provides an introduction to various concepts related to algorithms and certain specificities linked to scientific computing, as well as practical application in a number of computer pool projects.
 

Goals

  • Know the basics of algorithm design and be able to analyse their complexity
  • Be able to implement different kinds of algorithms in C and Matlab languages
  • Be familiar with the various methods of numerical integration of differential equations
  • Be able to recognise problems of non-polynomial complexity
  • Devise heuristic or probabilistic algorithmic strategies
 

Content

The course will begin with a quick introduction to programming in the C language, as well as various advanced features of this language. The first practical exercices will be devoted to exploring this language.

The rest of the theory course will cover the following elements:

  • Algorithmic complexity: Characteristics of a good algorithm, Complexity classes, Complexity of recursive algorithms, Sorting algorithms
  • Algorithmic strategies: Data structures (stacks, queues, linked lists, search trees), Algorithmic strategies (greedy algorithms, divide and conquer, dynamic programming, backtracking, branch-and-bound)
  • Numerical integration algorithms: Euler, Runge-Kutta, step-adaptative methods, multi-step methods, predictor-corrector methods
  • Non-polynomial algorithms: Decision problems, Classes P, NP and NP-complete, proofs of NP-completeness
  • Probabilistic algorithms: Random algorithms, Monte Carlo and Las Vegas algorithms, Monte Carlo methods, MCMC methods, Monte Carlo Tree Search

Several important practical exercises, in C and Matlab, will be based on the content and examples of the theory course.

 

Assessment method

Details concerning the evaluation method are specified on the French language version of the descriptive sheet.

 

Sources, references and any support material

Syllabus available on Webcampus
 

Language of instruction

Français
Training Study programme Block Credits Mandatory
Bachelier en sciences mathématiques Standard 0 5
Bachelier en sciences mathématiques Standard 3 5