(Durée : 2 heures)

L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.
Le langage de programmation choisi par le candidat doit être spécifié en tête de la copie.

Ce sujet porte sur la détection de zones rectangulaires monochromatiques dans une image. Imaginons par exemple une image en noir et blanc, le problème est d'en trouver la plus grande zone noire. Ces zones monochromatiques peuvent être représentées de manière compacte en retenant les cordonnées des coins et la couleur interne. En décomposant une image selon ces grands rectangles, il est possible de la compresser efficacement, les zones monochromatiques pouvant être représentées de manière très compacte.

La complexité, ou le temps d'exécution, d'un programme (fonction ou procédure) est le nombre d'opérations élémentaires (addition, soustraction, multiplication, division, affectation, etc...) nécessaires à l'exécution de . Lorsque cette complexité dépend d'un paramètre , on dira que a une complexité en , s'il existe tel que la complexité de est au plus , pour toute instance de taille , pour tout . Lorsqu'il est demandé de garantir une certaine complexité, le candidat devra justifier cette dernière si elle ne se déduit pas directement de la lecture du code.

Dans cette partie, nous allons étudier le problème de reconnaissance de forme sur des tableaux unidimensionnels. Nous supposerons donnés un entier et un tableau tab de taille dont les cases contiennent 0 ou 1 . Nous supposerons que les indices du tableau sont compris entre 1 et n. Le but de cette partie est de trouver le nombre maximal de 0 contigüs (c'est à dire figurant dans des cases consécutives) dans le tableau.

Dans cette partie nous utiliserons le tableau suivant comme exemple :

Question 1 Écrire une fonction nombreZerosDroite prenant en paramètres le tableau tab de taille ainsi qu'un indice compris entre et . Cette fonction devra renvoyer le nombre de cases contigües du tableau contenant 0 à droite de la case d'indice , cette case étant comprise. D'un point de vue formel il s'agit de renvoyer 0 si la case d'indice contient un 1 et sinon de renvoyer

Sur le tableau exemple précédent, en prenant comme indice nous obtenons 0 et pour l'indice votre fonction devra retourner 2 . Notez que si la case contient 1, alors votre fonction devra retourner 0 .

Il est maintenant possible de réaliser un algorithme de complexité optimale utilisant la fonction précédente. En voici une brève description. Parcourons le tableau de gauche à droite et à chaque début de plage de 0 contigüs, nous calculons la taille de cette plage puis repartons juste après elle. Ayant ainsi calculé la taille de toutes les plages de 0 il suffit de retenir celle de taille maximale. Sur l'exemple précédent, on part de l'indice 1 qui est un début de plage de 0 de taille 2. Nous continuons donc à chercher le prochain début de plage à partir de l'indice . On examine ensuite l'indice 4 qui contient encore un 1 puis arrivons à l'indice 5 qui est le début d'une plage de 0 de taille 3 . Nous allons donc chercher le prochaine début de plage à partir de l'indice etc

Question 2 Écrire une fonction nombreZerosMaximum qui renvoie le nombre maximal de 0 contigüs en utilisant l'algorithme précédent. On attachera une attention particulière à ce que l'algorithme produit soit de complexité linéaire c'est à dire en temps .

Cette partie consiste à développer un algorithme efficace pour détecter un rectangle d'aire maximale rempli de 0 dans un tableau bidimensionnel. Par mesure de simplification, nous travaillerons sur des tableaux carrés et nous supposerons donné un tableau tab2 de taille . Un tableau bidimensionnel sera adressé par tab2[i][j] et i représentera le numéro de ligne dans nos exemples.

Nous utiliserons le tableau suivant comme exemple :

Méthode naïve La première méthode proposée consiste à prendre une cellule ( ) et à trouver un rectangle d'aire maximale dont le coin inférieur gauche est cette cellule. Remarquez que suivant l'orientation donnée dans le tableau exemple ci-dessus, un rectangle d'aire maximale de coin inférieur gauche la cellule ( ) aura comme coin supérieur droit la cellule ( ) avec et . Par exemple, un rectangle d'aire maximale de coin inférieur gauche la cellule aura comme coin supérieur droit la cellule de coordonnées .

Question 3 Écrire une fonction rectangleHautDroit qui renvoie l'aire d'un rectangle d'aire maximale rempli de 0 et de coin inférieur gauche ( ). On cherchera la solution la plus efficace possible. Pour et sur le tableau exemple ci-dessus, la fonction devra renvoyer la valeur 10 .

Question 4 Expliquer comment trouver naïvement un rectangle d'aire maximale rempli de 0 en utilisant la fonction rectangleHautDroit. Quelle serait la complexité de cette approche en fonction de ?

Un peu de précalcul Notre algorithme parcourt de nombreuses fois les même cases afin de vérifier la présence d'un 0 ou d'un 1 . Nous allons donc effectuer avant notre algorithme un précalcul de certaines valeurs ce qui nous permettra, dans la partie III, d'accélérer les fonctions précédentes.

Pour chaque cellule ( ), nous allons calculer le nombre de cellules contigües contenant 0 au dessus de la cellule ( ), cette dernière étant comprise. Ce nombre est tel que les cellules contiennent 0 et la cellule contient 1 ou bien cette cellule n'existe pas. Ces valeurs seront rangées dans un tableau col. Le tableau col suivant est obtenu à partir du tableau exemple.

Question 5 Écrire une fonction colonneZeros qui renvoie un tableau bidimensionnel d'entiers col de taille et tel que donne le nombre de cellules contigües contenant 0 au dessus de ( ), cette cellule étant comprise. On apportera un soin particulier à programmer la fonction la plus rapide possible.

Question 6 Quelle est la complexité de la fonction colonneZeros?

Rectangle d'aire maximale dans un histogramme Une nouvelle étape dans notre algorithme réside dans la résolution du problème du calcul d'un rectangle d'aire maximale inscrit dans un histogramme. Nous supposerons donné un histogramme c'est à dire un tableau histo de taille contenant des entiers. Chaque valeur représentera la hauteur d'une barre de l'histogramme. Par exemple le tableau suivant est associé à l'histogramme à sa droite.

L'idée est de calculer un indice pour chaque colonne , tel que est le plus petit entier satisfaisant : et histo histo , pour tout tel que .

Notons que . Dans notre exemple nous aurons car la colonne est strictement plus petite que la colonne 3. Nous aurons par ailleurs car histo histo , histo histo , histo histo mais histo histo .

Nous pourrions calculer les valeurs de manière naïve mais cela ne permettrait pas d'améliorer notre algorithme. Nous allons donc procéder autrement.

On calcule successivement les valeurs de pour . Pour calculer on pose et on fait décroître tant que les colonnes sont plus grandes de la manière suivante :

Répéter :

Question 7 Montrer que l'algorithme précédent calcule correctement les valeurs de . De plus, montrer que l'algorithme fonctionne en temps sur le cas particulier du tableau histo de taille .

On supposera donnée une fonction calculeL(histo, ) qui renvoie en temps le tableau de taille tel que est l'indice défini précédemment. On supposera aussi donnée une fonction équivalente calculeR(histo, ) qui renvoie en temps un tableau dont les valeurs qui de manière analogue est l'indice maximal tel que histo histo pour tout tel que .

Question 8 Justifier que pour tout , le rectangle commençant à l'indice , terminant à l'indice et de hauteur histo est inclus dans l'histogramme.

Question 9 Soit un rectangle d'aire maximale inscrit dans l'histogramme. Supposons que ce rectangle commence à l'indice , termine à l'indice , et a pour hauteur . Montrer qu'il existe tel que histo , et .

Question 10 En déduire une fonction plusGrandRectangleHistogramme(histo, n) qui calcule et renvoie l'aire d'un plus grand rectangle inscrit dans l'histogramme. Donner la complexité de votre fonction plusGrandRectangleHistogramme.

En revenant au problème initial du calcul d'un rectangle de 0 d'aire maximale dans une matrice en deux dimensions, remarquer que chaque ligne du tableau col calculé par la fonction colonneZeros de la question 5 peut être interprétée comme un histogramme.

En utilisant cette analogie, il est possible de proposer une méthode efficace de résolution du problème.

Question 11 Écrire la fonction rectangleToutZero qui calcule un rectangle d'aire maximale rempli de 0 dans le tableau tab2 et en renvoie son aire.

Question 12 Quelle est la complexité de votre fonction?