907 -- Algorithmique du texte : exemples et applications. : Différence entre versions
De AgregmathKL
Ligne 11 : | Ligne 11 : | ||
*2014-2015 [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:907_2014-2015.pdf|907 Algorithmique du texte : exemples et applications.]] | *2014-2015 [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:907_2014-2015.pdf|907 Algorithmique du texte : exemples et applications.]] | ||
*2015-2016 [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:907_2015-2016.pdf|907 Algorithmique du texte : exemples et applications.]] | *2015-2016 [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:907_2015-2016.pdf|907 Algorithmique du texte : exemples et applications.]] | ||
− | + | *2015-2016 [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:907_2018-2019.pdf|907 Algorithmique du texte : exemples et applications.]] | |
== Développements == | == Développements == |
Version du 22 septembre 2019 à 17:15
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.
Sommaire
Plans scanés
- 2012-2013 907 (démo de rentrée), 907 Algorithmique du texte : exemples et applications.
- 2013-2014 907 Algorithmique du texte : exemples et applications.
- 2014-2015 907 Algorithmique du texte : exemples et applications.
- 2015-2016 907 Algorithmique du texte : exemples et applications.
- 2015-2016 907 Algorithmique du texte : exemples et applications.
Développements
- Plus longue sous-séquence commune
- Automate des occurrences
- Arbres binaires de recherche optimaux
- Analyse LR(0)
Plan Basile et Kévin (2012)
Le plan
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 Possibles
Proposés
- Automate des occurrences [Beauquier, Crochemore]
- Plus longue sous-séquence commune [Cormen]
- Recherche avec -différences [Cormen, Crochemore]
Possibles
- 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)
Références
- Crochemore et al.
- Beaquier Berstel Chrétienne
- Cormen et al.
- Papadimitriou
- E. Incerti : Compression d'images