Préambule
Ces notes de cours sont issues du cours d’informatique commune (IPT) subi par les élèves du lycée Masséna des classes de première année MPSI (831), PCSI (833) et de deuxième année MP*, MP, PC*, PC.
Le cours présenté ici est très détaillé, et tous les points ne sont pas nécessairement abordés en classe : il se veut utile autant pour l’élève qui veut un récapitulatif que pour celui qui souhaite aller plus loin.
Le polycopié se divise en 4 parties, elles-mêmes subdivisées en 13 chapitres. À ceux-ci s’ajoute un dernier chapitre explicitant brièvement l’usage des modules usuels en Python, notamment Numpy. Les trois premières parties sont relatives au programme de première année, la quatrième au programme de deuxième année. Le plan choisi est le suivant :
— La première partie est dévolue à l’« initiation ». Malgré ce nom, elle est fondamentale, notamment les chapitres 2 et 3. Elle se subdivise en 4 chapitres :
— Le chapitre 0 est un chapitre d’introduction à l’informatique, il présente un point de vue historique sur le développement de cette discipline, les principaux éléments constitutifs d’un ordinateur et le rôle du système d’exploitation. Le cours présenté ici est habituellement présenté en fin d’année, par choix pédagogique : il est en effet plus facile d’expliquer précisément le comportement d’un micro-processeur à des élèves qui savent déja programmer et ont une connaissance du système de numération binaire.
— Le chapitre 1 présente de manière détaillée les éléments au programme concernant la programmation en Python. Il est en pratique présenté peu à peu en cours et en TP, parallèlement aux chapitres qui suivent. L’utilisation des modules n’est pas présentée en détail dans ce chapitre mais reléguée en fin de polycopié.
— Le chapitre 2 présente la représentation des nombres (entier et flottants) dans un ordinateur. Il est plus détaillé que ce que préconise le programme officiel, mais les algorithmes de changements de base sur les entiers offrent une bonne introduction à l’algorithmique. L’addition des entiers relatifs sur des registres de taille fixée permet de plus de comprendre le fonctionnement d’un processeur. Enfin, la représentation des flottants offre un premier avertissement sur les erreurs d’arrondis.
— Le chapitre 3 donne les outils pour l’analyse théorique des algorithmes (terminaison / correction / complexité). C’est un chapitre crucial où sont présentés les algorithmes « basiques » au programme de première année : parcours de listes, recherche dichotomique ou de motif dans une chaîne de caractères
— La deuxième partie est dévolue à l’analyse numérique. Elle est très (peut-être trop) détaillée, mais c’est également un choix pédagogique motivé par l’importance qu’occupent les questions d’analyse numérique dans les concours. Elle se découpe en 5 chapitres.
— Le chapitre 4 présente une sensibilisation aux erreurs numériques et fait suite au chapitre 2. Peut-être un peu rébarbative, il explique certains comportements « étranges » observés en TP, à cause de l’utilisation des nombres flottants.
— Le chapitre 5 présente les deux méthodes au programme pour la résolution d’équations numériques : la méthode de la dichotomie et la méthode de Newton.
— Le chapitre 6 présente la résolution d’équations linéaires via l’algorithme du pivot de Gauss. Là encore, on fait attention aux erreurs d’arrondis.
— Le chapitre 7 présente des méthodes d’intégration de fonctions. Bien que la seule méthode au programme soit la méthode des rectangles (à gauche), on étudie également des méthodes d’ordre supérieur, notamment la méthode des trapèzes qui fait des apparitions régulières aux concours.
— Le chapitre 8 présente des méthodes de résolution d’équations différentielles. On fait le lien avec le chapitre précédent : les méthodes de résolution sont vues comme des applications des méthodes d’intégration approchée. Là encore, seule la méthode d’Euler (explicite) est au programme, mais d’autres méthodes font également l’objet de questions aux concours.
— Le chapitre 9, unique chapitre de la partie 3 (Bases de données), présente les bases de SQL et de l’algèbre relationnelle. Le choix de présenter l’algèbre relationnelle (pas clairement au programme) est là aussi motivé par sa présence aux concours.
— La partie 4 (Algorithmique avancée) présente le programme de deuxième année.
— Le chapitre 10 présente les algorithmes de tris « naïfs », c’est-à-dire quadratiques. C’est une bonne occasion de mettre en pratique les concepts introduits au chapitre 3.
— Le chapitre 11 présente la structure de pile (seule structure abstraite au programme). Pour justifier le chapitre, plusieurs applications sont données. On présente également une autre structure abstraite, celle de file.
— Le chapitre 12 introduit la récursivité, en s’appuyant sur le chapitre précédent. Pour ne pas se cantonner aux exemples « triviaux » d’algorithmes récursifs, on présente notamment un algorithme « Diviser pour régner ».
— Enfin, le chapitre 13 présente, en lien avec le chapitre précédent, les deux algorithmes de tri efficaces au programme : le tri fusion et le tri rapide. On donne également un algorithme de calcul de la médiane en temps linéaire en moyenne, basé sur une variante du tri rapide.
— Le chapitre 14, relégué en annexe, donne une présentation des modules usuels. Bien que leur connaissance ne soit pas exigible à l’écrit des concours, les écrits proposent souvent des questions où ils sont utilisés (notamment Numpy), même si certaines fonctions sont données en formulaire. La connaissance des modules est également utile pour la deuxième épreuve de mathématiques à l’oral de Centrale, ou encore pour effectuer des modélisations dans un TIPE.
Licence. Cette œuvre est mise à disposition sous licence Attribution - Partage dans les Mêmes Conditions 2.0 France. Pour voir une copie de cette licence, visitez ou écrivez à Creative Commons, PO Box 1866, Mountain View, CA 94042, USA.
Table des matières
I Initiation 11
0 Ordinateurs, Systèmes d’exploitation et Python 13
0.1 Qu’est ce qu’un ordinateur?............ . . . . . . . . . 13
0.1.1 Turing et ses machines............ . . . . . . . . 13
0.1.2 Prémices aux ordinateurs et modèle de Von Neumann........ . 15
0.1.3 Le rôle de chaque élément............. . . . . . . 16
0.1.4 Avantages et inconvénients............ . . . . .17
0.1.5 De nos jours ................ . . 17
0.1.6 Ordres de grandeur............... 17
0.2 Le système d’exploitation............... 18
0.2.1 Le multitâche................ . . 19
0.2.2 Identification des utilisateurs............ . . . . 19
0.2.3 Organisation des fichiers............ . . . . . . .20
0.2.4 Droits d’accès................ . . 20
0.3 Le langage Python................ . . . 21
1 Programmation en Python 23
1.1 Types simples et expressions ............ . . . . . . . . 23
1.1.1 Expressions................ . . . 23
1.1.2 Entiers................ . . . . . . 24
1.1.3 Flottants ................ . . . . 25
1.1.4 Booléens................ . . . . . 25
1.2 Variables ................ . . . . . . . . 26
1.2.1 Identificateurs ................ . 26
1.2.2 Variables ................ . . . . 27
1.3 Structures de contrôle................ . 28
1.3.1 Python et l’indentation............. . . . . . . . 28
1.3.2 Instruction conditionnelle if/else (si/sinon) ........ . . . . . . . 28
1.3.3 Boucle conditionnelle while (tant que)...........29
1.3.4 Boucle inconditionnelle for (pour ) ........... 30
1.3.5 Break et Continue............... 31
1.3.6 Boucles imbriquées............... 32
1.4 Structures de données................ . 32
1.4.1 Listes ................ . . . . . . 32
1.4.2 Tuples................ . . . . . . 35
1.4.3 Chaînes de caractères ............ . . . . . . . . 36
1.5 Fonctions................ . . . . . . . . 38
1.5.1 Motivation ................ . . . 38
1.5.2 Notions et syntaxe de base............ . . . . .38
1.5.3 Variables locales et globales............ . . . . . 41
1.5.4 Passage par références............. . . . . . . . .42
1.5.5 Une fonction : un objet comme les autres........ . . . . . . . . 42
1.6 Entrées/Sorties................ . . . . . 43
1.6.1 print et input................ . .43
1.6.2 Fonctions pour les fichiers............ . . . . . .44
2 Entiers, Flottants 47
2.1 Représentation des entiers naturels............ . . . . . 47
2.1.1 Écriture dans une base............ . . . . . . . . 47
2.1.2 Changement de base............ . . . . . . . . . 48
2.2 Représentation des entiers relatifs en binaire, additions......... . . . . 51
2.2.1 Entiers naturels de taille fixée et additions......... . . . . . . . 51
2.2.2 Entiers relatifs................ .52
2.2.3 En pratique. ................ . . 54
2.3 Représentation des nombres réels............ . . . . . . 55
2.3.1 Représentations des nombres dyadiques en binaire ........ . . . 55
2.3.2 Nombres flottants normalisés............ . . . . 56
2.3.3 Exceptions ................ . . . 56
2.3.4 Arrondis................ . . . . . 57
3 Analyse d’algorithmes 59
3.1 Terminaison................ . . . . . . . 59
3.1.1 Quelques exemples, exponentiation rapide........ . . . . . . . . 60
3.1.2 Variant de boucle................ 60
3.2 Correction................ . . . . . . . . 61
3.2.1 Correction des boucles while............ . . . . 61
3.2.2 Correction des boucles for............ . . . . . 62
3.2.3 D’autres exemples : parcours linéaires de listes ........ . . . . .63
3.2.4 Recherche efficace dans une liste triée : recherche dichotomique.... . . . . . . . 63
3.3 Complexité................ . . . . . . . 64
3.3.1 Introduction et tri par sélection............ . . . 64
3.3.2 Complexité : définitions et méthodes............ 66
3.3.3 Applications aux algorithmes vus précédemment........ . . . . 67
3.3.4 Quelques ordres de grandeur ............ . . . . 68
3.4 Recherche d’un motif dans une chaîne de caractères........ . . . . . . . 68
II Analyse numérique 71
4 Estimation d’erreurs numériques 73
4.1 Rappels sur la représentation des nombres réels........ . . . . . . . . . 73
4.2 Erreurs sur les sommes et produits............ . . . . . 73
4.2.1 Erreur sur la somme............ . . . . . . . . . 73
4.2.2 Erreur sur le produit............ . . . . . . . . . 75
4.3 Phénomènes d’instabilité et remèdes............ . . . . 75
4.3.1 Phénomènes de compensation............ . . . . 75
4.3.2 Problèmes mal posés............ . . . . . . . . . 78
5 Résolution d’équations numériques 81
5.1 Motivation ................ . . . . . . . 81
5.2 Méthode de la dichotomie............... 81
5.3 Méthode de Newton................ . . 83
5.3.1 Principe et code Python............ . . . . . . . 83
5.3.2 Convergence de la méthode de Newton........... 84
5.3.3 Variations et extensions............ . . . . . . . 85
6 Pivot de Gauss et résolution de systèmes linéaires 87
6.1 Introduction................ . . . . . . . 87
6.2 Formalisme matriciel et opérations élémentaires........ . . . . . . . . . 87
6.2.1 Formalisme matriciel............ . . . . . . . . . 87
6.2.2 Opérations élémentaires............ . . . . . . .88
6.3 L’algorithme du pivot de Gauss............ . . . . . . . 88
6.4 Écriture du pivot................ . . . . 90
6.5 Quelques exemples................ . . . 90
6.6 En Python ................ . . . . . . . 92
7 Calcul approché d’intégrales 93
7.1 Introduction................ . . . . . . . 93
7.2 Idée générale de l’approximation d’intégrales............ 93
7.3 Méthodes des rectangles................ 94
7.3.1 Principe général des méthodes élémentaire et composée ........ 94
7.3.2 Codes Python pour les méthodes composées........ . . . . . . . 94
7.3.3 Étude théorique ................ 95
7.4 Introduction aux méthodes de Newton-Cotes ........... 96
7.4.1 Principe général ................ 96
7.4.2 Méthode des trapèzes ............ . . . . . . . . 96
7.4.3 Méthode de Simpson............ . . . . . . . . . 97
7.4.4 Méthodes d’ordre supérieur............ . . . . . 98
7.4.5 Peut-on faire mieux?............ . . . . . . . . . 99
7.4.6 Influence des erreurs d’arrondi ............ . . . 100
7.5 Quelques estimations d’erreurs ............ . . . . . . . 100
7.6 Et les méthodes intégrées en Python?............ . . . 103
8 Résolution approchée d’équations différentielles 105
8.1 Introduction................ . . . . . . . 105
8.1.1 Motivation ................ . . . 105
8.1.2 Reformulation ................ . 105
8.1.3 Lien avec l’intégration............ . . . . . . . . 106
8.1.4 Formulation « à la odeint »............ . . . . .106
8.2 Méthode d’Euler explicite............... 107
8.2.1 Principe de la méthode : les rectangles à gauche ........ . . . . 107
8.2.2 Code(s) Python................ . 108
8.2.3 Variante pour les fonctions à valeurs vectorielles ........ . . . . 109
8.2.4 Exemple complet : le pendule amorti............ 109
8.3 Quelques notions d’analyse numérique............ . . . 110
8.3.1 Erreur sur l’exponentielle............ . . . . . . 110
8.3.2 Notion d’erreur de consistance ............ . . . 110
8.3.3 Ordre d’un schéma............... 111
8.4 Autres méthodes................ . . . . 112
8.4.1 Méthode d’Euler implicite............ . . . . . .112
8.4.2 Schéma prédicteur correcteur explicite (Runge-Kutta 2)........ 114
8.4.3 Méthode de Heun............... 114
8.4.4 Méthode Runge-Kutta 4............ . . . . . . . 115
8.4.5 Comparaison avec la tension aux bornes du condensateur....... 116
III Bases de données 119
9 Requêtes dans les bases de données 121
9.1 Introduction : limite des structures de données plates pour la recherche d’informations . . . . . . . . . 121
9.2 Présentation succincte des bases de données............ 122
9.2.1 Rôle des bases de données............ . . . . . . 122
9.2.2 Un exemple avec quelques requêtes............ .122
9.2.3 Architecture client-serveur............ . . . . . . 123
9.2.4 Abstraction des bases de données............ . . 124
9.3 Vocabulaire des bases de données............ . . . . . . 124
9.3.1 Modélisation en tableau............ . . . . . . . 124
9.3.2 Vocabulaire................ . . .124
9.3.3 Contraintes................ . . . 125
9.3.4 Clés................ . . . . . . . 125
9.4 Algèbre relationnelle simple............ . . . . . . . . . 126
9.4.1 Définition................ . . . . 126
9.4.2 Opérateurs ensemblistes............ . . . . . . .126
9.4.3 Opérateurs spécifiques............ . . . . . . . . 126
9.5 SQL.................... 128
9.5.1 Introduction ................ . . 128
9.5.2 Syntaxe................ . . . . . 128
9.6 Agrégats et fonctions d’agrégation ............ . . . . .129
9.6.1 Agrégats................ . . . . . 129
9.6.2 SQL................ . . . . . . . 130
9.6.3 Sélection après agrégation............ . . . . . . 130
9.7 Affichage des résultats................ . 131
9.7.1 Ordonner les résultats avec ORDER BY........ . . . . . . . . . 131
9.7.2 Limiter l’affichage avec LIMIT et OFFSET........ . . . . . . . 132
9.8 Composition de requêtes................ 132
9.9 Produit cartésien et jointure............ . . . . . . . . . 133
9.9.1 Introduction ................ . . 133
9.9.2 Notion de clé étrangère ............ . . . . . . . 133
9.9.3 Produit................ . . . . . 133
9.9.4 Division................ . . . . . 134
9.9.5 Jointure naturelle................ 134
9.9.6 Jointure................ . . . . . 135
9.10 Tables multiples dans SQL............... 135
9.10.1 Produit cartésien................ 135
9.10.2 Jointure naturelle................ 135
9.10.3 Division................ . . . . . 135
9.10.4 Jointure................ . . . . . 136
9.11 Pour conclure................ . . . . . . 136
IV Algorithmique « avancée » 137
10 Algorithmes naïfs de tri 139
10.1 Introduction : le problème du tri............ . . . . . .139
10.2 Tri par sélection................ . . . . 141
10.3 Tri à bulles................ . . . . . . . 142
10.4 Tri par insertion................ . . . . 143
10.5 Conclusion sur les tris par comparaisons quadratiques ........ . . . . .144
10.6 Un tri qui n’est pas un tri par comparaisons : le tri par comptage....... 145
11 Structures de données linéaires : piles (et files) 147
11.1 Les Piles : une classe abstraite ............ . . . . . . . 147
11.2 Implémentation d’une pile de capacité finie ............ 149
11.3 Implémentation d’une pile de capacité infinie ........... 150
11.4 Application à l’évaluation d’une expression postfixe........ . . . . . . . 151
11.5 Introduction à la programmation orientée objet........ . . . . . . . . . 153
11.5.1 Bases de la POO................ 153
11.5.2 Implémentation d’une pile de capacité finie avec une liste....... 153
11.5.3 Implémentation d’une pile non bornée avec une liste Python (vue comme une liste chaînée) . .154
11.5.4 Implémentation personnalisée d’une pile non bornée (liste chaînée).... . . . . . 154
11.6 Structure de file................ . . . . . 155
12 Récursivité 157
12.1 Principes de la récursivité............... 157
12.1.1 Définition................ . . . . 157
12.1.2 La pile d’exécution............... 157
12.1.3 D’autres exemples............... 158
12.1.4 Limites de la récursivité............ . . . . . . . 159
12.1.5 Avantage de la récursivité............ . . . . . .160
12.2 Terminaison, correction et complexité d’une fonction récursive........ . 162
12.2.1 Terminaison................ . . . 162
12.2.2 Correction................ . . . . 163
12.2.3 Complexité des fonctions récursives............ . 163
12.3 Diviser pour régner et algorithme de Karatsuba........ . . . . . . . . . 165
13 Algorithmes de tri efficaces, Médiane 169
13.1 Rappels sur la stratégie « Diviser pour régner »........ . . . . . . . . . 169
13.2 Tri Fusion................ . . . . . . . .169
13.2.1 La fonction de fusion............ . . . . . . . . . 169
13.2.2 Le tri en lui-même............... 171
13.3 Tri Rapide (QuickSort) ................173
13.3.1 Fonction de partition............ . . . . . . . . . 173
13.3.2 Le tri en lui-même............... 175
13.4 Une borne inférieure sur la complexité des tris par comparaisons .......177
13.5 Application : calcul de la médiane............. . . . . .177
13.6 Conclusion et comparaison des tris............ . . . . .179
VAnnexes 181
14 Modules usuels 183
14.1 Module math................ . . . . . . 183
14.1.1 Importation du module ............ . . . . . . . 183
14.1.2 De l’aide!................ . . . . 183
14.2 Module numpy................ . . . . . . 184
14.3 Module matplotlib................. . . 186
14.3.1 Options pyplot................ . 186
14.3.2 Quelques exemples............... 186
14.4 Module scipy................ . . . . . . 188
14.4.1 Résolution d’équations numériques............ . 188
14.4.2 Intégration de fonctions............ . . . . . . . 189
14.4.3 Intégration d’équations différentielles............ 189
14.5 Quelques autres modules................ 190
Première partie
Initiation
Chapitre 0
Ordinateurs, Systèmes d’exploitation et Python
0.1 Qu’est ce qu’un ordinateur?
Si on tente rapidement de définir ce qu’est un ordinateur au sens large du terme (y compris tablettes, smartphones ), on peut lister les éléments communs suivants :
— un ordinateur reçoit des informations par l’intermédiaire d’un utilisateur ou d’un réseau;
— un ordinateur émet des informations via le réseau ou un de ses périphériques; — un ordinateur a besoin d’une source d’énergie pour fonctionner.
Néanmoins cette première tentative s’avère infructueuse, on peut penser à plusieurs contre-exemples qui satisfont ces trois critères et qui ne sont pas pour autant des ordinateurs :
— un réfrigérateur nécessite une source d’énergie, il reçoit des informations de la part de capteurs (température ), il en émet sous la forme de signaux lumineux électriques;
— un interrupteur fonctionnant avec la luminosité ambiante reçoit de l’information par le biais de son capteur et transmet de l’information (ouvert-fermé), de plus le capteur peut nécessiter une source d’énergie pour fonctionner;
— le système ABS d’aide au freinage d’urgence d’une voiture reçoit également de l’information (vitesse ) et en emet sous forme de pression hydraulique sur le système de freinage;
— plus généralement, tout système électronique embarqué (système électronique et informatique autonome, ayant une tâche précise) vérifie ces trois critères. Mais l’utilisateur ne peut a priori pas détourner le système pour lui faire exécuter une autre tâche.
Tout cela montre que la définition de ce qu’est un ordinateur n’est pas une chose si triviale que cela. Tout ceci est lié à une des grandes problématiques du siècle dernier : qu’est ce qu’un calcul?
0.1.1 Turing et ses machines
Dans les années trente, quatre mathématiciens au moins cherchent à répondre à cette question : Kleene, Church, Turing et Post. Les questions posées commencent à recevoir une réponse et c’est la naissance de la calculabilité, qui vise à définir précisément ce qui est effectivement calculable. Alan Turing explore une autre approche originale, qui va lier la notion de « calcul » à la notion de « machine ». Il imagine une machine qui peut fonctionner sans intervention humaine.
Figure 1 – Alan Turing
Cette machine possède les caractéristiques suivantes :
— un ruban : aussi long que nécessaire, sur lequel la machine peut lire des données et en écrire d’autres, le ruban est divisé en cases (voir figure 2);
— une tête de lecture, à tout moment positionnée au niveau d’une case du ruban;
0.1. QU’EST CE QU’UN ORDINATEUR?
— un ensemble fini d’états : quand la machine lit un symbole, elle réagit en fonction de son état actuel et du symbole lu, en changeant d’état, en modifiant le symbole sur le ruban et en déplaçant la tête de lecture d’un cran sur la droite ou sur la gauche (elle n’est pas forcée d’effectuer toutes ces actions).
|
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
Figure 2 – Un ruban d’une machine de Turing
Donnons une brève description d’une machine de Turing testant si un nombre naturel n écrit en binaire est divisible par 3. On suppose que sur le ruban d’entrée (unidirectionnel, infini vers la droite, comme en figure 2) se trouve le mot écrit en binaire de gauche à droite, les bits de poids forts étant au début. Les autres cases du ruban sont vides. La machine doit écrire à la suite du nombre (à la première case vide), le symbole « V » ou « F » (pour vrai ou faux) suivant si le nombre est divisible par 3 ou non. On peut imaginer une machine à 4 états résolvant le problème :
— 3 états correspondant à la congruence modulo 3 de la portion du nombre lue jusqu’ici. Notons les 0,1,2.
— Un état supplémentaire (final) indiquant que le calcul est fini.
Pour compléter la description de notre machine de Turing, il faut donner la fonction de transition entre les états, c’est à dire la façon dont la machine réagit suivant son état et le symbole lu. Le tableau suivant donne la congruence modulo 3 de 2a et 2a + 1 en fonction de celle de a :
|
a |
0 |
1 |
2 |
|
2a |
0 |
2 |
1 |
|
2a + 1 |
1 |
0 |
2 |
Cette table nous donne l’essentiel de la fonction de transition : si la portion des bits lue jusque-là représente a en binaire, lire un 0 mène à la représentation de 2a, et lire un 1 mène à celle de 2a + 1. Si l’état courant représente la congruence modulo 2 du nombre obtenu en gardant seulement les k premiers bits du ruban, on sait dans quel état passer à la lecture du (k + 1)-ème. Dans tous les cas, on déplace la tête de lecture d’un cran vers la droite. Le lecteur vérifiera qu’en commençant à l’état 0, la lecture successive des bits du ruban de la figure 2 fait passer successivement par les états 1,2,2,1,2,2,2,1,0,0. Lorsqu’on atteint la première case vide, il suffit de remplacer le symbole « Vide » par « V » ou « F » suivant si l’on se trouve dans l’état 0 ou non, et de passer en état final. Ici, on écrirait « V » car on est dans l’état 0. Le nombre écrit sur le ruban est en fait 666 en binaire, qui est bien divisible par 3.
Dans l’exemple précédent, on a fait essentiellement de la lecture, mais on peut aussi calculer : pour additionner 1 au nombre naturel écrit en binaire sur le ruban (toujours avec la convention que les bits de poids forts sont au début), il suffit de se déplacer jusqu’à la fin du mot, (caractérisé par une case vide), revenir d’un cran à gauche, et de remplacer ensuite les 1 par des 0 en se déplaçant vers la gauche, jusqu’à retomber sur un 0 ou une case vide, qu’on transforme en 1, voir figure 3.
Figure 3 – Une machine de Turing permettant d’additionner 1 au nombre écrit sur le ruban
Attention, la « machine de Turing » reste un objet théorique. Cette machine est idéalisée car le ruban est supposé toujours suffisamment long pour permettre le calcul (il est donc virtuellement infini, même si une machine exécutant un calcul qui termine n’utilisera qu’une partie finie du ruban). Avec ce formalisme, un algorithme est simplement une machine de Turing particulière .
Une machine de Turing est essentiellement décrite par ses états possibles et sa fonction de transition. Comme le nombre d’états est fini, la description d’une machine de Turing est elle aussi finie, et peut elle même être encodée en binaire (ou avec un alphabet fini quelconque), et écrite sur un ruban. Turing montre qu’il existe (mathématiquement) une machine de Turing universelle : elle est capable de prendre sur un ruban la description de n’importe quelle machine de Turing et de simuler son exécution sur toute entrée placée à la suite sur le ruban. Un ordinateur est donc la réalisation concrète d’une telle machine de Turing universelle : il est capable d’exécuter un algorithme pour peu qu’il soit traduit dans un langage de programmation idoine.
Nos ordinateurs sont en fait un peu plus complexes afin d’être plus efficaces : se déplacer de case en case étant source d’inefficacité, il vaut mieux permettre de sauter d’une case à une autre case grâce à une adresse (et donc numéroter les cases du ruban). Actuellement, on parle plutôt de mémoire que de ruban, mais du point de vue de la calculabilité cela ne change rien.
0.1.2 Prémices aux ordinateurs et modèle de Von Neumann
Figure 4 – L’ENIAC
La première réalisation concrète d’une machine de Turing date de 1941, c’est le Z3 allemand, qui est électromécanique. La première réalisation entièrement électronique est l’ENIAC, qui date de 1943. L’ensemble fut conçu par John William Mauchly et John Eckert et ne fut pleinement opérationnel qu’en 1946. Von Neumann intégra l’équipe en 1944 et publia un rapport sur la conception de l’EDVAC (un autre ordinateur électronique) en 1945.
Figure 5 – Architecture de Von Neumann
Ce rapport décrit un schéma d’architecture de calculateur, organisé en trois éléments (unité arithmétique, unité de commande et mémoire contenant programme et données). Il décrit aussi des principes de réalisation pour ces éléments, notamment les opérations arithmétiques. Si ce dernier aspect dépend partiellement de la technologie de l’époque (et a
0.1. QU’EST CE QU’UN ORDINATEUR?
donc vieilli), le modèle d’architecture, qui marque une transition profonde avec les pratiques antérieures, reste d’une étonnante actualité. Ce modèle, auquel reste attaché le nom de Von Neumann, est représenté par le schéma de la figure 5. Il y a schématiquement quatre composants principaux :
— le processeur : qui se décompose en une unité de commande et une unité arithmétique et logique;
— la mémoire : qui contient des instructions et des données;
— les périphériques d’entrée-sortie : qui permettent une communication entre l’utilisateur et les machines (via clavier, souris, écran, );
— le bus : qui est le canal de communication entre la mémoire, le processeur et les périphériques.
La première innovation est la séparation nette entre l’unité de commande, qui est chargée d’organiser le flot des instructions, et l’unité arithmétique, chargée de l’exécution proprement dite de ces instructions. La seconde innovation est l’idée du programme enregistré : fini les rubans, cartes à trous Les instructions et les données sont maintenant enregistrées dans la mémoire selon un codage conventionnel. Un compteur ordinal ou pointeur d’instruction (program counter en anglais), contient l’adresse de l’instruction en cours d’exécution; il est automatiquement incrémenté après exécution de l’instruction, et explicitement modifié par les instructions de branchement (if, goto, jump ).
0.1.3 Le rôle de chaque élément.
Le processeur. Le processeur (CPU) est le cerveau de l’ordinateur, il donne des ordres aux périphériques et à la mémoire et est responsable de l’exécution du programme de l’ordinateur. Le processeur dispose d’une toute petite mémoire, typiquement de l’ordre de quelques dizaines ou centaines de mots mémoire (groupes de 64 bits), qu’on appelle des registres. La fonction du registre de données est de contenir les données transitant entre l’unité de traitement et l’extérieur. La fonction de l’accumulateur est principalement de contenir les opérandes ou les résultats des opérations de l’unité arithmétique et logique. Son unité arithmétique et logique permet de réaliser les calculs : — opérations arithmétiques binaires : addition, multiplication, soustraction, division; — opérations logiques, conjonction, disjonction et négation.
Figure 6 – Le circuit (sous forme de portes logiques) d’une unité arithmétique et logique sur des mots de 2 bits
L’unité de contrôle accède à la mémoire via le bus, et peut lire une case mémoire ou y écrire. Cependant cette unité ne contient pas le programme à exécuter : les instructions à exécuter sont codées sous la forme d’une suite de bits stockée en mémoire. Toutes les instructions sont réalisées dans l’ordre, mais les instructions de saut modifient cet ordre.
— une instruction de saut conditionnel modifie cet ordre si une certaine condition est vérifiée.
— une instruction de saut inconditionnel modifie cet ordre sans condition.
Les instructions for et while (qui n’existent pas en langage machine), peuvent être traduites par plusieurs instructions de saut conditionnelles et inconditionnelles.
La mémoire. La mémoire est une suite de chiffes binaires nommés bits, organisés en paquets de huit (les octets) puis en mots mémoire de 64 bits . Un mot en mémoire peut représenter plusieurs choses : une instruction, un entier La signification du mot dépend de l’utilisation qu’on en fait. La mémoire ne sert qu’à stocker ces mots, elle ne réalise aucune opération et n’effectue aucun calcul. Chaque mot possède une adresse, avec cette adresse on peut lire un mot ou alors écrire un autre mot à la place. Cette adresse est attribuée de manière aléatoire, d’où le nom de Random access memory (RAM).
Les périphériques. De manière formelle il s’agit de mémoire supplémentaire dans laquelle le processeur peut écrire pour donner des ordres au périphérique (afficher telle couleur sur tel pixel de l’écran) ou lire (réagir à telle touche tapée sur un clavier).
