Différences
Ci-dessous, les différences entre deux révisions de la page.
Les deux révisions précédentes Révision précédente Prochaine révision | Révision précédente | ||
tc_info:td3 [2018/10/03 12:35] – [Exercice 4 : Distances entre chaînes de caractères] edauce | tc_info:td3 [2019/11/14 11:02] (Version actuelle) – edauce | ||
---|---|---|---|
Ligne 1: | Ligne 1: | ||
+ | ==== TD5 : Algorithmes sur les textes ==== | ||
+ | < | ||
+ | {{ : | ||
+ | </ | ||
+ | ==== Exercice 1 : Chercher un mot ==== | ||
+ | Soit une chaîne de caractères '' | ||
+ | - Donner l' | ||
+ | - Donner de même l' | ||
+ | - (* *) On suppose qu'on peut tester si un caractère '' | ||
+ | |||
+ | ==== Exercice 2 : Compter les mots ==== | ||
+ | 1. Écrire un algorithme qui compte le nombre de mots dans un texte. | ||
+ | |||
+ | Remarque : On considère comme caractère d' | ||
+ | |||
+ | 2. (*) Dessiner l' | ||
+ | ==== Exercice 3 : Palindrome ==== | ||
+ | 1. Écrire un algorithme récursif permettant de savoir si un tableau de caractères est un palindrome (un palindrome se lit "à l' | ||
+ | |||
+ | Remarque : on ne considère ni la ponctuation, | ||
+ | |||
+ | Quelle est sa complexité? | ||
+ | |||
+ | 2. (*) Pouvez-vous définir un automate fini capable de reconnaître les palindromes? | ||
+ | |||
+ | ==== Exercice 4 : Distances entre chaînes de caractères ==== | ||
+ | |||
+ | On cherche à exprimer une distance entre deux chaînes de caractères. | ||
+ | |||
+ | |||
+ | Une distance entre 2 textes d1 et d2 est telle que : | ||
+ | * dist(d1,d2) = dist(d2,d1) | ||
+ | * dist(d1,d2) ≥ 0 | ||
+ | * dist(d1,d2) + dist(d2,d3) ≥ dist(d1,d3) | ||
+ | * | ||
+ | === Distance de Hamming | ||
+ | La distance de Hamming entre deux chaînes de même taille est définie comme le nombre de caractères non appariés. Ainsi la distance de Hamming entre " | ||
+ | |||
+ | === Distance d' | ||
+ | La distance d’édition est définie, pour deux chaînes de longueur quelconque, comme le nombre minimal d’opérations permettent de transformer d1 en d2, avec les opérations suivantes : | ||
+ | * **ins**(a) ⇢ insertion du caractère a | ||
+ | * **perm** (a, b) ⇢ remplacement de a par b | ||
+ | * **del** (a) ⇢ suppression du caractère a | ||
+ | |||
+ | Il existe différentes manières de transformer la chaîne d1 en d2. On peut par exemple supprimer tous les caractères de d1 et insérer tous les caractères de d2, mais c'est rarement le nombre d' | ||
+ | |||
+ | - Essayez de calculer "à la main" la distance d' | ||
+ | * entre " | ||
+ | * entre " | ||
+ | * Vérifiez sur ces exemples que l' | ||
+ | - La résolution de ce problème repose sur les principes de la programmation dynamique. Résoudre sur papier l' | ||
+ | - (*) Écrire l' | ||
+ | - (* *) Est-il possible de réduire cette complexité? | ||
+ | |||