INFO704 : Analyse d'algorithmes

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

TP

Énoncé du TP : Énoncé

Des instances d'entrées peuvent être trouvées à : Cities10, Cities15, Cities20, Cities100 et un générateur : generator_cities.cpp.

Les solutions exactes aux premières instances sont : Solution10, Solution15, Solution20. 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).

Le programme minCouplage.cpp que vous pouvez utiliser pour la phase 3 de l'algorithme de la section 3.

Problèmes (thème de la programmation dynamique)

Templates pour utiliser des fichiers plutôt que l'entrée standard et la sortie standard : Templates .cpp for files, Templates .py for files

Problème 1 :

- 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.
- 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.
- Sortie : Le nombre de produits que l'on peut obtenir à chaque test.
- Taille maximale des paramètres : N,E < 10^5.
- Fichiers de tests : small_input, test100, test100000, solution_small_input, solution100
- Exemples de solutions : Code python, Code c++

Exemple d'un test. Sur l'entrée :

 5 10
 2 7 4 3 6

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.

Problème 2 :

- 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). 
Comme ce nombre grossit très vite, on demandera juste le résultat modulo 123456789.
- 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. 
- Sortie : Le nombre de montées possibles pour chaque test (modulo 123456789).
- Taille maximale des paramètres : H < 10^8.
- Fichiers de tests : inputs
- Exemples de solutions : Code python, Code c++

Exemple d'un test. Sur l'entrée :

 2

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.

Problème 3 :

- 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.
- 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).
- Sortie : La valeur maximale que l'on peut obtenir à chaque test.
- Taille maximale des paramètres : valeurs des objets < 100, M < 100, N < 100.
- Fichiers de tests : small_input, dataDistrib10, dataDistrib50, dataDistrib100
- Exemples de solutions : Code python, Code c++

Exemple d'un test. Sur l'entrée :

 2 4 5
 2 1 10 3
 9 5 1 7

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.

Problème 4 :

- 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. 
Ce nombre grossissant vite, on s'intéressera au résultat modulo 123456789.
- 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.
- Sortie : Le nombre de chemins à chaque test.
- Taille maximale des paramètres : X < 10000, Y < 10000.
- Fichiers de tests : small_input, quartier10, quartier100, quartier1000, quartier10000
- Solutions : solution10, solution100, solution1000, solution10000

Exemple d'un test. Sur l'entrée :

 2 2 2
 1 0 'v'
 1 1 'v'

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.

Problème 5 :

- 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). 
Ce nombre grossissant vite, on s'intéressera au résultat modulo 123456789.
- 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.
- Sortie : Le nombre de façons d'obtenir S à chaque test.
- Taille maximale des paramètres : D < 1000,  F < 1000, S < 500000.
- Fichiers de tests :dataDices10, dataDices100, dataDices1000, dataDices10000
- Solution :solution10, solution100, solution1000
- Template : Template
- Générateur : generatorDices

Exemple d'un test. Sur l'entrée :

 2 4 6

Comme expliqué dans l'énoncé, la réponse attendue est 3.

Problème 6 :

- 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.
- 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.
- Sortie : Le prix minimal à payer lors de chaque test.
- Taille maximale des paramètres : n < 1000000, m < 10000, C < 100

Exemple d'un test. Sur l'entrée :

 5 2
 1 4 10 3 5  

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.

Problème 7 :

- 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.
- 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.
- Sortie : La longueur de la plus grande sous-suite en zig-zag pour chaque test.
- Taille maximale des paramètres : valeurs des objets < 100, M < 40, N < 50.

Exemple d'un test. Sur l'entrée :

 10
 1, 17, 5, 10, 13, 15, 10, 5, 16, 8

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.

Problèmes (thème des graphes)

Template pour les graphes : Template

Générateurs : generator_maze, plot_maze

Problème Labyrinthe :

- 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.
- 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).
- Sortie : Pour chaque test, dire s'il y a un chemin depuis l'entrée (au nord-ouest) vers la sortie (au sud-est).
- Taille maximale des paramètres : L < 1000, H < 1000.
- Hint : DFS (voire A*)

Problème Labyrinthe II :

- 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 !
- Entrée : Identique au problème précédent.
- Sortie : Pour chaque test, donner la longueur du plus court chemin depuis l'entrée (au nord-ouest) vers la sortie (au sud-est).
- Taille maximale des paramètres : L < 1000, H < 1000.
- Hint : BFS

Problème Labyrinthe III :

- 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 ?
- 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). 
- Taille maximale des paramètres : L < 1000, H < 1000.
- Hint : Kruskal

Réseau téléphonique :

- 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) ). 
- 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.
- Sortie : Pour chaque test donner le chemin avec bande-passante maximale.
- Taille maximale des paramètres : V < 100000, E < 1000000, BW < 1000. 
- Hint : Dijkstra

Problème Livraison :

- 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.
- 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.
- Sortie : Pour chaque test donner le nombre minimal de liaisons à rajouter pour pouvoir livrer toutes les villes.
- Taille maximale des paramètres : n < 100000, E < 1000000.
- Hint : Tarjan, Kosaraju

Analyse amortie

Tas binaires vs. Tas binomiaux vs. Tas de Fibonacci

Donner pour chacune de ces structures la complexité (amortie si c'est le cas) des différentes opérations :

- ajouter un élément
- trouver le plus petit élément
- supprimer le plus petit élément
- modifier la valeur d'une entrée
- supprimer un élément
- fusionner deux tas

Union-Find

- 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é. 
- 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 :
  - 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),
  - union(x, y)  établit l’équivalence (connexion) entre x et y
- 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)

Donner la complexité des deux opérations ('union' et 'find') dans les quatre structures suivantes :

- On stocke dans un tableau T de taille n : T[x] est le représentant de x.
- Lors de l'union de u avec v, on stocke dans v un pointeur vers u.
- 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.
- 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.

Si vous vous ennuyez

Coder une structure de donnée qui encode un ensemble d'entiers et qui supporte les deux opérations suivantes :

- Ajout(i) : Ajoute un élément i dans la structure.
- SuppressionMoitSup() : Supprime les n//2 plus grands entiers de la structure où n est le nombre d'entiers dans la structure.

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

---

Programmation linéaire

Exemples de programmes utilisant MIP de Python : SacAdos.py dames.py