Structure chaine de caractères
Une chaine de caractères est dans toute sa généralité définie comme un mot produit par un alphabet :
Définition
- Un alphabet $\mathcal{A}$ est un ensemble fini
- un mot est une suite finie d'éléments de $\mathcal{A}$
- une lettre est un élément d'un mot
- un langage est un ensemble, possiblement infini de mots d'un alphabet
Le langage formé de tous les mots d'un alphabet $\mathcal{A}$ est noté $\mathcal{A}^\star$
On représentera par la suite de façon indistincte un mot par :
- la suite finie $m = (a_i)_{1\leq i \leq n}$
- la chaîne de ses éléments concaténés : $m = a_1\dots a_n$
- un tableau $m = [a_1, \dots, a_n]$
En informatique, l'alphabet de prédilection est $\{0, 1\}$ mais a priori toutes les structures qu'on va définir vont fonctionner quelque soit l'alphabet.
La notion de langage est au cour même de l'algorithmie, on effleurera le sujet dans la prochaine partie, et est un sujet inépuisable d'applications pratiques (trouver des gènes dans un génome, correcteur orthographique, etc) et de sujets d'examens (nous verrons un cas d'école dans la troisième partie).
Nous verrons également comment passer d'un alphabet binaire à un alphabet quelconque et comment à été résolu de façon pratique la représentation informatique de l'écriture d'une langue humaine.
Encodage
TBD : pas implémentation (voir partie code pour utf8 et python). ici juste suite finie de caractère = mot = chaine de caractère ordre entre les caractères. facile pour nous mais peut etre un soucis pour les chinois implique ordre entre les mots en pratique pas que des 0 et des 1, des lettres.
TBD : pas juste 1 nombre de taille fixe. On module la taille selon l'usage. Plus c'est utilisé plus c'est court. Comment faire ? C'est le principe de unicode
Structure algorithmique
Langages et mots
TBD mots et décideur
Langages et algorithmes
Définition
Un décideur est un programme de :
$$f: \{0, 1\}^\star \rightarrow \{0, 1 \}$$
Définition
On appelle langage d'un décideur $d$ l'ensemble $d^{-1}(1)$.
On dira qu'un décideur $d$ accepte le langage $L$ si $L = d^{-1}(1)$ et qu'un langage $L$ est décidable s'il existe un algorithme pour l'accepter.
Tout langage n'est bien sur pas décidable. On a vu qu'il était impossible de savoir a priori si un programme va s'arrêter ou pas (l'algorithme STOP n'existe pas). Le langage composé des pseudo-codes associés aux algorithmes — c'est à dire les programmes qui s'arrêtent — n'est donc pas décidable. En revanche, le langage composé des pseudo-codes, est décidable (on peut facilement vérifier si un texte respecte les règles syntaxiques associé à un pseudo-code).
Montrez que l'ensemble des palindromes d'un alphabet $\mathcal{A}$ est décidable.
corrigé
corrigé
def palindrome(mot):
for i in range(len(mot)):
if mot[i] != mot[len(mot) - 1 - i]:
return False
return True
même distinction entre programme et algorithme : langages reconnaissable si programme (ne s'arrête pas forcément).
Automates
Grammaires
TBD : permet de compiler des programmes.
Problèmes algorithmique associés
Recherche de sous-mots
Recherche de sous-séquences
TBD
Recherche de motifs
TBD