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.

 

Teaching methods

Part of the lecture is given on the blackboard, with some computer science examples.

Programming work in a computer pool (C and Matlab).

Please note: due to continuous assessment, attendance at the computer pool programming exercises is compulsory!

 

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

French
Training Study programme Block Credits Mandatory
Bachelor in Mathematics Standard 0 5
Bachelor in Mathematics Standard 3 5