Sommaire: Cours éléments d’algorithmique en Java

I Pour débuter rapidement en Java
1 Fondements
1.1 Représentation des données en machine
1.1.1 La mémoire
1.1.2 Codage en mémoire d’une donnée : présentation informelle
1.1.3 Types simples et chaînes de caractères
1.2 Les variables et l’affectation
1.2.1 Déclaration de variable
1.2.2 Affectation
1.2.3 Déclaration avec initialisation
1.2.4 Signification du nom de la variable
1.2.5 Optimisations d’affectations
1.2.6 Retour sur les types simples : conversions
1.3 Instructions et expressions
1.3.1 L’affectation comme expression
1.3.2 Cas particulier : incrémentations et décrémentations
1.3.3 Expressions à effet de bord
1.4 Blocs et boucles
1.4.1 Blocs
1.4.2 Les instructions de branchement
1.4.3 Instructions while et do-while
1.4.4 Instruction for
2 Java sans objet 2.1 Programme minimum
2.1.1 La méthode main
2.1.2 Les arguments d’un programme
2.2 Les méthodes de classes (ou statiques)
2.2.1 Etude d’un exemple
2.2.2 Commentaires dans un programme
2.2.3 Nombres en argument de programme
2.2.4 Radiographie de la méthode pgcd
2.2.5 Comment ca marche ?
2.2.6 Passage des paramètres par valeur
2.2.7 Cout d’un appel de méthode
2.2.8 L’instruction return
2.3 Modularité
2.4 Conclusion provisoire
3 Les objets
3.1 Classes comme structures de données
3.1.1 Qu’est ce qu’un objet ?
3.1.2 Définir les classes d’objets
3.1.3 Créer des objets
3.2 Classes comme boîtes à outils sécurisées
3.2.1 Méthodes d’instance
3.2.2 Privatisation des champs
3.2.3 La méthode toString
3.3 Variables statiques et constantes
3.3.1 this implicite
4 Les tableaux 4.1 Tableaux à une dimension
4.1.1 Déclarations
4.1.2 Création
4.1.3 Taille et indexation d’un tableau
4.1.4 Coˆut des accès
4.1.5 Tableaux d’objets
4.2 Tableaux à plusieurs dimensions
4.2.1 Déclaration et création
4.2.2 Coˆut des accès
4.3 Effet du codage sur l’occupation mémoire
4.3.1 Puissance égyptienne
4.3.2 Puissance d’une matrice
II Eléments d’algorithmique
5 Principes généraux
5.1 Qu’est-ce qu’un algorithme ?
5.1.1 Définition informelle
5.1.2 Les grandes questions de la calculabilité
5.1.3 Le problème de l’arret
5.1.4 Pour conclure
5.2 Conception et expression d’algorithmes
5.2.1 Spécification du problème
5.2.2 Analyse descendante – Modularité
5.2.3 Correction de l’algorithme
5.3 Algorithmes récursifs
5.3.1 Introduction sur des exemples
5.3.2 Terminaison des algorithmes récursifs
5.3.3 Correction des algorithme récursifs
5.4 Complexité
5.4.1 Cout et complexité en temps d’un algorithme
5.4.2 Asymptotique
6 Structures séquentielles
6.1 Les listes
6.1.1 Description abstraite
6.1.2 Mise en œuvre par des tableaux
6.1.3 Mise en œuvre par des listes chaînées
6.1.4 Cas des listes ordonnées
6.1.5 Tableaux ou listes chaînées ?
8.6.1 L’algorithme de Dijkstra
8.6.2 Correction de l’algorithme
8.6.3 Complexité
8.6.4 Une mise en œuvre de l’algorithme en Java
9 Algorithmique du tri
9.1 Tris élémentaires
9.1.1 Le tri par sélection
9.1.2 Le tri par insertion
9.2 Tri rapide
9.3 Tri fusion
9.4 Tri par tas
9.5 Complexité du problème du tri
9.6 Complexité des algorithmes diviser pour régner
9.7 Exercices

Extrait du cours: Cours éléments d’algorithmique en Java

Chapitre 1 Fondements
Un ordinateur est constitué de divers modules :
– le processeur qui évalue des expressions (effectue des calculs) et qui exécute des instructions
– la mémoire dans laquelle sont enregistrées les informations (les programmes, les données et les résultats de calculs effectués sur ces dernières)
– les périphériques, dont le clavier, l’écran, les imprimantes, le disque dur, les réseaux . . .
Ces divers constituants communiquent entre eux au moyen de canaux appelés bus.
Instructions et expressions Les programmes sont amenés à modifier l’état de la mémoire (en y enregistrant des résultats par exemple) au moyen d’instructions. Dans la suite de ce document, on appellera effet de bord toute action du processeur provoquant un changement de l’état de la mémoire (on dira désormais un changement d’état sans plus de précision). Une instruction a donc, sauf exception, un effet de bord.
Ils font également effectuer par le processeur des calculs codés sous forme d’expressions. Par exemple, 2*3+2 et 5>8 sont des expressions que le processeur peut évaluer pour produire 8 et false respectivement. L’évaluation de ces deux expressions ne modifie pas l’état de mémoire.
Elles sont sans effet de bord.

