Complexité algorithmique - KAIN7M04

Objectif(s)

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.

Contenu(s)

A :
1. Calculs modulo un entier.
2. Cryptographie à clé secrète.
3. Cryptographie à clé publique.

B :
0) vocabulaire de base et représentation des graphes.
1) raisonnement sur les graphes (orientés ou non) avec les différentes classes : biparti, planaires, sans circuits, eulérien,
hamiltonien
2) présentation d'algorithmes classiques avec leur calcul de complexité : connexité et forte connexité et dfs, Dijkstra et bfs, Kruskal, Flot maximum
3) des exemples de modélisation avec les graphes.
4) un grand nombre de problèmes de décisions en graphe et leur classe de complexité.

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