Exercices de C++ spécifiques à ICC (lien programmation - théorie)

Cette page regroupe les exercices de programmation ayant pour thème des sujets de la partie théorie. La page est ordonnée par sujet de la partie théorie (ces sujets sont souvent traités dans des exercices de programmation plus tard dans le semestre car nécessitent des notions de programmation non encore vues à ce moment là).

Semaine 2 -- Algorithmes : bases

• Tous les exercices de programmation des semaines 3 et 4 sont de bons entraînements pour l’écriture d’algorithmes assez simples.
• En particulier, l'exercice supplémentaire fourni en semaine 5 propose de coder l'algorithme d'Euclide (recherche de PGCD).
• L'exercice supplémentaire n°11 de la semaine 4 MOOC (semaine 6 d'ICC) revient sur la recherche par dichotomie.
• L'exercice supplémentaire fourni en semaine 7 revient sur les algorithmes de tris.
• Un des exercices supplémentaires fournis en semaine 10 vous propose de résoudre le problème dit « de tranche maximale » avec différents algorithmes, dont la complexité varie de Ω(n³) à Ω(n).

Semaine 3 -- Algorithmes : méthodes de résolution

• L'exercice supplémentaire fourni en semaine 6 propose de coder une version récursive du calcul de la factorielle d'un nombre.
• L'exercice n°14 de la semaine 4 MOOC (semaine 6 d'ICC) s'intéresse à calculer les termes de la suite de Fibonacci (récursive).
• Le troisième exercice supplémentaire proposé en semaine 8 s'intéresse à programmer les tours de Hanoï.

Semaine 4 -- Théorie de la complexité

• Un exercice supplémentaire fourni en semaine 9 vous propose de résoudre le problème dit « du sac à dos » (problème NP-complet) ;
• et un autre exercice supplémentaire de la même semaine vous propose de coder une machine de Turing.

Semaine 5 -- Représentation des nombres

Ce qu'il faut surtout retenir de cette leçon pour la programmation, c'est de ne jamais faire de test d'égalité stricte entre deux double : ne faites pas

x == y

mais plutôt :

abs(x-y) < epsilon

Voici ensuite quelques idées de programmes à faire en C++ liés à ce chapitre :

• écrire un programme qui convertit de décimal en binaire et réciproquement : voir le premier exercice supplémentaire proposé en semaine 8 ;
• (pas encore rédigé/corrigé) écrire un programme qui demande une taille d'exposant et de mantisse ; puis qui traduit en représentation binaire à virgule flottante des nombres décimaux entrés au clavier.

Semaine 6 -- Signaux et filtres

Dans « l'étude de cas » de la partie programmation de la semaine 7, nous voyons comment calculer un filtre passe-bas (la « moyenne mobile discrète ») d'un signal déjà échantillonné.

Semaine 7 -- Th. d'échantillonnage

• Un des exercices supplémentaires de la semaine 9 vous propose de coder un signal, son échantillonnage et la reconstruction de celui-ci pour voir l'effet de la fréquence d'échantillonnage sur le résultat et « jouer » avec les résultats du théorème d'échantillonnage.

Semaine 8 -- Entropie

• Un des exercices supplémentaires de la semaine 8 propose de calculer l'entropie de chaînes de caractères et de distributions de probabilités.

Semaine 9 -- Th. de codage, codage de Huffman

• Un des exercices supplémentaires de la semaine 9 vous propose de réaliser des codes de Huffman de textes.