Séries d'exercices du module "algorithmes et structures de données" (S3)

Série du premier semestre. Elle comporte également des énoncés de TP.
Les exercices sont empruntés au livre de M. Zeggour aux éditions Chihab.

Série n°1 – Les listes linéaires chaînées

Développer les algorithmes suivants sur les listes linéaires chaînées :

1. Construire une LLC à partir de n données lues.

2. Calculer la longueur d'une LLC.

3. Rechercher dans une LLC l'élément qui a le plus grand nombre d'occurrences.

4. Accès par valeur dans une LLC.

5. Accès par position dans une LLC.

6. Suppression par valeur dans une LLC.

7. Suppression par position dans une LLC.

8. Insertion par position dans une LLC.

9. Interclassement de deux listes ordonnées.

10. Eclater une liste en 2 LLCs selon un critère donné.

11. Trier une LLC par la méthode des bulles.

12. Implémenter le modèle de LLC en utilisant la représentation contiguë.

13. Etudier les algorithmes de recherche, insertion et suppression d'un élément dans un vecteur. Les comparer avec ceux correspondant sur les LLCs.

15. Construire une liste bidirectionnelle à partir de n données.

16. Insérer un élément dans une liste bidirectionnelle.

17. Supprimer un élément dans une liste bidirectionnelle.

18. Ecrire les algorithmes d’insertion, suppression etc. dans une LLC unidirectionnelle en anneau (circulaire)

Travaux pratique

Un polynôme peut être représenté par une LLC. Dire comment. Ecrire les algorithmes suivants :

- calcul du polynôme en un point x donné.

- dérivé d'un polynôme.

- somme de deux polynômes.

- produit de deux polynômes.

Est-il préférable de représenter un polynôme par un tableau ou par une LLC ? Expliquez.

Série n°2 – Les Piles

1. Représenter les expressions suivantes sous forme polonaise postfixée :

a+b , (a+b)/d , ((c+d) +(d-e))+5, -(a+b)+(5+b)c, -(((a+b)+(c-d))/5)+a5

Essayer de donner l'algorithme d'évaluation sans utiliser la pile? Donner l'algorithme d'évaluation avec l'utilisation d'une pile.

2. On désire utiliser deux piles dans un programme. Sachant que les deux piles ne sont jamais remplies totalement en même temps, on prévoit d’utiliser un même tableau pour l’implémentation des deux piles, la première allant de 1 à n et la seconde ne n à 1.

Donner la définition du type de donnée d’une pareille pile

Ecrire les opérations du modèle adapté à cette forme de pile

3. Ecrire un algorithme qui transforme une chaîne de caractères en son miroir en utilisant des piles

4. Ecrire un algorithme qui génère, pour une chaîne de caractères représentant une expression arithmétique en sa forme préfixée puis qui évalue le résultat de l’expression préfixée

Exemple : a+b è +ab ; (a+b)*2 è *+ab2 ; a+2*b è +a*2b

5. On désire vérifier si un mot donné est un palindrome. Ecrire, en utilisant les piles, un algorithme qui vérifie cela.

Un palindrome est un mot qui s’écrit de droite à gauche et de gauche à droite de la même façon. Ex : ABBA.

Travaux pratiques

Ecrire un programme qui génère, pour une chaîne de caractères représentant une expression arithmétique donnée en entrée (par clavier) sa forme préfixée puis qui évalue le résultat de l’expression préfixée

Exemple : a+b è +ab ; (a+b)*2 è *+ab2 ; a+2*b è +a*2b

Série n°3 – Files et ensembles

1. Comment implémenter une file d'attente où chaque élément contient un nombre variable d'entiers.

2. Une file d'attente avec priorité est une file d'attente dans laquelle l'opération de défilement récupère l'élément le plus prioritaire. Définir le modèle et l'implémenter.

3. Donner une implémentation possible (schéma+description) pour :

    - une file de files,

    - une file de piles,

    - une pile de files,

    - une pile de piles.

4 – Ecrire les algorithmes de base de manipulation d’ensembles pour les représentations statique et dynamique, dans les cas d’ensembles ordonnés, non ordonnés, avec ou sans doublons

TP.

