Teaching

Supports vidéo

Algorithmiques (hors algorithmique des graphes)

  • Vidéo d'introduction à la complexité algorithmique.
  • Vidéo sur les notations O, Omega, Theta
  • Vidéo sur la comparaison de complexités algorithmiques
  • Vidéo sur Terminaison et correction d'algorithmes.
  • Vidéo sur la complexité dans le cas le pire.
  • Vidéo d'introduction aux algorithmes probabilistes (Las Vegas, Monte Carlo)
  • Vidéo sur QucikSelect, un algorithme de calcul de médian par une méthode Las Vegas
  • Vidéo sur un algorithme probabiliste de type Monte Carlo pour le calcul de median
  • Vidéo sur un algorithme probabiliste de type Monte Carlo pour vérifier un produit de matrices.
  • Vidéo sur Boyer-Moore simplifié.
  • Vidéo sur l'algorithme de Rabin-Karp
  • Vidéo sur les algorithmes gloutons (introduction)
  • Vidéo d'introduction à la génération aléatoire récursive uniforme
  • Vidéo sur le mélange de tableaux : algorithme de Fisher-Yates-Knuth
  • Vidéo sur l'algorithme de compression de Lempel (compression)
  • Video sur l'agorithme de compression de Lempel (décompression) 
  • Video sur l'agorithme de compression de Huffman (décompression)
  • Vidéo sur diviser pour régner en algorithmique
  • Vidéo sur le tri par insertion
  • Vidéo sur le tri bulle
  • Vidéo sur le tri rapide
  • Vidéo d'introduction sur les algorithmes d'approximations
  • Vidéo d'exemple d'approximation gloutonne : List Scheduling
  • Vidéo sur le tri comptage
  • Vidéo sur l'algorithme de Karatsuba (diviser pour régner)
  • Vidéo sur le Master Theorem
  • Vidéo d'introduction aux tables de hachage et l'adressage direct
  • Vidéo sur le chainage dans les tables de hachage
  • Vidéo sur l'adressage ouvert dans les tables de hachage

Graphes et Algorithmique des graphes (dont les arbres)  (certains problèmes sont dans la rubrique NP-complets):

  • 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 largeur illustré par des vampires.
  • 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 sur les graphes non orientés.
  • Vidéo d'introduction sur les graphes orientés
  • Vidéo sur les graphes bipartis
  • Vidéo sur la connexité et les composantes (fortement) connexes.
  • Vidéo sur les arbres (définis comme des graphes)
  • Vidéo sur le codage des graphes par listes d'adjacence.
  • Vidéo sur le codage des graphes par matrices d'adjacence.
  • Vidéo sur les notions de sous graphes, sous graphes induits, sous-graphes partiels.
  • Vidéo sur les graphes complets et graphes bipartis complets.
  • Vidéo sur la notion de clique.
  • Vidéo sur le tri topologique d'un graphe acyclique (partie 1).
  • Vidéo sur le tri topologique d'une graphe acyclique (partie 2)
  • Vidéo d'introduction à la coloration de graphes
  • Vidéo d'application de la coloration de graphes à la planification d'examens
  • Vidéo sur la définition d'un graphe d'intervalles
  • Vidéo sur l'application de la coloration de graphes au Suguru
  • Vidéo sur  les arbres définis inductivement
  • Vidéo sur le vocabulaire des arbres
  • Vidéo sur les graphes réguliers
  • Vidéo sur les isomorphismes de graphes
  • Vidéo sur l'algorithme de Dijkstra

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 comment prouver qu'un langage n'est pas régulier.
  • 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 la minimisation d'automates (méthode de Moore).
  • Vidéo sur le produit synchronisé d'automates.
  • Vidéo sur les mots et langages infinis.
  • Vidéo sur comment tester si un automate reconnaît le langage vide.
  • Vidéo sur comment tester l'inclusion de deux langages réguliers.
  • 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.
  • Vidéo sur le produit de deux langages reconnus par automates.
  • Vidéo sur l'étoile d'un langage reconnu par un automate.
  • Vidéo sur le passage d'une expression régulière vers un automate par l'algorithme de Thomson.
  • Vidéo d'introduction aux automates probabilistes.
  • Vidéo sur le miroir d'un langage donné par un automate.
  • Vidéo sur le miroir d'un mot et d'un langage
  • Vidéo sur le produit de mélange (shuffle)

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 et SAT, 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 définitions inductives
  • Vidéo de la définition inductive de la logique propositionnelle
  • Vidéo sur la différence entre syntaxe et sémantique
  • Vidéo sur les termes (définition).
  • Vidéo sur le lien entre arbres et termes.
  • Vidéo sur les arbres binaires définis inductivement (exemple de termes)
  • Vidéo sur les arbres définis inductivement
  • 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 sous-formule (exemple de sous-terme)
  • Vidéo sur la notion de substitution de variables dans un terme.
  • Vidéo sur la substitution dans une formule propositionnelle (exemple de substitution)
  • Vidéo sur la sémantique de la logique propositionnelle
  • Vidéo sur les littéraux et les formes normales
  • 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.
  • Vidéo sur la notion de matrice d'incidence d'un réseau de Petri.
  • Vidéo sur la notion de P-invariant (invariant de place)
  • Vidéo sur les réseaux de Petri et les graphes d'états
  • Vidéo sur les réseaux de Petri sans conflit.
  • Vidéo sur les omega marquages.
  • Vidéo sur l'algorithme de Karp-Miller
  • Vidéo sur les réseaux bornées/saufs
  • Vidéo sur la vivacité dans les réseaux de Petri

Python

  • Vidéo d'introduction sur les tableaux/listes.
  • Vidéo sur les méthodes insert() et append() de Python.
  • Vidéo sur le parcours de tableau en Python.
  • Vidéo sur la recherche du min dans un tableau 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èmes NP-complet, voir la rubrique dédiée)

  • Vidéo de présentation des machines de Turing.
  • Vidéo sur les machines de Turing déterministes (notations).
  • Vidéo sur les machines de Turing déterministes (calculs, configuration, acceptations...)
  • Vidéo d'introduction sur le lien entre théorie des langages et calculabilité
  • Vidéo sur les machines de Turing non déterministes.
  • Vidéo sur la complexité en temps des machines de Turing Déterministes. Classe P.
  • Vidéo sur la complexité en temps des machines de Turing Non déterministes. Classe NP.
  • Vidéo sur les certificats en calculabilité et la classe NP.
  • Vidéo sur le théorème de Cook
  • Vidéo sur le problème VertexCover
  • Vidéo sur le problème SetPartition
  • Vidéo sur le problème DominatingSet
  • Vidéo sur le problème BinPacking
  • Vidéo sur le problème KnapSack
  • Vidéo sur le problème SetCover
  • Vidéo sur les réductions ManyOne
  • Vidéo sur le problème Partition en Triangles
  • Vidéo sur les réductions de Turing polynomiales
  • Vidéo sur les problèmes NP-complets
  • Vidéo sur les problèmes de décision et d'optimisation
  • Vidéo sur l'heuristique de liste (approximation gloutonne)

SAT et 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 (les dames)
  • Vidéo sur le codage SAT du 3-coloriage de graphes.
  • Vidéo sur l'algorithme 2-SAT
  • Vidéo sur l'algorithme de Quine

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)
  • SVAM (slides cours 1, pdf) (slides cours 2, pdf)
  • SVAM (TD1, pdf) (TD2, pdf)

Licence Informatique

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