« INFO704 : Analyse d'algorithmes » : différence entre les versions

De Wiki du LAMA (UMR 5127)
Aller à la navigation Aller à la recherche
Aucun résumé des modifications
Aucun résumé des modifications
Ligne 24 : Ligne 24 :
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP1/tp1_enonce.pdf Sujet du TP 1]
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP1/tp1_enonce.pdf Sujet du TP 1]
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP1/fichiersTP1/ Fichiers pour le TP]
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP1/fichiersTP1/ Fichiers pour le TP]
- Nécessité d'importer la librairie Matplotlib



<!--
<!--


- 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
TP2 le 9 octobre : Problème NP-complet
Chaque groupe peut choisir un des trois sujets suivants
Chaque groupe peut choisir un des trois sujets suivants
Ligne 95 : Ligne 70 :
Cours 1 (7 septembre) : Introduction
Cours 1 (7 septembre) : Introduction
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S1Cours/CM1.pdf Introduction]
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S1Cours/CM1.pdf Introduction]
- Exemple de différents tris
- Exemple de différents tris <!-- [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO704/tri.tgz Programme C/gtk pour illustrer différents algorithmes de tri].-->
- Notions d'instance et de problème
- Notions d'instance et de problème
- Notion de complexité asymptotique
- Notion de complexité asymptotique
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S2TD/grandO.pdf Grand-O de la notation de Landau]
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S1Cours/grandO.pdf Grand-O de la notation de Landau]
<!-- - Encodage d'une instance
- Feuille de rappels : logarithme [https://mycore.core-cloud.net/index.php/s/yjRYKWTIvp6VXgy Logarithme.pdf], ordres de grandeur [https://mycore.core-cloud.net/index.php/s/EDOsgVW03uaTrVH Grand-O.pdf] et correction partielle [https://mycore.core-cloud.net/index.php/s/IJVyy3hokrZIMSw Correction.pdf].
-->




TD 1 (10 septembre) :
TD 1 (10 septembre) : Analyses d'algorithmes
Analyses d'algorithmes
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S2TD/ExoAnalyse.pdf Sujet du TD]
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S2TD/ExoAnalyse.pdf Sujet du TD]
<!-- - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S2TD/Correction_exercices_2et3.pdf Correction des questions 1 et 2 du TD] -->
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S2TD/rappelsLog.pdf Fonctions mathématiques de base : polynômes, exponentielles et logarithmes]
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S2TD/rappelsLog.pdf Fonctions mathématiques de base : polynômes, exponentielles et logarithmes]


Ligne 114 : Ligne 84 :
Algorithmes récursifs (Diviser pour régner)
Algorithmes récursifs (Diviser pour régner)
- Présentation des algorithmes Diviser-pour-régner.
- Présentation des algorithmes Diviser-pour-régner.
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S4Cours/fct_rec.pdf Théorème général.]
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S3Cours/fct_rec.pdf Théorème général.]
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S4Cours/distance_min.pdf distance minimale]
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S3Cours/distance_min.pdf distance minimale]


