INFO704 : Analyse d'algorithmes

Responsable 2019: Sébastien Tavenas

Adresse couriel : sebastien.tavenas@univ-smb.fr

Quelques ressources bibliographiques

Ouvrage de référence :

1. Cormen, Leiserson, Rivest et Stein, Algorithmique, 3e edition (2009). ( Aussi appelé "Introduction à l'algorithmique" pour les deux premières éditions )

Autres références bibliographiques :

1. Wilf, Algorithms and Complexity, (1994). Disponible en ligne
2. Garey et Johnson, Computers and intractability a guide to the theory of NP-completeness. (1979).
3. Hopcroft et Ullman, Introduction to automata theory, languages, and computation, (1979).

TP

TP1 le 25 septembre : Analyser la complexité d'algorithmes

- Sujet du TP 1

Fichiers pour le TP :

- Fichiers pour GraphChrono
- Fichiers pour Problème 2
- Fichiers pour Problème 3

- Pour le problème 1, si vous voulez pouvoir ouvrir des fichiers externes vous pouvez ajouter cette partie dans votre programme et utiliser le générateur pour le Problème 2 (pour ceux sous windows, le plus simple est sûrement de générer vos entrées directement à l'intérieur de votre programme)

   import sys
   filename = sys.argv[1]
   tab = []
   with open(filename, "r") as file:
       for line in file:
           tab.append( 1)

- Pour obtenir un graphe sous windows

   rajouter 'print(commands)' à la fin de fonction buildGnuPlotCommands
   Copier les lignes depuis 'set xlabel ... replot'
   Et les copier dans un émulateur en ligne de gnuplot comme http://gnuplot.respawned.com :
      Les insérer dans 'Plot script' à la place de ce qu'il y a après 'set output 'out.svg'

- Pour le Problème 2 pour générer des couples de coordonnées aléatoires directement dans python:

       import random
       A= []
       for i in range(input):
           A.append((random.randint(0,input),random.randint(0,input)))
       print(A)

- Pour le Problème 2 pour générer des couples de points aléatoires directement dans python:

       import random
       A= []
       for i in range(input):
           A.append(Point(random.randint(0,input),random.randint(0,input)))
       print(A)

TP2 le 9 octobre : Problème NP-complet

Chaque groupe peut choisir un des trois sujets suivants
 - Énoncé pour le choix de problème 3-Coloration
 - Énoncé pour le choix de problème Chemin Hamiltonien non orienté
 - Énoncé pour le choix de problème Chemin Hamiltonien orienté

- Fichiers relatifs au TP2

TP3 le 18 octobre : Réductions polynomiales

- Documents pour les réductions :
  * Avro Chapitre 10
  * Cormen-Leiserson-Rivest-Stein Coloration
  * Cormen-Leiserson-Rivest-Stein HNO(Attention la figure 34.16 est incorrecte. La remplacer par la figure 34.16 de la Version anglaise)
  * Hon HO Version francaise
  * Garey-Johnson HNO
  * wiki proof
- Voici des exemples d'entrée pour 3SAT et Couverture par Sommets :
  * 3SAT-vrai
  * CS-vrai
  * 3SAT-faux
  * CS-faux

Déroulement (2019-2020)

Cours 1 (9 septembre) : Introduction

- Introduction
- Exemple de différents tris 
- Notions d'instance et de problème
- Notion de complexité asymptotique

TD 1 (13 septembre) : Rappels de mathématiques

- Sujet du TD
- Grand-O de la notation de Landau
- Fonctions mathématiques de base : polynômes, exponentielles et logarithmes
- Correction des questions 1 et 2 du TD

TD2 (16 septembre) : Analyse des algorithmes

- Sujet du TD
- Complexité d'éléments basiques : instructions, tests, boucles Pour et TantQue
- Cas des algorithmes récursifs.
- Analyse des algorithmes

Cours 2 (18 septembre) : Algorithmes récursifs (Diviser pour régner)

- Présentation des algorithmes Diviser-pour-régner.
- Théorème général.
- distance minimale

TD 3 (23 septembre) : Algorithmes récursifs (Diviser-pour-régner)

- Exercice algorithmes récursifs 
- Correction des derniers exos de la feuille de TD.

Cours 3 (30 septembre) : Programmation dynamique.

TD 4 (30 septembre) : Programmation dynamique

- Énoncé de TD.
- Correction sur la distance de Levenshtein.

Cours 4 (1 octobre) : Complexité des problèmes

- Introduction aux classes de complexité.

Cours 5 (7 octobre) : Réductions de NP-complétude

TD 5 (15 octobre) : NP-complétude

- Énoncé du TD

Annales Examen

Examen 2017

Historique

Ce cours était donné précédemment par Xavier Provençal. Ce cours est une refonte de INFO724 Algorithmique avancée, graphes et NP-complétude.