Cours : Analyse d'algorithmes

Cours 1

• Distance minimale dans le plan
• Analyse fonctions récursives
• Exercices : simples algorithmes
• Exercices : algorithmes "diviser pour regner"

Cours 2

• Notes de cours : programmation dynamique
• Notes de cours : distance de Levenshtein
• TD programmation dynamique
• Autres exemples

Cours 3

• Notes de cours : 3SUM et 3Collinear
• Notes de cours : Clique/EI/CouvertureParSommets

Cours 4

• Notes de cours : classes de complexité
• Exercices sur NP-completude

Cours 5

• Exercice sur TSP

TP 1

• Énoncé TP1
• Problème 1 :
  • Générateur d'entrées
  • Trame python
  • Trame java
  • Trame c++
  • Trame c#
• Problème 2 :
  • Trame programme
  • Générateur points
• Problème 3 :
  • Générateur parties
• Fichiers graphChronoGenerator :
  • Fichier graphChronoGenerator,py
  • Fichier testData.json
  • En cas où

TP 2

• Énoncé TP2 partie 1
• Générateur de graphes :
  • Générateur aléatoire de graphes
  • Version avec nombre d'arêtes fixées
  • Exemple de graphe sans 3coloration
  • Exemple de graphe avec 3coloration
  • Exemple de graphe de taille 24 avec 3coloration

TP 3

• Énoncé TP2 partie 2
• Template pour Clique
• Générateur aléatoire de cnf

Examen de l'année dernière

• Examen 2022