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 2 : Suj

3 Djamel Eddine Z E G O U R Apprendre et enseigner l’algorithmique Tome 2 : Sujets d’examen corrigés. Institut National d’Informatique PDF created with pdfFactory Pro trial version www.software-partners.co.uk 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 compléments d'informations sur quelques notions élémentaires et sur les disques. L'annexe 4 PDF created with pdfFactory Pro trial version www.software-partners.co.uk 5 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 PDF created with pdfFactory Pro trial version www.software-partners.co.uk 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 (Page 7) . Enoncés de sujets d'examens Partie 2 (Page 35) . Corrigés de sujets d'examens Partie 3 (Page 111) . Exercices programmés en PASCAL Partie 4 : Annexes (Page 143) 1. Langage algorithmique 2. Rappel PASCAL 3. Proverbes de programmation PDF created with pdfFactory Pro trial version www.software-partners.co.uk 7 S O M M A I R E I. Enoncés de sujets d'examens C1. Concepts de base C2. Concepts de base - Programmation PASCAL - Machine de Turing C3. Concepts de base - Machine de Turing C4. Concepts de base - Machine de Turing C5. Machine de Turing - Programmation PASCAL C6. Machine de Turing - Vecteurs - Programmation PASCAL C7. Concepts de base C8. Machine de Turing - Programmation modulaire - Programmation PASCAL C9. Vecteurs - Fichiers - Programmation PASCAL C10. Programmation modulaire - Vecteurs - Programmation PASCAL C11. Machine de Turing - Vecteurs - Programmation PASCAL C12. Machine de Turing - Vecteurs - Programmation PASCAL C13. Listes linéaires chaînées - Programmation PASCAL C14. Machine de Turing - Programmation PASCAL C15. Vecteurs - Programmation PASCAL C16. Listes linéaires chaînées - Vecteurs - Fichiers C17. Machine de Turing - Programmation PASCAL C18. Vecteurs - Machine de Turing C19. Concepts de base - Machine de Turing C20. Machine de Turing - Vecteurs C21. Vecteurs C22. Concepts de base C23. Machine de Turing - Programmation modulaire - Programmation PASCAL C24. Programmation modulaire - Vecteurs - Programmation PASCAL C25. Vecteurs C26. Machine de Turing - Vecteurs - Programmation PASCAL C27. Machine de Turing - Programmation PASCAL C28. Concepts de base - Vecteurs - Programmation PASCAL C29. Machine de Turing II. Corrigés de sujets d'examens Corrigé 1.......................................................................................................... Corrigé 2.......................................................................................................... Corrigé 3.......................................................................................................... Corrigé 4.......................................................................................................... Corrigé 5.......................................................................................................... Corrigé 6.......................................................................................................... Corrigé 7.......................................................................................................... Corrigé 8.......................................................................................................... Corrigé 9.......................................................................................................... Corrigé 10........................................................................................................ Corrigé 11........................................................................................................ Corrigé 12........................................................................................................ Corrigé 13........................................................................................................ Corrigé 14........................................................................................................ Corrigé 15........................................................................................................ PDF created with pdfFactory Pro trial version www.software-partners.co.uk 8 Corrigé 16........................................................................................................ Corrigé 17........................................................................................................ Corrigé 18........................................................................................................ Corrigé 19........................................................................................................ Corrigé 20........................................................................................................ Corrigé 21........................................................................................................ Corrigé 22........................................................................................................ Corrigé 23........................................................................................................ Corrigé 24........................................................................................................ Corrigé 25........................................................................................................ Corrigé 26........................................................................................................ Corrigé 27........................................................................................................ Corrigé 28........................................................................................................ Corrigé 29........................................................................................................ III. Exercices programmés en PASCAL PROGRAMME 1. Réalisation d'un dessin PROGRAMME 2. Etablissement d'une facture PROGRAMME 3. Course de Ski ( I ) PROGRAMME 4. Les mots de la forme ....XY...... PROGRAMME 5. Les mots de la forme ....X....Y.... PROGRAMME 6. Analyse des constantes "virgule flottante" PROGRAMME 7. Recherche dichotomique dans un vecteur PROGRAMME 8. Course de ski ( II ) PROGRAMME 9. Parties d'un ensemble PROGRAMME 10. Inventaire IV. Annexes Annexe 1. Langage algorithmique Annexe 2. Rappel PASCAL Annexe 3. Proverbes de programmation PDF created with pdfFactory Pro trial version www.software-partners.co.uk 9 Partie 1 _________________________________________________________ Enoncés de sujets d’examens _________________________________________________________ PDF created with pdfFactory Pro trial version www.software-partners.co.uk 10 Exercice 1 : 2N Ecrire deux algorithmes différents permettant de calculer 2 N pour tout N >=0 donné a) d'abord en remarquant que 2N = 2 * 2 * . . * 2 ( N fois) b) puis en remarquant que 2N = 2N-1 + 2N-1 Exercice 2 : Extremum Soit une liste de K nombres ( K donné ). Ecrire l'algorithme qui permet de rechercher le maximum et le minimum. On suppose que chaque nombre est obtenu par un ordre de lecture. Exercice 3 : F ? Que fait l'algorithme suivant ? Justifier votre réponse. ALGORITHME F VAR Res, N, I : ENTIER DEBUT Lire(N) I := N Res := 1 TANTQUE I > 1 : Res := Res * I I := I - 1 FINTANTQUE Ecrire( N, res) FIN Exercice 4 : PGCD On suppose que MOD( N, A) est une fonction qui détermine le reste de la division de l'entier N par A. ex : Mod( 12, 7) = 5 Si Reste est le nom d'un objet de type variable entière l'action " Reste := Mod(N,A)" permet d'affecter à la variable Reste le reste de la division de N par A. Ceci étant, écrire l’algorithme permettant de déterminer le PGCD de deux nombres A et B donnés. Exercice 5 : Calcul Soit l'algorithme suivant : ALGORITHME Calcul VAR E1, E2, E3 : ENTIER R : REEL DEBUT E1 := 5 ; E2 := 8 E3 := E1 * E2 PDF created with pdfFactory Pro trial version www.software-partners.co.uk 11 E3 :=(E1 * E2) / 3 R := (E1 * E2) / 3 E3 := ( E1 + E2) / 2 R := ( E1 + E2 ) / 2 FIN Quelles sont les différentes valeurs que prennent E3 et R? Faire une trace. * * * * * Turing 1. Aspect algorithmique A - Soit une liste de N entiers. Ecrire les algorithmes suivants : a) - Calcul de la somme des nombres positifs et celle des nombres négatifs. b) - Nombre des sous-suites décroissantes. Exemple : si la liste est 7, 8, -1, 3, 5, -17, 15, -28 a) - somme des nombres positifs = 38 somme des nombres négatifs = -46 b) Les sous-suites décroissantes sont : {7}, {8, -1}, {3}, {5, -17}, {15, -28} B- On dit que deux nombres x et y sont amis si et seulement si x2 + y2 est un carré parfait. Ecrire l'algorithme qui recherche tous les nombres uploads/Industriel/ apprendre-et-enseigner-l-x27-algorithmique-zegour-djamel-eddine-tome-2.pdf