Le principe du flux, l'arbre et la forêt
Cette feuille en Postscript

1  Flux de caractères

Un flux est essentiellement caractérisé par une opération read qui renvoie « le truc suivant ». En Java les flux de caractères sont réalisés par la classe Reader.

  1. Voici la documentation de la méthode read d'un objet de la classe Reader.
    public int read() throws IOException
    Read a single character. This method will block until a character is available, an I/O error occurs, or the end of the stream is reached.
    Returns:

    The character read, as an integer in the range 0 to 16383 (0x00-0xffff), or -1 if the end of the stream has been reached

    Throws: IOException

    If an I/O error occurs (sic).

    Qu'est-ce au fond qu'un char de Java ? «-1 » est-il un caractère ? Pourquoi read renvoie-t-elle un int ?
  2. Écrire une méthode dump qui prend un flux en argument et affiche son contenu sur la sortie standard.
  3. À partir de quoi pensez-vous que l'on peut créer un flux ?
Solution.

2  Un graphe dans un fichier

On décide de décrire les graphes orientés par des fichiers texte et selon les conventions suivantes :

Par exemple : 

10
0 -> 9  6 ;
1 -> 8 0 ;
2 -> 7  4 ;
4 -> 9 7  3 ;
5 -> 8 ;
6 -> 5 1 ;
    
  1. Concevoir une classe Token des mots (ou lexèmes), écrire le code.
  2. Concevoir une classe Lexer des analyseurs lexicaux réalisée selon le principe du flux. On ne se donnera pas la peine d'écrire le code des méthodes.
  3. Donner le code d'un constructeur Graph (Reader in) pour la classe suivante des graphes.
    class Graph { // Graphes orientés private List [] succ ; Graph (int size) { succ = new List[size] ;} void arc(int src, int dst) { succ[src] = new List (dst,succ[src]) ; }
Solution.

3  Arbre et forêt

Voici deux classes définissant les arbres n-aires

class Tree { // Arbres n-aires int node ; Forest children ; Tree (int node, Forest children) { this.node = node ; this.children = children ; } } class Forest { // Une liste de Tree Tree first ; Forest next ; Forest (Tree first, Forest next) { this.first = first ; this.next = next ; } }

Une forêt est donc une liste ordonnée d'arbres. Dans un arbre, l'ordre gauche-droit des sous-arbres compte, il compte aussi dans une forêt. Enfin la racine de chaque arbre est identifiée par un entier, dans le champ node.

La définition des arbres est inductive, on pourrait aussi l'écrire ainsi :

T::=(n,F)n un entier
F::=єforêt vide
 ∣(T, F)

(En supposant en outre que tous les entiers n sont distincts.)

  1. Y-a-t-il des arbres, des forêts, vides ? Quelles sont les conséquences pour la programmation en Java ?
  2. Définir inductivement l'ordre postfixe des sommets d'une forêt, qui place les descendants avant les ancêtres et les sommets des arbres d'une forêt de gauche à droite. On cherchera à définir inductivement une suite ordonnée de sommets, à partir des définitions des arbres et des forêts.
  3. Écrire deux méthodes postOrder, une pour les forêts l'autre pour les arbres, qui renvoient une liste des sommets dans l'ordre postfixe (à l'aide de notre amie la classe des listes enrichie comme bon nous semble).
Solution.

4  Forêt profonde

Voici quelques méthodes supplémentaires pour la classe Graph.

Tree dfsTree(int node, boolean [] vu) { return new Tree(node, dfsForest(succ[node], vu)) ; } Forest dfsForest(List nodes, boolean [] vu) { if (nodes == null) return null ; int node = nodes.val ; if (!vu[node]) { vu[node] = true ; Tree t = dfsTree(node, vu) ; Forest f = dfsForest(nodes.next, vu) ; return new Forest (t, f) ; } else return dfsForest(nodes.next, vu) ; } Forest dfs(List nodes) { boolean [] vu = new boolean [succ.length] ; return dfsForest(nodes, vu) ; } Forest dff() { List allNodes = null ; for (int i = succ.length-1 ; i >= 0 ; i--) allNodes = new List (i, allNodes) ; return dfs(allNodes) ; }
  1. Que réalise ce code ?
  2. Voici une forêt produite à partir du graphe de l'exercice 2.
    Les arcs de la forêt ne regroupent pas tous les arcs du graphe d'origine, il manque les arcs 1 -> 0, 5 -> 8, 4 -> 9 et 2 -> 7. Ajouter ces arcs à la forêt et caractériser les nouveaux arcs en fonction de leur nature, arcs de retour, transverses, et de descente.
  3. Classifier précisément les arcs du graphe par rapport à la forêt, et énoncer la propriété-clé des arcs transverses.
  4. L'ordre préfixe des sommets d'une forêt, place les descendants après les ancêtres et les sommets des arbres d'une forêt de gauche à droite. Donner une définition précise.
  5. Caractériser les quatres sortes d'arcs produites par dff à l'aide des deux ordres préfixe et postfixe sur les sommets. Autrement dit, finir de remplir ce tableau :
    n → mpréfixepostfixe 
    Fn ≤ mn ≥ m 
    D  
    R  
    T  
  6. Quel est le rapport entre arcs de retour et les cycles du graphe ?
Solution.

5  Tri topologique

  1. Un tri topologique est une suite n1, n2, …, nk des sommets du graphe, telle que si il existe un chemin de n à m, alors n précède m dans la suite. Quid des cycles ?
  2. En examinant le tableau de la question 4-5, réaliser un tri topologique en une ligne.
  3. À quoi peut bien servir le tri topologique ?
Solution.
Ce document a été traduit de LATEX par HEVEA