Conception d’algorithmes Principes et 150 exercices non corrigés 2016 - PAR Patrick Bosc, Marc Guyomard et Laurent Miclet :
1 Mathématiques et informatique : notions utiles 1
1.1 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Démonstrations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.2 Dénombrements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2 Complexité d’un algorithme 17
2.1 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3 Spécification, invariants, itération 23
3.1 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4 Diminuer pour résoudre, récursivité 41
4.1 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
5 Essais successifs 49
5.1 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
6 PSEP 79
6.1 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
7 Algorithmes gloutons 87
7.1 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
8 Diviser pour Régner 115
8.1 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
9 Programmation dynamique 187
9.1 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
9.1.1 Découpe - Partage : problèmes à une dimension . . . . . . . . . . . . 188
9.1.2 Découpe - Partage : problèmes à deux dimensions . . . . . . . . . . . 196
9.1.3 Graphes - Arbres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
9.1.4 Séquences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
9.1.5 Images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
9.1.6 Jeux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
9.1.7 Problèmes pseudo-polynomiaux . . . . . . . . . . . . . . . . . . . . . 241
