TP 5 : Listes, vecteurs

Exercice 1 (Implémentation des ensembles) :

On utilise des listes pour représenter des ensembles. Ecrire des fonctions réalisant les opérations suivantes :

• appartenance à un ensemble

• suppression des redondances d’une liste

• intersection de deux ensembles • réunion de deux ensembles

• différence et différence symétrique de deux ensembles.

Exercice 2 (Tri par fusion naturelle) :

Soit L=[a_{0};...;a_{n−1}] une liste d’éléments comparables. On appelle séquence croissante toute sous-liste [a_{i};...;a_{j}] triée par ordre croissant, et séquence croissante maximale une séquence croissante qui n’est contenue dans aucune autre séquence croissante. On propose l’algorithme suivant pour trier L:

• parcourir L en fusionnant deux par deux les séquences croissantes maximales ;

• recommencer jusqu’à ce qu’il ne reste plus qu’une seule séquence.

1. Ecrire une fonction implémentant cet algorithme. Pour cela : • écrire une fonction recherchant la plus grande séquence croissante initiale de L, et la renvoyant avec le reste de la liste ;

• écrire une fonction fusionnant les séquences croissantes de L deux par deux ;

• écrire la fonction principale qui fusionne les sous-séquences maximales de L tant qu’il en reste plus d’une.

2. Evaluer la complexité de cette fonction.

Exercice 3 (Structure FIFO, files d’attentes) :

On utilise le type de données suivante :

              type 'a file = {mutable debut :  'a list; mutable fin :  'a list}

On ajoute un élément à une file en le plaçant en tête de la liste fin. Le premier élément d’une file est la tête de la liste debut. Lorsqu’on cherche à accéder au premier d’une file, il se peut que la liste debut soit vide. Dans ce cas, il convient d’abord de renverser la liste fin et la transférer dans la liste debut.

1. Programmer les primitives suivantes :

     • file_vide :  unit -> 'a file : crée une file vide
     • est_vide :  'a file -> bool : teste si la file est vide
     • miroir :  'a list -> 'a list : renverse une liste

• premier : 'a file -> 'a : renvoie la tête de la file

     • enfile :  'a -> 'a file -> 'a file : ajoute un élément à une file

• defile : 'a file -> 'a file : renvoie une file privée de sa tête.

2. Tester ces primitives su un exemple.

3. En évaluer la complexité temporelle.

Exercice 4 (Produits matriciels) :

Une matrice sera considérée comme un vecteur de vecteurs : type 'a matrice = 'a vect vect.

Par exemple, si A = [| [|1; 2|]; [|-1; 1|]|], alors A.(0) renvoie [|1; 2|], et A.(0).(1) renvoie 2.

1. Ecrire une fonction calculant la somme de deux matrices.

2. Ecrire une fonction calculant le produit de deux matrices.

En déduire une fonction exponentiation :  int matrice -> int -> int matrice calculant la puissance

nème d’une matrice carrée. Chercher un moyen de réduire au maximum le nombre de produits à effectuer.

3. Combien de produits d’entiers doit-on effectuer pour calculer A^{16}, où A est une matrice (n, n) ? Et A^{15} ?

4. Ecrire une fonction qui a une matrice A, deux entiers i et j et un réel α, associe la matrice déduite de A en ajoutant α fois la ligne j à la ligne i. En déduire une fonction calculant le déterminant d’une matrice. (Préférer la méthode du pivot au développement récursif par rapport à une ligne ou une colonne). Quelle est la complexité d’une telle fonction ? La comparer avec celle du développement.

Corrigé (partiel) du TP 5 : Listes et vecteurs

Exercice 1 Exercice 2 Exercice 3 Exercice 4