Portail informatique Année 2018 – 2019

CSC 3101 – Algorithmique et langage de programmation

Dans cette série d'exercice, vous apprenez à utiliser les méthodes statiques et vous étudiez des algorithmes classiques de recherche et de tri.

Durée des exercices obligatoires : 2h10 en présentiel
  • Exercice 1 : obligatoire (moyen, ∼1h)
  • Exercice 2 : obligatoire (moyen, ∼1h10)
  • Exercice 3 : entraînement (moyen, ∼1h10)
Le but de cet exercice est de vous familiariser avec les méthodes de classes en travaillant sur des tableaux de caractères. Créez un projet nommé palindrome contenant une classe Palindrome, elle-même contenant une méthode main. Créez une variable words initialisé avec les tableaux de caractères suivants :
  • { 'a', 'n', 'i', 'm', 'a', 'l' },
  • { 'r', 'a', 'd', 'a', 'r' },
  • { 'r', 'e', 's', 'u', 'm', 'a' },
  • { 'r', 'e', 's', 's', 'a', 's', 's', 'e', 'r' },
  • { 'r', 'e', 'l', 'a', 'c', 'e', 'r' },
  • { 'k', 'a', 'y', 'a', 'k' },
  • { 'v', 'i', 'v', 'e', ' ', 'J', 'a', 'v', 'a', ' ', '!' }

On vous rappelle que pour copier/coller sous Linux, il faut sélectionner à la souris la zone que vous souhaitez copier, puis cliquer sur le bouton du milieu de la souris pour coller.

Le tableau words est donc un tableau de (références vers des) tableaux de caractères, dont le type est naturellement char[][]. La déclaration et l'initialisation d'un tableau de tableau s'écrit : char tab[][] = { { 'p', 'r', 'e', 'm', 'i', 'e', 'r' }, { 's', 'e', 'c', 'o', 'n', 'd' }, ... };
Écrivez une méthode de classe nommée printWord(char[] word) affichant chacun des caractères du tableau de caractères word. De façon à éviter un retour à la ligne après l'affichage de chaque caractère, vous pouvez utiliser la méthode System.out.print(String msg) au lieu de la méthode System.out.println(String msg). Utilisez ensuite la méthode printWord pour afficher words[0] à partir de la méthode main. Écrivez une méthode de classe nommée printWords(char[][] words) utilisant printWord pour afficher chacun des tableaux de caractères référencés par words. Utilisez ensuite cette méthode pour afficher les éléments du tableau words à partir de la méthode main. Pour afficher un caractère, il suffit d'utiliser System.out.print(char c) (sans retour à la ligne) ou System.out.println(char c) (avec retour à la ligne). Notez que System.out.println(char c) est une surcharge de System.out.println(String msg) que vous avez déjà utilisé. Vous pouvez aussi utiliser System.out.println() sans paramètre, qui est une troisième surcharge et qui génère uniquement un retour à la ligne sans rien afficher de plus.

Pensez à utiliser la documentation Java (voir menu Liens utiles). Par exemple, vous pouvez voir les méthodes qui permettent d'effectuer des affichages dans le terminal ici.
Écrivez une méthode isPalindrome(char[] word) renvoyant vrai si le mot référencé par word est un palindrome et faux sinon. On vous rappelle qu'un palindrome est un mot dont l'ordre des lettres reste le même qu'on le lise de gauche à droite ou de droite à gauche. C'est par exemple le cas du mot « radar ».

Vous pouvez testez la méthode isPalindrome en affichant son résultat lorsque vous l'invoquez avec words[0] (résultat attendu faux) et avec words[1] (résultat attendu vrai).

Pour mettre en œuvre cet algorithme, vous pouvez par exemple parcourir la première moitié du mot (de 0 à word.length/2) avec une variable entière i, et vérifier que pour tout i, word[i] est égal à word[word.length - i - 1].
Écrivez une méthode printPalindromes(char[][] words) qui n'affiche que les palindromes des tableaux référencés par words. On cherche maintenant à trouver les anacyliques dans notre tableau de mots. Un anacyclique est un mot qui peut se lire dans les deux sens (aux accents près). Contrairement à un palindrome, lorsqu'on lit un anacyclique de droite à gauche, le mot résultant n'est pas forcément le même que celui obtenu en lisant de gauche à droite. De façon à trouver les anacyliques dans notre liste de mot, on va les réécrire en inversant l'ordre des lettres.

