“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 181 — #191
i
i
i
i
i
i
i
i
3.9 Exercices
181
➤ Exercice 10 — Les opérations sur les matrices
Supposons que nous représentons une matrice comme une liste de listes, où
chaque liste interne contient une rangée de la matrice. Définissez des fonctions
pour faire les opérations de base sur les matrices comme l’addition, la transposition et la multiplication.
➤ Exercice 11 — Le tri rapide
Voici un algorithme pour trier les listes. Son inventeur C.A.R. Hoare l’a appelé tri
rapide (« quicksort »), parce qu’à l’époque de son invention il était l’algorithme
de tri général le plus rapide connu. Il utilise une stratégie de diviser pour régner
qui donne une complexité en temps moyenne O(n log n). Voici une description
informelle de l’algorithme pour le modèle déclaratif. Avec une liste d’entrée L,
faites les opérations suivantes :
a) Choisissez le premier élément X de L comme l’élément pivot.
b) Partitionnez L en deux listes, L1 et L2, tel que chaque élément de L1 est plus
petit que X et chaque élément de L2 est plus grand ou égal à X.
c) Utilisez le tri rapide pour trier L1 dans S1 et pour trier L2 dans S2.
d) Concaténez les listes S1 et S2 pour obtenir la réponse.
i
i
i
i
i
i
i
i
3.9 Exercices
181
➤ Exercice 10 — Les opérations sur les matrices
Supposons que nous représentons une matrice comme une liste de listes, où
chaque liste interne contient une rangée de la matrice. Définissez des fonctions
pour faire les opérations de base sur les matrices comme l’addition, la transposition et la multiplication.
➤ Exercice 11 — Le tri rapide
Voici un algorithme pour trier les listes. Son inventeur C.A.R. Hoare l’a appelé tri
rapide (« quicksort »), parce qu’à l’époque de son invention il était l’algorithme
de tri général le plus rapide connu. Il utilise une stratégie de diviser pour régner
qui donne une complexité en temps moyenne O(n log n). Voici une description
informelle de l’algorithme pour le modèle déclaratif. Avec une liste d’entrée L,
faites les opérations suivantes :
a) Choisissez le premier élément X de L comme l’élément pivot.
b) Partitionnez L en deux listes, L1 et L2, tel que chaque élément de L1 est plus
petit que X et chaque élément de L2 est plus grand ou égal à X.
c) Utilisez le tri rapide pour trier L1 dans S1 et pour trier L2 dans S2.
d) Concaténez les listes S1 et S2 pour obtenir la réponse.