Tous les langages de programmation ont leurs spécificités mais lorsqu'un développeur crée un nouveau programme, la première étape est toujours la même : réfléchir à l'enchaînement des différentes actions à réaliser par la machine. L'objectif de ce livre est de vous apprendre à comprendre et concevoir les algorithmes permettant le fonctionnement d'un programme.

Pour cela, après une introduction générale sur l'algorithmique, vous apprenez les bases de la programmation en utilisant du pseudo-code : variables, conditionnelles, boucles, tableaux, procédures et fonctions.

Ensuite, ce livre présente les concepts de la programmation orientée objet, utilisée par la plupart des langages actuels, en utilisant l'algorithmique mais également comment programmer en orienté objet avec Java. Ainsi, vous apprenez à créer des classes et des instances de celles-ci, à créer des associations entre elles, à utiliser la notion d'héritage, de classes abstraites et d'interfaces. Vous serez capable de traiter des exceptions et de traquer les bugs de vos applications. Vous apprendrez à utiliser la généricité afin de coder des méthodes, des interfaces et des classes génériques.

Un chapitre du livre est consacré à l'organisation de la mémoire afin de mieux comprendre le fonctionnement de la programmation.   

Enfin, le dernier chapitre du livre présente la notion de complexité d'un algorithme en illustrant cela au travers de différents algorithmes de tris de tableaux. 

Afin de vous aider à mettre en pratique et à développer votre maîtrise de l'algorithmique et de Java, des exercices sont proposés avec leurs corrections en pseudo-code ainsi que leurs implémentations en Java.

La plupart des algorithmes (exemples et exercices) de ce livre sont implémentés en Java et les sources, directement utilisables, sont disponibles en téléchargement sur le site www.editions-eni.fr.

Téléchargements

• Des fichiers complémentaires (179 Ko)

Avant-propos

1. Introduction

Introduction à l’algorithmique

1. Introduction
2. Les algorithmes hors du domaine de l’informatique
3. Les objectifs de l’algorithmique
   1. 1. La conception
   2. 2. La complexité
   3. 3. La calculabilité
   4. 4. La correction
4. Les représentations possibles pour un algorithme informatique
   1. 1. Les logigrammes
   2. 2. Le pseudo-code

Le pseudo-code

1. La structure de l’algorithme
2. Les commentaires
3. La déclaration de variables
   1. 1. Qu’est-ce qu’une variable ?
   2. 2. Les types
   3. 3. La déclaration d’une variable
4. L'affectation d'une valeur
5. La déclaration d'une constante
6. Les opérations
   1. 1. Les opérations arithmétiques
      1. a. Les quatre opérations arithmétiquesusuelles
      2. b. La division entière et son reste
      3. c. Les opérateurs d’affectation combinés à unopérateur arithmétique
      4. d. L’incrémentation et la décrémentation
      5. e. La priorité d’exécution des calculs
   2. 2. Les opérateurs de comparaison
      1. a. L’égalité
      2. b. La différence
      3. c. La supériorité et l’infériorité
   3. 3. Les opérateurs booléens
      1. a. L’opérateur et
      2. b. L’opérateur ou
      3. c. L’opérateur non
7. La console
   1. 1. L’écriture de messages à l’utilisateur
   2. 2. L’affichage formaté en Java
   3. 3. L’affichage standard et l’affichagedes erreurs en Java
   4. 4. La saisie de valeur par l’utilisateur
8. La génération de nombres aléatoires
9. Les outils pour écrire du pseudo-code et du Java
   1. 1. L’utilisation de Notepad++ pour écriredu pseudo-code
   2. 2. Les environnements de développement intégré
10. Exercices
    1. 1. Valeurs des variables
    2. 2. Quels affichages ?
    3. 3. Il fait quoi ?
    4. 4. Vitesse moyenne
11. Solutions des exercices
    1. 1. Valeurs des variables
    2. 2. Quels affichages ?
    3. 3. Il fait quoi ?
    4. 4. Vitesse moyenne

Les conditionnelles

