Complexité algorithmique et cryptographie

Diplômes intégrant cet élément pédagogique :

Descriptif

A : Cryptographie et Complexité
Introduire les principes de la cryptographie : clé secrète et clé publique, algorithmes et protocoles
- Comprendre les principes sous-jacents aux cryptosystèmes et à leur utilisation.

B : Graphes et Complexité.
Le cours présente la théorie des graphes. On y présente la théorie des graphes sous plusieurs de ses aspects.
1) L'aspect complexité : complexité des algorithmes et complexité des problèmes. Dans ce cadre on présente des problèmes de décision et on travaille la notion de "bonne caractérisation". On y présente des problèmes polynomiaux et aussi des problèmes NP-complets. Dans le but d'éclairer les notions de classes de complexité des problèmes NP, NP-complet, Co-NP et P. On y présente la notion de réduction polynomiale d'un problème vers un autre. Tous les exemples sont pris en théorie des graphes. L'étudiant progresse en graphe et en complexité.
2)
Les aspects modélisations. Les graphes sont très utilisés dans les problèmes de routage en réseau, les problèmes de trafic en transport, l'étude des jeux, en recherche d'information (graphe du web), en codage, en ordonnancement et emploi du temps, ...
3) Les aspects raisonnement : développer une aptitude à raisonner mieux en face de structures discrètes, en particulier la rédaction de démonstration, la justification propre d'un algorithme et surtout la récurrence.
4) Les aspects algorithmiques : (ex) utiliser la structure de donnée "tas binaire" dans différents algorithmes.

Pré-requis

A : Aucun pré-requis
B : Algorithmique de base

Bibliographie

Wikipedia. Portail de la Cryptographie.

Informations complémentaires

Lieu(x) : Grenoble - Saint-Martin d'Hères
Langue(s) : Français