TD 12 - Parcours de matrice

1 Parcours simple

1.1 Exercice 1

On dit qu’une matrice \(M\) de taille \(n \times m\) est creuse si la majorité de ses éléments sont nuls.

Écrivez un algorithme qui reçoit en entrée une matrice \(M\) (de taille \(n \times m\) contenant des nombres entiers) et qui renvoie VRAI si la matrice est creuse, FAUX sinon.

On considérera ici qu’une matrice est creuse si au moins 70% de ses éléments sont nuls.

NoteMatrices creuses

Les matrices creuses sont très courantes en calcul scientifique (réseaux, graphes, équations différentielles). Des structures de données spécialisées permettent de les stocker efficacement (COO, CSR, CSC).

2 Autres parcours

2.1 Exercice 2

On dit qu’une matrice \(n\times n\) est triangulaire supérieure si tous les nombres en dessous de la diagonale sont nuls. Par exemple

\[ M_1=\begin{pmatrix} 1 & 1 & 0 \\ 0 & 4 & 6 \\ 0 & 0 & 9 \end{pmatrix} \quad \text{et} \quad M_2=\begin{pmatrix} 5 & 0 & 0 \\ 0 & 0 & 6 \\ 0 & 0 & 2 \end{pmatrix} \]

sont triangulaires supérieures. Par contre

\[ M_3=\begin{pmatrix} 1 & 0 & 0 \\ 0 & 5 & 0 \\ 0 & 1 & 2 \end{pmatrix} \quad \text{et} \quad M_4=\begin{pmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 1 & 0 & 0 \end{pmatrix} \]

ne le sont pas.

Écrire un algorithme TRIANGLE_SUP qui prend en entrée une matrice \(M\) sous forme de tableau de tableaux de taille \(n\times n\) et qui retourne VRAI si \(M\) est triangulaire supérieure et FAUX sinon.

Faire une analyse en pire et en meilleur cas. Quelle est la complexité générale de l’algorithme ?

2.2 Exercice 3

On rappelle qu’une matrice \(M\) est un tableau de tableaux. L’élément \(M[i][j]\) se trouve sur la ligne d’indice \(i\) et sur la colonne d’indice \(j\). On appelle permutation circulaire (à droite) d’un tableau, le décalage de chaque valeur du tableau d’un indice sur la droite, avec retour de la dernière valeur à l’indice 1. Par exemple, le tableau \([4,0,1,2,3]\) est la permutation circulaire du tableau \([0,1,2,3,4]\).

  1. Écrire un algorithme EstPermutation(T1,T2) qui retourne VRAI si le tableau T2 est la permutation circulaire du tableau T1 et FAUX sinon (on suppose les deux tableaux de taille \(n\)).

  2. On dit qu’une matrice carrée est circulante si chaque ligne est une permutation circulaire de la ligne du dessus. Par exemple

    \[\begin{pmatrix} 0 & 1 & 2 & 3 & 4 \\ 4 & 0 & 1 & 2 & 3 \\ 3 & 4 & 0 & 1 & 2 \\ 2 & 3 & 4 & 0 & 1 \\ 1 & 2 & 3 & 4 & 0 \end{pmatrix} \text{ est une matrice circulante.}\]

    Écrire un algorithme EstCirculante(M) qui retourne VRAI si la matrice \(n\times n\) est circulante, FAUX sinon (l’algorithme doit s’arrêter dès que possible).

  3. Donner la complexité de l’algorithme précédent en justifiant brièvement.

3 En plus

3.1 Exercice 4 🏠

On appelle tableau binaire de taille \(n\) un tableau de \(n\) éléments ne contenant que les nombres 0 et 1. Dans la suite de l’exercice, M désigne une matrice de taille \(m\) dont chaque ligne est un tableau binaire de taille \(n\).

On pourra utiliser si besoin l’algorithme EchangerLignes(M,i,j) de complexité \(\Theta(1)\) qui permute les lignes \(i\) et \(j\) de la matrice.

  1. Écrire un algorithme PLSUn(T) qui renvoie la longueur de la plus longue séquence de 1 consécutifs du tableau \(T\). Par exemple pour le tableau [1,1,0,1,0,0,1,1,1,1,0,1,1,1] l’algorithme renverra 4.

  2. Écrire un algorithme Propager(M,i) qui parcourt la matrice M de la ligne d’indice \(1\) jusqu’à la ligne d’indice \(i\) et, pour chaque indice \(j\), échange les lignes consécutives M[j] et M[j+1] si la plus longue séquence de 1 consécutifs de M[j] est supérieure à celle de M[j+1]. Cet algorithme renvoie FAUX si aucun échange n’a été effectué et VRAI sinon.

  3. Écrire un algorithme TriLignes(M) qui trie les lignes de la matrice M en fonction de la longueur de la plus longue séquence de 1 consécutifs (de la plus petite vers la plus grande). L’algorithme devra être optimisé pour terminer plus vite en cas d’instance favorable.

  4. Faire une étude en meilleur et pire cas et donner la complexité générale de l’algorithme TriLignes(M).

  5. On suppose maintenant que la matrice M a été triée à l’aide de l’algorithme précédent. Écrire un algorithme ChercheLigne(M,k) de complexité \(O(n\log(m))\) qui renvoie VRAI s’il existe une ligne dont la plus longue séquence de 1 consécutifs est égale à \(k\) et FAUX sinon.

AstuceIndices
  • Question 3 : Tri à bulles avec optimisation (flag pour détecter si trié)
  • Question 4 : Complexité comme tri à bulles optimisé
  • Question 5 : Recherche dichotomique sur les lignes + parcours linéaire de chaque ligne testée