Pour commencer, on vous demande d'écrire une méthode reverseWord(char[] word) qui inverse les lettres dans le tableau word (c.-à-d., la lettre à la position i est inversée avec la lettre à la position word.length - i - 1). Vous remarquerez que, comme word est passé par référence, le mot référencé par l'appelant est bien modifié.

Testez votre méthode en inversant le mot words[0] dans la méthode main. Pensez à afficher le mot inverse avec la méthode printWord.

si vous inversez word[i] avec word[word.length - i - 1] puis word[word.length - i - 1] avec word[i], vous allez inverser deux fois les lettres ce qui annule la première inversion !
Pour finir, écrivez une méthode reverseWords(char[][] list) qui inverse l'ordre des lettres de chacun des mots référencés par list. Quel mots et phrases sont des anacycliques ? Tous les mots, sauf le dernier, sont des anacycliques.

Le tri étant décidément une réelle passion chez les informaticiens, nous allons étudier un nouvel algorithme de tri appelé l'algorithme de tri fusion (merge sort en anglais). Cet algorithme est intéressant car il peut être mis en œuvre de façon relativement efficace.

L'algorithme de tri fusion part de l'idée qu'il faut diviser pour mieux régner. Le principe est de prendre un tableau non trié et de le partitionner en deux parties à peu près égales. Ensuite, de façon récursive, l'algorithme trie le tableau de gauche et le tableau de droite. Enfin, l'algorithme fusionne les deux tableaux triés pour construire un tableau contenant tous les éléments triés. Cette opération de fusion est une opération relativement efficace car fusionner des tableaux triés est rapide en terme de temps de calcul.

Le schéma suivant illustre le principe. De façon récursive, l'algorithme commence par partitionner les tableaux jusqu'à obtenir des tableaux de taille 1. Ce tableau de taille 1 est naturellement trié. Ensuite, l'algorithme fusionne les tableaux de façon à reconstruire la liste triée.

La mise en œuvre que nous vous proposons dans cet exercice n'est pas optimisée, mais elle a l'avantage d'être relativement simple à comprendre. Cette mise en œuvre est subdivisée en trois parties. Dans la première partie, nous écrivons la méthode qui fusionne des tableaux triés. Dans la second partie, nous écrivons la méthode qui partitionne les tableaux. Enfin, dans la troisième partie nous complétons notre programme en utilisant les deux méthodes précédentes.

Une illustration fantaisiste de l'algorithme est donnée ici. la fusion Créez un projet nommé msort contenant une classe MergeSort, elle-même contenant une méthode main. Allouez le tableau d'entiers t1 initialisé avec les valeurs 3, 4, 7 et le tableau d'entiers t2 initialisé avec les valeurs 1, 2, 5, 9. Écrivez une méthode display prenant en argument un tableau d'entiers et l'affichant dans le terminal. Vérifiez que votre méthode est correcte en l'appelant avec l'argument t1. Avant de pouvoir fusionner les deux tableaux, nous avons besoin de deux méthodes annexes. La première méthode, nommée int[] right(int[] tab), alloue un tableau de taille tab.length - 1. Elle copie les éléments de droite du tableau tab (c.à-d., à partir de l'élément d'index 1) dans le tableau alloué et renvoie ce nouveau tableau. De façon à tester la méthode right, appelez la dans la méthode main avec l'argument t1, et vérifiez, en affichant le résultat de right avec display, que le nouveau tableau contient 4, 7. La seconde méthode annexe se nomme int[] merge(int val, int[] tab) et effectue l'opération inverse : elle renvoie un nouveau tableau dont le premier élément est val suivi d'une copie des éléments de tab. Vérifiez que votre méthode est correcte en affichant le résultat de merge(1, t1). Nous pouvons maintenant mettre en œuvre la fusion. Pour cela, vous allez écrire une nouvelle méthode nommée merge, prenant en argument deux tableaux t1 et t2 triés et renvoyant la fusion de ces deux tableaux. Le fait qu'il y ait deux méthodes merge ne pose pas de problème car les arguments des deux méthodes sont différents, ce qui permet à Java de savoir quelle méthode on souhaite appeler en fonction des paramètres.

