Les bases de l'informatique et de la programmation

François Morain

Description

Les premiers pas en JAVA, les instructions, avec une introduction sur la complexité des algorithmes

Informations

• Publié par: Force_IT
• Nombre de lectures: 123
• Licence : En savoir +
  Paternité, pas d'utilisation commerciale, partage des conditions initiales à l'identique
• Langue: Français

Extrait

Les bases de l’informatique et de
la programmation
Ecole polytechnique
Fran cois Morain22Table des matieres
I Introduction a la programmation 11
1 Les premiers pas en Java 13
1.1 Le premier programme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.1.1 Ecriture et execution . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.1.2 Analyse de ce programme . . . . . . . . . . . . . . . . . . . . . . 14
1.2 Faire des calculs simples . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.3 Types primitifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.4 Declaration des variables . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.5 A ectation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.6 Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.6.1 Regles d’evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.6.2 Incrementation et decrementation . . . . . . . . . . . . . . . . . 18
1.7 Methodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2 Suite d’instructions 21
2.1 Expressions booleennes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.1.1 Operateurs de comparaisons . . . . . . . . . . . . . . . . . . . . . 21
2.1.2 Connecteurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2 Instructions conditionnelles . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.1 If-else . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.2 Forme compacte . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.3 Aiguillage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3 Iterations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3.1 Boucles pour (for) . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3.2 Iterations tant que . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.3.3 It repeter tant que . . . . . . . . . . . . . . . . . . . . . . 27
2.4 Terminaison des programmes . . . . . . . . . . . . . . . . . . . . . . . . 28
2.5 Instructions de rupture de contr^ ole . . . . . . . . . . . . . . . . . . . . . 28
2.6 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.6.1 Methode de Newton . . . . . . . . . . . . . . . . . . . . . . . . . 28
3 Methodes : theorie et pratique 31
3.1 Pourquoi ecrire des methodes . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2 Comment des methodes . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2.1 Syntaxe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2.2 Le type special void . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2.3 La surcharge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
34 TABLE DES MATIERES
3.3 Visibilite des variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.4 Quelques conseils pour ecrire un programme . . . . . . . . . . . . . . . . 36
3.5 exemples de programmes complets . . . . . . . . . . . . . . . . 37
3.5.1 Ecriture binaire d’un entier . . . . . . . . . . . . . . . . . . . . . 37
3.5.2 Calcul du jour correspondant a une date . . . . . . . . . . . . . . 38
4 Tableaux 43
4.1 Declaration, construction, initialisation . . . . . . . . . . . . . . . . . . . 43
4.2 Representation en memoire et consequences . . . . . . . . . . . . . . . . 44
4.3 Tableaux a plusieurs dimensions, matrices . . . . . . . . . . . . . . . . . 47
4.4 Les tableaux comme arguments de fonction . . . . . . . . . . . . . . . . 48
4.5 Exemples d’utilisation des tableaux . . . . . . . . . . . . . . . . . . . . . 49
4.5.1 Algorithmique des . . . . . . . . . . . . . . . . . . . . . 49
4.5.2 Un peu d’algebre lineaire . . . . . . . . . . . . . . . . . . . . . . 51
4.5.3 Le crible d’Eratosthene . . . . . . . . . . . . . . . . . . . . . . . 52
4.5.4 Jouons a la bataille rangee . . . . . . . . . . . . . . . . . . . . . 54
4.5.5 Pile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5 Composants d’une classe 59
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.1.1 Declaration et creation . . . . . . . . . . . . . . . . . . . . . . . . 59
5.1.2 Objet et reference . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.1.3 Constructeurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.2 Autres composants d’une classe . . . . . . . . . . . . . . . . . . . . . . . 62
5.2.1 Methodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.2.2 Passage par reference . . . . . . . . . . . . . . . . . . . . . . . . 62
5.2.3 Variables de classe . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.2.4 Utiliser plusieurs classes . . . . . . . . . . . . . . . . . . . . . . . 63
5.3 Autre exemple de classe . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.4 Public et private . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
6 Recursivite 65
6.1 Premiers exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
6.2 Un piege subtil : les nombres de Fibonacci . . . . . . . . . . . . . . . . . 68
6.3 Fonctions mutuellement recursives . . . . . . . . . . . . . . . . . . . . . 70
6.3.1 Pair et impair sont dans un bateau . . . . . . . . . . . . . . . . . 70
6.3.2 Developpement du sinus et du cosinus . . . . . . . . . . . . . . . 71
6.4 Le probleme de la terminaison . . . . . . . . . . . . . . . . . . . . . . . . 72
7 Introduction a la complexite des algorithmes 73
7.1 Complexite des algorithmes . . . . . . . . . . . . . . . . . . . . . . . . . 73
7.2 Calculs elementaires de complexite . . . . . . . . . . . . . . . . . . . . . 74
7.3 Quelques algorithmes sur les tableaux . . . . . . . . . . . . . . . . . . . 74
7.3.1 Recherche du plus petit element . . . . . . . . . . . . . . . . . . 74
7.3.2 Recherche dichotomique . . . . . . . . . . . . . . . . . . . . . . . 75
7.3.3 Recherche simultanee du maximum et du minimum . . . . . . . 76
7.4 Diviser pour resoudre . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
7.4.1 Recherche d’une racine par dichotomie . . . . . . . . . . . . . . . 78
7.4.2 Exponentielle binaire . . . . . . . . . . . . . . . . . . . . . . . . . 78TABLE DES MATIERES 5
7.4.3 Les tours de Hanoi . . . . . . . . . . . . . . . . . . . . . . . . . . 80
8 Introduction aux structures de donnees dynamiques 83
8.1 Operations elementaires sur les listes . . . . . . . . . . . . . . . . . . . . 84
8.1.1 Creation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
8.1.2 A c hage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
8.1.3 Longueur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
8.1.4 Le i-eme element . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
8.1.5 Ajouter des elements en queue de liste . . . . . . . . . . . . . . . 87
8.1.6 Copier une liste . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
8.1.7 Suppression de la premiere occurrence . . . . . . . . . . . . . . . 89
8.2 Interlude : tableau ou liste ? . . . . . . . . . . . . . . . . . . . . . . . . . 90
8.3 Partages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
8.3.1 Insertion dans une liste triee . . . . . . . . . . . . . . . . . . . . 91
8.3.2 Inverser les eches . . . . . . . . . . . . . . . . . . . . . . . . . . 92
8.4 Exemple de gestion de la memoire au plus juste . . . . . . . . . . . . . . 92
9 Introduction a la programmation objet 95
9.1 Methodes de classe et methodes d’objet . . . . . . . . . . . . . . . . . . 95
9.2 Un exemple de classe prede nie : la classe String . . . . . . . . . . . . 96
9.2.1 Proprietes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
9.2.2 Arguments de main . . . . . . . . . . . . . . . . . . . . . . . . . 98
II Problematiques classiques en informatique 101
10 Ranger l’information . .. pour la retrouver 103
10.1 Recherche en table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
10.1.1 Recherche lineaire . . . . . . . . . . . . . . . . . . . . . . . . . . 103
10.1.2 Recherche dichotomique . . . . . . . . . . . . . . . . . . . . . . . 104
10.1.3 Utilisation d’index . . . . . . . . . . . . . . . . . . . . . . . . . . 106
10.2 Trier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
10.2.1 Tris elementaires . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
10.2.2 Un tri rapide : le tri par fusion . . . . . . . . . . . . . . . . . . . 109
10.3 Stockage d’informations reliees entre elles . . . . . . . . . . . . . . . . . 112
10.3.1 Piles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
10.3.2 Files d’attente . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
10.3.3 Information hierarchique . . . . . . . . . . . . . . . . . . . . . . . 116
10.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
11 Recherche exhaustive 125
11.1 Rechercher dans du texte . . . . . . . . . . . . . . . . . . . . . . . . . . 125
11.2 Le probleme du sac- a-dos . . . . . . . . . . . . . . . . . . . . . . . . . . 130
11.2.1 Premieres solutions . . . . . . . . . . . . . . . . . . . . . . . . . . 130
11.2.2 Deuxieme approche . . . . . . . . . . . . . . . . . . . . . . . . . 1