« INFO003 C1 : 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
 
(18 versions intermédiaires par le même utilisateur non affichées)
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]
<li> [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S1Cours/grandO.pdf Grand-O de la notation de Landau]
<li> [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S1Cours/grandO.pdf Grand-O de la notation de Landau]
<li> [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S2TD/rappelsLog.pdf Fonctions mathématiques de base : polynômes, #exponentielles et logarithmes]
<li> [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S2TD/rappelsLog.pdf Fonctions mathématiques de base : polynômes, exponentielles et logarithmes]
</ul>
</ul>




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>
<li> [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S4TD/exos_diviser_pour_regner.pdf Exercices sur la complexité des fonctions récursives] <br>
<li> [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S4TD/exos_diviser_pour_regner.pdf Exercices sur la complexité des fonctions récursives] <br>
<li> [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/correctionQ4.pdf Correction de l'exercice 4] <br>
<li> [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/correctionQ4.pdf Correction de l'exercice 4] <br>
<li> [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S3Cours/distance_min.pdf distance minimale]
<li> [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/distance_min.pdf distance minimale]
</ul>
</ul>




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://ufile.io/mpb9nyfs levenshtein.py]
<li> [https://ufile.io/yynjjdlp animaux]
</ul>
</ul>

<h3>Problème de livraison par drones :</h3>
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/Courrier_par_drones/tp.pdf Ancien sujet de TP] <br>
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/Courrier_par_drones/solveTSP.py algorithmes] <br>
Exemples d'entrées :
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/Courrier_par_drones/Cities10 Taille 10],
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/Courrier_par_drones/Cities15 Taille 15],
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/Courrier_par_drones/Cities20 Taille 20],
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/Courrier_par_drones/Cities100 Taille 100]


<h3>Autour de la NP-complétude</h3>
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/ClassesComplexite/ClassesComplexite.pdf Notes sur les classes P et NP]<br>
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/ClassesComplexite/ExerciceNPcompletude.pdf Exercices sur la NP-complétude]<br>
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/ClassesComplexite/examen2020.pdf Examen du cours donné en 2020]


<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>

<h5>Fichiers pour le problème 1</h5>
<ul>
<li> Trame (en fonction de votre langage) : [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/TP1/Pb1/votreAlgo.cpp c++],
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/TP1/Pb1/votreAlgo.py python],
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/TP1/Pb1/votreAlgo.java java],
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/TP1/Pb1/votreAlgo.cs c#]
<li> [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/TP1/Pb1/genererNombres.py Générateur d'entrées]
</ul>
<h5>Fichiers pour le problème 2</h5>
<ul>
<li> Générateur d'entrées : [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/TP1/Pb2/genererPoints.py Générateur d'entrées]
<li> Exemple d'entrée : [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/TP1/Pb2/pointsListe_25 Exemple de taille 25]
</ul>
<h5>Fichiers pour le problème 3</h5>
<ul>
<li> Générateur d'entrées : [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/TP1/Pb3/genererPartie.py Générateur d'entrées]
<li> Exemple d'entrée : [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/TP1/Pb3/partie_10 Exemple de taille 10],
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/TP1/Pb3/partie_23 Exemple de taille 23],
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/TP1/Pb3/partie_100 Exemple de taille 100]
</ul>


<h3>TP2 : </h3>
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/TP2/tp-part-1.pdf Énoncé partie 1] <br>
Un générateur d'entrées ainsi que des entrées toutes faites sont données : <br>
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/TP2/generator.py generator.py], <br>
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/TP2/3C_vrai.txt 3C_vrai.txt],
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/TP2/3C_vrai20.txt 3C_vrai20.txt],
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/TP2/3C_vrai25.txt 3C_vrai25.txt],
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/TP2/3C_faux20.txt 3C_faux20.txt]. <br>
<br>
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/TP2/tp-part-2.pdf Énoncé partie 2] <br>
Des templates pour l'utilisation des SAT-solvers <b>Picosat</b> et <b>Pycosat</b> sont donnés: <br>
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/TP2/solveClique.cpp Template pour c++],
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/TP2/solveClique.py Template pour Python]




<!--
<!--

Dernière version du 16 novembre 2022 à 09:58

Responsable 2022 : Sébastien Tavenas
Adresse courriel : sebastien.tavenas@univ-smb.fr


Quelques ressources introductives :


Des ressources sur la complexité d'un algorithme récursif :


Programmation dynamique :

Problème de livraison par drones :

Ancien sujet de TP
algorithmes
Exemples d'entrées : Taille 10, Taille 15, Taille 20, Taille 100


Autour de la NP-complétude

Notes sur les classes P et NP
Exercices sur la NP-complétude
Examen du cours donné en 2020


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
Fichiers pour le problème 2
Fichiers pour le problème 3


TP2 :

Énoncé partie 1
Un générateur d'entrées ainsi que des entrées toutes faites sont données :
generator.py,
3C_vrai.txt, 3C_vrai20.txt, 3C_vrai25.txt, 3C_faux20.txt.

Énoncé partie 2
Des templates pour l'utilisation des SAT-solvers Picosat et Pycosat sont donnés:
Template pour c++, Template pour Python




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