Cours : Analyse d'algorithmes

Cours 1

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

Cours 2

Cours 3

• Notes programmation dynamique (à lire en premier)
• Notes sur la distance de Levenshtein
• Sources pour le problème Fibonacci
• Sources pour le problème de la distance de Levenshtein

Cours 4

• Note réduction 3SUM et 3ALIGNES
• Problèmes : Clique - Ensembles indépendants - Couverture par Sommets

Cours 5

• Notes sur les classes de complexité

TP 1

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

TP 2

• Énoncé TP2
• 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
• Template pour les objets graphes
• Template pour un fichier utilisant l'objet précédent
• Solver pour Clique à base de Pycosat
• Générateur aléatoire de cnf (avec 0 à la fin de la ligne)
• Générateur aléatoire de cnf (sans 0 à la fin de la ligne)

Examen de l'année dernière

• Sujet de l'année dernière