HOME / SEMESTRE 2: CRYPTOGRAPHIE ET SéCURITé (CS) /

Complexité algorithmique et chiffrement

  1. Introduction
  2. Calcul de coût d'un algorithme
  3. Complexité en temps et en espace
  4. Machines de Turing
  • Machines équivalentes.
  • Machines de Turing non déterministes
  • Machines de Turing universelles
  1. Langage reconnu par une machine de Turing
  2. Problème de décision.
  3. Problèmes P, NP, NP-dur et autres.
  • Le problème « Premier » est NP.
  • Le problème de satisfaisabilité
  • Le problème TSP
  1. Algorithmes déterministes
  2. Algorithmes probabilistes
  3. Réduction et complétude
  4. Théorie de la complexité et la cryptographie moderne.