Graphes langages et automates (Automne 2010)

Horaires

  • Cours : Mercredi 13h45 - 15h45, Salle Thémis 69
  • TD (un seul groupe) : Mercredi 16h00 - 19h15. La salle change souvent. Ci-dessous, pour chaque séance la salle TD est indiqué entre parenthèses.

Liens et contact

Planning Prévisionnel

  • Mercredi 15/09 : Cours 1
    Introduction, définition de graphe, graphe complémentaire, isomorphismes et automorphismes de graphes, graphes complets, bipartis, bipartis complets. Les matrices d'adjacence A(G) et d'incidence M(G).
  • Mercredi 22/09 : Cours 2 - TD 1
    Comment compter les graphes simples sur n sommets; classes d'isomorphisme de graphes, le groupe d'automorphismes et son cardinal. Le degré d'un sommet; somme des degrés, sommets impairs.
  • Mercredi 29/09 : Cours 3 - TD 2
    Cheminement dans les graphes, chaînes simples, élémentaires; comment compter les nombres de chaînes de longueur fixée. Cycles; un graphes qui a tous les sommets de degré au moins égal à 2 contient un cycle.
  • Mercredi 06/10 : Cours 4 - (TD 3 - Quai 43 s.109)
    Caractérisation de graphes bipartis. Suites de degrés et séquences réalisables.
    Application : le problème de la plus courte chaîne, l'algorithme de Dijkstra (un exemple de l'algorithme).
  • Mercredi 13/10 : Cours 5 - (TD 4 - Quai 43 s.109)
    Arbres et forêts, caractérisation des arbres. Arêtes séparatrices
  • Mercredi 20/10 : Cours 6 - (TD 5 - Quai 43 s.112)
    Sommets séparateurs. Arbres recouvrants. Comment calculer le nombre d'arbres recouvrants d'un graphe connexe : formule de récurrence. Formule de Cayley pour les graphes complets.
  • Mercredi 27/10 : Cours 7 - (TD 6 - Préfa 16 (Préfa TP))
    Application : le problème de l'arbre de poids optimal ; algorithme de Jarnik-Prim. Tours eulériens et chaînes eulériennes : caractérisation de graphes eulériens.
  • Mercredi 03/11 : Le CC2 aura lieu de 14h00 à 15h15 en Salle Thémis 69.
  • Mercredi 10/11 : Cours 8 - (TD 7 - Préfa 16 (Préfa TP))
    Cycles Hamiltoniens : condition nécessaire, une condition suffisante (Théorème de Dirac). Exemples : le graphe de Petersen, le graphe de Herschel, les graphes des solides de Platon. Application : le problème du postier chinois.
  • Mercredi 17/11 : Cours 9 - (TD 8 - Préfa 16 (Préfa TP))
    Langages et expressions rationnelles. Monoïdes, morphismes de monoïdes. Exemples.
  • Mercredi 24/11 : Pas de cours - (TD 9 le matin 8h15 - 11h30 Préfa 16 (Préfa TP))
  • Mercredi 01/12 : Cours 10 - (TD 10 - Préfa 16 (Préfa TP))
    Cours annulé à cause de la neige.
  • Mercredi 08/12 : Cours 11 - (TD 11 - Préfa 16 (Préfa TP))
    Automates et langages des mots acceptés. Procès de normalisation. Automate avec ε-transitions, passage à un automate sans ε-transitions. Théorème de Kleene.
  • Mercredi 15/12 : Cours 12 - (TD 12 - Préfa 16 (Préfa TP))
    Preuve du Théorème de Kleene. Lemme de Arden et application pour trouver le langage accepté par un automate. Automates déterministes. Processus de détermination.
  • Mercredi 12/01 : Lemme de l'étoile et langages non rationnels. Restitution CC3.

Contrôles Continus

  • DM1 à rendre le mercredi 29 septembre, Ex. 11 de la feuille 1. Notes de 0 à 3 sur Tomuss.
  • CC1 : Mercredi 13 octobre de 13h45 à 14h45. Corrigé du CC1.
  • CC2 : Mercredi 3 novembre de 14h00 à 15h15 : il portera sur les arbres jusqu'à l'algorithme de Jarnik-Prim inclus. Corrigé du CC2. Solution longue de l'Exo 3 en utilisant la récurrence.
  • CC3 : Mercredi 15 décembre de 14h00 à 15h15. Corrigé du CC3. Question 1 point 5) lire “doit contenir A au moins 2 fois” et non “doit contenir A au moins trois fois”.
  • DM2 à rendre le mercredi 12 janvier, Ex. 81-82-83-86-87. Corrigé DM2.

Fiches Travaux Dirigés TD

 
 
Valid XHTML 1.0 Valid CSS Driven by DokuWiki