Automate des occurrences : Différence entre versions
De AgregmathKL
(Page créée avec « Ce développement présente une implémentation de l'algorithme de Morris-Pratt par un automate fini : L'automate des occurrences. == Remarques == == Le développement == ... ») |
|||
| (Une révision intermédiaire par un autre utilisateur non affichée) | |||
| Ligne 2 : | Ligne 2 : | ||
== Remarques == | == Remarques == | ||
| + | * Il faut pouvoir expliciter l'algorithme qui calcule la fonction de transition dans l'automate (algorithme de calcul des bords maximaux [Beauquier] modifié) | ||
| + | * Il y a une démonstration par récurrence [Cormen, p.886] qui évite l'introduction de morphisme d'automate. | ||
== Le développement == | == Le développement == | ||
| + | |||
| + | [[Fichier:Pdf.png|alt=Tex|link=|24px]] [[Media:Automate occurrences.pdf | Automate des occurrences.pdf ]] | ||
== Recasements == | == Recasements == | ||
| Ligne 12 : | Ligne 16 : | ||
* Beauquier p.350 à 354 | * Beauquier p.350 à 354 | ||
(Il est à noter que la preuve donnée du théorème (Proposition 1.9) est incomplète). | (Il est à noter que la preuve donnée du théorème (Proposition 1.9) est incomplète). | ||
| + | |||
| + | [[Category: Développement de la leçon 907]] | ||
| + | [[Category: Développement de la leçon 908]] | ||
Version actuelle en date du 26 février 2015 à 21:12
Ce développement présente une implémentation de l'algorithme de Morris-Pratt par un automate fini : L'automate des occurrences.
Remarques
- Il faut pouvoir expliciter l'algorithme qui calcule la fonction de transition dans l'automate (algorithme de calcul des bords maximaux [Beauquier] modifié)
- Il y a une démonstration par récurrence [Cormen, p.886] qui évite l'introduction de morphisme d'automate.
Le développement
Recasements
- 907 -- Algorithmique du texte : exemples et applications.
- 908 -- Automates Finis, exemples et applications
Références
- Beauquier p.350 à 354
(Il est à noter que la preuve donnée du théorème (Proposition 1.9) est incomplète).
