Cours 2018-2019

Algorithmique mathématique pour le calcul scientifique [SMATB306]

  • 4 crédits
  • 22.5h+37.5h
  • 1er quadrimestre
Langue d'enseignement: Français

Acquis d'apprentissage

Ce cours se veut une introduction aux algorithmes mathématiques, qui sont des outils importants du calcul scientifique. Le cours aborde ainsi les bases du calcul en virgule flottante, les approximations dans le calcul différentiel numérique et la complexité algorithmique.

Contenu

Le cours se décompose en quatre parties principales. I) Arithmétique en virgule flottante - Représentation machine des entiers, réels, systèmes de précision machine dans la norme IEEE et procédures d'arrondis - Exemples des erreurs d'arrondis dans les algorithmes de calcul du nombre pi 
II) Algorithmes de calcul différentiel - Les différences finies - Erreur numérique : entre erreur d'arrondi et erreur de troncature - Intégration numérique d'équations différentielles ordinaires (problème de Cauchy, ou problème aux valeurs initiales) III) Complexité des algorithmes séquentiels déterministes - Estimation du nombre d'opérations élémentaires - Caractérisation de la complexité algorithmique - Récursivité - Echelle de complexité algorithmique et exemples (algorithmes arithmétiques, de tri, transformée de Fourier discrète et rapide, etc.) IV) Stratégies algorithmiques (algorithmes gloutons, stratégie diviser pour régner, backtracking, branch-and-bound) - Intelligence artificielle en théorie des jeux

Description des exercices

Travaux pratiques sur ordinateur : conceptions et implémentations d'algorithmes mathématiques en Matlab et/ou en C.

Disciplines

Théorie des algorithmes
Programmation du calcul numérique
Programmation et méthodes de simulation

Pré-requis

Les unités d’enseignement d’une des propositions suivantes:

  1. Projet de programmation [SINFB206]
  2. Compléments de programmation [SINFB207]

Co-requis

Equations différentielles [SMATB222] et Algèbre linéaire II [SMATB240]

Méthodes d'enseignement

Le cours théorique se donne au tableau avec de nombreux exemples pratiques d'algorithmes de mathématiques appliquées, abordés sous l'ange pratique en discutant les résultats d'une implémentation réelle. Le cours est accompagné par de nombreux travaux pratiques de programmation (en C et/ou en Matlab) qui reprennent les thèmes et exemples vus au cours.

Mode d'évaluation

L'examen comporte deux parties : un examen pratique et un examen oral. Ces deux parties sont considérées comme des activités d'apprentissage distinctes d'une même unité d'enseignement. L'examen pratique est constitué de petits exercices de programmation à réaliser directement sur ordinateur et de l'interprétation des résultats obtenus. En ce qui concerne l'examen oral, les questions portent sur la théorie, à la fois sur des questions de présentation de la matière ou de démonstration, ainsi que sur la capacité de l'étudiant à concevoir une stratégie algorithmique à partir d'un problème donné. La note finale est au minimum la moyenne arithmétique (arrondie vers le bas) des notes de l'examen oral et de l'examen pratique, à condition que ces deux activités d'apprentissage soient réussies séparément (notes d'au moins 10/20). En cas d'échec modéré à l'une de ces activités d'apprentissage (note d'au moins 7/20), les deux examens sont considérés conjointement au niveau de leur contenu afin de déterminer si l'étudiant a acquis suffisamment de connaissances et de compétences que pour justifier une réussite globale pour l'unité d'enseignement, la moyenne arithmétique n'étant plus un critère suffisant de réussite dans ce cas. Une note strictement inférieure à 7/20 à l'une de ces activités d'apprentissage entrainera automatiquement une note d'échec pour l'unité d'enseignement.

Sources, références et supports éventuels

A. Quarteroni, R. Sacco, F. Saleri, "Méthodes Numériques, Algorithmes, analyse et applications", Springer 2007. J. C. Butcher, "Numerical Methods for Ordinary Differential Equations", Wiley, 2003. M.L. Overton, "Numerical Computing with IEEE Floating Point Arithmetic", SIAM, 2001.

Langue d'enseignement

Français

Lieu de l'activité

NAMUR

Faculté organisatrice

Faculté des sciences
Rue de Bruxelles, 61
5000 NAMUR

Cycle

Etudes de 1er cycle