1. Présentation
2. La structure de contrôle Si (forme simple)
3. La structure de contrôle Si (forme double)
4. L'imbrication des structures de contrôle
5. La structure de contrôle Selon
6. L’opérateur ternaire ? :
7. Exercices
   1. 1. La météo
   2. 2. La météo version 2
   3. 3. Le nom du mois
   4. 4. Le temps de cuisson
   5. 5. Le bulletin de paie
8. Solutions des exercices
   1. 1. La météo
   2. 2. La météo version 2
   3. 3. Le nom du mois
   4. 4. Le temps de cuisson
   5. 5. Le bulletin de paie

Les boucles

1. Présentation
2. La structure de contrôle Pour
3. La structure de contrôle TantQue
4. La structure de contrôle Répéter
5. Le choix de la boucle la plus adaptée
6. Les boucles imbriquées
7. Exercices
   1. 1. La moyenne de notes (version 1)
   2. 2. La moyenne de notes (version 2)
   3. 3. La moyenne de notes (version 3)
   4. 4. Devinez à quel nombre je pense
   5. 5. À moi de trouver
   6. 6. Que fait cet algorithme ?
   7. 7. Affichage de répliques de films (version1)
   8. 8. Affichage de répliques de films (version2)
   9. 9. Saisie d’un multiple de trois
   10. 10. ASCII Art !
   11. 11. ASCII Art 2
8. Solutions des exercices
   1. 1. La moyenne de notes (version 1)
   2. 2. La moyenne de notes (version 2)
   3. 3. La moyenne de notes (version 3)
   4. 4. Devinez à quel nombre je pense
   5. 5. À moi de trouver
   6. 6. Que fait cet algorithme ?
   7. 7. Affichage de répliques de films (version1)
   8. 8. Affichage de répliques de films (version2)
   9. 9. Saisie d’un multiple de trois
   10. 10. ASCII Art !
   11. 11. ASCII Art 2

Les tableaux

1. Présentation
2. La déclaration d’un tableau
3. L’utilisation d’un tableau
4. Le parcours d’un tableau
5. Les tableaux : un type référence
6. Les tableaux multidimensionnels
7. Exercices
   1. 1. Décollage immédiat
   2. 2. Nombres d’occurrences
   3. 3. Moyenne de notes (version 4)
   4. 4. Machine à voter
   5. 5. Palindrome
   6. 6. Que fait-il donc ?
   7. 7. Matrix
   8. 8. Micro bataille navale
   9. 9. Morpion
8. Solutions des exercices
   1. 1. Décollage immédiat
   2. 2. Nombres d’occurrences
   3. 3. Moyenne de notes (version 4)
   4. 4. Machine à voter
   5. 5. Palindrome
   6. 6. Que fait-il donc ?
   7. 7. Matrix
   8. 8. Micro bataille navale
   9. 9. Morpion

Les procédures et fonctions

1. Présentation
2. La déclaration d'un sous-algorithme
   1. 1. Déclaration d’une procédure
   2. 2. Déclaration d’une fonction
3. L'appel à un sous-algorithme
   1. 1. L’appel à une procédure
   2. 2. L’appel à une fonction
4. La transmission d'informations entre un sous-algorithme et l'algorithme appelant
   1. 1. Les constantes globales
   2. 2. Le passage de paramètres
      1. a. Le passage en paramètres des types valeur
      2. b. Le passage en paramètre des types référence
   3. 3. Le retour d’une fonction
5. La récursivité
6. Exercices
   1. 1. C’est le plus grand
   2. 2. Micro bataille navale (version 2)
   3. 3. Un tableau et des fonctions
   4. 4. Le jeu du saute-mouton
   5. 5. ASCII Art Studio
7. Solutions des exercices
   1. 1. C’est le plus grand
   2. 2. Micro bataille navale (version 2)
   3. 3. Un tableau et des fonctions
   4. 4. Le jeu du saute-mouton
   5. 5. ASCII Art Studio

La programmation orientée objet

1. Présentation
   1. 1. Qu’est-ce que la programmation orientée objet?
   2. 2. L’intérêt de la programmation orientéeobjet
