A. Sigayret : Algorithmique

Exercices d'algorithmique : série 6


Une file F est une liste dans laquelle on peut ajouter un élément à une extrémité et retirer un élément à l'autre extrémité (comme une file d'attente : "First In First Out"). Nous choisirons les actions élémentaires suivantes :
estvide(F) : teste si une file F est vide.
debut(F) : retourne la valeur présente au début d'une file F non vide sans changer cette file.
défiler(F) : retourne la valeur présente au sommet d'une file F non vide après avoir supprimé l'élément au sommet de cette file.
enfiler(F,x) : ajoute un élément de valeur x à la fin de la file F.

Une pile P est une liste donc l'accès ne se fait qu'à une extrémité qui est son sommet (comme une pile d'assiettes : "Last In First Out"). Nous choisirons les actions élémentaires suivantes :
estvide(P) : teste si une pile P est vide.
sommet(P) : retourne la valeur présente au sommet d'une pile P non vide sans changer cette pile.
dépiler(P) : retourne la valeur présente au sommet d'une pile P non vide après avoir supprimé l'élément au sommet de cette pile.
empiler(P,x) : ajoute un élément de valeur x au sommet de la pile P.

Exercice 6.1. Files
Ecrire un algorithme pour chacun des problèmes suivants. En faire la preuve et déterminer la complexité.
a) Supprimer tous les éléments d'une file situés au dessus d'un valeur donnée.
b) Transférer le contenu d'une file vers une autre file.
c) Vérifier si une valeur donnée appartient à une file.
d) Calculer la taille d'une file.
e) Ne conserver qu'une seule occurrence d'une valeur donnée dans une file.
f) Purger une file : supprimer toutes les occurrences multiples d'une file (càd ne garder qu'un exemplaire de chaque valeur de la file).

Exercice 6.2. Piles
Ecrire un algorithme pour chacun des problèmes suivants. En faire la preuve et déterminer la complexité.
a) Supprimer tous les éléments d'une pile situés au dessus d'un valeur donnée.
b) Transférer le contenu d'une pile vers une autre pile, en conservant les éléments dans le même ordre.
c) Vérifier si une valeur donnée appartient à une pile.
d) Calculer la taille d'une pile.
e) Ne conserver qu'une seule occurrence d'une valeur donnée dans une pile, l'ordre de la pile devra être conservée.

Exercice 6.3.
a) Ecrire un algorithme qui transfert le contenu d'une file dans une pile.
b) Ecrire un algorithme qui transfert le contenu d'une pile dans une file.
c) Ecrire un algorithme qui inverse une pile.
d) Ecrire un algorithme qui inverse une file.
e) Ecrire un algorithme qui fusionne deux piles.
f) Ecrire un algorithme qui fusionne deux files.

Exercice 6.4.
La suite de Fibonacci est définie par Fibo(0)=Fibo(1)=1 et pour n>1 Fibo(n)=Fibo(n−1)+Fibo(n−2).
a) Ecrire un algorithme itératif qui calcule Fibo(n) pour n donné. Cet algorithme utilisera au plus trois variables et aucune autre structure de données.
b) Ecrire un algorithme qui place dans une file les n premières valeurs de la suite de Fibonacci ; chaque valeur Fibo(i) ne sera calculée qu'une seule fois.
c) Ecrire un algorithme qui place dans une pile les n premières valeurs de la suite de Fibonacci ; chaque valeur Fibo(i) ne sera calculée qu'une seule fois.
d) Ecrire un algorithme itératif qui calcule Fibo(n) pour n donné ; chaque valeur Fibo(i) ne sera calculée qu'une seule fois et l'espace mémoire utilisé sera le plus petit possible.
e) Même question avec un algorithme récursif.

