Ce livre sur l'algorithmique est destiné à toute personne qui s'intéresse au développement d'applications informatiques et qui souhaite s'initier ou retrouver les bases fondamentales de la programmation. Il ne s'agit pas ici de programmer avec un langage ou un autre, mais bien de raisonner sur un problème pour concevoir une solution abstraite. Ce travail de réflexion et de conception prépare le stade ultime de l'implémentation et du cycle de vie du programme concret.

Le lecteur ne trouvera pas dans ce livre un recueil d'algorithmes qu'il devrait ensuite adapter pour résoudre des problèmes, mais au contraire une introduction originale et efficace à l'algorithmique pour apprendre à analyser un problème.

Le livre est divisé en deux parties. Dans la première partie sont détaillées les notions d'algorithmique de base et la méthode de construction raisonnée d'un algorithme impératif : l'auteur y précise notamment la distinction entre la spécification et la réalisation d'un algorithme et montre que l'algorithmique proprement dite s'arrête là où commence la programmation. Dans la deuxième partie, l'auteur propose cette fois des solutions à des problèmes plus élaborés dans divers domaines du calcul automatique, comme la simulation de phénomènes aléatoires ou le cryptage des données.

Toutes les activités proposées restent élémentaires avec le souci constant de privilégier le raisonnement qui conduit à l'élaboration des algorithmes.

Dans cette nouvelle édition du livre, l'auteur ajoute encore plus d'exercices avec leur solution détaillée et commentée, en téléchargement sur le site www.editions-eni.fr.



Quizinclus dans
la version en ligne !

• Testez vos connaissances à l'issue de chaque chapitre
• Validez vos acquis

Téléchargements

• Des fichiers complémentaires (4964 Ko))

Qu'est-ce que l'algorithmique ?

1. Qu'est-ce que l'algorithmique ?
2. Structure du livre
3. Public visé
4. Conventions adoptées
5. Préface à la troisième édition

Programmes directs

1. Introduction
2. Premiers exemples
3. Définition informelle d'un algorithme
4. Spécifications
5. Premiers algorithmes
6. Exercices résolus
7. Exercices
8. Notes bibliographiques
9. Résumé
10. Bibliographie

L'alternative

1. Introduction
2. Définition de l'alternative
3. Exercices résolus
4. Exercices
5. Résumé

Structures élémentaires

1. Introduction
2. Les chaînes de caractères
   1. 1. Les caractères
   2. 2. Les chaînes de caractères
   3. 3. Exercices d’application sur les chaînes decaractères
3. Le tableau
   1. 1. Les tableaux simples
   2. 2. Tableaux composés
   3. 3. Deux fonctions utiles sur les tableaux
      1. a. La fonction appartient
      2. b. La fonction sous_tableau
   4. 4. Exercices d’application sur les tableaux
4. Définir un nouveau type de données
   1. 1. Définir un type de données
   2. 2. Discussion sur les invariants
   3. 3. Exercices d’application sur les types de données
5. Notes bibliographiques
6. Résumé
7. Bibliographie

Itération

1. Introduction
2. Premiers exemples de construction d'itérations
   1. 1. La table de multiplication
      1. a. Le problème
      2. b. Construction de l’itération
      3. c. Une autre version
   2. 2. Itérer dans un tableau
      1. a. Rang de la composante minimum d’un tableau
      2. b. Rechercher dans un tableau trié
      3. c. Recherche par dichotomie
      4. d. Extensions
3. Explorer un tableau
   1. 1. Rechercher une identité : le problème
   2. 2. L’algorithme à écrire : chercher_identité
   3. 3. Utilisation : effacer tous les clients d’identité donnée
   4. 4. Définition de chercher_identité
   5. 5. Vieillir les clients
   6. 6. Exercices
4. Algorithme ou programme ?
   1. 1. Un exemple édifiant
      1. a. Quelques maladresses : les notations
      2. b. Quand les fautes font oublier les maladresses
   2. 2. Une solution au problème de la moyenne
   3. 3. Compléter l’exercice : les spécificationsqui manquent
   4. 4. Compléter l’exercice : remplir le tableau
5. Exercices d'application
6. Notes bibliographiques
7. Résumé
8. Bibliographie

Récursivité

1. Introduction
2. Introduction à la récursivité : les chaînes de caractères
   1. 1. Présentation de la récursivité
   2. 2. Quelques exemples de spécifications récursives
   3. 3. Exercices résolus
   4. 4. Exercices
3. Les nombres et la récursivité
   1. 1. Arithmétique
   2. 2. Factorielle et autres exercices usés
   3. 3. Fractions
   4. 4. Fonction réelle