Eléments d’algorithmique en Java
1.1 Representation des données en machine
1.1.1 La memoire
La mémoire d’un ordinateur est une suite ordonnée de bits. Un bit est un composant élémentaire, pouvant prendre deux états et deux seulement, communément notés 0 et 1, tout comme un interrupteur électrique n’a que deux positions : éteint et allumé. Les bits de la mémoire sont regroupés par huit : un groupe de huit bits est un octet (byte en anglais).
0
1000011000000000000000000000000
64 72 80 88
Figure 1.2 – Une zone mémoire de 4 octets
Enfin, bits et octets sont numérotés. Ce numéro d’ordre est appelé adresse (du bit ou de l’octet).
La figure 1.2 représente une zone de la mémoire constituée des quatre octets d’adresses respectives 64, 72, 80, 88.
L’état de la mémoire est la suite des états (0 ou 1) des bits qui la composent. L’état de la zone mémoire représentée sur la figure 1.2 est donc :
1.1.2 Codage en mémoire d’une donnée : présentation informelle
Toute donnée, aussi complexe soit-elle, est donc représentée in fine par une suite binaire. Inversement, il faut être capable de décoder une suite binaire pour retrouver la donnée qu’elle représente. Examinons tout d’abord les données de type simple.
En ce qui concerne les entiers, une idée naturelle est de les représenter par leur développement en base 2. Pour prendre en compte le signe, on est amené à utiliser un bit supplémentaire, dit bit de signe, qui est 0 pour les entiers positifs et 1 pour les négatifs. Par exemple, sachant que 97 = 1 +25+26, on peut envisager de coder l’entier 97 par 01100001 et l’entier -97 par 11100001.
1.1.3 Types simples et chaınes de caractères
Le type String C’est un type un peu particulier qui désigne les chaınes de caractères et qui n’est donc pas un type simple. Les chaînes de caractères sont notées entre guillemets : « Ceci est une chaîne de caractères ». Elles peuvent etre concaténées au moyen de l’opérateur binaire + et affichées à l’écran au moyen de l’instruction :
1.2 Les variables et l’affectation
Une variable est une zone mémoire dédiée à l’enregistrement d’une donnée. Elle est caractérisée par :
– son adresse : celle du premier octet qu’elle occupe
– son type : il définit sa taille et le codage/décodage
– sa valeur : c’est son état à un instant donné. Cet état peut évidemment varier, d’où le nom de variable.
1.2.1 Déclaration de variable
Toute variable utilisée dans un programme doit etre déclarée au préalable comme suit.
Exemple 1.4 int age;
char initiale;
Dans un programme, la déclaration d’une variable provoque l’allocation en mémoire de l’espace nécessaire pour coder les données du type indiqué. L’adresse de la zone allouée est associée au nom de la variable. A ce stade là, la valeur de la variable existe (bien évidemment, la variable se trouve dans un certain état !) mais est indéterminée : la mémoire allouée a pu être utilisée par un  autre programme puis libérée en l’état. La variable est dite non initialisée. Plusieurs variables de même type peuvent etre déclarées simultanément. Leurs noms sont alors séparés par des virgules.
Exemple 1.5 float perimetre, surface ;
1.2.2 Affectation
Une affectation consiste à enregistrer une valeur dans une variable. Il s’agit donc d’une instruction (effet de bord). La syntaxe des affectations est la suivante.
1.2.3 Déclaration avec initialisation
Toute variable peut etre initialisée au moment de sa déclaration selon la syntaxe suivante :
Ainsi, on peut écrire :
int age = 97;
char initiale = ’a’;
float surface = 0.16,
<type> <nom de la variable> = <expression>;
périmètre = 1.6;
au lieu de
int age;
char initiale;
float surface;
float perimetre;
age = 97;
initiale = ’a’;
surface = 0.16;
perimetre = 1.6;
Attention : ne pas confondre l’affectation age = 97 et l’expression booléenne age == 97.
1.2.4 Signification du nom de la variable
Le nom d’une variable désigne à la fois son adresse et sa valeur. Dans une affectation, l’ambiguité est levée par le contexte. L’exécution de l’instruction :
age = 2*age +1;
a pour effet de rajouter 1 au double de la valeur de age et d’enregistrer le résultat à l’adresse age. Ainsi, à gauche du signe d’affectation, le nom age désigne l’adresse de la variable, tandis qu’à droite il désigne sa valeur.

……….

Si le lien ne fonctionne pas correctement, veuillez nous contacter (mentionner le lien dans votre message)
Cours éléments d’algorithmique en Java (1375 KO)  (Cours PDF)