Exercice 6.5.
La fonction de Syracuse d'un entier naturel n non nul est défini par : si n est paire Syr(n)= n div 2, sinon Syr(n)=3*n+1. La suite de Syracuse de n est formée des entiers obtenus en appliquant successivement la fonction Syr à partir de n et jusqu'à 1. Pour n=5n, aura par exemple (5,16,8,4,2,1)
a) Ecrire un algorithme qui construit la suite de Syracuse d'un nombre.
b) Une conjecture (non prouvée) veut que la suite de Syracuse de tout entier naturel non nul converge vers 1. Quelle est la conséquence de l'absence de preuve sur la complexité du problème ? sur son déterminisme ?

Exercice 6.6.
Un caviste range dans trois rayonnages différents d'une cave les bouteilles de vin blanc, rosé et rouge. Ces bouteilles arrivent une à une sur un tapis roulant , tandis que le livreur décharge son camion au hasard sur l'autre extrémité du tapis.
a) Les trois rayonnages ont chacun k cases et le nombre de bouteilles passées par l'associé n'est pas connu à l'avance. Par quelle structure de données modéliser les trois rayonnages ? Le tapis roulant ?
b) Ecrire un algorithme qui effectue le remplissage des rayonnages à partir du camion.
c) Si le rayonnage des vins rouges (resp. rosé et blanc) est plein, le caviste posera par terre les bouteilles de rouges qui arrivent. Quand tous les rayonnages seront pleins ou que le camion sera vidé, il inversera le sens du tapis roulant pour renvoyer les bouteilles en trop vers le camion. Modifier l'algorithme précédent en conséquence.
d) Montrer que dans le premier algorithme la complexité est linéaire dans le nombre de cases du rayonnage ou bien dans le nombre de bouteilles. Quelle est la complexité du deuxièem algorithme ?
N.B. voir le problème du drapeau hollandais dans la série 4.

Exercice 6.7.
Une table de hachage est une structure de données permettant de ranger des objets qui correspond à un tableau T de k listes T[1],... T[k]. Une fonction élémentaire hachage(b) permet de décider en O(1) dans laquelle des k listes un objet b à ajouter doit être placé. Une procédure placer(b,i) permet d'ajouter un objet b à une liste T[i].
On s'intéresse ici au placement d'une liste de n mots à placer dans cette structure. La fonction de hachage utilise la première lettre du mot sans tenir compte des majuscules ni des accents (k=26).
a) Pourquoi hachage(b) est-elle en O(1) ?
b) Comment choisir la structuration des listes T[i] pour que placer(b,i) soit aussi fait en O(1) ?
c)) Ecrire les algorithmes correspondant à ces deux actions.
d) Ecrire l'algorithme qui ajoute n mots à une table de hachage initialement vide. Quel est la complexité de cet algorithme ?
e) Comment peut-on gérer la possibilité qu'un même mot puisse se trouver en plusieurs exemplaires dans la liste de mots entrée ? Cela permet-il de diminuer la complexité temporelle ? L'espace mémoire utilisé ?
f) Ecrire un algorithme qui permette ensuite de rechercher si un mot donné appartient à la table de hachage. Quelle est sa complexité ? Peut-on faire mieux ?
g) Quels arguments permettraient de montrer que la complexité temporelle en moyenne de l'algorithme de recherche soit inférieure à la complexité dans le pire cas ?

Exercice 6.*.
Dans des langages fonctionnels comme Lisp et Caml, le type liste a des actions élémentaires qui le rapproche du type pile :
estvide(S) : teste si une liste S est vide.
tete(S) : retourne le premier élément d'une liste S non vide.
queue(S) : retourne la liste S privée de son premier élément.
ajouter(S,x) : retourne la liste S à laquelle a été ajouté en tête l'élément x.
Modifier chacun des algorithmes ci-dessus utilisant une liste ou une pile pour n'utiliser que ces actions supplémentaires  recalculer en conséquence la complexité.
Remarque. On trouvera dans les exercices de Caml, des exercices d'application sur cette structure de données.