Livre_silo 30 août 2013 16:32 Page 7
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
VII
Table des matières
4.2.2 Indentation signifiante . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
4.2.3 Test avec alternative . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.2.4 Tests imbriqués . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4.3 Boucles conditionnelles . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.3.1 Nécessité des boucles . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.3.2 Syntaxe d’une boucle conditionnelle . . . . . . . . . . . . . . . . . . . . 96
4.3.3 Terminaison de boucle . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
4.3.4 Invariant de boucle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4.3.5 Boucle infinie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
4.4 Boucles inconditionnelles . . . . . . . . . . . . . . . . . . . . . . . . . . 104
4.4.1 Boucle for . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
4.4.2 Valeurs itérables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
4.4.3 L’itérable range . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
4.4.4 Interrompre une boucle . . . . . . . . . . . . . . . . . . . . . . . . . . 108
4.4.5 Boucles imbriquées . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
4.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
C
Fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
5.1 La notion de fonction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
5.1.1 Le retour de valeur . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
5.1.2 Variables globales et locales . . . . . . . . . . . . . . . . . . . . . . . . 119
5.1.3 Ordre d’évaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
5.1.4 Passage par valeur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
5.2 Mécanismes avancés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
5.2.1 Fonctions locales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
5.2.2 Fonctions comme valeurs de première classe . . . . . . . . . . . . . . . . . 124
5.2.3 Fonctions partielles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
5.2.4 Fonctions de bibliothèque . . . . . . . . . . . . . . . . . . . . . . . . . 127
5.2.5 Méthodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
5.3 La récursivité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
5.3.1 Concevoir une fonction récursive . . . . . . . . . . . . . . . . . . . . . . 132
5.3.2 Terminaison et correction d’une fonction récursive . . . . . . . . . . . . . . 135
5.3.3 Complexité d’une fonction récursive . . . . . . . . . . . . . . . . . . . . 138
5.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
C
Notions de complexité et algorithmique sur les tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
6.1 Complexité d’un algorithme . . . . . . . . . . . . . . . . . . . . . . . . . 144
6.1.1 Plusieurs algorithmes pour un même problème . . . . . . . . . . . . . . . 144
6.1.2 Complexité et notation O . . . . . . . . . . . . . . . . . . . . . . . . . 146
6.1.3 Différentes nuances de complexité . . . . . . . . . . . . . . . . . . . . . 148
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
VII
Table des matières
4.2.2 Indentation signifiante . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
4.2.3 Test avec alternative . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.2.4 Tests imbriqués . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4.3 Boucles conditionnelles . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.3.1 Nécessité des boucles . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.3.2 Syntaxe d’une boucle conditionnelle . . . . . . . . . . . . . . . . . . . . 96
4.3.3 Terminaison de boucle . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
4.3.4 Invariant de boucle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4.3.5 Boucle infinie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
4.4 Boucles inconditionnelles . . . . . . . . . . . . . . . . . . . . . . . . . . 104
4.4.1 Boucle for . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
4.4.2 Valeurs itérables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
4.4.3 L’itérable range . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
4.4.4 Interrompre une boucle . . . . . . . . . . . . . . . . . . . . . . . . . . 108
4.4.5 Boucles imbriquées . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
4.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
C
Fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
5.1 La notion de fonction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
5.1.1 Le retour de valeur . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
5.1.2 Variables globales et locales . . . . . . . . . . . . . . . . . . . . . . . . 119
5.1.3 Ordre d’évaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
5.1.4 Passage par valeur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
5.2 Mécanismes avancés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
5.2.1 Fonctions locales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
5.2.2 Fonctions comme valeurs de première classe . . . . . . . . . . . . . . . . . 124
5.2.3 Fonctions partielles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
5.2.4 Fonctions de bibliothèque . . . . . . . . . . . . . . . . . . . . . . . . . 127
5.2.5 Méthodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
5.3 La récursivité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
5.3.1 Concevoir une fonction récursive . . . . . . . . . . . . . . . . . . . . . . 132
5.3.2 Terminaison et correction d’une fonction récursive . . . . . . . . . . . . . . 135
5.3.3 Complexité d’une fonction récursive . . . . . . . . . . . . . . . . . . . . 138
5.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
C
Notions de complexité et algorithmique sur les tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
6.1 Complexité d’un algorithme . . . . . . . . . . . . . . . . . . . . . . . . . 144
6.1.1 Plusieurs algorithmes pour un même problème . . . . . . . . . . . . . . . 144
6.1.2 Complexité et notation O . . . . . . . . . . . . . . . . . . . . . . . . . 146
6.1.3 Différentes nuances de complexité . . . . . . . . . . . . . . . . . . . . . 148