907 -- Algorithmique du texte : exemples et applications. : Différence entre versions

De AgregmathKL
Aller à : navigation, rechercher
 
(17 révisions intermédiaires par 6 utilisateurs non affichées)
Ligne 1 : Ligne 1 :
−
Par "texte", on entend "information" : programme, document, ADN...
+
= Plans scanés =
−
* Comparaison de deux séquences (comparaison d'un mot avec une entrée d'un dictionnaire puis correction etc., comparaison d'ADN)
+
*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]]
−
* Recherche d'une chaîne dans une autre (dans un logiciel de traitement de texte, un moteur de recherche sur l'Internet
+
*2013-2014 [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:907_2013-2014.pdf|Plan scanné de l'année 2013-2014]]
−
* Stockage de texte : compression via les arbres de Huffman
+
*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]]
  
−
Extrait du site [http://agreginfo.free.fr] concernant cette leçon.
 
  
−
= Plan Basile et Kévin (2012) =
+
== Autre plan : Basile et Kévin (2012) ==
−
== Le plan ==
+
 
Intro définition texte.
 
Intro définition texte.
−
=== I - Recherche de Motifs ===
+
=== I - Recherche de Motifs [Beauquier]===
 
# But et algorithme naïf
 
# But et algorithme naïf
−
# Algorithmes de Morris-Pratt et Knuth-Morris-Pratt
+
#* Cadre de la recherche de motif
 +
#* Algo naïf
 +
# Algorithmes de Morris-Pratt  
 +
#* Amélioration Knuth-Morris-Pratt
 
#* Automate des occurences (DEV)
 
#* Automate des occurences (DEV)
 
# Algorithme d'Horspool-Boyer-Moore
 
# Algorithme d'Horspool-Boyer-Moore
−
# Bilan
+
# 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 ===
 
=== II - Comparaisons entre mots ===
−
# Distances
+
# Distances [Croch]
 
#* préfixe, suffixe, sous-mot, édition, Hamming
 
#* préfixe, suffixe, sous-mot, édition, Hamming
−
# Plus longue sous-suite commune (DEV)
+
# Alignements
 
#* Application génétique
 
#* Application génétique
 +
# Plus longue sous-suite commune (DEV)
  
 
=== III - Recherche approchée ===
 
=== III - Recherche approchée ===
−
# Avec Joker
+
# Avec Joker [Crochemore]
 
# Avec <math>k</math> différences (DEV)
 
# Avec <math>k</math> différences (DEV)
 
# Application correction orthographique ?
 
# Application correction orthographique ?
Ligne 31 : Ligne 39 :
 
#* Application à la compression d'images
 
#* Application à la compression d'images
  
−
== Développements Possibles ==
+
 
−
* Morris-Prat (Beauquier)
+
= Développements =
−
* Knuth-Morris-Pratt
+
<DynamicPageList>
−
** Algorithme en lui-même
+
category            = Développement de la leçon 907
−
** Automate des occurences
+
</DynamicPageList>
−
* Plus longue sous-suite commune (Cormen)
+
 
−
* Tri des suffixes (Crochemore)
+
== Autres développements ==
−
* Algorithme de Rabin-Karp
+
* [[Automate des occurrences]] [Beauquier, Crochemore]
−
* Calcul de la distance d'édition
+
* [[Plus longue sous-séquence commune]] [Cormen]
−
* Recherche avec <math>k</math> différences
+
* Recherche avec <math>k</math>-différences [Cormen, Crochemore]
−
* Méthode de compression Ziv-Lempel77
+
* 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 <math>k</math>-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)
 
* ... éventuellement de la compilation (analyse lexicale et syntaxique)
  
−
== Références ==
+
 
 +
= 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.
 +
* Papadimitriou
 +
* E. Incerti : Compression d'images
 +
 
 +
 
 +
 
 +
[[Category:Leçon d'informatique]]
 +
[[Category:Anciennes leçons]]

Version actuelle en date du 22 avril 2022 à 10:46

Plans scanés


Autre plan : Basile et Kévin (2012)

Intro définition texte.

I - Recherche de Motifs [Beauquier]

  1. But et algorithme naïf
    • Cadre de la recherche de motif
    • Algo naïf
  2. Algorithmes de Morris-Pratt
    • Amélioration Knuth-Morris-Pratt
    • Automate des occurences (DEV)
  3. Algorithme d'Horspool-Boyer-Moore
  4. 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

  1. Distances [Croch]
    • préfixe, suffixe, sous-mot, édition, Hamming
  2. Alignements
    • Application génétique
  3. Plus longue sous-suite commune (DEV)

III - Recherche approchée

  1. Avec Joker [Crochemore]
  2. Avec k différences (DEV)
  3. Application correction orthographique ?

IV - Compression

  1. Codage de Huffman [Incerti]
    • Application à la compression d'images


Développements


Autres développements

  • Automate des occurrences [Beauquier, Crochemore]
  • Plus longue sous-séquence commune [Cormen]
  • Recherche avec k-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 :
  • 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
Récupérée de « https://minerve.ens-rennes.fr/index.php?title=907_--_Algorithmique_du_texte_:_exemples_et_applications.&oldid=4940 »