CSC 3101 – Algorithmique et langage de programmation

Dans un projet nommé ast, créez une classe tsp.ast.Main contenant une méthode main.

Écrivez une classe nommée Scalar avec un unique champ (privé) de type entier nommé value. Outre un constructeur permettant d'initialiser le champ value, ajoutez les méthodes d'instance suivantes à Scalar :

• public int get() : cette méthode renvoie la valeur du scalaire,
• public String toString() : cette méthode retourne une chaîne de caractères représentant la valeur du scalaire en utilisant la méthode statique Integer.toString(int i).

Dans la méthode main, créez le scalaire 1 et affichez-le dans le terminal.

On souhaite maintenant créer un arbre capable d'additionner deux scalaires. Écrivez une classe nommée Add contenant deux champs de type Scalar nommés left et right. Le constructeur de Add doit prendre en argument les opérandes de gauche et de droite et les affecter aux champs. Ajoutez les méthodes suivantes à Add :

• public int execute() : renvoie le résultat de l'addition de l'opérande de gauche avec l'opérande de droite.
• public String toString() : renvoie la chaîne de caractères (+ e1 e2), dans laquelle e1 est la représentation de left sous la forme d'une chaîne de caractères et e2 celle de right.

Dans la méthode main, utilisez Add pour calculer et afficher le résultat de l'addition de 1 et 2. Vous veillerez aussi à afficher l'expression et à vérifier que l'affichage produit est bien (+ 1 2).

Créez une interface nommée Node définissant la méthode int execute(). Comme Add possède déjà une méthode execute, vous pouvez aussi directement déclarer que Add met en œuvre Node sans autre modification.

Modifiez Scalar de façon à ce que Scalar mette en œuvre Node. L'évaluation d'un scalaire doit simplement renvoyer sa valeur.

Dans Add, modifiez les types des membres de gauche et de droite de façon à ce que ce qu'ils aient le type générique Node. Modifiez le constructeur de façon à prendre en paramètre deux nœuds, et modifiez la méthode execute de façon à ce qu'elle additionne le résultat de execute() sur le membre de gauche avec le résultat de execute() sur le membre de droite. Vérifiez que vous arrivez toujours à calculer la somme de 1 et 2.

Construisez l'expression correspondant à (+ (+ 1 2) (+ 3 4)) dans la méthode main. Affichez cette expression sur le terminal avant d'afficher le résultat de son évaluation. Sur le terminal, vous devriez voir :

Nous modifions notre code étape par étape pour introduire une nouvelle classe générique représentant n'importe quelle opération. Dans un premier temps, nous insérons une classe abstraite nommée Operation dans l'arbre d'héritage. Cette classe représente une opération quelconque. Pour le moment, cette classe est vide, le but de la question n'étant que de l'insérer de façon à obtenir l'arbre d'héritage/mise en œuvre suivant :

Créez donc une classe abstraite nommée Operation et mettant en œuvre Node. Cette classe est abstraite, car elle ne met pas elle-même en œuvre la méthode execute qui est mise en œuvre dans les classes filles. Modifiez ensuite la classe Add de façon à ce qu'elle ne mette plus en œuvre Node, mais hérite de Operation.

La classe Operation représente n'importe quelle opération et le nombre d'opérandes n'est donc pas fixe (l'inversion du signe a une unique opérande alors que l'addition en a deux). Pour cette raison, ajoutez à la classe Operation :

• un champ privé Node[] ops contenant l'ensemble des opérandes,
• une méthode publique Node op(int i) permettant d'accéder à la i^ième opérande,
• une méthode publique int nbOps() renvoyant le nombre d'opérandes,
• un constructeur publique Operation(Node... ops) permettant d'initialiser le champ ops de Operation. On vous rappelle que Node... ops permet de déclarer une méthode avec un nombre variable d'arguments, et que les arguments sont rangés sous la forme d'un tableau dans ops.

Pour finir, dans le constructeur de Add, utilisez super pour initialiser de façon adéquate le tableau d'opérandes de Operation via le constructeur de Operation. À cette étape, les opérandes sont donc représentés deux fois : une fois dans Operation sous la forme d'un tableau et une fois dans Add sous la forme des champs left et right. Pour le moment, conservez cette double représentation.

Modifiez les méthodes int execute() et String toString() de Add de façon à utiliser la méthode Node op(int i) pour accéder aux opérandes. Vous pouvez maintenant vous débarrasser des champs left et right de Add de façon à ne conserver qu'une unique représentation des opérandes dans la classe Operation.