2. Les notions de classe et d'instance
3. La déclaration d'une classe
4. Les attributs d’instance
5. Les constantes
6. Les méthodes d'instance
   1. 1. La déclaration d’une méthode d’instance
   2. 2. Les méthodes Getters et Setters
   3. 3. La surcharge de méthodes
7. La création d’une instance
   1. 1. La déclaration et l’instanciation d’une variablede type classe
   2. 2. Les tableaux d’instances
8. Les constructeurs
   1. 1. Le constructeur par défaut
   2. 2. Les constructeurs
   3. 3. La surcharge de constructeurs
9. Les attributs de classe
10. Les méthodes de classe
    1. 1. La déclaration d’une méthode declasse
    2. 2. L’appel à une méthode declasse
    3. 3. Récapitulatif des méthodes de classepar rapport aux méthodes d’instance
11. Les instances : un type référence
12. Exercices
    1. 1. Les dés
    2. 2. Les clients
    3. 3. Micro bataille navale (version 3)
    4. 4. Micro bataille navale (version 4)
13. Solutions des exercices
    1. 1. Les dés
    2. 2. Les clients
    3. 3. Micro bataille navale (version 3)
    4. 4. Micro bataille navale (version 4)

Les relations entre les classes

1. Présentation
2. L'utilisation d'une classe par une autre
3. Les associations
4. L’héritage
   1. 1. La notion d’héritage
   2. 2. La déclaration de l’héritage
   3. 3. Les constructeurs et l’héritage
      1. a. Le constructeur par défaut
      2. b. Définir un constructeur
   4. 4. La substitution de méthodes
   5. 5. Le transtypage
      1. a. Le transtypage ascendant
      2. b. Le transtypage descendant
      3. c. Le transtypage et les méthodes substituées
5. Les classes internes en Java
   1. 1. La définition
   2. 2. L’accès aux attributs
6. La création d’instances par méthode de classe en Java
   1. 1. L’encapsulation des constructeurs
   2. 2. Un nommage différent pour les créateursd’instance
   3. 3. Le renvoi d’un sous-type
7. Exercices
   1. 1. La bataille de dés
   2. 2. Les clients (version 2)
8. Solutions des exercices
   1. 1. La bataille de dés
   2. 2. Les clients (version 2)

Les éléments abstraits

1. Les classes abstraites
2. Les méthodes abstraites
   1. 1. La déclaration de méthodes abstraites
   2. 2. L’implémentation d’une méthode abstraite
   3. 3. L’appel à des méthodes abstraites
3. Les interfaces
   1. 1. La déclaration d’une interface
   2. 2. L’implémentation d’une interface
   3. 3. Le transtypage et les interfaces
   4. 4. Les méthodes par défaut en Java
4. Exercices
   1. 1. La location de cycles
      1. a. Les classes et leurs attributs
      2. b. Les méthodes
      3. c. Le code
   2. 2. Vitesse moyenne version multilingue
5. Solutions des exercices
   1. 1. La location de cycles
      1. a. Les classes et leurs attributs
      2. b. Les méthodes
      3. c. Le code
   2. 2. Vitesse moyenne version multilingue

Les erreurs et les exceptions

1. Présentation
2. Les erreurs détectées à la compilation
3. Les erreurs détectées à l'exécution
   1. 1. Les erreurs irrécupérables
      1. a. La saturation de la pile des appels de méthodes
      2. b. La saturation de la mémoire
      3. c. Solutions
   2. 2. Les exceptions en algorithmique
      1. a. Le traitement d’une exception
      2. b. La levée d’une exception
   3. 3. Les exceptions en Java
      1. a. La levée d’une exception
      2. b. Les catégories d’exceptions
      3. c. La propagation d’une exception
      4. d. Le traitement d’une exception
      5. e. Les traitements à effectuer dans tous lescas
   4. 4. Les exceptions personnalisées en Java
