Contenu de l'AA

En plus d'une introduction, le cours est structuré en 4 parties distinctes:

Partie 0) Introduction

- Présentation du cours (plan/structure, références, etc.) et de ses objectifs
- Modalités du cours et organisation

Partie 1) Théorie des Graphes, Algorithmique et Combinatoire

- Rappel des notions et définitions de base
- Représentation des graphes : matrices d'adjacence et d'incidence
- Accessibilité  
- Chaînes et chemins, Cycles et circuits
- Distances 
- Flots
- Couplages 
- Arbres couvrants et arbres de plus courts chemins 
- Coloration
- Elements de combinatoire énumérative

Partie 2) Analyse d'algorithmes

- Complexité des algorithmes (en temps et en espace)
- Comparaison asymptotique de fonctions

Partie 3) Méthodes mathématiques pour l'informatique

- Logique mathématique : logique propositionnelle et logique des prédicats
- Raisonnement mathématique : déduction, induction, récurrence, etc. 
- Algèbre linéaire
- Théorie des matrices et calcul matriciel

Partie 4) Optimisation mathématique

- Modélisation et formulation de programmes mathématiques
- Programmation linéaire: méthodes du simplexe et du simplexe dual
- Problèmes: transport, flot maximum, flots de coût minimum, sac à dos
- Programmation linéaire en nombres entiers: méthode arborescente

Supports principaux non reproductibles

Sans objet

Support complémentaires non reproductibles

Sans objet

Autres références conseillées

Les références (par parties) du cours sont fournies lors de la première séance et mise à disposition sur le site Moodle du cours.

Mode d'enseignement

• En présentiel

Types d'activités

• Cours magistraux
• Travaux pratiques
• Projet sur ordinateur

Evaluations

Les modalités d'évaluation de l'AA sont précisées dans la fiche de l'UE dont elle dépend