Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

3 Djamel Eddine Z E G O U R Apprendre et enseigner l’algorithmique Tome 1 : Cou

3 Djamel Eddine Z E G O U R Apprendre et enseigner l’algorithmique Tome 1 : Cours et annexes. Institut National d’Informatique 4 P r é f a c e Introduction Ce livre est le fruit d'une vingtaine d’années d’expérience dans le domaine de l'algorithmique et de la programmation. C'est le cours tel qu'il est assuré à l'Institut National d'Informatique d'Alger (Ex C.E.R.I) pour les étudiants de première année du cycle "ingénieur d'état en informatique". Il constitue un support de cours pour des étudiants n'ayant aucune connaissance en programmation. Il est aussi destiné à des étudiants ayant déjà une première expérience en programmation et qui veulent connaître davantage sur l'art de la programmation. Objectif du cours Le cours couvre quatre grands aspects très liés : algorithmique, donnée, méthodologie et programmation. Dans une première étape, on s’intéresse essentiellement au formalisme algorithmique, ensemble de conventions permettant d'exprimer des solutions. On opère alors sur des objets simples et on développe des algorithmes sur la machine de Turing. Quant à la seconde étape, elle est totalement consacrée à l'étude des structures de données élémentaires à savoir les vecteurs, les listes linéaires et les fichiers . Un langage de programmation pédagogique est utilisé afin de s'initier à la programmation (PASCAL). Une méthode de recherche d'algorithmes, l'analyse descendante, est abordée avec tous les concepts qui s'y rattachent. Contenu La première partie renferme le cours d'algorithmique. Les concepts de base sont donnés en montrant la construction de programmes simples depuis leur expression en langage naturel avec ses inconvénients à leur expression entièrement dans un langage algorithmique. Une multitude d'algorithmes sont développés sur la machine de Turing afin de se familiariser avec le langage algorithmique. Une introduction aux fichiers et particulièrement aux structures de fichiers est donnée avec de nombreux programmes. On y trouvera essentiellement, les programmes de création, de maintenance et de tri de fichiers. Une méthode de conception d'algorithmes qu'est l'analyse descendante est exposée et illustrée en PASCAL en présentant tous les concepts qui s'y rattachent tels que la notion de portée, de communication entre modules, paramètres formels et réels, objet locaux et globaux, etc. La seconde partie fournit un recueil de sujets d'examens. Pour chaque sujet, il est spécifié l'ensemble des cours à connaître. La partie 3 fournit des corrigés types des sujets présentés dans la partie 2. La partie 4 présente un ensemble d'exercices de programmation corrigés. Pour chaque programme, nous avons présenté les données et les résultats parfois détaillés dans le but de montrer leur conformité. La partie 5 présente une série d'annexes très utiles pour un environnement de programmation. L'annexe 1 résume le langage algorithmique utilisé. Les annexes 2 et 3 donnent des 5 compléments d'informations sur quelques notions élémentaires et sur les disques. L'annexe 4 résume les principales fonctions DOS utiles pour toute utilisation de micro-ordinateur. Les annexes 5 et 6 fournissent des moyens, d'une part, pour représenter schématiquement des algorithmes (organigrammes) et, d'autre part, pour les traduire dans des langages de bas niveau (langage d'assemblage par exemple). Dans l'annexe 7, on trouvera une façon de rédiger un dossier de programmation. Enfin, nous avons terminé par l'annexe 8 par un ensemble de conseils pratiques sous forme de proverbes utiles pour tout programmeur. Remerciements Nous exprimons nos remerciements les plus chaleureux à notre collègue W.K Hidouci pour ses conseils et surtout son efficacité dans la lecture approfondie de certaines parties de ce manuscrit. Professeur Djamel Eddine ZEGOUR 6 Organisation du livre Tome1 Partie 1 . Cours d'algorithmique Partie 2 : Annexes 1. Langage algorithmique 2. Notions élémentaires 3. Les Disques 4. Système d'exploitation MS-DOS : aide mémoire 5. Organigrammes 6. Traduction des algorithmes vers les langages de bas niveau 7. Rapport de programmation 8. Proverbes de programmation Tome2 Partie 1 . Enoncés de sujets d'examens Partie 2 . Corrigés de sujets d'examens Partie 3 . Exercices programmés en PASCAL Partie 4 : Annexes 1. Langage algorithmique 2. Rappel PASCAL 3. Rapport de programmation 4. Proverbes de programmation 7 S O M M A I R E I. Cours d'algorithmique Partie 1. Concepts de base de l'algorithmique COURS 1. Une introduction à l'algorithmique 1.1 Introduction 1.2 Mise en oeuvre d'une application 1.3 Exemples d'algorithmes 1.4 Quelques définitions du mot 'algorithme' 1.5 Propriétés COURS 2. Inconvénients du langage naturel 2.1 Exemple 1 2.2 Exemple 2 2.3 Synthèse COURS 3. Structures de contrôle, introduction à la notion de variable 3.1 Structures de contrôle 3.2 Notion d'ardoise 3.3 Exemples COURS 4. Objets, notion d'affectation et structure d'un algorithme 4.1 Variables et constantes 4.2 Expressions sur les objets 4.3 Autres actions du langage algorithmique 4.4 Structure d'un algorithme 4.5 Exemples TRAVAUX DIRIGES.................................................................................. Partie 2. Programmation PASCAL COURS 5. Présentation générale du langage PASCAL 5.1 Vocabulaire 5.2 Objets 5.3 Expressions 5.4 Instructions 5.5 Structure d'un programme 5.6 Exemples COURS 6. Entrées/Sorties PASCAL 6.1 Lecture 6.2 Ecriture 6.3 Les fichiers TEXT TRAVAUX DIRIGES.................................................................................. 8 Partie 3. Expérimentation sur la machine de Turing COURS 7. Machine-caractères 7.1 Présentation 7.2 Exemples COURS 8. Machine-nombres 8.1 Présentation 8.2 Structure de contrôle " POUR" 8.3 Exemples TRAVAUX DIRIGES.................................................................................. Partie 4. Programmation modulaire COURS 9. Actions composées 9.1 Exemple d'introduction : calcul de Cnp 9.2 Actions composées 9.3 Fonctions 9.4 Prédicats 9.5 Utilisation en PASCAL COURS 10. Analyse descendante 10.1 Définition 10.2 Caractéristique 10.3 Technique 10.4 Exemple COURS 11. Communication entre modules 11.1 Nomenclature 11.2 Portée des objets 11.3 Communication entre modules COURS 12. Illustration de l'analyse descendante et la communication entre modules à travers un exemple 12.1 Enoncé 12.2 Les différents modules 12.3 Rédaction de la solution 12.3.1 Communication par variables globales 12.3.2 Communication par paramètres 12.3.3 Communication par paramètres et par variables globales TRAVAUX DIRIGES.................................................................................. Partie 5. Objets composés COURS 13. Les objets composés 13.1 Introduction 13.2 Définition de type 13.3 Déclaration des variables 13.4 Accès 9 13.5 Utilisation en PASCAL Partie 6. Vecteurs COURS 14. Notion de vecteur 14.1 Introduction 14.2 Caractéristiques 14.3 Définition formelle 14.4 Terminologie et Notation 14.5 Accès à un élément du vecteur 14.6 Vecteur ordonné 14.7 Mesures 14.8 Description algorithmique COURS 15. Algorithmes sur les vecteurs 15.1 Algorithmes traitant un seul vecteur 15.2 Algorithmes traitant plusieurs vecteurs 15.3 Algorithmes de mise à jour 15.4 Algorithmes de tri 15.5 Utilisation en PASCAL COURS 16. Vecteurs de vecteurs 16.1 Vecteurs de vecteurs ou matrices 16.2 Tableaux à n dimensions 16.3 Représentation mémoire 16.4 Description algorithmique TRAVAUX DIRIGES.................................................................................. Partie 7. Listes linéaires chaînées COURS 17. Les listes linéaires chaînées 17.1 Notion d'allocation dynamique 17.2 Exemple 17.3 Définition d'une liste linéaire chaînée 17.4 Modèle sur les listes linéaires chaînées COURS 18. Algorithmes sur les listes et programmation en PASCAL 18.1 Algorithmes sur les listes 18.2 Utilisation en PASCAL TRAVAUX DIRIGES.................................................................................. Partie 8. Fichiers COURS 19. Introduction aux fichiers et Opérations fondamentales sur les fichiers 19.1 Raisons de l'utilisation des mémoires secondaires 19.2 Fichier 19.3 Structure de fichier 19.4 Fichiers physiques et fichiers logiques 19.5 Ouverture, création et fermeture 10 19.6 Lecture et écriture 19.7 Détection de la fin de fichier 19.8 L'opération Positionner ( "SEEK" ) 19.9 Utilisation en PASCAL 19.10 Exemple : programmation des opérations de base COURS 20. Concepts fondamentaux des structures de fichiers 20.1 Fichiers continus ( ‘Stream’) 20.2 Structures des champs 20.3 Structures des articles 20.4 L'accès séquentiel 20.5 L'accès direct 20.6 Article d'en-tête 20.7 Accès aux fichiers et organisation de fichier 20.8 Exemple d'utilisation en PASCAL COURS 21. Maintenance de fichiers 21.1 Maintenance de fichiers 21.2 Réorganisation 21.3 Exemple : programmation du module de réorganisation COURS 22. Tri de fichiers 22. 1 Tri de tout le fichier entièrement en mémoire 22. 2 Tri entièrement en mémoire uniquement des clés du fichier 22. 3 Tri par fusion 22.4 Exemple : programmation du tri par fusion II. Annexes Annexe 1. Langage algorithmique Annexe 2. Notions élémentaires Annexe 3. Les disques Annexe 4. Système d'exploitation MS-DOS : aide mémoire Annexe 5. Organigrammes Annexe 6. Traduction vers des langages de bas niveau Annexe 7. Rapport de programmation Annexe 8. Proverbes de programmation 11 Partie 1. Concepts de base de l'algorithmique COURS 1. Une introduction à l'algorithmique Objectifs : situer le mot " algorithme" dans les différentes étapes de la mise en oeuvre d'une application, puis en donner quelques définitions avant d'énoncer les principales propriétés que doit satisfaire un algorithme 1.1 Introduction L'utilisation d'un ordinateur pour la résolution d'une application (travail que l'on soumet à un ordinateur) nécessite tout un travail de préparation. N'ayant aucune capacité d'invention, l'ordinateur ne peut en effet qu’exécuter les ordres qui lui sont fournis par l'intermédiaire d'un programme. Ce dernier doit donc être établi de manière à envisager toutes les éventualités d'un traitement. 1.2 Mise en oeuvre d'une application Plusieurs étapes sont nécessaires pour mettre en oeuvre une application : Etape 1 : Définition du problème Il s'agit de déterminer toutes les informations disponibles et la forme des résultats désirés. Etape 2 : Analyse du problème Elle consiste à trouver le moyen de passer des données aux résultats. Dans certains cas, on peut être amené à faire une étude théorique. Le résultat de l'étape d'analyse est un algorithme. Une première définition d'un algorithme peut être la uploads/Ingenierie_Lourd/ aea-tome1.pdf