Nous souhaitons maintenant rendre la méthode String toString() générique en la déplaçant de Add vers Operation. Dans Operation, on connaît les opérandes, mais pas encore l'opération. Pour cette raison, nous effectuons une étape intermédiaire avant de déplacer la méthode String toString(). À cette étape, on vous demande donc juste d'ajouter une méthode abstraite String opString() à la classe Operation et de la mettre en œuvre dans Add. Cette mise en œuvre doit renvoyer la chaîne de caractères "+". Enfin, modifiez Add.toString() de façon à utiliser opString() pour générer le '+'.

Déplacez maintenant String toString() de Add vers Operation. Au lieu de considérer que votre opération a forcément deux opérandes, modifiez la méthode toString() pour qu'elle concatène les nbOps() opérandes.

Écrivez une classe Neg héritant de Operation et permettant d'inverser le signe de son opérande. Modifiez la méthode main de façon à afficher et évaluer l'arbre (+ (+ 1 2) (- (+ 3 4))) qui devrait donner comme résultat -4.

Ajoutez une classe Variable héritant de Scalar et contenant :

• un champ String name indiquant le nom de la variable,
• un constructeur prenant en argument le nom de la variable et pré-initialisant la variable à 0 en utilisant super.

Évaluer une variable revient à renvoyer sa valeur. La méthode int execute() mise en œuvre dans Scalar effectue déjà ce travail et il n'est donc pas nécessaire de la redéfinir dans Variable. En revanche, lorsqu'on affiche une variable avec String toString(), on veut afficher le nom de la variable et non sa valeur. Redéfinissez donc la méthode String toString() dans Variable de façon à afficher le nom de la variable. Dans la méthode main, allouez une variable x, puis affichez et évaluez l'arbre (+ x 20), qui devrait donc être évalué à 20 puisque x est pré-initialisé à 0.

Ajoutez une classe Set, héritant de Operation, et permettant de modifier une variable. Cette opération prend deux arguments : une variable et un nœud quelconque. L'affichage d'une expression doit produire la chaîne de caractère (set! var val) où var est la variable et val un nœud quelconque.

Testez votre opération Set en affichant et évaluant l'expression (set! x 22) avant d'afficher et évaluer l'expression (+ x 20). Ces affichages et évaluations devrait produire l'affichage suivant :

De façon à afficher des résultats intermédiaires, ajoutez une classe Echo héritant de Opération. Cette classe représente une opération (echo expr), qui affiche sur le terminal le résultat de l'évaluation de expr avant de renvoyer ce résultat. Vérifiez que (+ (echo (+ 1 2)) 7) affiche bien 3 pendant l'évaluation et que l'évaluation de l'expression est bien égale à 10.

Pour gérer les conditions, nous avons besoin de booléens. Dans notre petit interpréteur, un scalaire est directement considéré comme un booléen : si sa valeur est égale à 0, c'est que le scalaire est un booléen faux, sinon, c'est que c'est un booléen vrai. À partir de ce choix, ajoutez une classe If permettant d'évaluer une condition. L'arbre d'une condition est (if condition ifTrue ifFalse), où condition, ifTrue et ifFalse sont des nœuds. Vérifiez que (if 1 42 666) s'évalue bien en 42 et (if 0 42 666) s'évalue bien en 666.

Pour écrire des programmes avancés, nous avons besoin de blocs. Un bloc est simplement une opération dont le nombre d'opérandes est variable et telle que son évaluation évalue chacune des opérandes avant de renvoyer le résultat de l'évaluation de son dernier opérande. Lorsque nous affichons l'arbre, nous représentons l'expression correspondant à un bloc par (begin e1 ... en). Ajoutez une classe Begin permettant d'évaluer un bloc. Vérifiez que (if 1 (begin (echo 0) 42) 666) affiche bien 0 pendant l'évaluation et que le résultat de cette évaluation est bien 42.

Ajoutez maintenant la classe Lt permettant d'évaluer un arbre (< e1 e2). Cette évaluation doit renvoyer vraie (1) si e1 est plus petit que e2 et faux (0) sinon.

Finalement, ajoutez une classe While permettant d'évaluer l'arbre (while cond body). L'évaluation doit commencer par évaluer cond. Si le résultat de cette évaluation est vrai (un nombre différent de 0), l'évaluation doit continuer en évaluant body avant de recommencer l'évaluation de cond. Le résultat de l'évaluation doit être celui du dernier body exécuté. Si body n'est jamais exécuté, le résultat de l'évaluation doit être le nombre 0.

Construisez, affichez et interprétez l'arbre (begin (set! x 0) (while (< x 10) (begin (echo x) (set! x (+ x 1))))). Qu'affiche votre programme ?

Pour implémenter l'algorithme que nous verrons plus loin, il nous faut pouvoir manipuler plus en détails les arêtes du graph. Créez une nouvelle classe Edge qui représente une arête. On devra pouvoir obtenir le nœud source, le nœud destination, le poids de la connexion (la distance), et une représentation textuelle de l'arête.
Pour la représentation textuelle, il faudra réimplémenter toString venant d'Object.

