« INFO003 C1 : Analyse d'algorithmes » : différence entre les versions
Aller à la navigation
Aller à la recherche
Aucun résumé des modifications |
Aucun résumé des modifications |
||
| Ligne 3 : | Ligne 3 : | ||
Quelques ressources introductives : |
<h3>Quelques ressources introductives : </h3> |
||
<ul> |
<ul> |
||
<li> [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S1Cours/CM1.pdf Introduction] |
<li> [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S1Cours/CM1.pdf Introduction] |
||
| Ligne 11 : | Ligne 11 : | ||
Des ressources sur la complexité d'un algorithme récursif : |
<h3>Des ressources sur la complexité d'un algorithme récursif :</h3> |
||
<ul> |
<ul> |
||
<li> [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S3Cours/fct_rec.pdf Théorème général] <br> |
<li> [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S3Cours/fct_rec.pdf Théorème général] <br> |
||
| Ligne 20 : | Ligne 20 : | ||
Programmation dynamique: |
<h3>Programmation dynamique :</h3> |
||
<ul> |
<ul> |
||
<li> [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/decoupe_barre.py Programme de découpe de barres] |
<li> [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/decoupe_barre.py Programme de découpe de barres] |
||
<li> [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/Levenshtein.py Levenshtein] (vous pouvez utiliser le fichier [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/animaux animaux] comme dictionnaire |
<li> [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/Levenshtein.py Levenshtein] (vous pouvez utiliser le fichier [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/animaux animaux] comme dictionnaire) |
||
</ul> |
</ul> |
||
<h3>TP1 : </h3> |
|||
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/TP1/tp1_enonce.pdf Énoncé] <br> |
|||
Vous pouvez (conseillé) utiliser les outils suivants : <br> |
|||
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/TP1/graphChronoGenerator.py graphChronoGenerator.py] et [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/TP1/parametresGraphChronoGenerator.json parametresGraphChronoGenerator.json] <br> |
|||
Les fichiers précédents permettent de de ne pas mesurer le temps de génération des entrées et seulement le temps de calcul, mais en cas de soucis, vous pouvez utiliser ces (petites) variations : <br> |
|||
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/TP1/graphChrono.py graphChrono.py] et [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/TP1/parametresGraphChrono.json parametresGraphChrono.json] <br> |
|||
<h4>Fichiers pour le problème 1</h4 |
|||
<!-- |
<!-- |
||
Version du 13 octobre 2022 à 10:33
Responsable 2022 : Sébastien Tavenas
Adresse courriel : sebastien.tavenas@univ-smb.fr
Quelques ressources introductives :
- Introduction
- Grand-O de la notation de Landau
- Fonctions mathématiques de base : polynômes, #exponentielles et logarithmes
Des ressources sur la complexité d'un algorithme récursif :
- Théorème général
- Exercices sur la complexité des fonctions récursives
- Correction de l'exercice 4
- distance minimale
Programmation dynamique :
- Programme de découpe de barres
- Levenshtein (vous pouvez utiliser le fichier animaux comme dictionnaire)
TP1 :
Énoncé
Vous pouvez (conseillé) utiliser les outils suivants :
graphChronoGenerator.py et parametresGraphChronoGenerator.json
Les fichiers précédents permettent de de ne pas mesurer le temps de génération des entrées et seulement le temps de calcul, mais en cas de soucis, vous pouvez utiliser ces (petites) variations :
graphChrono.py et parametresGraphChrono.json