Semestre 1 :
Ces matières m'ont permis d'approfondir ma compréhension des algorithmes et de leur efficacité. En R1.01, j'ai appris les bases de l'algorithmique (boucles, tableaux, structures de données), mais surtout les premières notions de comparaison d'algorithmes : mesurer le temps d'exécution, compter les opérations élémentaires, et comparer différentes approches de tri ou de recherche. C'est aussi dans cette ressource que j'ai découvert les ArrayList en Java, indispensables pour la SAE. En R1.03 (Architecture des ordinateurs), j'ai mieux compris comment un programme s'exécute au niveau matériel, ce qui m'a aidé à comprendre pourquoi certains algorithmes sont plus rapides que d'autres selon la manière dont ils accèdent à la mémoire. Les ressources R1.06 (Mathématiques discrètes) et R1.07 (Outils mathématiques fondamentaux) m'ont donné les outils pour formaliser la complexité des algorithmes : la notation theta, le raisonnement par récurrence, et l'arithmétique modulaire, directement utile pour comprendre la fonction de hachage de Rabin-Karp.
Dans cette SAE, nous devions implémenter en Java quatre algorithmes de recherche de sous-chaîne dans un texte (Naïf, Knuth-Morris-Pratt, Rabin-Karp et Boyer-Moore), puis comparer leur efficacité sur différents types de textes. Le travail se faisait en binôme.
Nous avons commencé par l'algorithme naïf, car c'était le plus simple à comprendre et à coder. Cela nous a permis d'obtenir rapidement une base fonctionnelle et de mettre en place la structure du projet : les ArrayList pour stocker le texte, la génération de textes aléatoires et répétitifs, ainsi que les méthodes de test. Une fois le naïf opérationnel, nous disposions d'un point de comparaison fiable pour les trois autres algorithmes.
Pour KMP, nous avons mis du temps à comprendre le tableau de la fonction préfixe. Nous avons d'abord tenté de coder directement à partir du sujet, mais nous nous trompions dans les décalages. Nous avons donc choisi de dérouler l'algorithme à la main, sur papier, avec plusieurs exemples, avant de recoder. Cette étape nous a débloqués. Rabin-Karp était plus mathématique, avec une fonction de hachage déroulante en base 101, mais une fois la formule du sujet comprise, l'implémentation a été assez directe. Boyer-Moore était clairement le plus complexe, avec ses deux tableaux (tableau des sauts et tableau des bons suffixes). Nous nous sommes réparti le travail : l'un codait le tableau 1, l'autre le tableau 2, puis nous avons assemblé le tout.
Nous avons travaillé régulièrement sur les créneaux en autonomie. Lorsque nous bloquions sur un algorithme, nous passions au suivant pour ne pas perdre de temps, puis nous y revenions avec un regard neuf. Pour les tests d'efficacité, nous avons fait tourner chaque algorithme sur des textes de 500 à 10 000 caractères, en comptant les opérations élémentaires et en mesurant le temps d'exécution avec System.nanoTime(). Nous avons ensuite présenté les résultats dans des tableaux et tracé les courbes pour le rapport PDF.
La ressource principale mobilisée est R1.01 (Initiation au développement). C'est grâce à elle que nous avons su manipuler les ArrayList (ArrayList<Character> pour le texte, ArrayList<Integer> pour les positions trouvées), écrire des boucles imbriquées pour les comparaisons caractère par caractère, et structurer chaque algorithme dans sa propre classe Java. Les techniques de test vues en cours (testAlgo et testCasAlgo) nous ont aussi servi à valider chaque algorithme avant de passer aux mesures d'efficacité.
R1.03 (Architecture des ordinateurs) nous a aidés à comprendre pourquoi certains algorithmes sont plus performants. Par exemple, le fait que KMP ne revienne jamais en arrière dans le texte réduit les accès mémoire, ce qui explique en partie sa rapidité par rapport au naïf sur les textes répétitifs.
R1.06 (Mathématiques discrètes) a été directement utile pour Rabin-Karp. L'arithmétique modulaire et le calcul en base b = 101, utilisé dans la fonction de hachage, reprennent des notions vues en cours. Sans ces bases, la formule de hachage déroulante aurait été incompréhensible.
R1.07 (Outils mathématiques fondamentaux) nous a aidés pour l'analyse de la complexité. Nous avons utilisé les notions de polynômes et de fonctions pour évaluer f(n) de l'algorithme naïf et en déduire son theta. Les notions de suites nous ont aussi servi à comprendre le comportement asymptotique des algorithmes.
Pour la partie anglaise, toute notre Javadoc était rédigée en anglais comme demandé, et nous avons consulté des ressources en ligne en anglais pour mieux comprendre les algorithmes, notamment la page Wikipedia anglaise de Boyer-Moore, plus claire que la version française..
Pour AC12.01 (Analyser un problème avec méthode), nous avons découpé le problème de recherche de sous-chaîne en sous-problèmes clairement définis pour chaque algorithme. Par exemple, pour KMP, nous avons distingué la construction du tableau de la fonction préfixe et la phase de recherche dans le texte. Pour Boyer-Moore, nous avons séparé la construction du tableau des sauts, celle du tableau des bons suffixes, ainsi que la comparaison à rebours. Ce découpage nous a permis de coder et de tester chaque partie indépendamment, avant de les assembler.
Pour AC12.02 (Comparer des algorithmes pour des problèmes classiques), c'était le coeur de la SAE. Nous avons comparé les quatre algorithmes sur deux types de textes : des textes aléatoires et des textes répétitifs (type "AAAAAAA..."). Les résultats ont montré que le naïf était nettement plus lent sur les textes répétitifs, car il revient toujours au début du motif. À l'inverse, KMP restait stable quel que soit le type de texte. Rabin-Karp avait des performances proches du naïf dans le pire cas, mais meilleures en moyenne. Enfin, Boyer-Moore était le plus rapide sur les textes aléatoires grâce à ses grands décalages. Nous avons produit des graphiques qui illustrent clairement ces différences, puis nous les avons commentés dans notre rapport.
Pour AC12.03 (Formaliser et mettre en oeuvre des outils mathématiques pour l'informatique), nous avons calculé f(n) de façon exacte pour l'algorithme naïf, puis déduit que sa complexité est en theta(n * m) dans le pire cas. Pour Rabin-Karp, nous avons implémenté la fonction de hachage déroulante, fondée sur l'arithmétique en base 101 et les codes ASCII. Nous avons aussi utilisé des compteurs d'opérations élémentaires (variable cpt de type long dans la boucle la plus imbriquée) afin de mesurer empiriquement la complexité de chaque algorithme et de confronter nos mesures à la théorie.