Les bases de l'informatique et de la programmation

Les bases de l’informatique et de la programmation

E´cole polytechnique

Franc¸ois Morain

Table des mati`eres

I        Introduction `a  la  programmation         11

1. Les premiers pas en Java        13

1. Le premier programme        13

1. E´criture et execution´         13
2. Analyse  de ce programme        14

1. Faire  des calculs simples        15
2. Types primitifs        15
3. Affectation        16
4. Op´erations         17

1. R`egles d’´evaluation         17
2. Incr´ementation et d´ecrementation         18

1. Fonctions        19

1. Suite d’instructions        21

1. Expressions bool´eennes         21

1. Op´erateurs de comparaisons         21
2. Connecteurs        22

1. Instructions conditionnelles        22

1. If-else        22
2. Forme compacte        23
3. Aiguillage        23

1. It´erations         24

1. Boucles pour        24
2. It´erations  tant que         26
3. It´erations  r´ep´eter  tant que         27

1. Terminaison des programmes        28
2. Instructions de rupture de contrˆole         28
3. Exemples        28

1. M´ethode de Newton         28

1. Fonctions   :  th´eorie et  pratique         31

1. Pourquoi ´ecrire des fonctions         31
2. Comment ´ecrire des fonctions         32

1. Syntaxe        32
2. Le type sp´ecial void         33

1. Visibilit´e des variables         33
2. Quelques conseils pour ´ecrire un programme         35
3. Quelques exemples de programmes complets        36

1. E´criture binaire d’un entier         36

3

1. Calcul du jour correspondant a` une date         37

1. Tableaux        41

1. D´eclaration,  construction,  initialisation         41
2. Premiers exemples        42
3. Tableaux a` plusieurs dimensions, matrices         43
4. Les tableaux  comme arguments de fonction        44
5. Exemples d’utilisation des tableaux        44

1. Algorithmique des tableaux        44
2. Un peu d’alg`ebre lin´eaire         46
3. Le crible d’Eratosthene        47
4. Jouons a` l’escarmouche         47
5. Pile        50

1. Composants d’une classe        53

1. Constantes  et variables globales        53
2. Les classes pour d´efinir des enregistrements         53
3. Constructeurs        54
4. Les m´ethodes statiques et les autres         54
5. Utiliser plusieurs classes        56
6. Public et private        56
7. Un exemple de classe pr´ed´efinie  : la classe String         57

1. Propri´et´es         57
2. Arguments de main        58

1. Les objets comme  arguments de fonction        59

1. R´ecursivit´e         61

1. Premiers exemples        61
2. Un pi`ege subtil   : les nombres de Fibonacci         64
3. Fonctions  mutuellement r´ecursives         65

1. Pair  et impair  sont dans un bateau        66
2. D´eveloppement du sinus et du cosinus         66

1. Diviser pour r´esoudre         67

1. Recherche  d’une racine par dichotomie        67
2. Les tours de Hanoi        68

1. Un peu de th´eorie         69

1. La fonction d’Ackerman        69
2. Le probl`eme de la terminaison         71

1. Probl´ematiques  classiques en informatique         73

1. Introduction a` la  complexit´e  des  algorithmes         75

1. Complexit´e des algorithmes         75
2. Calculs ´el´ementaires  de complexit´e         76
3. Quelques algorithmes  sur les tableaux        76

1. Recherche du plus petit ´el´ement         76
2. Recherche dichomotique        77
3. Recherche simultan´ee du maximum et du minimum         78

1. Exponentielle r´ecursive         79

8.4        Conclusions        100

...