Home
About

S5 : Algorithmie avancée

Enseignements/Enseignements MPCI/S5 : Algorithmie avancée

Programme

En trois parties.

Modèles de calculs et classes de problèmes "utiles"

Semaine 1

  1. Rappels :
    1. écrire un algorithme avec un pseudo-code
    2. importance de la complexité polynomiale
  2. Réduction de problèmes
  3. Problèmes de NP
  4. Le problème SAT

Théorie des graphes

Semaine 2 à 5

Un outil de modélisation puissant pour résoudre (joliment) nombre de problèmes informatique.

Semaine 1

Cours 1

Semaine 1

  1. Graphes bases :
    1. rappel des définitions
    2. quelques propriétés sur les degrés, les chemins et les cycles
  2. Rappel : encodage d'un graphe
  3. cliques et stables
Cours 2
  1. chemins cycles et connexité
    1. chemin
    2. composante connexe
  2. Parcours eulériens
  3. Parcours hamiltoniens
  4. applications :

Semaine 2

Qu'ont-ils fait en arbre ? Parcours ? ALM ? chemin positif et négatif à coût min ? parcours largeur/profondeur flot ?

  1. rappels sur les chemins les plus courts :
    1. Poids positifs
    2. Noms des algorithmes pour poids quelconques
  2. Arbres :
    1. version théorie des graphes des arbres
      • définitions
      • propriétés fondamentales
      • Cayley et Prüfer
    2. Arbres couvrants

Semaine 3

TBD :

  1. Bi-parti
  2. coloriabilité

Semaine 4

TBD :

  1. couplage
  2. planarité

DS

TBD le faire.

Cryptographe

TBD en 2 semaines algo protocoles pgp et envois de message chiffrés

Bonus

TBD au choix :

  • recherche universelle
  • théorème de Cook-Levin
  • graphes infinis
  • méthode probabiliste ?
  • ...

Modalités de contrôle

Note

La note de cette UE résulte de cette formule :

$$ \max (\frac{DM+ DS + ET}{3}, ET) $$

Avec :

Rendus