Skip to main content Informatique en prépa - Lycée Malherbe 

4.1- TP - Programmation impérative

Ce TP a pour objectif de vous familiariser avec la programmation impérative en OCaml, c'est à dire avec des boucles et des références.

Nous allons faire du calcul matriciel, pas forcément extremement intéréssant, mais c'est de l'entrainement.

Pour représenter les matrices, nous allons utiliser un tableau de tableaux de flottants.

OCaml

Loading editor...

type mat = float array array;;

Pour rappel, on dispose des fonctions suivantes pour travailler avec les tableaux :

Vous pouvez aussi convertir un entier en flottant avec float_of_int.

Q1

Ecrivez une fonction zero n m qui renvoie la matrice zéro de taille

OCaml

Loading editor...

Vérification : zero
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).
Q2

Ecrivez une fonction identite n qui renvoie la matrice identité de taille , en utilisant une ou deux boucles for imbriquées.

OCaml

Loading editor...

Q3

Ecrivez une fonction random_mat: int -> int -> mat pour générer une matrice de taille de contenu aléatoire. Random.float max permet de générer un flottant aléatoire entre 0 et max.

OCaml

Loading editor...

Q4

Ecrivez une fonction dim: mat -> int*int qui renvoie les dimensions d'une matrice.

OCaml

Loading editor...

Q5

Ecrivez une fonction sum: mat -> mat -> mat qui réalise la somme de deux matrices de même taille. Votre fonction doit créer une nouvelle matrice pour le résultat.

OCaml

Loading editor...

Q6

Ecrivez une fonction compat: mat -> mat -> bool qui détermine si deux matrices sont compatibles pour être multipliées.

OCaml

Loading editor...

Q7

Ecrivez une fonction mul: mat -> mat -> mat qui multiplie deux matrices.

OCaml

Loading editor...

Vérification : mul
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).

Algorithme de Strassen

Wikipédia l'explique mieux que moi :

On découpe les matrices , et en quatre blocs de taille :

On a alors :

Cette méthode nécessite 8 multiplications de matrices pour calculer les , comme dans le produit classique.

La force de l'algorithme de Strassen réside dans un ensemble de sept nouvelles matrices , qui vont servir à exprimer les avec seulement 7 multiplications au lieu de 8 :

Les s'expriment alors comme :

Voir la page Wikipédia.

On se propose d'implémenter cet algorithme en OCaml. On se limitera aux matrices carrées.

Q8

Ecrivez des fonctions split: mat -> mat * mat * mat * mat et concat: mat * mat * mat * mat -> mat qui permettent de découper des matrices carrées et de les recoller. Tester votre fonction en vérifiant qu'une même matrice découpée recollée reste bien... La même matrice.

OCaml

Loading editor...

Vérification : split et concat
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).
Q9

Ecrivez une fonction moins: mat -> mat qui renvoie la négation d'une matrice.

OCaml

Loading editor...

Q10

Ecrivez une fonction strassen: mat -> mat -> mat qui multiplie deux matrices en utilisant l'algorithme de Strassen. Quelle est sa complexité ?

OCaml

Loading editor...

Vérification : strassen
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).

Pour votre culture, la meilleur complexité connue est actuellement . On sait seulement qu'on ne peut pas faire mieux que (il faut au moins lire les coefficients) : ce qui se situe entre les deux reste un problème ouvert.

Voir la page Wikipédia.

OCaml

Loading editor...


Entrez le code donné en cours pour accéder à la solution :