Précisions sur les précisions
Vous dites que le programme sera jugé sur sa vitesse. Je me demandais
cependant si la vitesse en question était la complexité ou alors la vitesse
réelle. En effet on peut être tenté "d'optimiser" en ne multipliant par
exemple pas les appels aux fonctions... quitte à rendre le code moins
lisible. De plus se pose le problème du language. Il me semble que ce sujet
peut être très bien traité en C. Cependant il me semble plus logique de le
faire en java, pour être dans la continuité du cours et car mon binome ne
sait pas programmer en C. Pour toutes ces raisons je partirais plutôt sur un
programme en java dépourvu d'optimisations "d'execution", en donnant de
l'importance à l'algorithme utilisé et non à son code. Mais j'aurais aimé
savoir.
Par « vitesse » j'entend ce qui est dit dans l'énoncé : il faut
implémenter les ensembles de façon efficace (avec les entiers).
Dès lors (mais c'est un peu spécieux...) la complexité des opération
ensemblistes est en cout constant (c'est spécieux parce que ce n'est
vrai que pour des ensembles de taille <= 64).
Donc la complexité attendue est linéaire dans la taille du fichier lu
multiplié par nerrs.
Tout cela en négligeant le traitement du motif (linéaire en sa
longueur), c'est à dire en se plaçant dans le cas d'un petit motif et
d'un gros fichier.
Disons qu'il s'agit de complexité tempérée par un peu de
pragmatisme !
Mon autre question concerne de plus près le sujet, notamment les
"extensions". La première (rajouter # et ?) laisse le programme proche de
l'original et peut donc être fait dans un deuxième temps. Cependant, si on
veut traiter les expressions régulières, il me semble que l'algorithme
utilisé différe assez (notamment pour la gestion efficace de l'ensemble des
états de l'automate), et que donc il faut réécrire cette partie. Ma question
est donc : est ce que si on fait l'extension permettant de traiter les
expressions rationnelles, il faut commencer par faire le sujet de base ?
Non, la machinerie d'exécution des automates ne change pas trop du
sujet simple aux expressions régulières. Ce qui change c'est qu'au
dernier niveau on est bien obligé de se rendre compte que toutes ces
bidouilles sur les entiers sont l'exécution d'un automate
non-déterministe.
Le point clé, qui permet de réaliser les transitions par masquage et
décalage est que les transitions étiquetées par des
caractères sont toujours d'un état numéro k vers un état numéro k+1.
Le travail principal pour passer aux expressions régulière est :
-
Conception.
- Programmation : analyse syntaxique et compilation de l'expression régulière en
un automate encodé par divers tableaux d'entiers.
Enfin, j'ai un peu réflechi aux algorithmes pour le cas des expressions
rationnelles, et il me semble qu'ils sont forcement "pas mal" moins efficaces
à cause du fait que les transitions de l'automate peuvent alors "sauter" des
états et retourner en arrière. Comment savoir s'il y a beaucoup plus efficace
que les algorithmes auquels je pense ? Quels sont les ordres de grandeurs ?
Ce sont en effet les transition “epsilon” (les seules à opérer
entres états de numéros arbiraires) qui font la différence. Je vous
invite à bien lire le paragraphe 3.8 de l'article
agrep.1.ps.
Il montre à peu près comment les implémenter efficacement en les
précalculant.
D'expérience et en négligeant le temps de compilation (minime pour un
petit motif), ajouter ce type de transition aux transitions « caractères »
double à peu près le temps d'exécution.
En conclusion, je pense que de commencer le sujet au niveau PIa en
intprétant les articles en termes d'automates (comme commence à le
faire le sujet) est la démarche la plus productive.