UE I6-A - Algorithmique et mathématiques 2

Les automates finis permettent de modéliser des programmes informatiques à mémoire finie. Ils permettent de résoudre des problèmes à un niveau d'abstraction élevé, sans s'encombrer des spécificités d'un langage donné, et en se concentrant sur les invariants à maintenir pour parvenir à une solution. L'étude de ce modèle s'inscrit dans le cadre général de la théorie des langages abordée ensuite dans les modules IF203 (compilation) et IF228 (calculabilité et complexité). L'enseignement aborde des notions théoriques (automates finis, langages réguliers, expressions régulières, équivalence de ces trois formalismes, non-déterminisme, automate minimal, lemme de l'étoile) ainsi que leur utilisation pour la résolution de problèmes concrets.

Voir la page complète

Après une brève introduction des graphes, ce cours présente des problèmes sur les graphes admettant une solution algorithmique efficace. L'étude de ces solutions sera l'occasion d'exhiber des propriétés classiques en Théorie des Graphes.

Introduction

Exemples de problèmes
Définitions générales
Chemins et arbres


Problèmes de parcours

Une solution gloutonne pour l'arbre couvrant minimal
Parcours en largeur
Le problème du plus court chemin
Parcours en profondeur


Autres problèmes

Le problème du flot maximal
Le problème du couplage maximum

Voir la page complète

La programmation linéaire et et sa version avec des variables entières sont de puissants outils pour la modélisation et la résolution de problèmes d'optimisation combinatoire. Ce cours a pour objectif d'introduire la modélisation mathématique sous forme de programmes linéaires et de programmes linéaires en nombres entiers, ainsi que les méthodes algorithmiques utilisées pour résoudre ces modèles à l'aide de l'algorithme du simplex et des méthodes de branch-and-bound dédiées.

Voir la page complète

Le module d'Algorithmique Numérique décrit un ensemble de méthodes et d'algorithmes adaptés à la modélisation de problèmes numériques.

Introduction au calcul numérique : problèmes de représentation des nombres et d'approximaiotn, conditionnement
Méthodes de résolution de systèmes linéaires : Gauss Cholesky A=LDL' méthodes itératives : Jacobi Gauss-Seidel relaxation gradient
Méthode des moindres carrés : équation normale factorisations de matrices
Valeurs propres et vecteurs propres : réduction à la forme tridiagonale bissection de Givens méthode de la puissance itérée
Résolution d'équations non linéaires : méthodes itératives racines de polynômes cas de la dimension supérieure à 1
Méthodes numériques d'interpolation et d'intégration.
Equations différentielles : Problème de Cauchy méthode de Runge-Kutta différences finies éléments finis

Voir la page complète