907 -- Algorithmique du texte : exemples et applications. : Différence entre versions
De AgregmathKL
(7 révisions intermédiaires par 4 utilisateurs non affichées) | |||
Ligne 1 : | Ligne 1 : | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
= Plans scanés = | = Plans scanés = | ||
− | 2012 [[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|Plan scanné de l'année 2013-2014]] |
+ | *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|Plan scanné de l'année 2015-2016]] | ||
+ | *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 43 : | 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 63 : | 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]
- 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