INFO704 : Analyse d'algorithmes : Différence entre versions

De Wiki du LAMA (UMR 5127)
Aller à : navigation, rechercher
(4 révisions intermédiaires par le même utilisateur non affichées)
Ligne 18 : Ligne 18 :
  
 
TP1 le 25 septembre : Analyser la complexité d'algorithmes
 
TP1 le 25 septembre : Analyser la complexité d'algorithmes
<!-- - [https://www.dropbox.com/l/scl/AAAtj6rrfWhzr8X-YdsiHSPi3LGJJxM1BnE Sujet du TP 1]
 
-->
 
 
  - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP_Analyse/tp1_enonce.pdf Sujet du TP 1]
 
  - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP_Analyse/tp1_enonce.pdf Sujet du TP 1]
 
Fichiers pour le TP :
 
Fichiers pour le TP :
Ligne 63 : Ligne 61 :
 
         print(A)
 
         print(A)
  
<!--
+
TP2 le 9 octobre : Problème NP-complet
  '''Seuls les deux premiers problèmes suffisent pour avoir la note maximale!!!'''
+
  Chaque groupe peut choisir un des trois sujets suivants
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP1/tp1_enonce.pdf Énoncé du TP]
+
  - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP2/tp-part-1_3C.pdf Énoncé pour le choix de problème 3-Coloration]
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP1/fichiersTP1 Fichiers relatifs au TP1]
+
  - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP2/tp-part-1_CHN.pdf Énoncé pour le choix de problème Chemin Hamiltonien non orienté]
-->
+
  - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP2/tp-part-1_CHO.pdf Énoncé pour le choix de problème Chemin Hamiltonien orienté]
  
TP2 le 9 octobre : Problème NP-complet
 
<!--
 
 
  - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/SurWiki Fichiers relatifs au TP2]
 
  - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/SurWiki Fichiers relatifs au TP2]
-->
+
 
  
 
<!---  
 
<!---  
Ligne 138 : Ligne 134 :
  
 
TD 3 (23 septembre) : Algorithmes récursifs (Diviser-pour-régner)
 
TD 3 (23 septembre) : Algorithmes récursifs (Diviser-pour-régner)
  - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S5TD/exos.pdf Exercice algorithmes récursifs]  
+
  - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S5TD/exo_div_pour_regner.pdf Exercice algorithmes récursifs]  
 
  - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S5TD/Solution-TD_operationsEntiers.pdf Correction des derniers exos de la feuille de TD.]
 
  - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S5TD/Solution-TD_operationsEntiers.pdf Correction des derniers exos de la feuille de TD.]
 
<!--  
 
<!--  
Ligne 159 : Ligne 155 :
  
 
TD 4 (30 septembre) : Programmation dynamique
 
TD 4 (30 septembre) : Programmation dynamique
 +
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S7TD/TD-prog_dynamique.pdf Énoncé de TD.]
 
  - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S8Cours/Levenshtein.pdf Correction sur la distance de Levenshtein.]
 
  - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S8Cours/Levenshtein.pdf Correction sur la distance de Levenshtein.]
  
 
Cours 4 (1 octobre) : Complexité des problèmes
 
Cours 4 (1 octobre) : Complexité des problèmes
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S8Cours/Levenshtein.pdf Correction sur la distance de Levenshtein.]
 
 
  - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S8Cours/presentation1.0.pdf Introduction aux classes de complexité.]
 
  - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S8Cours/presentation1.0.pdf Introduction aux classes de complexité.]
 
<!-- - Complexité d'un problème.
 
<!-- - Complexité d'un problème.

Version du 9 octobre 2019 à 07:47

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

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

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.