Les bases de l'informatique et de la programmation
Cours : Les bases de l'informatique et de la programmation. Rechercher de 53 000+ Dissertation Gratuites et MémoiresPar Tianah Razafinome • 19 Août 2020 • Cours • 58 761 Mots (236 Pages) • 597 Vues
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
- Les premiers pas en Java 13
- Le premier programme 13
- E´criture et execution´ 13
- Analyse de ce programme 14
- Faire des calculs simples 15
- Types primitifs 15
- Affectation 16
- Op´erations 17
- R`egles d’´evaluation 17
- Incr´ementation et d´ecrementation 18
- Fonctions 19
- Suite d’instructions 21
- Expressions bool´eennes 21
- Op´erateurs de comparaisons 21
- Connecteurs 22
- Instructions conditionnelles 22
- If-else 22
- Forme compacte 23
- Aiguillage 23
- It´erations 24
- Boucles pour 24
- It´erations tant que 26
- It´erations r´ep´eter tant que 27
- Terminaison des programmes 28
- Instructions de rupture de contrˆole 28
- Exemples 28
- M´ethode de Newton 28
- Fonctions : th´eorie et pratique 31
- Pourquoi ´ecrire des fonctions 31
- Comment ´ecrire des fonctions 32
- Syntaxe 32
- Le type sp´ecial void 33
- Visibilit´e des variables 33
- Quelques conseils pour ´ecrire un programme 35
- Quelques exemples de programmes complets 36
- E´criture binaire d’un entier 36
3
- Calcul du jour correspondant a` une date 37
- Tableaux 41
- D´eclaration, construction, initialisation 41
- Premiers exemples 42
- Tableaux a` plusieurs dimensions, matrices 43
- Les tableaux comme arguments de fonction 44
- Exemples d’utilisation des tableaux 44
- Algorithmique des tableaux 44
- Un peu d’alg`ebre lin´eaire 46
- Le crible d’Eratosthene 47
- Jouons a` l’escarmouche 47
- Pile 50
- Composants d’une classe 53
- Constantes et variables globales 53
- Les classes pour d´efinir des enregistrements 53
- Constructeurs 54
- Les m´ethodes statiques et les autres 54
- Utiliser plusieurs classes 56
- Public et private 56
- Un exemple de classe pr´ed´efinie : la classe String 57
- Propri´et´es 57
- Arguments de main 58
- Les objets comme arguments de fonction 59
- R´ecursivit´e 61
- Premiers exemples 61
- Un pi`ege subtil : les nombres de Fibonacci 64
- Fonctions mutuellement r´ecursives 65
- Pair et impair sont dans un bateau 66
- D´eveloppement du sinus et du cosinus 66
- Diviser pour r´esoudre 67
- Recherche d’une racine par dichotomie 67
- Les tours de Hanoi 68
- Un peu de th´eorie 69
- La fonction d’Ackerman 69
- Le probl`eme de la terminaison 71
- Probl´ematiques classiques en informatique 73
- Introduction a` la complexit´e des algorithmes 75
- Complexit´e des algorithmes 75
- Calculs ´el´ementaires de complexit´e 76
- Quelques algorithmes sur les tableaux 76
- Recherche du plus petit ´el´ement 76
- Recherche dichomotique 77
- Recherche simultan´ee du maximum et du minimum 78
- Exponentielle r´ecursive 79
8 | Ranger l’information . . . pour la retrouver | 83 | |
8.1 Recherche en table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . | 83 | ||
8.1.1 | Recherche lin´eaire . . . . . . . . . . . . . . . . . . . . . . . . . . | 83 | |
8.1.2 | Recherche dichotomique . . . . . . . . . . . . . . . . . . . . . . . | 84 | |
8.1.3 | Utilisation d’index . . . . . . . . . . . . . . . . . . . . . . . . . . | 84 | |
8.2 | Trier | . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . | 86 |
8.2.1 | Tris ´el´ementaires . . . . . . . . . . . . . . . . . . . . . . . . . . . | 86 | |
8.2.2 | Un tri rapide : le tri par fusion . . . . . . . . . . . . . . . . . . . | 89 | |
8.3 Stockage d’informations reli´ees entre elles . . . . . . . . . . . . . . . . . 8.3.1 Files d’attente . . . . . . . . . . . . . . . . . . . . . . . . . . . . | 92 92 | ||
8.3.2 Information hi´erarchique . . . . . . . . . . . . . . . . . . . . . . . | 93 |
8.4 Conclusions 100
...