Analyse d'algorithmes

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

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

-->