Semaine du lundi 16 septembre 2024
Unir-Trouver
- Connaître le principe d'au moins une implémentation naïve
- Connaître le principe de l'implémentation par arbres, et de ses deux optimisations (union par rang et compression de chemin)
- Savoir appliquer une version demandée sur un exemple
- Connaître les complexités associées
- Bien connaître la spécification de la structure, afin de pouvoir prouver la correction d'algorithmes qui l'utilisent.
On pourra demander, en guise de question de cours, d'appliquer une version d'Unir-Trouver à un exemple. On peut ensuite proposer des exercices simples dans lesquels on utilise cette structure de données.
Langages réguliers
- Connaître les notions de mots, facteurs, préfixes, suffixes, sous-mots ; le mot-vide, et l'opération de concaténation.
- Connaître la notion de langage comme ensemble de mots ; les opérations de concaténation, d'union, et d'étoile de langages.
On pourra poser des exercices simples demandant de vérifier des propriétés autour de langages.
