Cours 2017-2018

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, véritables outils de "mathématiques expérimentales". Le fil conducteur du cours est constitué par les trois vertus de tout bon algorithme: 1) donner une réponse correcte (validité) 2) sa concision ou son élégance et 3) son efficacité en termes de rapidité d'exécution. 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) - Méthodes explicites et implicites, problèmes raides - Méthodes à un pas et multi-pas 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, algorithmes combinatoires, etc.) IV) Algorithmes heuristiques et non-polynomiaux - Stratégies algorithmiques (algorithmes gloutons, stratégie diviser pour régner, programmation dynamique, backtracking, branch-and-bound) - Intelligence artificielle en théorie des jeux (arbres min-max, élagage alpha-bêta, fonctions d'évaluation) - Introduction aux problèmes NP-complets

Description des exercices

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

Disciplines

Théorie de la décision et des jeux
Programmation du calcul numérique
Programmation et méthodes de simulation
Théorie des algorithmes

Pré-requis

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

  1. Equations différentielles [SMATB222] et Algèbre linéaire II [SMATB240] et Projet de programmation [SINFB206]
  2. Equations différentielles [SMATB222] et Algèbre linéaire II [SMATB240] et Compléments de programmation [SINFB207]

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). Cette note finale peut être ajustée positivement afin de refléter l'impression générale donnée par l'étudiant. En cas d'échec modéré à l'une de ces activités d'apprentissage (note d'au moins 7/20), les deux examens oral et pratique seront 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