Objectif : Le but de cette UE est d’étudier des problèmes fondamentaux en informatique sous leurs aspects théoriques et structurels (mathématiques discrètes/informatique fondamentale), tout en soulignant leur portée pratique (liens avec des problèmes concrets et implémentation, en C, des algorithmes).
Cette UE est composée de deux grandes parties, non indépendantes :
- Théorie des graphes.
- Chemins (eulériens, hamiltoniens, flots et k-connexité) et arbres (planté et non plantés)
- Graphes planaires et problèmes de colorations
- Graphes aléatoires et graphes infinis
- Problèmes classiques (stables et cliques, couverture, couplages bipartis et généraux)
- Problèmes algorithmiques.
- Classes de problèmes (P, NP et avatars), réductions et applications pratique
- Pseudo-aléatoire et Algorithmes randomisés,
- Problèmes de Cryptographie (zero-knowledge proof, chiffrement symétrique et asymétrique, algorithme de Diffie-Hellman, signatures)
- Implémentation efficace structures de données classiques comme les arbres, pile/files et graphes (gestion de la mémoire, pile et pointeurs, langage C),
Les graphes peuvent être vus comme un outil permettant de résoudre efficacement un problème algorithmique (les arbres de recherche par exemple) ou encore comme support à la recherche de chemins entre sommets (comme pour le cours « Graphes et arbres » du S3). Nous prenons le parti ici de les étudier au contraire comme un objet mathématique dont on cherche à déterminer les propriétés.
De plus, les algorithmes de ce cours seront élégants et efficaces mais nécessiteront pour être mis en œuvre des connaissances variés, allant des probabilités aux raisonnements combinatoires, et forment une suite logique au cours d’algorithmie du S1.
Enfin, malgré le caractère résolument théorique de cette UE, on s’attachera tout au long de celle-ci à montrer les liens entre des problèmes concrets importants et ces structures discrètes et algorithmiques. Cette UE sera aussi l’occasion d’apprendre et d’utiliser le langage C particulièrement adapté pour comprendre comment gérer la mémoire, programmer au niveau système et implémenter efficacement les structures de données.
