X ENS Informatique Commune PSI PT 2004

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.

On attachera une grande importance à la concision, à la clarté, et à la précision de la rédaction.

Le temps d'exécution d'une fonction est le nombre d'opérations élémentaires (addition, soustraction, multiplication, division, affectation, etc.) nécessaire au calcul de . Lorsque ce temps d'exécution dépend d'un paramètre , il sera noté . On dit que la fonction s'exécute :

On recherche les cercles d'amis dans un ensemble de personnes ( ). un moment donné, et sont amis ; et sont amis ; et sont amis. On notera par la relation d'amitié. On a donc .

La relation d'amitié indirecte est définie selon le principe que « les amis de mes amis sont mes amis >>. On pose donc :

Pour , on a donc . Il en résulte que et sont des amis indirects s'ils sont amis ou s'ils ont un ami indirect en commun. On dira aussi que et appartiennent à un même cercle d'amis.

Ainsi en prenant et , les cercles d'amis sont . Il y a trois cercles d'amis : n'a d'autre ami que lui-même; sont des amis indirects ; et sont aussi amis.

On cherche à répondre à la question suivante : étant donné un couple ( ), a-t-on ?
Dans chaque cercle d'amis, on élit un représentant (unique). La relation d'amitié indirecte est représentée par un tableau de éléments vérifiant la propriété suivante : en partant de toute entrée dans , la suite définie par et pour converge vers un vérifiant qui est le représentant unique du cercle d'amis de .

Ainsi dans l'exemple précédent, en prenant et comme représentants de , et , le tableau peut représenter la relation d'amitié indirecte . Mais on aurait pu aussi prendre ; etc.

Question 1 Donner la valeur du tableau quand . Donner ses valeurs possibles quand et pour deux valeurs et données.

Pour déterminer le représentant du cercle d'amis de , on explore le tableau à partir de l'indice jusqu'à trouver tel que . Dans l'exemple, quand , on trouve le représentant du cercle d'amis de , en cherchant celui de puisque , puis celui de puisque , pour finalement trouver puisque .

Question 2 Écrire une fonction representant retournant, en temps linéaire par rapport à , l'indice du représentant du cercle d'amis de .

Question 3 Écrire une fonction sontAmis qui retourne la valeur vrai si et faux sinon. (Dans les langages de programmation où les valeurs booléennes n'existent pas, on rendra l'entier 0 pour la valeur faux et 1 pour la valeur vrai).

On veut maintenant modifier la relation en ajoutant la nouvelle relation . Deux nouveaux amis viennent de se déclarer ; leurs cercles d'amis respectifs peuvent donc fusionner. On doit modifier le tableau tout en préservant sa propriété d'indiquer les représentants. On ajoute une relation entre le représentant de et le représentant de . On peut donc poser soit , soit .

Question 4 Écrire une fonction ajout qui modifie le tableau représentant la relation après l'ajout de la nouvelle relation . Donner un ordre de grandeur du temps d'exécution de cette fonction par rapport à .

Question 5 Montrer sur un exemple que le choix laissé arbitraire dans la modification du tableau peut influer sur le temps d'exécution de la fonction representant. Donner une piste pour garantir un meilleur temps d'exécution.

Dans la suite, on dira que et sont «équivalents» si .

On cherche à déterminer les objets contenus dans une image numérique noir et blanc représentée par une matrice . Typiquement, ou . Chaque élément de l'image ( ), encore appelé pixel, est un entier valant 0 (blanc) ou 1 (noir). La couleur du fond de l'image est supposée blanche ; un pixel valant 1 appartient à un des objets. Le but de cette partie consiste à colorier chaque pixel de par le numéro ( ) de l'objet auquel il appartient. On réserve la valeur 0 pour les pixels du fond de l'image, c'est-à-dire valant déjà la valeur 0 dans l'image initiale. Par convention, la première ligne de la matrice est en haut de l'image (nord) et la première colonne est à gauche (ouest).

Dans l'image suivante, il y a 5 objets dans l'image de gauche qui devient après coloriage l'image de droite :

Question 6 Écrire une fonction couleurNO( ) qui retourne la couleur du pixel au nord-ouest du pixel pour vérifiant et . Cette fonction retourne aussi la couleur du fond lorsque ou . Écrire de même les fonctions couleurN et couleurO( ) qui retournent respectivement les couleurs du pixel au nord et à l'ouest du pixel .

La reconnaissance des différents objets d'une image se fait en deux phases. D'abord, on identifie les objets figurant sur l'image. Par la suite, on procède au coloriage de tous les pixels. Par convention, on dira que deux pixels (valant 1) appartiennent à un même objet s'ils sont connectés sur des axes nord/sud, est/ouest ou nord-ouest/sud-est (Attention, ils sont dans des objets différents s'ils sont uniquement connectés nord-est/sud-ouest). Plus exactement, les pixels et sont dans un même objet si et on a soit et , soit et , soit .

La phase d'identification des objets se fait par modification progressive de la matrice en déplaçant de gauche à droite et de haut en bas une fenêtre de quatre pixels. On suppose que les pixels au nord-ouest, au nord, et à l'ouest du pixel courant en bas à droite de la fenêtre sont déjà identifiés. Soient no, leurs couleurs respectives.

Pour identifier le pixel non blanc , on applique les règles suivantes, l'une après l'autre, en s'arrêtant lorsqu'une condition est satisfaite :

Ainsi, dans l'exemple ci-dessus, les couleurs 2 et 3 sont équivalentes.

La variable globale aura comme valeur le nombre de couleurs nécessaires pour identifier les objets de . On suppose que cette valeur est bornée par une constante C pas trop grande, et on gère les équivalences entre couleurs avec un tableau de longueur selon les méthodes de la première partie.

Question 7 Écrire une fonction marquage( ) qui identifie les objets de la matrice de pixels selon la méthode décrite précédemment, tout en modifiant les valeurs de la variable et du tableau global représentant les équivalences entre les couleurs attribuées aux pixels de . Donner un ordre de grandeur de son temps d'exécution en fonction de R et C .

La deuxième phase de l'algorithme consiste à re-parcourir l'image de haut en bas et de gauche à droite en coloriant avec une même couleur tous les pixels appartenant à un même objet. Si l'image contient objets, les couleurs utilisées seront prises entre 1 et (tout en gardant 0 pour la couleur du fond). Le tableau servira à résoudre les équivalences entre couleurs trouvées pendant la première phase pour transformer toutes les couleurs équivalentes en une seule couleur.

Question 8 Écrire une fonction diffusion( ) qui effectue la deuxième phase en coloriant avec une même couleur les points ayant des couleurs équivalentes. Donner un ordre de grandeur de son temps d'exécution en fonction de R et C . En déduire la fonction colorier effectuant le coloriage de .