http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?action=history&feed=atom&title=Analyse_d%27algorithmesAnalyse d'algorithmes - Historique des versions2026-05-21T08:42:03ZHistorique des versions pour cette page sur le wikiMediaWiki 1.39.4http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=Analyse_d%27algorithmes&diff=14304&oldid=prevStave le 10 octobre 2022 à 11:202022-10-10T11:20:30Z<p></p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="fr">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Version précédente</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Version du 10 octobre 2022 à 11:20</td>
</tr><tr>
<td colspan="2" class="diff-lineno">Ligne 1 :</td>
<td colspan="2" class="diff-lineno">Ligne 1 :</td>
</tr>
<tr>
<td class="diff-marker" data-marker="−"></td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Responsable <del style="font-weight: bold; text-decoration: none;">2021</del>: Sébastien Tavenas <br></div></td>
<td class="diff-marker" data-marker="+"></td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Responsable <ins style="font-weight: bold; text-decoration: none;">2022 </ins>: Sébastien Tavenas <br></div></td>
</tr>
<tr>
<td class="diff-marker"></td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Adresse courriel : sebastien.tavenas@univ-smb.fr</div></td>
<td class="diff-marker"></td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Adresse courriel : sebastien.tavenas@univ-smb.fr</div></td>
</tr>
<tr>
<td class="diff-marker"></td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td>
<td class="diff-marker"></td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td>
</tr>
<tr>
<td colspan="2" class="diff-lineno">Ligne 111 :</td>
<td colspan="2" class="diff-lineno">Ligne 111 :</td>
</tr>
<tr>
<td class="diff-marker"></td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> 1 4 10 3 5 </div></td>
<td class="diff-marker"></td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> 1 4 10 3 5 </div></td>
</tr>
<tr>
<td class="diff-marker"></td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Partant de la ville V1, on peut aller à la ville V2 et faire le plein (coût 4), puis aller à la ville V4, refaire le plein (coût 3) et on a assez pour arriver à la ville V5. Le coût optimal est donc de 7.</div></td>
<td class="diff-marker"></td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Partant de la ville V1, on peut aller à la ville V2 et faire le plein (coût 4), puis aller à la ville V4, refaire le plein (coût 3) et on a assez pour arriver à la ville V5. Le coût optimal est donc de 7.</div></td>
</tr>
<tr>
<td class="diff-marker" data-marker="−"></td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;"><!</del>--En améliorant l'algorithme, on doit pouvoir trouver un algorithme fonctionnant en \(O(n\log n)\). --<del style="font-weight: bold; text-decoration: none;">></del></div></td>
<td class="diff-marker" data-marker="+"></td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>--En améliorant l'algorithme, on doit pouvoir trouver un algorithme fonctionnant en \(O(n\log n)\). --</div></td>
</tr>
<tr>
<td class="diff-marker"></td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td>
<td class="diff-marker"></td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td>
</tr>
<tr>
<td class="diff-marker"></td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td>
<td class="diff-marker"></td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td>
</tr>
</table>Stavehttp://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=Analyse_d%27algorithmes&diff=14303&oldid=prevStave : Page créée avec « Responsable 2021: Sébastien Tavenas <br> Adresse courriel : sebastien.tavenas@univ-smb.fr <!-- == TP == Énoncé du TP : [https://www.lama.univ-savoie.fr/pagesmembres/t... »2022-10-10T11:19:17Z<p>Page créée avec « Responsable 2021: Sébastien Tavenas <br> Adresse courriel : sebastien.tavenas@univ-smb.fr <!-- == TP == Énoncé du TP : [https://www.lama.univ-savoie.fr/pagesmembres/t... »</p>
<p><b>Nouvelle page</b></p><div>Responsable 2021: Sébastien Tavenas <br><br />
Adresse courriel : sebastien.tavenas@univ-smb.fr<br />
<br />
<!--<br />
<br />
== TP ==<br />
Énoncé du TP :<br />
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/tp.pdf Énoncé]<br />
<br />
Des instances d'entrées peuvent être trouvées à :<br />
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/Cities10 Cities10],<br />
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/Cities15 Cities15],<br />
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/Cities20 Cities20],<br />
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/Cities100 Cities100]<br />
et un générateur :<br />
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/generator_cities.cpp generator_cities.cpp].<br />
<br />
Les solutions exactes aux premières instances sont :<br />
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/Solution10 Solution10],<br />
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/Solution15 Solution15],<br />
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/Solution20 Solution20].<br />
Attention, pour le programmes de la partie 1 et 3, c'est normal si vous obtenez des résultats un peu plus grands (je vous rappelle que ces programmes ne calculent que des approximations du résultat, mais devraient être plus rapide à tourner).<br />
<br />
Le programme [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/minCouplage.cpp minCouplage.cpp] que vous pouvez utiliser pour la phase 3 de l'algorithme de la section 3.<br />
<br />
<br />
== Problèmes (thème de la programmation dynamique) ==<br />
<br />
Templates pour utiliser des fichiers plutôt que l'entrée standard et la sortie standard :<br />
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/templateWithFiles.cpp Templates .cpp for files], [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/templateWithFiles.py Templates .py for files]<br />
<br />
Problème 1 :<br />
- Il y a N produits à acheter, chacun ayant un certain prix. Vous avez une somme E d'euros à votre disposition. Le but est d'obtenir le nombre maximum d'objets possible.<br />
- Entrée : La première ligne indique le nombre de tests à réaliser. Chaque test commence par une ligne avec les valeurs N et E. La ligne suivante contient N entiers: la liste des prix des N produits.<br />
- Sortie : Le nombre de produits que l'on peut obtenir à chaque test.<br />
- Taille maximale des paramètres : N,E < 10^5.<br />
- Fichiers de tests : [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/Pb1/small_input small_input], [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/Pb1/test100 test100], [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/Pb1/test100000 test100000], [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/Pb1/solution_small_input solution_small_input], [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/Pb1/solution101 solution100]<br />
- Exemples de solutions : [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/Pb1/gain.py Code python], [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/Pb1/gain.cpp Code c++]<br />
Exemple d'un test. Sur l'entrée :<br />
5 10<br />
2 7 4 3 6<br />
On a assez d'argent pour acheter les produits 1, 3 et 4. On ne peut pas acheter 4 produits. Donc la réponse attendue est 3.<br />
<br />
<br />
<br />
Problème 2 :<br />
- Une échelle à H barreaux. Lorsqu'on se trouve sur un barreau, on peut soit monter au barreau juste au-dessus, soit sauter le prochain barreau pour aller deux crans au-dessus (nos jambes ne sont pas assez longues pour sauter deux barreaux d'un coup). On veut savoir combien il y a de façons d'aller sur le dernier barreau (sans jamais redescendre). <br>Comme ce nombre grossit très vite, on demandera juste le résultat modulo 123456789.<br />
- Entrée : La première ligne indique le nombre de tests à réaliser. Chaque test consiste en 1 ligne qui contient un entier H correspondant au nombre de barreaux de l'échelle. <br />
- Sortie : Le nombre de montées possibles pour chaque test (modulo 123456789).<br />
- Taille maximale des paramètres : H < 10^8.<br />
- Fichiers de tests : [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/Pb2/inputs inputs]<br />
- Exemples de solutions : [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/Pb2/code.py Code python], [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/Pb2/code.cpp Code c++]<br />
Exemple d'un test. Sur l'entrée :<br />
2<br />
On peut soit monter les deux barreaux d'un coup (en sautant le premier barreaux), soit monter d'abord sur le premier barreau et ensuite sur le second. Donc la réponse attendue est 2. <br />
<br />
<br />
<br />
Problème 3 :<br />
- Devant vous, il y a N distributeurs. Chacun contient une pile de M objets. Quand vous mettez 1 euro dans un distributeur, le premier objet (le plus bas) de cette pile tombe et vous l'obtenez (donc si vous souhaitez un objet particulier, il va falloir prendre tous les objets au-dessous). Chaque objet a une certaine valeur. Le but est de maximiser la valeur obtenue avec une certaine somme d'euros E initiale.<br />
- Entrée : La première ligne indique le nombre de tests à réaliser. Chaque test commence par une ligne avec les valeurs N, M et E. Ensuite on trouve N nouvelles lignes : chacune correspond à un distributeur. Sur ces lignes, on trouve les M valeurs des objets dans ce distributeur (la première valeur correspond au premier objet qui va tomber).<br />
- Sortie : La valeur maximale que l'on peut obtenir à chaque test.<br />
- Taille maximale des paramètres : valeurs des objets < 100, M < 100, N < 100.<br />
- Fichiers de tests : [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/Pb3/small_input small_input], [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/Pb3/dataDistrib10 dataDistrib10], [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/Pb3/dataDistrib50 dataDistrib50], [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/Pb3/dataDistrib100 dataDistrib100]<br />
- Exemples de solutions : [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/Pb3/algoDistrib.py Code python], [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Cours_M2/Pb3/algoDistrib.cpp Code c++]<br />
Exemple d'un test. Sur l'entrée :<br />
2 4 5<br />
2 1 10 3<br />
9 5 1 7<br />
Avec 5 euros, on peut acheter les 3 premiers objets du premier distributeur (de valeurs 2, 1 et 10) et les deux premiers du deuxième distributeur de valeurs 9 et 5). Ce qui fait une valeur totale de 27. On ne peut pas obtenir plus. Donc la réponse attendue est 27.<br />
<br />
<br />
<br />
Problème 4 :<br />
- Vous vivez dans un quartier de New-York. La carte du quartier correspond à une grille (à coordonnées entières). Vous habitez en position (0,0) de cette grille (au sud-ouest) et vous travaillez en position (X,Y) (au nord-est). Pour changer, chaque matin, vous essayer d'aller au travail avec un nouveau chemin (mais vous avez seulement le temps de prendre un chemin rapide : à tout moment, vous devez vous déplacer soit vers l'est, soit vers le nord.). Vous aimeriez connaitre le nombre de chemins possibles. Toutefois il y a un soucis, certaines routes sont bloquées. <br>Ce nombre grossissant vite, on s'intéressera au résultat modulo 123456789.<br />
- Entrée : La première ligne indique le nombre de tests à réaliser. Chaque test commence par une ligne avec les valeurs X,Y et B (le nombre de blocages dans le quartier). Ensuite on trouve B nouvelles lignes : chacune correspond à un blocage et est de la forme : 'a b d' où a et b sont des nombres et d (la direction du blocage) est soit 'h' (horizontal), soit 'v' (vertical). Par exemple, un blocage : '3 5 h' signifie que depuis la position (3,5), la route qui va vers l'est est bloquée.<br />
- Sortie : Le nombre de chemins à chaque test.<br />
- Taille maximale des paramètres : X < 10000, Y < 10000.<br />
- Fichiers de tests : [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/Pb4/small_input small_input], [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/Pb4/quartier10 quartier10], [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/Pb4/quartier100 quartier100], [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/Pb4/quartier1000 quartier1000], [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/Pb4/quartier10000 quartier10000]<br />
- Solutions : [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/Pb4/solution10 solution10], [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/Pb4/solution100 solution100], [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/Pb4/solution1000 solution1000], [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/Pb4/solution10000 solution10000]<br />
Exemple d'un test. Sur l'entrée :<br />
2 2 2<br />
1 0 'v'<br />
1 1 'v'<br />
On peut vérifier que tous les chemins possibles sont HHVV, VHHV et VVHH (où H correspond à un pas horizontal et V à un pas vertical). Donc la réponse attendue est 3.<br />
<br />
<br />
<br />
Problème 5 :<br />
- Il y a D dés, chacun avec F faces. Nous voulons calculer la probabilité d'obtenir la somme S quand les dés sont lancés. en fait, il suffit de compter combien de fois la somme S peut être obtenue. Par exemple, avec 2 dés de 4 faces, il y a 3 façons d'obtenir la somme 6 : (2,4), (3,3) et (4,2). <br>Ce nombre grossissant vite, on s'intéressera au résultat modulo 123456789.<br />
- Entrée : La première ligne indique le nombre de tests à réaliser. Chaque test correspond à une ligne où apparaissent trois entiers D, F et S.<br />
- Sortie : Le nombre de façons d'obtenir S à chaque test.<br />
- Taille maximale des paramètres : D < 1000, F < 1000, S < 500000.<br />
- Fichiers de tests :[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/Pb5/dataDices10 dataDices10], [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/Pb5/dataDices100 dataDices100], [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/Pb5/dataDices1000 dataDices1000], [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/Pb5/dataDices10000 dataDices10000]<br />
- Solution :[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/Pb5/solution10 solution10], [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/Pb5/solution100 solution100], [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/Pb5/solution1000 solution1000]<br />
- Template : [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/Pb5/TemplateDices Template]<br />
- Générateur : [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/generator_dices.cpp generatorDices]<br />
Exemple d'un test. Sur l'entrée :<br />
2 4 6<br />
Comme expliqué dans l'énoncé, la réponse attendue est 3.<br />
<br />
<br />
<br />
Problème 6 :<br />
- Un camion doit acheminer sa cargaison depuis la ville V1 vers la ville Vn. Lors de ce voyage, il traverse les villes V1, V2, V3, ..., Vn. À son départ, le camion a le réservoir plein : il contient m gallons d'essence. Pour aller d'une ville à la suivante le camion utilise un gallon d'essence. Toutefois, dans chacune des villes Vi, le camion peut faire le plein en payant un prix Ci (si Ci =0, cela signifie que la ville Vi ne possède pas de station d'essence et donc qu'il n'est pas possible de faire le plein ici). Donnés le nombre de villes n, la taille du réservoir m et le prix du plein dans chacune des villes tabPrix, trouver un algorithme qui identifie le coût minimal d'un tel voyage.<br />
- Entrée : La première ligne indique le nombre de tests à réaliser. Chaque test consiste en 2 lignes. La première contient deux entiers n et m correspondant au nombre de villes et à la capacité du réservoir. La seconde ligne contient n entiers correspondant aux prix du plein dans chaque ville.<br />
- Sortie : Le prix minimal à payer lors de chaque test.<br />
- Taille maximale des paramètres : n < 1000000, m < 10000, C < 100<br />
Exemple d'un test. Sur l'entrée :<br />
5 2<br />
1 4 10 3 5 <br />
Partant de la ville V1, on peut aller à la ville V2 et faire le plein (coût 4), puis aller à la ville V4, refaire le plein (coût 3) et on a assez pour arriver à la ville V5. Le coût optimal est donc de 7.<br />
<!--En améliorant l'algorithme, on doit pouvoir trouver un algorithme fonctionnant en \(O(n\log n)\). --><br />
<br />
<br />
<br />
Problème 7 :<br />
- Une suite de nombres est appelée en zig-zag si la différence entre les paires successives de nombres alterne entre positive et négative. Une suite avec au plus deux éléments est trivialement toujours en zig-zag. Par exemple, 1, 7, 4, 9, 2, 5 est une suite en zig-zag car les différences (6,-3,5,-7,3) alternent. Par opposition, les suites 1,4,7,2,5 et 1,7,4,5,5 ne sont pas en zig-zag. Donnée une suite d'entiers, le but est de trouver la longueur de la plus longue sous-suite qui est en zig-zag.<br />
- Entrée : La première ligne indique le nombre de tests à réaliser. Chaque test consiste en 2 lignes. La première contient un entier N correspondant à la taille de la suite. La seconde ligne contient N entiers correspondant aux valeurs de la suite.<br />
- Sortie : La longueur de la plus grande sous-suite en zig-zag pour chaque test.<br />
- Taille maximale des paramètres : valeurs des objets < 100, M < 40, N < 50.<br />
Exemple d'un test. Sur l'entrée :<br />
10<br />
1, 17, 5, 10, 13, 15, 10, 5, 16, 8<br />
Il y a plusieurs sous-suites en zig-zag de longueur 7, par exemple 1,17,10,13,10,16,8. Aucune n'a longueur 8. Donc la réponse attendue est 7. <br />
<br />
<br />
<br />
== Problèmes (thème des graphes) ==<br />
<br />
Template pour les graphes : [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/TemplateGraph.cpp Template]<br />
<br />
Générateurs : [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/generator_maze.cpp generator_maze], [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/plot_maze.cpp plot_maze]<br />
<br />
Problème Labyrinthe :<br />
- Donné un labyrinthe, on aimerait savoir s'il existe un chemin vers la sortie. Le chemin sera basé sur une grille. Entre deux cases adjacentes, on pourra se déplacer s'il n'y a pas de mur entre.<br />
- Entrée : La première ligne indique le nombre de tests à réaliser. Chaque test commence par une ligne avec deux entiers L et H. Le premier est la largeur et le second la hauteur du labyrinthe. Ensuite viennent H lignes (la première correspond au nord). Chacune contient L caractères (le premier caractère correspond au point le plus à l'ouest de cette ligne). Le caractère 'E', signifie que depuis ce point on peut aller à l'est mais qu'il y a un mur en direction du sud, 'S', signifie que l'on peut aller au sud mais pas à l'est, 'N' (None) signifie que l'on peut aller ni au sud, ni à l'est et enfin 'B' (Both) signifie que l'on peut aller au sud et à l'est. (S'il n'y a pas de mur, on peut bien sûr aussi aller à l'ouest ou au nord).<br />
- Sortie : Pour chaque test, dire s'il y a un chemin depuis l'entrée (au nord-ouest) vers la sortie (au sud-est).<br />
- Taille maximale des paramètres : L < 1000, H < 1000.<br />
- Hint : DFS (voire A*)<br />
<br />
Problème Labyrinthe II :<br />
- Ce coup-ci est organisée une course de labyrinthes. Donc non seulement, on aimerait trouver un chemin vers la sortie, mais on voudrait que ce chemin soit le plus court !<br />
- Entrée : Identique au problème précédent.<br />
- Sortie : Pour chaque test, donner la longueur du plus court chemin depuis l'entrée (au nord-ouest) vers la sortie (au sud-est).<br />
- Taille maximale des paramètres : L < 1000, H < 1000.<br />
- Hint : BFS<br />
<br />
Problème Labyrinthe III :<br />
- Après avoir beaucoup participé à des expéditions de labyrinthes, nous voilà passés passés de l'autre côté de l'organisation. On voudrait donc créer de superbes labyrinthes. Et on est un peu difficile, on veut que les labyrinthes que l'on fabrique aient un et exactement un chemin qui mène du départ à l'arrivée. Pouvez-vous coder un tel algorithme pour nous aider ?<br />
- Entrée : La première ligne indique le nombre de tests à réaliser. Chaque test consiste en 1 ligne contenant deux entiers L et H (largeur et hauteur du labyrinthe à fabriquer). <br />
- Taille maximale des paramètres : L < 1000, H < 1000.<br />
- Hint : Kruskal<br />
<br />
Réseau téléphonique : <br />
- Dans une compagnie de téléphone, les lignes ont une certaine bande-passante (BW). Nous voulons router les appels téléphoniques via le chemin avec bande-passante maximale. La bande-passante d'un chemin est donnée par sa liaison la plus faible (BW(path) = min_(e in path)(BW(e) ). <br />
- Entrée : La première ligne indique le nombre de tests à réaliser. Chaque test commence par une ligne avec les valeurs V et E (les nombres de sommets et de liaisons). Ensuite on trouve E nouvelles lignes : chacune correspond à une arête (non-orientée) et est de la forme : 'a b w' où a et b sont des sommets (0 <= a,b < V) et w est la bande passante de cette liaison.<br />
- Sortie : Pour chaque test donner le chemin avec bande-passante maximale.<br />
- Taille maximale des paramètres : V < 100000, E < 1000000, BW < 1000. <br />
- Hint : Dijkstra<br />
<br />
<br />
Problème Livraison :<br />
- Nous venons de monter une entreprise de skis eléctriques au Bourget-du-Lac, et on aimerait exporter nos produits dans un certain nombres de villes V (par exemple V = [Bourget, Tokyo, Grenoble, Mexico, Brest, Sydney]). On fait affaire avec un prestataire de livraison qui a dans son catalogue un certain nombre de liaisons qu'il est capable de faire (par exemple L = [Mexico -> Sydney, Tokyo-> Mexico, Mexico -> Grenoble, Brest -> Grenoble]). On aimerait s'occuper du nombre minimal de liaisons à rajouter pour pouvoir être capable de livrer dans toutes les villes.<br />
- Entrée : La première ligne indique le nombre de tests à réaliser. Chaque test commence par une ligne avec les valeurs n et l (les nombres de villes et de liaisons déjà existantes). Sur la ligne suivante, on trouve la liste des n villes. Enfin on trouve l nouvelles lignes : chacune correspond à une liaison effectuée par le prestataire (orientée) et est de la forme : 'a -> b' où a et b sont deux villes.<br />
- Sortie : Pour chaque test donner le nombre minimal de liaisons à rajouter pour pouvoir livrer toutes les villes.<br />
- Taille maximale des paramètres : n < 100000, E < 1000000.<br />
- Hint : Tarjan, Kosaraju<br />
<br />
<br />
<br />
== Analyse amortie ==<br />
<br />
<br />
=== Tas binaires vs. Tas binomiaux vs. Tas de Fibonacci ===<br />
<br />
Donner pour chacune de ces structures la complexité (amortie si c'est le cas) des différentes opérations :<br />
- ajouter un élément<br />
- trouver le plus petit élément<br />
- supprimer le plus petit élément<br />
- modifier la valeur d'une entrée<br />
- supprimer un élément<br />
- fusionner deux tas<br />
<br />
<br />
<br />
=== Union-Find ===<br />
<br />
- Problème de connexité. On cherche une structure qui permet de savoir si deux points dans un graphe sont connexes et qui garde 'conserve' les résultats de manière à pouvoir répondre à une longue suite de telles questions de connexité. <br />
- Abstraction. On veut identifier (petit à petit, après requêtes) les classes d'équivalence dans l’ensemble {0, 1, 2, . . . , n−1}. Opérations supportées :<br />
- find(x) retourne un représentant de la classe de x (chaque classe a un unique représentant). find(x) = find(y) si et seulement si les deux appartiennent dans la même classe (ils sont connexes),<br />
- union(x, y) établit l’équivalence (connexion) entre x et y<br />
- Exemple : union(3, 4); union(4, 9); union(8, 0); union(2, 3); union(7, 4); union(6, 4); union(5, 0); find(2); find(6)<br />
<br />
<br />
Donner la complexité des deux opérations ('union' et 'find') dans les quatre structures suivantes :<br />
- On stocke dans un tableau T de taille n : T[x] est le représentant de x.<br />
- Lors de l'union de u avec v, on stocke dans v un pointeur vers u.<br />
- Lors de l'union de u et de v, on dirige la plus petite classe vers l'autre. Plus précisément, on garde en mémoire la taille des classes, et si la classe de u est plus petite que v, on pointe u vers v, sinon on pointe v vers u.<br />
- Identique à la précédente mais avec compression de chemin : quand on cherche un représentant, on redirige tous les sommets parcourus directement vers le représentant.<br />
<br />
=== Si vous vous ennuyez ===<br />
<br />
Coder une structure de donnée qui encode un ensemble d'entiers et qui supporte les deux opérations suivantes :<br />
- Ajout(i) : Ajoute un élément i dans la structure.<br />
- SuppressionMoitSup() : Supprime les n//2 plus grands entiers de la structure où n est le nombre d'entiers dans la structure.<br />
<br />
Le but est d'obtenir une structure pour laquelle les deux opérations ci-dessus sont en temps amorti constant (supposant qu'on parte de la structure vide.)<br />
<br />
----<br />
<br />
<br />
<br />
== Programmation linéaire ==<br />
Exemples de programmes utilisant MIP de Python :<br />
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/SacAdos.py SacAdos.py]<br />
[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/Materiel_online/dames.py dames.py]<br />
<br />
<br />
<br />
--><br />
<br />
<br />
<!--<br />
#== Quelques ressources bibliographiques ==<br />
#<br />
#Ouvrage de référence :<br />
## Cormen, Leiserson, Rivest et Stein, Algorithmique, 3e edition (2009). ( Aussi appelé "Introduction à l'algorithmique" pour les deux premières #éditions )<br />
#<br />
#Autres références bibliographiques :<br />
## Wilf, Algorithms and Complexity, (1994). [http://www.math.upenn.edu/%7Ewilf/AlgoComp.pdf Disponible en ligne]<br />
## Garey et Johnson, Computers and intractability a guide to the theory of NP-completeness. (1979).<br />
#!-- # Paschos, Complexité et approximation polynomiale, (2004). --<br />
## Hopcroft et Ullman, Introduction to automata theory, languages, and computation, (1979). <br />
#<br />
#== TP ==<br />
#<br />
#Dates provisoires : <br />
# - 22/25 septembre<br />
# - 9 octobre<br />
# - 16 octobre<br />
#<br />
#<br />
#TP1 les 22/25 septembre : Analyser la complexité d'algorithmes<br />
# - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP1/tp1_enonce.pdf Sujet du TP 1]<br />
# - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP1/fichiersTP1/ Fichiers pour le TP]<br />
# - Nécessité d'importer la librairie matplotlib<br />
#<br />
#<br />
#TP2 le 9 octobre : Problème NP-complet<br />
# - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP2/tp-part-1.pdf Sujet du TP 2 (Partie I)]<br />
# - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP2/instances/ Exemples d'entrée]<br />
# - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP2/generator.py Générateur aléatoire d'entrées]<br />
#<br />
#<br />
#TP3 le 16 octobre : Réductions<br />
# - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP3/tp-part-2.pdf Sujet du TP 2 (Partie II)]<br />
# - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP3/solveClique.py Esquisse de résolveur pour Clique]<br />
# - Nécessité d'importer la librairie pycosat<br />
#<br />
#!--- <br />
#TP les 10 octobre et 6 novembre.<br />
#<br />
# - Énoncé du TP, première partie : [https://mycore.core-cloud.net/index.php/s/CmLxKnYRdR3ots9 tp-part-1.pdf]. Plus de détails pour chacuns des #trois sujets :<br />
# * [https://mycore.core-cloud.net/index.php/s/pGWYh5foa81qWMQ tp-part-1-CHO.pdf]<br />
# * [https://mycore.core-cloud.net/index.php/s/28cFgEefXqte4hO tp-part-1-CHNO.pdf]<br />
# * [https://mycore.core-cloud.net/index.php/s/qttUkOHtF6Fawel tp-part-1-3C.pdf]<br />
#Voici aussi un exemple d'entrée pour chaque sujet :<br />
# * [https://mycore.core-cloud.net/index.php/s/0vzGaxLoTG7ILMV Graphe-vrai-CHO.pdf]<br />
# * [https://mycore.core-cloud.net/index.php/s/QUHwEnb8nlkpFxh Graphe-vrai-CHNO.pdf]<br />
# * [https://mycore.core-cloud.net/index.php/s/ItC1deMoQ2dZ1So Graphe-vrai-3C.pdf]<br />
#-----<br />
#TP3 le 18 octobre : Réductions polynomiales<br />
# - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP3/tp-part-2.pdf Énoncé du TP, deuxième partie].<br />
# - Documents pour les réductions :<br />
# * [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP3/DocsReduction/Avro--Chapter10--ChallengingReductions.pdf Avro #Chapitre 10]<br />
# * [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP3/DocsReduction/Cormen_Coloration.pdf Cormen-Leiserson-Rivest-Stein #Coloration]<br />
# * [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP3/DocsReduction/Cormen_HNO.pdf Cormen-Leiserson-Rivest-Stein HNO]<br />
#(Attention la figure 34.16 est incorrecte. La remplacer par la figure 34.16 de la [https://www.lama.univ-#savoie.fr/pagesmembres/tavenas/info704/TP3/DocsReduction/Cormen_HNO_english.pdf Version anglaise])<br />
# * [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP3/DocsReduction/Cours_Hon_HO2.pdf Hon HO] [https://mycore.core-#cloud.net/index.php/s/eQ1hJsUxci863kx Version francaise]<br />
# * [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP3/DocsReduction/garey-HNO.pdf Garey-Johnson HNO]<br />
# * [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP3/DocsReduction/wiki_proof.pdf wiki proof]<br />
# - Voici des exemples d'entrée pour 3SAT et Couverture par Sommets :<br />
# * [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP3/Instances/3sat_vrai 3SAT-vrai]<br />
# * [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP3/Instances/CS_vrai CS-vrai]<br />
# * [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP3/Instances/3sat_faux 3SAT-faux]<br />
# * [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP3/Instances/CS_faux CS-faux]<br />
#<br />
#--<br />
#<br />
#== Déroulement (2020) ==<br />
#<br />
#Cours 1 (7 septembre) : Introduction<br />
# - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S1Cours/CM1.pdf Introduction]<br />
# - Exemple de différents tris <br />
# - Notions d'instance et de problème<br />
# - Notion de complexité asymptotique<br />
# - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S1Cours/grandO.pdf Grand-O de la notation de Landau]<br />
#<br />
#<br />
#TD 1 (10 septembre) : Analyses d'algorithmes<br />
# - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S2TD/ExoAnalyse.pdf Sujet du TD]<br />
# - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S2TD/rappelsLog.pdf Fonctions mathématiques de base : polynômes, #exponentielles et logarithmes]<br />
#<br />
#<br />
#Cours 2 (17 septembre) : Algorithmes récursifs (Diviser pour régner)<br />
# - Présentation des algorithmes Diviser-pour-régner.<br />
# - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S3Cours/fct_rec.pdf Théorème général.]<br />
# - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S3Cours/distance_min.pdf distance minimale]<br />
#<br />
#<br />
#TD 2 (29 septembre) : Exercices d'analyse pour des algos récursifs ("Master Theorem")<br />
# - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S4TD/exos_diviser_pour_regner.pdf Exercices, complexité des fonctions #récursives].<br />
# - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S2TD/Solution-TD_operationsEntiers.pdf Solutions des questions 6 et 7].<br />
# - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S2TD/Solution_Question5.pdf Solution de la question 5].<br />
#<br />
#<br />
#Cours 3 (2 octobre) : Programmation dynamique<br />
# - Algorithme récursif pour les nombres de Fibonacci<br />
# - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S5Cours/decoupe_barre_acompleter.py Programme python pour le problème #de découpe de barres]<br />
# - Algorithme de [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S5Cours/Levenshtein.pdf Levenshtein]<br />
# - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S6TD/Cours_ProgDyn_Fibo_Levenshtein.pdf Présentation 'tablette' vue en #cours]<br />
#<br />
#<br />
#TD 3 (5 octobre) : Exercices sur la programmation dynamique<br />
#<br />
# - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S6TD/exemples_pour_prog_dynamique.pdf Sujet du TD]<br />
# - Si besoin, problème du sous-tableau de somme maximale.<br />
# - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S6TD/Notes_TD_progDyn.pdf Notes lors de la correction]<br />
# <br />
#<br />
#Cours 4 (13 octobre) : Premières réductions algorithmiques<br />
# - Un liste de réductions algorithmiques entre différents problèmes<br />
# - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S7TD/Notes_red_3SUM_3Collinear.pdf Note sur les mathématiques derrière la #réduction de 3SUM vers 3COLLINEAR]<br />
#!-- Réductions de NP-complétude<br />
#!-- - Problèmes NP-difficiles et NP-complets.<br />
# - Théorème de Cook-Levin. [https://mycore.core-cloud.net/index.php/s/V9OUMtvnDuezpKl Cook-Levin]<br />
# - Preuve de NP-Complétude. !-- : Couverture des arêtes et k-coloriage. --<br />
#--<br />
#!-- Complexité des problèmes<br />
# - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S8Cours/presentation1.0.pdf Introduction aux classes de complexité.]<br />
#!-- - Complexité d'un problème.<br />
# - Classe P.<br />
#!-- - Types de problèmes ( décision, optimisation, existence ). --<br />
# - Réduction polynomiale.<br />
# - Algorithme de vérification.<br />
# - Classe NP.<br />
#--<br />
#TD 4 (14 octobre) : Clique et consorts<br />
# - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S8Cours/Clique-EI-CS.pdf Réductions autour de Clique et NP-complétude de #Clique]<br />
# - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S8Cours/ProblemeSAT.pdf Notes sur le problème SAT]<br />
#!-- Programmation dynamique<br />
# - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S7TD/TD-prog_dynamique.pdf Énoncé de TD.]<br />
# - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S8Cours/Levenshtein.pdf Correction sur la distance de Levenshtein.]<br />
#--<br />
#<br />
#Cours 5 (23 octobre, matin) : Classes de complexité et NP-complétude<br />
# - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S9Cours/IntroNPcompletude.pdf Petite introduction en survol de la NP-#complétude]<br />
# - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S9Cours/INFO704-Classes_de_complexite.pdf Notes de cours sur les classes #de complexité]<br />
# - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S9Cours/VraiFaux-NP-completude.pdf Petit Vrai/Faux sur la NP-complétude]<br />
# - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S9Cours/Levin-Cook.pdf Hors programme : slides sur les classes de #complexité que j'avais utilisé lors d'une année antérieure quand je faisais la preuve du théorème de Levin-Cook]<br />
#<br />
#TD 5 (23 octobre, après-midi) : Classes de complexité et NP-complétude<br />
# - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S10TD/Enonce_TD.pdf Énoncé du TD]<br />
# - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S10TD/INFO704-Probleme_sac_a_dos.pdf Problème du sac à dos]<br />
# - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S10TD/Corrige_exercice3.pdf Corrigé de l'exercice 3 du TD]<br />
#<br />
#<br />
#== Annales Examen ==<br />
#<br />
#[https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/Examen/examen.pdf Examen 2017]<br />
#<br />
#== Historique ==<br />
#Ce cours était donné précédemment par Xavier Provençal.<br />
#Ce cours est une refonte de [http://lama.univ-savoie.fr/mediawiki/index.php/INFO724_:_Algorithmique_avanc%C3%A9e,_graphes_et_NP-#Compl%C3%A9tude INFO724 Algorithmique avancée, graphes et NP-complétude].<br />
#<br />
--></div>Stave