4. Exercices
   1. 1. Le calcul de la racine carrée
   2. 2. La calculatrice en Java
      1. a. Création d’une classe DepassementCapaciteException
      2. b. Création de la classe utilitaire Operation
      3. c. Création de la calculatrice
5. Solutions des exercices
   1. 1. Le calcul de la racine carrée
   2. 2. La calculatrice en Java
      1. a. Création d’une classe DepassementCapaciteException
      2. b. Création de la classe utilitaire Operation
      3. c. Création de la calculatrice

La généricité

1. Présentation
2. Les procédures et les fonctions génériques
   1. 1. La déclaration
   2. 2. L’appel
   3. 3. L’utilisation du type génériquedans la procédure ou la fonction
   4. 4. Les contraintes sur un type générique
      1. a. Type avec des valeurs ordonnées
      2. b. Type implémentant une interface
      3. c. Type héritant d’une classe
   5. 5. Plusieurs types génériques
3. Les classes génériques
   1. 1. La déclaration
   2. 2. L’instanciation
4. Les interfaces génériques
   1. 1. La déclaration
   2. 2. L’implémentation
      1. a. L’implémentation par une classe non générique
      2. b. L’implémentation par une classe générique
5. La généricité en Java
   1. 1. Les méthodes génériques
      1. a. La déclaration
      2. b. L’appel
      3. c. Les méthodes génériquesde Java
   2. 2. Les contraintes sur un type générique
      1. a. Type héritant d’une classe ou implémentantune interface
      2. b. Type de valeurs ordonnées
   3. 3. Les classes génériques
      1. a. La déclaration
      2. b. L’instanciation
      3. c. Les classes génériques de Java
   4. 4. Les interfaces génériques
      1. a. La déclaration
      2. b. L’implémentation
      3. c. Les interfaces génériques de Java
   5. 5. Les types valeur et la généricité
6. Exercices
   1. 1. Tirage au sort
   2. 2. À l’envers
   3. 3. Se mélanger les pinceaux
   4. 4. Le plus grand
   5. 5. Procédures et fonctions génériquesen Java
   6. 6. Apprentissage liste de vocabulaire
   7. 7. Le podium
7. Correction des exercices
   1. 1. Tirage au sort
   2. 2. À l’envers
   3. 3. Se mélanger les pinceaux
   4. 4. Le plus grand
   5. 5. Procédures et fonctions génériquesen Java
      1. a. Tirage au sort
      2. b. À l’envers
      3. c. Se mélanger les pinceaux
      4. d. Le plus grand
   6. 6. Apprentissage liste de vocabulaire
   7. 7. Le podium

La mémoire

1. Présentation
2. Les bases
   1. 1. Les nombres entiers
      1. a. Les bases utilisées en informatique
      2. b. Notation
      3. c. La conversion d’une base vers la base dix
      4. d. La conversion de la base dix vers une autre base
   2. 2. Les nombres réels
      1. a. La conversion d’une base vers la base dix
      2. b. La conversion de la base dix vers une autre base
3. Les nombres entiers
   1. 1. Les octets
      1. a. Les bits et les octets
      2. b. Les multiples
   2. 2. Les entiers naturels
   3. 3. Les entiers relatifs
4. Les nombres réels
   1. 1. La forme normalisée
   2. 2. La norme IEEE-754
      1. a. Le codage du signe
      2. b. Le codage de l’exposant
      3. c. Le codage de la mantisse
      4. d. L’assemblage
      5. e. Les valeurs particulières
5. Les caractères
   1. 1. Le code ASCII
   2. 2. Les pages nationales ou ASCII étendu
   3. 3. L’Unicode
      1. a. L’UTF-32
      2. b. L’UTF-16
      3. c. L’UTF-8
   4. 4. Les opérations sur les caractères
      1. a. L’incrémentation et la décrémentation
      2. b. Le changement de type
      3. c. L’addition et la soustraction
      4. d. La comparaison
