tc_info:2023-td-texte-corr

Différences

Ci-dessous, les différences entre deux révisions de la page.

Lien vers cette vue comparative

Les deux révisions précédentes Révision précédente
Prochaine révision		 Révision précédente
tc_info:2023-td-texte-corr [2023/11/29 12:51] – [Exercice 6] edaucetc_info:2023-td-texte-corr [2023/12/01 09:49] (Version actuelle) – [Exercice 4 : Expressions régulières] edauce
Ligne 15: Ligne 15:
     i <-- 0     i <-- 0
     tant que i < n - m:     tant que i < n - m:
-        j <-- i+        j <-- 0
         tant que j < m et d[i+j] = t[j] :         tant que j < m et d[i+j] = t[j] :
             j += 1             j += 1
Ligne 33: Ligne 33:
     i <-- 0     i <-- 0
     tant que i < n - m:     tant que i < n - m:
-        j <-- i+        j <-- 0
         tant que j < m et d[i+j] = t[j] :         tant que j < m et d[i+j] = t[j] :
             j += 1             j += 1
Ligne 39: Ligne 39:
            l.append(i)            l.append(i)
         i <-- i + 1            i <-- i + 1   
 +    retourner l
 </code> </code>
 +
  
 Cette approche a un inconvénient : après une comparaison infructueuse, la comparaison suivante débutera à la position i + 1, sans tenir aucun compte de celles qui ont déjà eu lieu à l'itération précédente, à la position i.  Cette approche a un inconvénient : après une comparaison infructueuse, la comparaison suivante débutera à la position i + 1, sans tenir aucun compte de celles qui ont déjà eu lieu à l'itération précédente, à la position i. 
  
-L'algorithme de Knuth-Morris-Pratt examine d'abord la chaîne ''t'' et en déduit des informations permettant de ne pas comparer chaque caractère plus d'une fois. +** Algorithme de Boyer-Moore ** 
 + 
 +L'algorithme de Boyer-Moore examine d'abord la chaîne ''t'' et en déduit des informations permettant de ne pas comparer chaque caractère plus d'une fois. 
  
-On regardera une version simplifiée de l'algo de Knuth-Morris-Pratt : 
   * On suppose qu'on peut tester si un caractère ''c'' appartient au motif ''t'' en temps constant   * On suppose qu'on peut tester si un caractère ''c'' appartient au motif ''t'' en temps constant
   * Le but est de calculer un décalage permettant de ne pas inspecter les positions où il n'y a aucune chance de trouver le motif ''t''.   * Le but est de calculer un décalage permettant de ne pas inspecter les positions où il n'y a aucune chance de trouver le motif ''t''.
   * On commence par chercher la position ''i = m - 1''    * On commence par chercher la position ''i = m - 1'' 
-  * On inspecte la chaîne ''d'' de ''i'' à ''i - m'' décroissant, et on s'arrête au premier caractère commun (i.e. ''j''<= ''i'' t.q. ''d[i-j]'' appartient à ''t'') +  * Soit ''c'' = ''d[i]'' le dernier caractère 
-  * Soit ''c'' = ''d[i-j]'' le caractère commun +  * Si ''c'' n'est pas dans ''t'', le décalage vaut ''m'' 
-  * On note ''k'' la position de la première occurrence de ''c'' dans ''t[:m-j-1]'' +  * Sinon on note ''k'' la position de la dernière occurrence de ''c'' dans ''t'' 
-  * Le décalage est égal à ''m - 1 - j - k'' +    * si ''k'' vaut ''m-1'' (dernier caractère), le décalage vaut ''m'' 
-  * Si on ne trouve rien, le décalage vaut ''m''+    * Sinon le décalage est égal à ''m - 1 - k'' 
 + 
 + 
 +**Exemple:** 
 +  RECHERCHE DE CHAINES CODEES EN MACHINE 
 +  CHINE 
 +       CHINE 
 +            CHINE 
 +               CHINE 
 +                CHINE 
 +                     CHINE 
 +                          CHINE 
 +                               CHINE 
 +                                   CHINE 
 +  RECHERCHE DE CHAINES CODEES EN MACHINE
  
-A illustrer au tableau : 
-{{:tc_info:corr:reherche-chine.png?400|}} 
  
-Si vous en avez le courage, voici le code :+Voici le code :
 <code> <code>
 Algo : recherche améliorée Algo : recherche améliorée
Ligne 66: Ligne 81:
     i <-- m - 1     i <-- m - 1
     tant que i < n :     tant que i < n :
-      # PRE-TRAITEMENT +      # PRE-TRAITEMENT       
-      j <-- 0 +        c = d[i]   
-      tant que j < m  - 1: +        si c appartient à t: 
-        c = d[i - j]   +           k <-- dernière_occurrence(c, t) 
-        si c appartient à t[:m-j-1] +           si k == m-1: 
-           k <-- dernière_occurrence(c, t[:m-j-1])   +               decalage <-- m 
-           decalage <--  m - 1 - j  - k +           sinon   
-           break +               decalage <--  m - 1  - k  
-        sinon +        sinon: 
-           j += 1   +           decalage <-- m
-      si j == m - 1: +
-         decalage <-- m+
       # TRAITEMENT       # TRAITEMENT
       j <-- 0       j <-- 0
Ligne 167: Ligne 180:
  
 <note tip> <note tip>
 +Réponse : ''\w+\.(gif|png|jpg)''
  
-''TODO'' +{{:tc_info:automate-term.png?600|}}
 </note> </note>
 +
 +** 4. Donnez une expression régulière pour reconnaître les URL commençant par {{https://|https://}}.**
 +
 +Correction : 
 +<code>
 +https://[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}
 +</code>
 +
 +** 5. Écrivez une expression régulière pour reconnaître la date et l'heure au format ''YYYY-MM-DD (HH:MM)'' **
 +Correction : 
 +<code>
 +\d\d\d\d-(0[1-9]|1[12])-(0[1-9]|[12][0-9]|3[0-1]) \((0[0-9]|1[0-9]|2[0-3]):[0-5][0-9]\)
 +</code>
 +
 ==== Exercice 5 ==== ==== Exercice 5 ====
 +
 1.  **Ecrire l'algorithme de reconnaissance de l'expression régulière ''(a|b)*c''** 1.  **Ecrire l'algorithme de reconnaissance de l'expression régulière ''(a|b)*c''**
 <code python> <code python>
  • tc_info/2023-td-texte-corr.1701258707.txt.gz
  • Dernière modification : 2023/11/29 12:51
  • de edauce