⚫
<!--
⚫
Programmation dynamique.
⚫
!-- - Problème de la distance minimum dans un nuage de points. [https://mycore.core-cloud.net/index.php/s/fh9C1oJ4HymuJI0 Distance]
- Problème du rendu de monnaie. [https://mycore.core-cloud.net/index.php/s/taOj7Moq8gDy9vz Rendu monnaie]
!-- - Complexité en cas moyen.
- Complexité d'un algorithme probabiliste.
- Solutions aux exercices du cours précédent : [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/solutionsDPR/dmin.cpp dmin.cpp] [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/solutionsDPR/multGrandsEntiers.cpp multGrandsEntiers.cpp] [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/solutionsDPR/sommeMax.cpp sommeMax.cpp]
⚫
- Distance de Levenshtein [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/Levenshtein.py Levenshtein.py] [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/animaux Petite banque de mots].
- Devoir "Impression équilibrée"
- [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/impression_eq.py Code à compléter (Python 2).]
- [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/impression_eq-python3.py Code à compléter (Python 3).]
-->


TD 2 (29 septembre) : Exercices d'analyse pour des algos récursifs ("Master Theorem")
TD 2 (29 septembre) : Exercices d'analyse pour des algos récursifs ("Master Theorem")
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S2TD/exos_diviser_pour_regner.pdf Exercices, complexité des fonctions récursives].
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S4TD/exos_diviser_pour_regner.pdf Exercices, complexité des fonctions récursives].
<!-- - [https://www.csd.uwo.ca/~mmorenom/CS424/Ressources/master.pdf Pour s'entraîner, exercices supplémentaires sur l'application du "Théorème maître" (sur la page de Marc Moreno Maza, MIT)]. -->
<!-- - [https://www.csd.uwo.ca/~mmorenom/CS424/Ressources/master.pdf Pour s'entraîner, exercices supplémentaires sur l'application du "Théorème maître" (sur la page de Marc Moreno Maza, MIT)]. -->
<!-- Complexité des problèmes
<!-- Complexité des problèmes
Ligne 146 : Ligne 104 :
Cours 3 (2 octobre) :
Cours 3 (2 octobre) :
<!--
<!--
⚫
Programmation dynamique.
Analyse des algorithmes
⚫
- Problème du rendu de monnaie. [https://mycore.core-cloud.net/index.php/s/taOj7Moq8gDy9vz Rendu monnaie]
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S3TD/ExoAnalyse.pdf Sujet du TD]
⚫
- Distance de Levenshtein [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/Levenshtein.py Levenshtein.py] [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/animaux Petite banque de mots].
- Complexité d'éléments basiques : instructions, tests, boucles Pour et TantQue
- Cas des algorithmes récursifs.
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S3TD/BasesAnalyse.pdf Analyse des algorithmes]
!-- - Retour sur la feuille de rappels et exo "Analyse d'algorithmes, les bases".
- Tests empiriques de la complexité des fonctions récursives : [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/graphChrono.tgz Script pour fabriquer une courbes des temps de calcul (utilise gnuplot)].
- [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/fct_rec.pdf Théorèmes relatifs à la complexité temporelle des fonctions récursives].
- [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/distance_min.pdf Problème du calcul de la distance minimum entre deux points].
-->
-->


TD 3 (5 octobre) :
TD 3 (5 octobre) :
⚫
<!--
<!-- Algorithmes récursifs (Diviser-pour-régner)
- [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.]
!--
- Comparaison d'approches naïves VS diviser-pour régner (théorie et implémentation).
!-- - Problème du sous-tableau de somme maximale. --
!-- - Problème du sous-tableau de somme maximale. --
- Problème de la multiplication de grands entiers.
-- - [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/graphChrono.tgz Deuxième version du script graphChrono.py pour fabriquer une courbes des temps de calcul (utilise gnuplot)].
-->
-->


Version du 1 octobre 2020 à 14:25

Responsable 2020: 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

Dates provisoires : 

- 22/25 septembre
- 9 octobre
- 16 octobre


TP1 les 22/25 septembre : Analyser la complexité d'algorithmes 

- Sujet du TP 1
- Fichiers pour le TP
- Nécessité d'importer la librairie Matplotlib


Déroulement (2020)

Cours 1 (7 septembre) : Introduction 

- Introduction
- Exemple de différents tris 
- Notions d'instance et de problème
- Notion de complexité asymptotique
- Grand-O de la notation de Landau


TD 1 (10 septembre) : Analyses d'algorithmes 

- Sujet du TD
- Fonctions mathématiques de base : polynômes, exponentielles et logarithmes


Cours 2 (17 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 2 (29 septembre) : Exercices d'analyse pour des algos récursifs ("Master Theorem") 

- Exercices, complexité des fonctions récursives.


Cours 3 (2 octobre) :

TD 3 (5 octobre) :

Cours 4 (13 octobre) :

TD 4 (14 octobre) :

Cours 5 (23 octobre, matin) :

TD 5 (23 octobre, après-midi) :

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.

Récupérée de « http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=INFO704_:_Analyse_d%27algorithmes&oldid=12589 »