Dans la classe Location (CI5), rajoutez une fonction pour obtenir la liste des nœuds du graph et la liste des arêtes du graph. Pour cela, vous pouvez utiliser la classe ArrayList donnée par Java. Voici un exemple de fonctions qui pourront vous être utiles:
On pourra utiliser une fonction auxiliaire récursive. Pour savoir si un nœud a déjà été visité ou pas, on peut rajouter un champ privé visited. Cependant, il ne faut pas oublier de le réinitialiser avant de terminer la fonction !

Pour mieux visualiser nos graphs, nous allons utiliser un outil appelé GraphViz. Cet outil prend en entrée un format appelé dot. Pour notre exemple, nous génèrerons des String qui auront le format suivant: graph{ Evry -- Paris [label=26.0]; San_Sebastian -- Bayonne [label=45.0]; }
Nous commencerons toujours par graph{ et terminerons par }. Ensuite, chaque ligne représente une arête. Nous mettons à gauche et à droite de deux tirets le représentant du nœud, qui est ici son nom avec les espaces remplacés par des _ (on peut utiliser la fonction s.replace). Au bout de la ligne, nous avons le label de l'arête qui est la distance entre les deux villes. Nous l'avons simplifiée ici pour la rendre plus lisible avec un Math.floor.
Écrivez une fonction pour obtenir la représentation sous le format dot d'un graphe.
Bien que vous puissiez utiliser une concaténation de String avec s1 + s2, cela peut se révéler inefficace en pratique. En effet, concaténer deux String revient à concaténer deux tableaux, et donc à recréer un nouveau tableau de taille suffisante et d'y copier les deux String. Cela nous donne rapidement des complexités quadratiques en le nombre de concaténations. À la place, vous pouvez utiliser un StringBuilder.
Une fois la fonction implémentée, vous pouvez visualiser votre graphe en ligne en visitant ce site : https://dreampuf.github.io/GraphvizOnline.
Vous aurez sûrement besoin de la liste des arêtes...

Pour l'algorithme des arbres couvrant, il nous faut pouvoir trier les edges en fonction des poids ou distances. Pour cela nous pouvons utiliser la fonction: Cependant, cette fonction ne prend pas la classe Edge en argument ! Par contre, elle prend l'interface Comparable<Edge> (voir CI7). Cette interface ne contient qu'une seule méthode public int compareTo(Edge edge). Cette dernière renvoie un entier négatif si l'arête actuelle est "plus petite" que l'arête en argument, 0 si elles sont égales et un nombre positif sinon.
Faites en sorte que Edge soit de type Comparable<Edge>. On devra rajouter dans la définition de la classe class Edge implements Comparable<Edge>

Finalement, notre algorithme final va avoir besoin de manipuler des ensembles disjoints. Pour cela, nous allons créer une classe DisjointSets qui fonctionne comme suit :

• Chaque Location se voit attribuer un indice unique qui va correspondre à une position dans un tableau.
• Un champ parents contiendra pour chaque indice son indice parent. Au début, chaque élément est son propre parent.
• Un représentant d'un set est un indice qui est son propre parent. Pour savoir dans quel set appartient un indice, nous devons remonter ses parents jusqu'à trouver un représentant.
• Pour faire l'union de deux sets à partir de deux indices donnés, on commence par prendre les deux représentants. Ensuite, on définit le parent de l'un comme étant le parent de l'autre.

Implémentez dans DisjointSets les fonctions int findRepresentative(Location location) qui nous donne le représentant d'une Location, boolean haveSameRepresentatives(Location l1, Location l2) qui nous dit si deux Location ont les mêmes parents, et void union(Location l1, Location l2) qui unifie deux ensembles pour qu'ils aient le même représentant.
Cet algorithme s'appelle Union-Find.

Quelle est la complexité de l'union dans le pire des cas ?

Pour obtenir l'arbre couvrant minimal, nous allons implémenter l'algorithme de Kruskal dont voici le pseudo-code : Créez un DisjointSet à partir des arêtes A = Les arêtes en ordre croissant ArêtesArbreFinal = [] Pour chaque arête (u, v) dans A Si u et v sont dans des sets différents Ajoutez (u, v) à ArêtesArbreFinal Faire l'union des sets de u et v retourner ArêtesArbreFinal
Implémentez cet algorithme. Notez qu'il ne renvoie pas un arbre à proprement parler, mais que l'on pourrait facilement le créer à partir des arêtes.

Quelle est la complexité de l'algorithme de Kruskal dans le pire des cas avec notre implémentation ?

Obtenez la représentation dot de l'arbre couvrant pour vérifier vos résultats.
On peut extraire une méthode statique de la fonction implémentée plus haut et fonctionnant avec une ArrayList de Edge.