L'essentiel de l'informatique en prépa scientifique
Cours, exemples, QCM et exercices corrigés en Python et SQL
2e édition
Frantz Barrault
Ellipses
1 Représentation des nombres5
1.1 Bases et systèmes de numération5
1.2 Représentation des nombres dans un ordinateur8
1.3 Entiers naturels codés sur des mots de taille fixe9
1.4 Entiers relatifs codés sur des mots de taille fixe11
1.5 Entiers « longs » de Python12
1.6 Représentation des nombres réels15
QCM20
Exercices20
2 Nombres et booléens en Python25
2.1 Les nombres entiers25
2.2 Les nombres flottants26
2.3 Les booléens27
2.4 Liens entre entiers, flottants et booléens29
QCM30
Exercices31
3 Chaînes de caractères33
3.1 Notion de chaîne de caractères33
3.2 Opérations sur les chaînes de caractères35
3.3 Ordre et chaînes de caractères (comparaison)35
3.4 Des chaînes aux nombres et réciproquement37
3.5 Des chaînes aux listes de chaînes et réciproquement37
QCM38
Exercices39
4 Variables et structures de contrôle45
4.1 Variables45
4.2 Une fonction pour afficher, la fonction print47
4.3 Bloc d'instructions et indentations48
4.4 Structures conditionnelles49
4.5 Boucles50
QCM54
Exercices54
5 Listes, tuples et dictionnaires59
5.1 Les listes59
5.2 Les tuples64
5.3 Les dictionnaires65
5.4 Fonctions de hachage66
QCM70
Exercices70
6 Fonctions77
6.1 Introduction77
6.2 Définir ses propres fonctions78
6.3 Fonctions récursives83
6.4 Les limites de la récursivité88
6.5 Effets de bord90
6.6 Pour aller plus loin91
QCM92
Exercices93
7 Modules et fichiers101
7.1 Les modules101
7.2 Les fichiers105
QCM109
Exercices110
8 Complexité et preuve d'un algorithme115
8.1 Introduction115
8.2 Évaluation de la complexité algorithmique117
8.3 Preuve de correction, preuve de terminaison121
8.4 Tests123
QCM125
Exercices126
9 Images numériques129
9.1 Qu'est-ce qu'une image numérique ?129
9.2 Réduction et filtres131
9.3 Images en Python134
QCM138
Exercices138
10 Algorithmes de tri145
10.1 Généralité sur la notion d'ordre et le tri145
10.2 L'algorithme de tri par insertion146
10.3 L'algorithme de tri par sélection149
10.4 L'algorithme de tri fusion150
10.5 Tri rapide154
QCM156
Exercices156
11 Le problème du sac à dos159
11.1 Introduction159
11.2 Représentation des données159
11.3 Le sac à dos fractionnaire160
11.4 Le sac à dos 0-1162
11.5 Programmation dynamique168
11.6 Remarques sur la complexité170
11.7 Algorithme génétique171
12 Algorithmique du texte177
12.1 Généralité sur la recherche de sous-chaînes177
12.2 Recherche naïve de sous-chaînes178
12.3 Algorithme de Boyer-Moore181
Exercices183
13 Les k-moyennes et proches voisins189
13.1 L'algorithme KNN des k plus proches voisins189
13.2 Algorithme des k-moyennes193
14 Graphes197
14.1 Vocabulaire des graphes orientés197
14.2 Vocabulaire des graphes non orientés199
14.3 Connexité des graphes non orientés200
14.4 Matrice d'adjacence et liste d'adjacence d'un graphe non orienté200
14.5 Parcours en largeur d'un graphe orienté201
14.6 Parcours en profondeur d'un graphe207
14.7 Écriture récursive des algorithmes de parcours212
14.8 Le problème de la représentation des files par des listes en Python214
QCM215
Exercices216
15 Graphes pondérés221
15.1 Notion de graphe pondéré221
15.2 Algorithme de Prim223
15.3 Algorithme de Dijkstra228
15.4 Algorithme A*233
Exercices240
16 Jeux et I.A.243
16.1 Arbre de jeu243
16.2 L'algorithme minimax244
16.3 Introduction aux jeux de parité247
Exercices250
17 Notion de base de données251
17.1 Introduction251
17.2 Vocabulaire252
17.3 Les types de données en SQL254
17.4 En pratique254
Exercices254
18 Les bases des requêtes SQL255
18.1 Sélection des données255
18.2 Les fonctions d'agrégation et de regroupement262
18.3 Opérations ensemblistes266
Exercices267
19 Jointures et sous-requêtes269
19.1 Produit cartésien269
19.2 Jointure270
19.3 Sous-requêtes272
Exercices275
A Installer Python et SQL281
B Éditeurs et E.N.T. pour Python283
Index285