On désire simuler le fonctionnement du traitement des processus (programmes en cours d’exécution) dans un environnement multitâche. Les processus sont identifiés par des entiers. Chaque processus a un temps d’exécution et une priorité. Le processeur exécute par quantum de temps de 1 sec. Chaque processus qui est retiré de la file est exécuté pendant un quantum de temps après quoi, s’il n’a pas fini de s’exécuter, il repart dans la file.

Implémenter un pareil simulateur et donnez pour une arrivée de dix processus arbitraires ne nécessitant pas plus de 3 min chacun, arrivant toutes les 5 secondes l’un, l’état du système (l’état de la file avec les temps restants) toutes les 30 secondes.

Pour pouvoir faire le travail, il faudra considérer que :

-          Lorsqu’un quantum de temps s’écoule, on gère la file (ajout de nouveau processus le cas échéant et ce qui doit s’en suivre selon l’architecture suivi pour l’implémentation du modèle de file avec priorité.)

-          Ensuite, on retire un nouveau processus de la file (le plus prioritaire)

Il faudra expliquer :

-          Comment représenter un processus

-          Définir le type abstrait de donnée file avec priorité

-          Définir les opérations du modèle

-          Décrire le fonctionnement du simulateur

-          Donnez, en résultat de l’exécution, un état de la file toute les 20 secondes jusqu’à ce qu’elle soit vide.

Série n°4 – La récursivité

1. Ecrire l'algorithme récursif qui calcule la somme des n premiers entiers naturels.

2. Ecrire les algorithmes récursifs correspondant au:

        (a) quotient de a par b,

        (b) reste de a et b,

        (c) pgcd (plus grand diviseur commun) de deux entiers non négatifs.

3. Soit A un tableau d'entiers. Présenter des algorithmes récursifs pour

        (a) le maximum de A,

         (b) le minimum de A,

         (c) la somme des éléments de A,

         (d) le produit des éléments de A,

         (e) la moyenne des éléments de A.

4. Développer les algorithmes itératifs et récursifs pour:

         (a) la factorielle,

         (b) le produit a*b,

         (c) la séquence de Fibonnacci.

Evaluer (trace) les algorithmes pour les cas suivants :6! ; 9! ; 100*3 ; 6*4 ; fib(10) ; fib(11). Comparer les algorithmes itératifs et récursifs

5. Algorithmes récursifs sur les listes linéaires chaînées (llc):

         (a) inverser une llc,

         (b) rechercher un élément donné dans une llc.

FSI

6 – Ecrire des algorithmes récursifs qui :

-          Evalue un nombre écrit en binaire

-          Evalue un nombre romain (écrit en chiffre romains)

7 – Donnez une version récursive de l’algorithme de tri indirect

Sujet de TP : Algorithmes de tri et de recherche

Tri :

Il est demandé d’implémenter six des sept algorithmes de tri vus en cours et td et de faire des batteries de tests qui permettent d’apprécier la notion de complexité.

Pour chacun des six algorithmes (Sélection, Insertion, Indirect, Bulles, Fusion, Hoare), faire un ensemble de tests en calculant pour les mêmes vecteurs remplis aléatoirement (mais aussi pour les vecteurs répondant au meilleur des cas (vecteur déjà trié) ainsi qu’au pire (vecteur trié à l’envers) ) le temps mis par l’algorithme de tri.

Il est souhaitable de choisir des vecteurs de 1000, 10000 et 100000 valeurs pour pouvoir apprécier le temps d’exécution en fonction de la taille des vecteurs et de comparer les résultats obtenus avec les complexités  théoriques.

Recherche :

Il est demandé d’implémenter les deux solutions pour la recherche auto-adaptative et de vérifier l’assertion de Knuth. Pour rappel, la recherche auto-adaptative dans une liste linéaire chaînée permet :

1 – soit de ramener la valeur recherchée en tête de la liste pour favoriser sa recherche un autre fois

2 – soit de la faire progresser vers le tête d’une position

Selon Knuth, la première idée est meilleure si le nombre de recherche est inférieur à n2 (n étant le nombre d’éléments) , sinon, si le nombre de recherches est supérieur ou égal à n2, le seconde idée devient meilleure.

Il est demandé d’implémenter les deux méthodes et de faire des tests pour vérifier si l’assertion est vérifiée. Il faudra faire des relevés et tracer deux courbes sous Excel pour établir ou rejeter la remarque de Knuth.