Home
About

S5 : Algorithmie avancée

Enseignements/Enseignements MPCI/S5 : Algorithmie avancée

Programme

En quatre parties.

TBD année prochaine faire préparer le cours avant et au tableau aller plus loin ?

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

  1. cours 1 : Modèle de calcul
    1. pseudo-assembleur
    2. Architecture de Von Neumann
    3. Modèle de la Machine de Turing
  2. Cours 2 : Turing et NP
    1. Machines de Turing
      1. définition alternatives
        • 2 curseurs
        • 2 rubans
        • alphabets
      2. Modèle 01#
      3. coder avec Turing
        1. doublement de batons
        2. autres exemples
    2. réduction de problèmes
    3. Classes de problèmes :
      1. P, NP et NPC : avec vérifieurs
      2. Recherche universelle
  3. Cours 3 : NP et Turing, NPC
    1. SAT, 3-SAT et 2-SAT
    2. P, NP et NPC
      1. de vérifieur à décideur
      2. SAT est NPC
  4. Cours 4 : problème du sac à dos
    1. SAC à dos est NPC
    2. résolutions :
      1. fractionnel
      2. énumération (juste donner le principe)
      3. programmation dynamique

C

Le but de cette partie est d'avoir assez de bases en C pour s'amuser.

N'hésitez pas à suivre et à faire également les exercices du cours suivant :

https://www.0de5.net/stimuli/a-reintroduction-to-programming/essentials/just-enough-c-to-have-fun

  1. Cours 1 : Système et consequences pour le code
    1. architecture générale
    2. Mémoire :
      1. organisation système de la mémoire
      2. différence entre pile et tas
    3. cours de C : survole tout jusqu'aux exercices. A préparer chez vous
  2. Cours 2 : exercices en C

DM

Faire en C le projet sac à dos

A rendre pour le 18 octobre.

TBD année prochaine :

  1. les faire préparer le cours :
    1. lire le cours : (pseudo-assembleur si pas préparé avant), von Neumann et C avant
    2. faire le premier exercice
  2. pendant le cours faire le système avec radare2 qui décompile à la volée comme dans <https://www.youtube.com/watch?v=76acHVJfziw.

Bases de la théorie des graphes

Cours 1

  1. Graphes bases :
    1. rappel des définitions
    2. quelques propriétés sur les degrés, les chemins et les cycles
    3. NP complétude du problème clique
  2. exercice sur les tournois

Cours 2

  1. Parcours eulériens
  2. Parcours hamiltoniens
  3. idée du problème du postier chinois

Cours 3

  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

Problèmes de flots

Cours 1 : problèmes

Problème et résolutions flots

Cours 2 : applications

Exercices sur les flots :

  1. applications directs
  2. Problèmes de transport
  3. Bataille de la Marne

Graphes biparti

  1. graphes bi-parti bases
  2. parcours de graphes classiques

DS

Temporellement placé juste après le cours 6.

sujet

Couplages dans les graphes

Cours 1 et 2

  1. graphes bi-parti (fin) :
    1. théorème de Graham-Pollack
    2. NP-complétude de la reconnaissance triparti
  2. couplage
  3. Application : algorithme de Chritofides
  4. $k$-connectivité d'un graphe

Cryptographie

Cours 1, 2 et 3

Cryptographie

Colorabilité

TBD

Planarité

TBD

Graphes aléatoires et infini

TBD

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