Septembre

jeudi 3: alphabets, mots, langages; opérations sur les mots, sur les langages; définition des expressions rationnelles sur un alphabet X; sémantique des expressions rationnelles; (2 heures)
jeudi 10: définition d'un automate déterministe complet; définition d'un calcul; définition de l'étiquette d'un calcul; définition d'un calcul réussi; définition d'un langage reconnaissable (par un a.f.d.c.); exemples: automate reconnaissant le langage décrit par l'expression a*b(a+b)*; automate reconnaissant le langage des mots contenant un nombre pair de a et un nombre impair de b; le complémentaire d'un langage reconnu par un a.f.d.c. est lui-même reconnaissable par un a.f.d.c.; (1 heure)
jeudi 17: automate produit; la réunion et l'intersection de deux langage reconnaissables sont elles-mêmes reconnaissables; deux preuves de l'existence de langage non rationnels: l'une, non constructive, l'autre contructive (lemme de l'étoile); exemples de langages non rationnels; (1 heure)
jeudi 24: définition d'un automate fini déterministe non complet; tout automate de ce type est équivalent à un a.f.d.c.; états accessibles, coaccessibles; algorithme d'émondage d'un a.f.d.; résolution de deux problèmes de décision: le langage reconnu par un a.f.d. est-il vide? est-il fini? (1 heure 30)

Octobre

jeudi 1^er: preuve de l'implication reconnaissable implique rationnel par la méthode de McNaughton et Yamada; automate des résiduels; automates finis non déterministes: définition, quelques exemples; construction de l'automate des parties et du déterminisé; (1 heure)
jeudi 8: preuve de l'équaivalence entre un a.f.n.d. et son déterminisé; automates à transitions instantanées: définition, exemples; description de la méthode de Thompson; (1 heure)
jeudi 15: on prouve que les automates à transitions instantanées ne sont pas plus puissants que les a.f.d.; (1 heure)
jeudi 22: automate minimal: algorithme de Moore;

jeudi 5:
jeudi 12: de l'automate fini à l'expression rationnelle, par la méthode des équations aux langages; exercices divers;
jeudi 19: arbres: définitions éqvalentes; noeuds, feuilles; enracinement d'un arbre; hauteur d'un arbre; arbres binaires: relation entre le nombre de nÏuds et le nombre de feuilles; définition en Caml d'un squelette d'arbre binaire;
jeudi 26: calcul de l'expression des nombres de Catalan; exemples de situations où apparaissent ces nombres; exemples d'évaluations associées à des arbres binaires; définition d'un arbre binaire de recherche;

jeudi 3: arbres binaires de recherche: algorithmes pour l'insertion aux feuilles, pour la suppression d'une clé et pour la recherche d'une clé; programmation en Caml de ces algorithmes; scission et fusion d'arbres binaires de recherche
jeudi 10: calcul de la profondeur moyenne des nœuds dans un arbre binaire de recherche
jeudi 17: parcours en largeur, parcours en profondeur; programmation de ces opérations;
jeudi 24: étude des arbres dictionnaires

jeudi 7: présentation de programmes écrits en Caml; quelques exercices (automate fini; algorithmes)
jeudi 14: programmation: calcul de la longueur minimale d'un mot reconnu par un a.f.; construction de la liste des mots de longueur minimale; écriture de fonction relatives aux nombres premiers: isprime, nextprime, liste de nombres premiers, liste de nombres premiers jumeaux, recherche de triplets de nombres premiers formant une suite arithmétique
jeudi 21 janvier: exercices de théorie des graphes
jeudi 28 janvier: exercices d'algorithmique