4. Nombres et chaînes de caractères : édition d'un entier
5. Problèmes
   1. 1. Recherche par dichotomie dans un tableau trié
   2. 2. Palindromes
   3. 3. Le drapeau de Dijkstra
6. Résumé

Récursivité ou itération ?

1. Introduction
2. Retour sur la récursivité
   1. 1. Premier exemple
   2. 2. Deuxième exemple
   3. 3. Troisième exemple
3. Récursivité ou itération ?
4. Exercices
5. Résumé

Trier

1. Introduction
2. Spécifier un algorithme de tri
   1. 1. Présentation du problème du tri
   2. 2. Étude de la postcondition du tri
3. Quelques algorithmes simples
   1. 1. Tri par permutations : introduction
   2. 2. Tri par permutations
   3. 3. Tri « à bulle » (bubblesort)
   4. 4. D’autres tris par permutations
4. Fusionner deux tableaux triés
   1. 1. Définition d’un vecteur
      1. a. Définition des prédicats
      2. b. Primitives de placement dans le vecteur
      3. c. Accès aux composantes du vecteur
      4. d. Exemples
   2. 2. Fusion de deux vecteurs triés
      1. a. Spécification de l’algorithme de fusion
      2. b. Analyse de la fusion
5. Exercices
   1. 1. Tri par insertion dichotomique
   2. 2. Un tri topologique
   3. 3. Compléter les spécifications
6. Notes bibliographiques
7. Résumé
8. Bibliographie

Édition d'un nombre

1. Introduction
2. Édition d'un entier dans une base quelconque
   1. 1. Nombre de chiffres d’un entier
   2. 2. Résolution du problème d’édition
   3. 3. Résolution du problème réciproque
3. Conversion des adresses Internet
   1. 1. Conversion d’un entier en adresse « InternetProtocol »
      1. a. Introduction
      2. b. Conversion d’une adresse IPv4 en un entier
      3. c. Conversion d’une adresse entièreen une adresse IPv4
   2. 2. Exercice
4. Conversion d’un nombre entier en chiffre romain
5. Vérification des identifiants d'entreprises
6. Vérification des identifiants de livres
7. Résumé
8. Bibliographie

Introduction aux fichiers

1. Introduction
2. Notions élémentaires
   1. 1. Fichiers et articles
   2. 2. Organisation et accès aux fichiers
   3. 3. Association d’un fichier physique à un programme
3. Organisation séquentielle
   1. 1. Introduction
   2. 2. Traitement d’un fichier séquentiel en lecture
   3. 3. Parcours d’un fichier séquentiel
   4. 4. Traitement en écriture d’un fichierséquentiel
   5. 5. Mise à jour d’un fichier à organisationséquentielle
4. L'organisation directe et l'accès sélectif
   1. 1. Correspondance à l’aide d’une table d’accès
   2. 2. Correspondance à l’aide d’une fonction derépartition
5. Problèmes
   1. 1. Statistiques d’import/export
   2. 2. Exploiter un questionnaire d’attitude
   3. 3. Exploiter les réponses à une enquêted’utilité publique
   4. 4. Rechercher les anagrammes dans un dictionnaire
6. Notes bibliographiques
7. Résumé
8. Bibliographie

Simuler

1. Introduction
2. Générer des nombres pseudo-aléatoires
   1. 1. Quelques générateurs
      1. a. Le 147-générateur
      2. b. Générateurs de Hamming
   2. 2. Tester une suite de nombres pseudo-aléatoires
      1. a. Test de l’histogramme
3. Jeux de hasard
   1. 1. Simuler une roulette
   2. 2. Simuler un dé
4. Simulation de processus dynamiques
   1. 1. Propagation d’une rumeur
   2. 2. Course poursuite
5. Simulation statistique de phénomènes déterministes
   1. 1. Calculer p
   2. 2. Évaluer une intégrale définie
6. Simulation de phénomènes aléatoires
   1. 1. À la chasse aux mouches
   2. 2. Propagation d’une rumeur
   3. 3. Fiabilité des systèmes
   4. 4. Dispersion des valeurs des composants d’un circuit électronique
7. Notes bibliographiques
8. Résumé
9. Bibliographie

Crypter

1. Introduction
2. Intégrité
   1. 1. Présentation
   2. 2. Comparer deux empreintes
   3. 3. Condenser le contenu d’un fichier
3. Confidentialité
   1. 1. Principes mathématiques de la confidentialité
   2. 2. Cryptographie à clé secrète
   3. 3. Cryptographie à clé symétrique
   4. 4. Codage élémentaire : XOR
   5. 5. Codage de Vernam
   6. 6. Codage élémentaire à substitutionmono-alphabétique simple
   7. 7. La méthode de Vigenère
4. Notes bibliographiques
5. Conclusion
6. Bibliographie