« 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 25 : | Ligne 25 : | ||
<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>Problème de livraison par drones :</h3> |
|||
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/Courriers_par_drones/tp.pdf Ancien sujet de TP] <br> |
|||
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/Courriers_par_drones/solveTSP.py algorithmes] <br> |
|||
Exemples d'entrées : |
|||
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/Courriers_par_drones/Cities10 Taille 10] <br> |
|||
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/Courriers_par_drones/Cities15 Taille 15] <br> |
|||
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/Courriers_par_drones/Cities20 Taille 20] <br> |
|||
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/Courriers_par_drones/Cities100 Taille 100] <br> |
|||
Version du 14 octobre 2022 à 05:38
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)
Problème de livraison par drones :
Ancien sujet de TP
algorithmes
Exemples d'entrées :
Taille 10
Taille 15
Taille 20
Taille 100
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
Fichiers pour le problème 1
- Trame (en fonction de votre langage) : c++, python, java, c#
- Générateur d'entrées
Fichiers pour le problème 2
- Générateur d'entrées : Générateur d'entrées
- Exemple d'entrée : Exemple de taille 25
Fichiers pour le problème 3
- Générateur d'entrées : Générateur d'entrées
- Exemple d'entrée : Exemple de taille 10, Exemple de taille 23, Exemple de taille 100