Cours Algorithme : Les Structures Complexes - Graph - Arbre - Sous-ensemble - Permutations

- Sous-ensemble d'un ensemble.
- Arbres (Binaires ou autres).
- Graphes.
- Permutations.
    
  

1 Structures complexes

   

1.1 Exemples 

  

• Sous-ensembles d'un ensemble
• Arbres (binaires ou autres...)
• Graphes
• Permutations 

   

Si un programme construit et utilise une seule structure, des méthodes ad hoc suffisent. Si le programme en utilise beaucoup, il faut penser à l'efficacité des opérations nécessaires.

  

1.2 Opérations utiles

  

• Boucler sur toutes les structures
• Stocker une structure dans l'espace minimum possible (code)
• Récupérer une structure stockée (décode)
• compter les structures

  

Remarque : Il faut souvent choisir une taille de structure (disons n), sinon on ne peut utiliser de fonction de boucle. 

  

1.3 Sous-ensembles et permutations

 

Pas de gros problème :

    

• Sous-ensemble de n objets entier en 0...2n-1
• Permutation? considérer une permutation comme n entiers en 0...n-1 donne une représentation par un entier en 0...nⁿ-1
• Mais tous les entiers ne correspondent pas à une permutation (nⁿ entiers mais n! permutations)
• Interpréter suite a₁, a₂, ..., a_n avec 1 < =a_i < =i: échanger les éléments n et a_n, ensuite n-1 et a_n-1 et ainsi de suite; chaque permutation est générée une seule fois.
• Facile à générer la suite des a à partir d'un entier en 0...n!-1
• (Remarquer existence d'algorithmes plus astucieux qui génèrent toutes les permutations avec une seule transposition à chaque itération) 

     

1.4 Exemple sur les arbres

   

1.4.1 Générer tous les arbres binaires (sans valeurs aux sommets) (de taille n)

 

Pour toute taille i possible du sous-arbre gauche (0...n-1)

générer tous les sous-arbres gauches (taille i)i

générer tous les sous-arbres droits (taille n-1-i)

   

• mais complication de programmation; il faut chaque combinaison possible d'un sous-arbre gauche et droit
• une solution: procédures init et prochain 

   

1.4.2 Compter les arbres (binaires)

  

En ce cas il existe une formule simple mais... 

  

• Soit T(n) le nombre d'arbres de taille n T(0)=1
• Considérer le nombre avec sous-arbre gauche de taille i :

• Programmation dynamique! 

  

1.4.3 Coder un arbre (de taille n, entier en 0...T(n)-1) 

  

• Ordonner les arbres selon la taille de leur sous-arbre gauche, et ensuite selon son code
• code(A)=sommei=0taille(A.gauche)-1T(i)*T(n-1-i)+code(A.gauche)*T(A.droite)+code(A.droite)
• code(arbre.vide)=0 

  

1.4.5 Décoder un arbre

  

Etant donné le code c d'un arbre de taille n, trouver :

   

• La taille du sous-arbre gauche
• Le code du sous-arbre gauche
• Le code du sous-arbre droit
• Et continuer récursivement 

   

1.4.6 En général 

    

Un algorithme de génération donne des algorithmes de codage décodage :

   

• Ordonner les objets selon les choix faits par l'algorithme
• considérer le nombre d'objets susceptibles d'être générés par chaque choix
• ajouter pour coder
• soustraire pour décoder 

    

1.4.7 Des cas plus compliqués 

  

Par exemple des arbres (non binaires), par exemple : Arbre = vide ou racine + ensemble de sous-arbres. Il s’agit d’ensemble, donc il n’y a pas d’ordre.

Pour simplifier, on considère les cas de degré max 2. Un arbre peut être alors représenté par un arbre binaire mais, de plusieurs façons! 

  

1.5 Représentations canoniques 

  

Quand une structure a plusieurs représentations, on en choisit arbitrairement une comme la ``vraie'' ou canonique. Par exemple ordonner les arbres (binaires) par taille, sous-arbre gauche, sous-arbre droit et dire que la représentation canonique d'un arbre est le premier arbre binaire qui en est une représentation.

Pour cela, on utilise une fonction qui permet de décider si une représentation est canonique : 

  

Récurrence pour le nombre d'arbres de taille n (n > 1): 

  

  

Remarques :

    

• arrondir vers le bas dans la division n/2
• les quatre parties sont: un seul sous-arbre (forcément de taille n-1, deux sous-arbres de taille différente, le plus petit de taille i, deux sous-arbres identiques, deux sous-arbres différents de la même taille).
• Mêmes principes pour codage et décodage 

  

1.6 Des Problèmes Difficiles

   

Les problèmes de codage et décodage sont parfois très compliqués. On peut citer comme exemple les graphes sur n sommets de degré maximum (par exemple) 3. On peut les générer en considérant chaque sommet à son tour et ajoutant un nombre d'arêtes jusqu'à 3 - degré actuel. Mais contraintes : pas d'arête à un sommet qui a déjà comme degré 3. Donc, on se retrouve avec une multitude de possibilités de compléter? 

  

1.7 Graphes et isomorphisme!

  

Souvent, on considère deux structures comme identiques si on peut transformer l'une dans l'autre par une permutation des composants. On veut générer (ou compter) un représentant canonique de chaque classe d'équivalence. Mais les classes ne sont pas toutes de la même taille! Il est donc difficile de savoir si une structure est canonique ou de décider si deux structures sont isomorphes (Pb NP-complet).

  

-------------------------------------------------------------------------------------------------------
Précédent : Les Structures Récursives
                       
                Suivant : Fonctions sur les Nombres