Nous mettons en œuvre merge de façon récursive :
  • Si t1 a une taille égale à zéro, alors merge doit renvoyer t2
  • Si t2 a une taille égale à zéro, alors merge doit renvoyer t1
  • Si t1[0] est plus petit que ou égal à t2[0], alors merge doit renvoyer le tableau construit à partir de t1[0] et du résultat de la fusion de la partie droite de t1 avec le tableau t2. La partie droite de t1 s'obtient en appelant la méthode right et l'ajout à gauche de t1[0] s'obtient en appelant la seconde méthode merge que vous avez défini à la question précédente.
  • Dans le cas inverse, il suffit d'appeler merge en inversant les rôles de t1 et t2.

Testez merge en affichant le résultat de la fusion de t1 et t2 dans la méthode main.
le partitionnement Dans cette partie, nous nous occupons de partitionner un tableau. Commencez par supprimer les tests actuels de la méthode main (les définitions des t1 et t2 incluses). À la place, allouez un tableau d'entiers nommé tab initialisé à 4, 7, 3, 9, 1, 2, 5. Écrivez une méthode int[] extract(int[] tab, int start, int end) qui extrait de tab le sous-tableau commençant à l'indice start inclus et finissant à l'indice end non inclus. Testez votre méthode extract en affichant le résultat de l'extraction de la moitié gauche de tab dans la méthode main. Vous devriez obtenir le tableau 4, 7, 3. le tri fusion Nous pouvons enfin mettre en œuvre l'algorithme du tri-fusion. Écrivez une méthode int[] mergeSort(int[] tab) mettant en œuvre l'algorithme de tri fusion pour renvoyer un tableau contenant les éléments de tab triés. Pour vous guider, nous vous proposons d'utiliser un algorithme récursif :
  • Si tab a une taille inférieure ou égale à 1, alors le tableau est déjà trié et il suffit de le renvoyer.
  • Sinon, il faut appeler mergeSort sur la partie gauche de tab, puis mergeSort sur la partie droite de tab et enfin utiliser merge pour fusionner les résultats des deux appels à mergeSort.
Félicitations ! Vous venez de mettre œuvre votre premier algorithme complexe en Java !
L'algorithme de tri rapide (quick sort en anglais) est un des algorithmes de tri les plus efficaces connus : c'est un algorithme qui a une complexité moyenne optimale, même si cet algorithme peut devenir inefficace dans des cas pathologiques. De plus, l'algorithme de tri rapide est un algorithme de tri en place, c'est-à-dire qu'il ne nécessite pas de tableau annexe pour trier les éléments. L'algorithme de tri fusion que vous avez étudié dans l'exercice précédent a aussi une complexité moyenne optimale, mais il nécessite un tableau annexe, ce qui rend le tri rapide plus efficace en pratique.

L'algorithme de tri rapide part aussi de l'idée qu'il faut diviser pour mieux régner. Toutefois, contrairement au tri rapide, lorsque l'algorithme de tri rapide divise le tableau en deux parties, le tri rapide s'assure que tous les éléments du tableau de gauche sont plus petits que tous les éléments du tableau de droite. Au final, il n'y a donc pas besoin de fusionner les tableaux comme dans le tri fusion puisque les tableaux de gauche et de droite sont déjà bien placés.

Pour y arriver, le tri rapide choisit un élément appelé pivot dans le tableau. Le choix de ce pivot est libre, mais on prend en général l'élément le plus à droite du tableau. Ensuite, l'algorithme place ce pivot à sa place définitive en s'assurant que tous les éléments à gauche du pivot sont plus petits que le pivot et que tous les éléments à droite du pivot sont plus grands. On peut remarquer que, comme le pivot est choisit de façon arbitraire, le tableau de gauche et le tableau de droite ont une taille quelconque. À l'étape suivante, on trie de façon récursive les tableaux de gauche et de droite.

Le schéma ci-dessous illustre l'étape de partitionnement. Après avoir choisit l'élément de droite comme pivot, c'est-à-dire l'élément 5, l'algorithme initialise i et final à 0. L'indice i sert à parcourir le tableau alors que l'indice final sert à savoir quelle sera la place finale du pivot.

