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
  

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

• TP sécurité cryptanalyse statistique,( pdf) textetest textepiege textepiege2 napoleon1 napoleon2
  
• Sécurité Cours protocole (pdf)
• Logique et déduction (cours 1 et 2, pdf)  (cours 3 pdf) (cours 4 et 5pdf) (cours 6, pdf)
• Logique et déduction (TD 1 et 2, pdf) (TD 3 et 4, pdf) (TD 5 et 6, pdf)
• Logique et déduction (TP1, pdf) (TP2, pdf) (TP3, 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