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 :

Array.make n val pour créér un tableau 1D rempli de val
Array.make_matrix n m val idem pour 2 dimensions
On peut remplacer make par init, auquel cas la valeur est remplacée par une fonction qui prend en argument l'indice et renvoie la valeur à cet indice.

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...

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...

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...

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...

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 :

Code d'accès