Previous Up

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 :
  1. Conception.
  2. 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.
Previous Up