Algorithmique et mathématiques discrètes

Algorithmique

De nombreux problèmes pratiques peuvent être modélisés à l'aide de graphes, et leur résolution nécessite des algorithmes de graphes. Ce cours explore les algorithmes pour les problèmes les plus classiques, tels que les parcours de graphes, le plus court chemin, les arbres couvrants de poids minimum, et le flot maximum. 

Mathématiques discrètes

L'objectif de ce cours est de se familiariser avec les notions de base des mathématiques discrètes qui sont pertinentes pour l'informatique. Après ce cours, l'étudiant sera capable de :

• expliquer et formuler les définitions par récurrence et les preuves par récurrence ;
• appliquer les principes combinatoires aux problèmes de dénombrement ;
• expliquer, formuler, et appliquer les concepts de base de la théorie des graphes, en particulier la connexité, l'acyclicité, les graphes planaires et bipartis ;
• expliquer, formuler, et appliquer les concepts de base de la théorie des probabilités, en particulier les probabilités discretes, les variables aléatoires, l'indépendance, et l'espérance ;
• donner des explications de haut niveau sur les concepts et les raisonnements mathématiques.

Algorithmique

Sujets centraux

1. Introduction
   • Graphes : définitions de base
   • Représentation matricielle et par listes
   • Lemme de la poignée de main
   • Connexité
   • Arbres
   • Rappels sur la complexité algorithmique, notation grand O, Ω et Θ
2. Parcours de graphes
   • Parcours en largeur (BFS)
   • Parcours en profondeur (DFS)
   • Graphes orientés acycliques (DAG)
   • Tri topologique
   • Composantes fortement connexes
3. Plus court chemin
   • Algorithme de Dijkstra
   • Algorithme de Bellman–Ford
   • Algorithme de Floyd–Warshall
   • Algorithme de Johnson
4. Arbres couvrants de poids minimum
   • Algorithme de Kruskal
   • Implementation de l'algorithme de Kruskal avec la structure de données union-find
   • Algorithme de Prim
   • Implementation de l'algorithme de Prim avec les files de priorité
5. Flot max, coupe min
   • Algorithme de Ford–Fulkerson
   • Algorithme de Edmonds–Karp
   • Couplages dans les graphes bipartis : théorèmes de König et de Hall
6. Algorithme d'approximation
   • Algorithme d'approximation pour vertex cover
   • Graphes eulériens, algorithme de Hierholzer
   • Problème du voyageur de commerce (TSP) : algorithme de Christofides

Sujets potentiellement traités

1. - Coloration
   • Algorithme glouton de coloration
   • Graphes d'intervalles

Mathématiques discrètes

Sujets centraux

• Définitions et preuves par récurrence
• Dénombrements et notions de graphes
• Connexité, acyclicité, arbres
• Graphes planaires, formule d'Euler
• Probabilités discrètes
• Variables aléatoires, indépendance, espérance