907 -- Algorithmique du texte : exemples et applications. : Différence entre versions
De AgregmathKL
| Ligne 1 : | Ligne 1 : | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
= Plans scanés = | = Plans scanés = | ||
| − | *2012-2013 [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:907_2012-2013.pdf| | + | *2012-2013 [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:907_2012-2013.pdf|Plan démo de rentrée de l'année 2012-2013]], [[Média:907_2012-2013_2.pdf|Plan scanné de l'année 2012-2013]] |
| − | *2013-2014 [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:907_2013-2014.pdf| | + | *2013-2014 [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:907_2013-2014.pdf|Plan scanné de l'année 2013-2014]] |
| − | *2014-2015 [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:907_2014-2015.pdf| | + | *2014-2015 [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:907_2014-2015.pdf|Plan scanné de l'année 2014-2015]] |
| − | *2015-2016 [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:907_2015-2016.pdf| | + | *2015-2016 [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:907_2015-2016.pdf|Plan scanné de l'année 2015-2016]] |
| − | *2018-2019 [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:907_2018-2019.pdf| | + | *2018-2019 [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:907_2018-2019.pdf|Plan scanné de l'année 2018-2019]] |
| − | |||
| − | |||
| − | |||
| − | |||
| − | = | + | == Autre plan : Basile et Kévin (2012) == |
| − | + | ||
Intro définition texte. | Intro définition texte. | ||
=== I - Recherche de Motifs [Beauquier]=== | === I - Recherche de Motifs [Beauquier]=== | ||
| Ligne 51 : | Ligne 39 : | ||
#* Application à la compression d'images | #* Application à la compression d'images | ||
| − | + | ||
| − | === | + | = Développements = |
| + | <DynamicPageList> | ||
| + | category = Développement de la leçon 907 | ||
| + | </DynamicPageList> | ||
| + | |||
| + | == Autres développements == | ||
* [[Automate des occurrences]] [Beauquier, Crochemore] | * [[Automate des occurrences]] [Beauquier, Crochemore] | ||
* [[Plus longue sous-séquence commune]] [Cormen] | * [[Plus longue sous-séquence commune]] [Cormen] | ||
* Recherche avec <math>k</math>-différences [Cormen, Crochemore] | * Recherche avec <math>k</math>-différences [Cormen, Crochemore] | ||
| − | |||
| − | |||
* Algorithmes de recherche de motifs : | * Algorithmes de recherche de motifs : | ||
** Morris-Prat [Beauquier] | ** Morris-Prat [Beauquier] | ||
| Ligne 71 : | Ligne 62 : | ||
* ... éventuellement de la compilation (analyse lexicale et syntaxique) | * ... éventuellement de la compilation (analyse lexicale et syntaxique) | ||
| − | == | + | |
| + | = Commentaires = | ||
| + | Par "texte", on entend "information" : programme, document, ADN... | ||
| + | * Comparaison de deux séquences (comparaison d'un mot avec une entrée d'un dictionnaire puis correction etc., comparaison d'ADN) | ||
| + | * Recherche d'une chaîne dans une autre (dans un logiciel de traitement de texte, un moteur de recherche sur l'Internet | ||
| + | * Stockage de texte : compression via les arbres de Huffman | ||
| + | |||
| + | Extrait du site [http://agreginfo.free.fr] concernant cette leçon. | ||
| + | |||
| + | |||
| + | = Références = | ||
* Crochemore et al. | * Crochemore et al. | ||
* Beaquier Berstel Chrétienne | * Beaquier Berstel Chrétienne | ||
* Cormen et al. | * Cormen et al. | ||
| − | |||
* Papadimitriou | * Papadimitriou | ||
* E. Incerti : Compression d'images | * E. Incerti : Compression d'images | ||
| + | |||
| + | |||
[[Category:Leçon d'informatique]] | [[Category:Leçon d'informatique]] | ||
| + | [[Category:Anciennes leçons]] | ||
Version actuelle en date du 22 avril 2022 à 10:46
Sommaire
Plans scanés
- 2012-2013
Plan démo de rentrée de l'année 2012-2013, Plan scanné de l'année 2012-2013 - 2013-2014 Plan scanné de l'année 2013-2014
- 2014-2015 Plan scanné de l'année 2014-2015
- 2015-2016 Plan scanné de l'année 2015-2016
- 2018-2019 Plan scanné de l'année 2018-2019
Autre plan : Basile et Kévin (2012)
Intro définition texte.
I - Recherche de Motifs [Beauquier]
- But et algorithme naïf
- Cadre de la recherche de motif
- Algo naïf
- Algorithmes de Morris-Pratt
- Amélioration Knuth-Morris-Pratt
- Automate des occurences (DEV)
- Algorithme d'Horspool-Boyer-Moore
- Bilan et applications
- Tableau comparatif des complexités [Cormen + Beauquier]
- Applications
- à l'analyse lexicale.
- à la recherche dans un éditeur de texte.
II - Comparaisons entre mots
- Distances [Croch]
- préfixe, suffixe, sous-mot, édition, Hamming
- Alignements
- Application génétique
- Plus longue sous-suite commune (DEV)
III - Recherche approchée
- Avec Joker [Crochemore]
- Avec
différences (DEV) - Application correction orthographique ?
IV - Compression
- Codage de Huffman [Incerti]
- Application à la compression d'images
Développements
- Plus longue sous-séquence commune
- Automate des occurrences
- Arbres binaires de recherche optimaux
- Analyse LR(0)
Autres développements
- Automate des occurrences [Beauquier, Crochemore]
- Plus longue sous-séquence commune [Cormen]
- Recherche avec -différences [Cormen, Crochemore]
- Algorithmes de recherche de motifs :
- Morris-Prat [Beauquier]
- Knuth-Morris-Pratt [Beauquier, Knuth]
- Automate des occurrences [Beauquier, Crochemore]
- Algorithme de Rabin-Karp [Cormen]
- Algorithmes de programmation dynamique :
- Recherche avec -différences [Cormen, Crochemore]
- Plus longue sous-séquence commune [Cormen]
- Calcul de la distance d'édition [Papadimitriou]
- Recherche avec
- Tri des suffixes [Crochemore]
- Méthode de compression Ziv-Lempel77 [Incerti]
- ... éventuellement de la compilation (analyse lexicale et syntaxique)
Commentaires
Par "texte", on entend "information" : programme, document, ADN...
- Comparaison de deux séquences (comparaison d'un mot avec une entrée d'un dictionnaire puis correction etc., comparaison d'ADN)
- Recherche d'une chaîne dans une autre (dans un logiciel de traitement de texte, un moteur de recherche sur l'Internet
- Stockage de texte : compression via les arbres de Huffman
Extrait du site [1] concernant cette leçon.
Références
- Crochemore et al.
- Beaquier Berstel Chrétienne
- Cormen et al.
- Papadimitriou
- E. Incerti : Compression d'images