Le principe de l'algorithme est de n'incrémenter final qu'après s'être assuré que l'élément à la place final (et donc tous les éléments à gauche de final) est strictement plus petit que le pivot. Par exemple, lorsque i est égal à 1, l'élément à l'indice final (7) est plus grand que le pivot (5), donc l'algorithme n'incrémente pas final. En revanche, dès que l'algorithme s'aperçoit qu'un élément pourrait être bien placé en échangeant des éléments, l'algorithme incrémente final. C'est, par exemple, le cas lorsque i est égal à 2. Dans ce cas, l'élément à la place final vaut 7, l'élément à la place i vaut 3 et l'élément pivot vaut 5. Comme 3 est plus petit que 5, il suffit d'inverser 3 et 7 pour que l'élément à la place final devienne strictement plus petit que le pivot. Une fois cette inversion effectuée, on peut incrémenter final puisque 3 est maintenant bien placé. À la fin de l'étape de partitionnement, on est assuré que les éléments à gauche de final sont strictement plus petits que le pivot, alors que les éléments à droite de final sont plus grands ou égaux. Il suffit alors de déplacer le pivot à la place final, comme illustré à l'étape fin, puis de trier les tableaux de gauche et de droite.
i=0 Teste si tab[i] < pivot vrai => échange tab[i] et tab[final] et incrémente final
i=1 Teste si tab[i] < pivot faux => ne fait rien
i=2 Teste si tab[i] < pivot vrai => échange tab[i] et tab[final] et incrémente final
i=3 Teste si tab[i] < pivot faux => ne fait rien
i=4 Teste si tab[i] < pivot vrai => échange tab[i] et tab[final] et incrémente final
i=5 Teste si tab[i] < pivot vrai => échange tab[i] et tab[final] et incrémente final
i=6 i atteint pivot => échange pivot avec tab[final]
Fin État à la fin du partitionnement Ce qui est à gauche du pivot est plus petit que ce qui est à droite

Une illustration folklorique de l'algorithme est donnée ici. Créez un projet nommé qsort contenant une classe QuickSort, elle-même contenant une méthode main. Allouez le tableau d'entiers tab initialisé avec les valeurs 4, 7, 3, 9, 1, 2, 5, écrivez une méthode display pour afficher le tableau et testez-la avec tab. Avant de s'occuper du partitionnement, nous commençons par une méthode annexe appelée swap. Cette méthode prend en argument un tableau d'entiers et deux indices, et inverse les éléments se trouvant à ces indices. Testez votre méthode en inversant les éléments aux positions 0 et 4 de tab et en affichant le tableau. Écrivez une méthode partition prenant en argument un tableau d'entiers et deux indices nommés start et end, et renvoyant un entier. Cette méthode doit appliquer l'algorithme de partitionnement décrit au début de l'exercice sur le sous-tableau se trouvant entre start et end inclus. La méthode doit renvoyer l'emplacement final (remarque : final étant un mot clé du langage Java, nommez votre variable f). Testez votre méthode en appelant partition(tab, 0, tab.length - 1) dans la méthode main, et vérifiez que le tableau est bien celui indiqué à la dernière étape de l'illustration. Écrivez une méthode quicksort prenant en argument un tableau d'entiers et deux indices nommés start et end. Cette méthode doit trier récursivement le tableau se trouvant entre start et end inclus.
  • Si la différence entre end et start est inférieur ou égale à zéro, le tableau à une taille inférieure ou égale à 1, ce qui signifie que le sous-tableau est trié. Il ne faut donc rien faire.
  • Sinon, c'est que le tableau a une taille au moins égale à deux. La méthode doit donc :
    • Appeler partition pour partitionner le tableau et stocker l'indice final dans une variable locale,
    • Appeler quicksort avec la partie gauche du tableau (entre start et final - 1) et quicksort avec la partie droite du tableau (entre final + 1 et end).

Testez votre méthode quicksort en appelant quicksort(tab, 0, tab.length - 1) dans votre méthode main. Vérifiez que le tableau est bien trié en appelant display.
Finalement, écrivez une seconde méthode quicksort ne prenant qu'un tableau d'entiers en argument, et appelant la seconde méthode quicksort de façon à trier entièrement le tableau passé en argument. Félicitations ! Vous savez maintenant trier des tableaux en Java !