Informatique
Langages formels
Qu’est-ce qu’un langage formel, un alphabet et un mot. Notions de base de la théorie des langages formels, expliquées par comparaison avec la langue courante et sur des exemples.
Automates finis
L’automate fini comme modèle de calcul avec des états et des transitions. Définition, diagramme d’états, formalisation du calcul et exemples de mots acceptés.
Minimisation des automates
États inaccessibles d’un automate fini, que l’on ne peut atteindre depuis l’état initial. Définition et méthode pour les supprimer sans danger.
Propriétés de clôture des langages réguliers
Les langages réguliers sont stables par réunion, intersection, concaténation et étoile. Ce que signifie la stabilité par une opération et pourquoi elle est vraie pour les langages réguliers.
Expressions régulières
Qu’est-ce qu’une expression régulière et comment elle décrit un ensemble de mots. Définition, comparaison avec les expressions arithmétiques et lien avec les automates finis.
Estimer le nombre de valeurs distinctes
Linear counting : comment estimer le nombre de valeurs distinctes dans de grandes données. Fonctions de hachage, tableaux de bits et pourquoi la méthode naïve ne suffit pas.
Filtre de Bloom : un élément est-il dans l’ensemble ?
Le filtre de Bloom est une structure de données probabiliste qui répond vite à la question : cet élément est-il dans l’ensemble ? Principe, fonctions de hachage et usages concrets.
Chiffrement de César
Comment fonctionne le chiffrement de César, l’un des plus anciens moyens de chiffrer un texte. Principe du décalage des lettres, généralisation du chiffrement et outil de chiffrement en ligne.
Chiffre de Vigenère
Le chiffre de Vigenère utilise plusieurs alphabets et résiste donc à l’analyse fréquentielle. Principe du chiffrement, carré de Vigenère, choix de la clé et outil en ligne.