6. Les différentes zones mémoire
   1. 1. La pile
   2. 2. Le tas
   3. 3. Les instances et les tableaux
      1. a. Les instances
      2. b. Les instances et l’héritage
      3. c. Les tableaux
      4. d. Les opérations sur les instances et les tableaux
   4. 4. Le passage des paramètres
      1. a. Le passage en paramètre de types valeur
      2. b. Le passage en paramètre de types référence
   5. 5. Le retour d’une fonction
      1. a. Le retour d’un type valeur
      2. b. Le retour d’un type référence
   6. 6. Le ramasse-miettes
7. Exercices
   1. 1. Conversion d’une base à une autre
      1. a. Convertir les valeurs suivantes en base 10
      2. b. Convertir les valeurs suivantes en base 2 et en base16
      3. c. Convertir les valeurs suivantes en base 16
      4. d. Convertir les valeurs suivantes en base 2
      5. e. Convertir les valeurs suivantes en base 10
      6. f. Convertir les valeurs suivantes en base 2
   2. 2. Algorithme de conversion
   3. 3. Codage de valeurs en byte, short et int
      1. a. Comment sont codées les valeurs suivantesen byte ?
      2. b. Comment sont codées les valeurs suivantesen short ?
      3. c. Comment sont codées les valeurs suivantesen int ?
   4. 4. Codage de valeurs en float
      1. a. Quelles valeurs sont codées par les octetssuivants ?
      2. b. Comment sont codées les valeurs suivantesen float ?
   5. 5. Unicode
8. Correction des exercices
   1. 1. Conversion d’une base à une autre
      1. a. Convertir les valeurs suivantes en base 10
      2. b. Convertir les valeurs suivantes en base 2 et en base16
      3. c. Convertir les valeurs suivantes en base 16
      4. d. Convertir les valeurs suivantes en base 2
      5. e. Convertir les valeurs suivantes en base 10
      6. f. Convertir les valeurs suivantes en base 2
   2. 2. Algorithme de conversion
   3. 3. Codage de valeurs en byte, short et int
      1. a. Comment sont codées les valeurs suivantesen byte ?
      2. b. Comment sont codées les valeurs suivantesen short ?
      3. c. Comment sont codées les valeurs suivantesen int ?
   4. 4. Codage de valeurs en float
      1. a. Quelles valeurs sont codées par octets suivants?
      2. b. Comment sont codées les valeurs suivantesen float ?
   5. 5. Unicode
      1. a. UTF-8
      2. b. UTF-32
      3. c. UTF-16

La complexité des algorithmes

1. Présentation
2. L’ordre de grandeur de la complexité
3. Les catégories de complexité
4. Illustration avec les algorithmes de tri
   1. 1. Le tri par sélection
      1. a. Le principe de fonctionnement
      2. b. L’algorithme
      3. c. Un exemple d’utilisation
      4. d. La complexité
   2. 2. Le tri à bulles
      1. a. Le principe de fonctionnement
      2. b. L’algorithme
      3. c. Un exemple d’utilisation
      4. d. La complexité
   3. 3. Le tri par insertion
      1. a. Le principe de fonctionnement
      2. b. L’algorithme
      3. c. Un exemple d’utilisation
      4. d. La complexité
   4. 4. Le tri de Shell
      1. a. Le principe de fonctionnement
      2. b. L’algorithme
      3. c. Un exemple d’utilisation
      4. d. La complexité
   5. 5. Le tri fusion
      1. a. Le principe de fonctionnement
      2. b. L’algorithme
      3. c. Un exemple d’utilisation
      4. d. La complexité
   6. 6. Le tri rapide
      1. a. Le principe de fonctionnement
      2. b. L’algorithme
      3. c. Un exemple d’utilisation
      4. d. La complexité
   7. 7. Le tri par tas
      1. a. Le principe de fonctionnement
      2. b. L’algorithme
      3. c. Un exemple d’utilisation
      4. d. La complexité
   8. 8. Synthèse
   9. 9. Les limites de la complexité
5. Exercices
   1. 1. L’ordre de grandeur
   2. 2. L’implémentation des algorithmes de tri enJava
6. Solutions des exercices
   1. 1. L’ordre de grandeur
   2. 2. L’implémentation des algorithmes de tri enJava