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

• Exercices : programmation dynamique
• Distance de Levenshtein
• Attribution de skis
• Fichiers pour problème attributions skis :
  • Trame python algorithme récursif
  • Générateur de listes de skis et skieurs

Cours 3

• Problème du voyageur de commerce

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é
• Exercices sur la NP-complétude

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 (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