Teaching

Supports vidéo

Algorithmique :

  • Vidéo  sur le parcours préfixe d'arbres.
  • Vidéo  sur le parcours suffixe d'arbres.
  • Vidéo  sur le parcours en largeur d'un graphe orienté.
  • Vidéo  sur le parcours en profondeur d'un graphe orienté.
  • Vidéo d'introduction aux arbres binaires de recherche.
  • Vidéo des algorithmes de recherche et d'insertion dans un arbre binaire de recherche.
  • Vidéo sur la suppression dans un arbre binaire de recherche.
  • Vidéo d'introduction à la complexité algorithmique.

Théorie des langages (réguliers), automates

  • Vidéo sur la notion d'alphabet et de mot fini.
  • Vidéo sur la notion de langages, produit, étoile et expressions régulières.
  • Vidéo sur la définition d'un automate fini.
  • Vidéo sur la définition d'un mot/langage reconnu par un automate et sur les expressions régulières.
  • Vidéo sur le produit d'automates finis.
  • Vidéo sur les automates déterministes.
  • Vidéo sur la  déterminisation d'un automate fini.
  • Vidéo sur les automates complet et la complétion.
  • Vidéo sur le complémentaire d'un langage régulier.
  • Vidéo sur les états accessibles, co-accessibles et les automates émondés.
  • Vidéo sur le lemme de l'étoile.
  • Vidéo sur l'élimination des epsilon-transitions.
  • Vidéo sur le quotient (résiduel) de langages.
  • Vidéo sur l'équivalence et le théorème de Myhill-Nerode.
  • Vidéo sur le produit synchronisé d'automates.
  • Vidéo sur les mots et langages infinis.
  • Vidéo sur les automates de Büchi.
  • Vidéo sur le produit d'automates de Büchi.
  • Vidéo sur la définition d'un monoïde.
  • Vidéo sur les notion de morphismes de monoïde et de monoïde libre.
  • Vidéo sur la reconnaissance d'un langage par morphisme/monoïde.

Langages algébriques, grammaires algébriques (hors-contexte)

  • Vidéo d'introduction aux grammaires algébriques
  • Vidéo sur les dérivations, dérivations gauches et droites, langage reconnu
  • Vidéo sur les arbres de dérivation
  • Vidéo sur les grammaires algébriques linéaires
  • Vidéo sur les grammaires ambiguës.
  • Vidéo sur l'élimination des production epsilon dans les grammaires algébriques.
  • Vidéo d'introduction sur les automates à pile.
  • Vidéo sur la définition d'un automate à pile, mots et langages reconnus.
  • Vidéo sur les automates à piles déterministes.

Logique et informatique, réécriture (pour les SAT solver, voir la rubrique dédiée)

  • Vidéo sur la syntaxe de la logique LTL.
  • Vidéo sur la sémantique de la logique LTL.
  • Vidéo illustrative de l'utilisation de LTL.
  • Vidéo sur les termes (définition).
  • Vidéo sur le lien entre arbres et termes.
  • Vidéo sur la notion de position dans un terme.
  • Vidéo sur la notion de sous-terme à une position donnée.
  • Vidéo sur la notion de substitution de variables dans un terme.
  • Vidéo sur la notion de substitution d'un sous-terme dans un terme.
  • Vidéo de présentation de la réécriture de termes à l'aide d'exemples.
  • Vidéo d'introduction au calcul de Séquents (partie 1).
  • Vidéo calcul de Séquents (partie 2) : logique propositionnelle.

Réseaux de Petri

  • Vidéo d'introduction aux réseaux de Petri.
  • Vidéo sur les notations de précédence et succession.
  • Vidéo sur les marquages accessibles.
  • Vidéo sur le graphe d'accessibilité.
  • Vidéo sur l'exemple du feu tricolore.
  • Vidéo sur l'exemple du dîner des philosophes.
  • Vidéo sur l'exemple de la Chèvre, du chou et du loup.
  • Vidéo sur les réseaux de Petri multi-arcs.
  • Vidéo d'un exemple de réseau de Petri multi-arc.
  • Vidéo sur la notion de couverture dans les réseaux de Petri.

Python

  • Vidéo sur les identifiants et variables.
  • Vidéo sur le codage des listes.
  • Vidéo sur les copies de listes.
  • Vidéo sur le passage de paramètres.

Calculabilité (pour l'approche par SAT solver pour les problème NP-complet, voir la rubrique dédiée)

SAT solvers

  • Vidéo sur l'introduction à l'utilisation de SAT solvers.
  • Vidéo sur un exemple de codage d'un problème NP-complet par une approche SAT
  • Vidéo sur la mise en oeuvre d'un SAT solver pour l'exemple précédent.
  • Vidéo sur l'algorithme 2-SAT

Polys et supports pdf

Master Informatique

  • CNP : TP sur les problèmes NP-complet, pdf
  • CNP (slides partie 1, pdf) (slides partie 2, pdf) (slides partie 3 pdf) (sujet 2017 pdf)

Licence Informatique

  • TP sécurité cryptanalyse statistique, pdf

DUT Informatique (archives 2020)

  • Polycopié Mathématiques Discrètes, S2 IUT info pdf (cours-TD) (sujet 2018 pdf)
  • Polycopié Analyse Numérique, S2 IUT info pdf (Cours-TD)
  • Polycopié Probabilités et Statistiques (cours-TD), S3 IUT Info pdf )  (sujet 2018 partie 1 pdf)
  • Polycopié Compléments d'Algèbre (Cours-TD-TP), S4 IUT Info, Etudes longues, pdf
  • Polycopié TP Graphes et langages, partie 2, pdf