Le but de cette section est de recenser une liste d’exercice d’informatique théorique que j’ai écrit. Initialement rédigé en collaboration avec Pierre Mahmoud–Lamy pour être publié, nous avons préféré les partager aux plus grand nombre. Une partie d’entre eux servent également à présenter des résultats, certains importants, d’autres beaucoup plus niches, de l’informatique fondamentale. Ils sont principalement destinés aux étudiants de niveau Licence et permettent d’approfondir des concepts vus en cours et aux élèves de CPGE en MP2I et MPI.
Liste d’Exercices
Correction et Terminaison
- La fonction d’Ackermann : Preuve de terminaison d’une fonction récursive.
- La fonction 91 de McCarthy : Preuve de terminaison d’une fonction récursive et calcul exacte de sa valeur.
- Le problème du drapeau Hollandais : Algorithme de tri particulier qui se trouve à la base de certains algorithmes de quicksort.
- Exponentiation rapide et Algorithme de Hörner : Effectuer des exponentiations et évaluer des polynômes avec un nombre faible de multiplication.
Représentation de données
- Le codage de Gray : Une représentation des entiers en binaire tel que les entiers ne sont modifiés que d’un seul bit à chaque incrémentation.
- Fibonnacci et Zeckendorf : Représenter les entiers grâce à la suite de Fibonnacci.
Schémas algorithmiques
- Distance d’édition : Le calcul d’une distance entre les mots.
- Produit efficace en binaire : Un algorithme pour multiplier plus rapide que celui appris au primaire.
- Problème de la sous-séquence maximale : Un exercice complet utilisant différent schémas algorithmiques pour résoudre un problème sur une liste.
Théorie des graphes
- Les graphes d’intervalles : Étude d’une famille de graphes définis par l’intersection d’intervalles.
- Les graphes cordaux : Étude d’une famille de graphes contenant la famille des graphes d’intervalles.
- Théorème de Kirchhoff : Un théorème permettant de compter le nombre d’arbres couvrants dans un graphe.
- Formule de Cayley : Une autre formule de dénombrement du nombre d’arbres couvrants, cette fois-ci sur les graphes complets.
Théorie des langages
- Stabilité des langages rationnels : Un aperçu des différentes opérations stables sur les langages rationnels.
- Un critère de non régularité : on s’intéresse à une propriété sur les langages impliquant qu’ils ne sont pas reconnaissables par automate fini.
Complexité et Approximation
- Le problème des trois couleurs : Une preuve de la NP-complétude de 3-COLOR dans les cas planaires et non planaires.
- Coloration de Wigderson : Une méthode de coloration d’un graphe que l’on sait trois coloriable.
- Problème de la couverture par sommet : Une preuve de la NP-complétude de VERTEX COVER ainsi qu’un algorithme d’aproximation
Remerciement
Je remercie chaleureusement Pierre Mahmoud–Lamy qui a relu une bonne partie de ces exercices.