Remerciez-le!

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

Auteur Daniel KPO LOUA Enseignant vacataire en informatique à l’INP-HB Doctoran

Auteur Daniel KPO LOUA Enseignant vacataire en informatique à l’INP-HB Doctorant à l’EDP / INP-HB au LARIT Département : Maths – Info kpoloua@gmail.com / 00225 77 09 37 26 CM: 06HTD: 04H Cours d’informatique Initiation à L’algorithme Prépa MPSI 2018 - 2019 L’algo en Prépa M. P. S. I Octobre 2018 A Celui qui peut tout Et qui me rend capable de tout, Mon bien-aimé Père ! Table des matières CHAPITRE 2 : introduction à l’algorithmique ................................................. 3 2.1. Concernant ce cours ............................................................................................ 4 2.1.1. Compétences requises de l’étudiant ............................................................. 4 2.1.2. Un petit conseil .............................................................................................. 5 2.2. L’algorithmique .................................................................................................... 5 2.2.1. Histoire .......................................................................................................... 5 2.2.2. L’algorithme ................................................................................................... 5 2.2.3. L’algorithmique .............................................................................................. 7 2.2.4. La spécification de l’algorithme ..................................................................... 8 2.2.5. Les caractéristiques et les propriétés d’un algorithme................................... 8 2.3. Le Langage de Description des Algorithmes ....................................................... 9 2.4. L’analyse du problème ....................................................................................... 10 2.4.1. Définition du problème ................................................................................ 10 2.4.2. L’indentification des informations ................................................................ 10 2.4.3. La spécification des résultats ...................................................................... 11 2.4.4. Analyse des données .................................................................................. 11 2.4.5. Le corps de l’algorithme. ............................................................................. 11 2.4.6. La validation de l’algorithme ........................................................................ 11 2.5. Les déclarations ................................................................................................. 11 2.5.1. Les arbres programmatiques (AP) .............................................................. 11 2.5.2. Les constantes ............................................................................................ 12 2.5.3. Les variables ............................................................................................... 13 2.5.4. Les types ..................................................................................................... 13 2.5.5. Quelques règles du LDA sur les variables .................................................. 14 2.6. Notions de base ................................................................................................. 15 2.6.1. La lecture .................................................................................................... 15 2.6.2. L’écriture ..................................................................................................... 15 2.6.3. L’affectation ................................................................................................. 16 2.6.4. Les commentaires ....................................................................................... 16 2.7. Les opérateurs ................................................................................................... 17 2.8. Mise en œuvre 1 ................................................................................................ 18 CHAPITRE 3 : Les structures de contrôle ..................................................... 21 3.1. Les tests ou les structures conditionnelles......................................................... 22 MPSI A&C / 2018-2019 3.1.1. Les algorigrammes ...................................................................................... 22 3.1.2. Les tests ...................................................................................................... 22 3.1.3. Les structures conditionnelles simples ........................................................ 23 3.1.4. Les structures conditionnelles alternatives .................................................. 24 3.1.5. Les structures conditionnelles imbriquées ................................................... 25 2.1. Mise en œuvre 2 ................................................................................................ 28 3.2. Les boucles ou structures itératives ................................................................... 29 3.2.1. La boucle Pour … Faire .............................................................................. 29 3.3. Mise en œuvre 3 ................................................................................................ 33 CHAPITRE 4 : Les sous-algorithmes ............................................................... 35 1.1. Contexte ............................................................................................................ 36 1.2. Les sous-procédures ......................................................................................... 37 1.2.1. Définition ..................................................................................................... 37 1.3. Les fonctions ...................................................................................................... 38 1.3.1. Les fonctions prédéfinies ............................................................................. 38 1.4. La procédure principale ..................................................................................... 39 1.4.1. La portée des variables ............................................................................... 40 1.4.2. Le mode de passage des variables ............................................................. 44 1.5. Mise en œuvre 4 ................................................................................................ 45 1.6. La récursivité ..................................................................................................... 47 1.6.1. Définition ..................................................................................................... 47 1.6.2. Avantages ................................................................................................... 47 1.6.3. Quelques exemples..................................................................................... 47 CHAPITRE 5 : Les types construits ................................................................. 51 5.1. Les tableaux ...................................................................................................... 52 5.1.1. Définition ..................................................................................................... 52 5.1.2. Déclaration .................................................................................................. 52 5.1.3. Les Tableaux dynamique ............................................................................ 52 5.2. Les opérations sur les tableaux ......................................................................... 53 5.2.1. Remplir un tableau ...................................................................................... 53 5.2.2. Affichage des éléments d’un tableau .......................................................... 54 5.2.3. Maximum et minimum d’un tableau ............................................................. 54 5.2.4. Trier un tableau ........................................................................................... 54 5.3. Mise en œuvre 5 ................................................................................................ 56 5.4. Les chaines de caractères ................................................................................. 56 MPSI A&C / 2018-2019 5.4.1. Bon à savoir : .............................................................................................. 56 5.4.2. Définition ..................................................................................................... 56 5.4.3. Déclaration .................................................................................................. 57 5.4.4. Les opérations sur les chaines .................................................................... 57 5.5. Les enregistrements .......................................................................................... 58 5.5.1. Définition ..................................................................................................... 58 5.5.2. Déclaration d’un type structuré .................................................................... 58 5.5.3. Déclaration d'un enregistrement à partir d'un type structuré ....................... 59 5.5.4. Manipulation d’un enregistrement ............................................................... 60 5.5.5. Un enregistrement comme champ d'une structure ...................................... 61 5.5.6. Les tableaux d'enregistrements (ou tables) ................................................. 62 5.6. Mise en œuvre 6 ................................................................................................ 63 MPSI A&C / 2018-2019 CHAPITRE 2 Introduction à l’algorithmique « Un langage de programmation est une convention pour donner des ordres à un ordinateur. Ce n’est pas censé être obscur, bizarre et plein de pièges subtils. Ça, ce sont les caractéristiques de la magie. » Dave Small MPSI A&C / 2018-2019 2.1. Concernant ce cours A la fin de ce cours vous serez capable de : analyser, spécifier et modéliser de manière rigoureuse une situation ou un problème, indépendamment d’un langage de programmation ; expliquer le fonctionnement d’un algorithme ; déterminer la trace d’un algorithme ; justifier qu’une itération (ou boucle) produit l’effet attendu au moyen d’un invariant ; démontrer qu’une boucle se termine effectivement, modifier un algorithme existant pour obtenir un résultat différent ; décomposer un problème complexe en sous-problèmes relativement simples 2.1.1. Compétences requises de l’étudiant Faudrait-il que l’étudiant soit : Un informaticien, Un matheux, Un Prépa…. pour comprendre ce cours d’algorithme ? Non, je ne pense pas. La maîtrise de l’algorithmique requiert deux qualités, très complémentaires d’ailleurs : 1. Il faut avoir une certaine intuition, car aucune recette ne permet de savoir a priori quelles instructions permettront d’obtenir le résultat voulu. C’est là, si l’on y tient, qu’intervient la forme « d’intelligence » requise pour l’algorithmique. Alors, c’est certain, il y a des gens qui possèdent au départ davantage cette intuition que les autres. Cependant, et j’insiste sur ce point, les réflexes, cela s’acquiert. Et ce qu’on appelle l’intuition n’est finalement que de l’expérience tellement répétée que le raisonnement, au départ laborieux, finit par devenir « spontané ». 2. Il faut être méthodique et rigoureux. En effet, chaque fois qu’on écrit une série d’instructions qu’on croit justes, il faut systématiquement se mettre mentalement à la place de la machine qui va les exécuter, armé d'un papier et d'un crayon, afin de vérifier si le résultat obtenu est bien celui que l’on voulait. Cette opération ne requiert pas la moindre once d’intelligence. Mais elle reste néanmoins indispensable, si l’on ne veut pas écrire à l’aveuglette. Le but de ce cours est d'étudier comment on peut résoudre un problème en utilisant le Langage de Description des Algorithmes suivant l'approche Bertini et Tallineau. Il va donc falloir étudier les principes fondamentaux de la programmation, base valable quel que soit le langage utilisé. MPSI A&C / 2018-2019 2.1.2. Un petit conseil Pour mieux bénéficier de ce cours, il vous est fortement recommandé comme d’ailleurs, de vous exercer dans un rythme maintenu. Ecrire deux algorithmes chaque soir avant de vous endormir. Une période d’un mois serait largement suffisante pour déceler le mythe des algorithmes. Ainsi parviendrez-vous à faire face à tout algorithme quel que soit son degré de complexité. 2.2. L’algorithmique 2.2.1. Histoire C'est un mathématicien Perse du 8ème siècle, Al-Khawarizmi, qui a donné son nom à la notion d'algorithme. Son besoin était de traduire un livre de mathématiques venu d'Inde pour que les résultats et les méthodes exposés dans ce livre se répandent dans le monde Arabe puis en Europe. Les résultats devaient donc être compréhensibles par tout autre mathématicien et les méthodes applicables, sans ambiguïté. Si l'origine du mot algorithme est très ancienne, la notion même d'algorithme l'est plus encore : on la sait présente chez les Babyloniens, 1800 ans avant JC. 2.2.2. L’algorithme Lire attentivement ce texte : Le mot attiéké est une déformation du mot 'adjèkè' de la langue ébrié parlée dans le sud de la Côte d'Ivoire. À l'origine (et parfois encore aujourd'hui), les femmes ébriés ne confectionnent pas de la même manière l'attiéké qu'elles vendent avec celui qui est consommé par leur propre ménage. Par conséquent, elles qualifiaient d'adjèkè le produit vendu pour le commerce ou pour la vente, afin de marquer la différence avec le produit consommé à la maison (Ahi). Ce sont ensuite les transporteurs bambaras qui ont propagé ce mot le faisant passer à 'atchèkè'. Les colons français (certainement pour motif d'esthétisme à l'écriture) écrivirent 'attiéké'; mais, dans la rue, on prononce souvent 'tch(i)éké', avec amuïssement du a initial. Spécialité culinaire de certains peuples lagunaires (Ebrié, Adjoukrou, Alladian, Abidji, Avikam, Attié, Ahizi) du Sud de la Côte d'Ivoire, l'attiéké est traditionnellement produit par les femmes, des équipes constituées dans le village se groupant pour la production. Sa consommation est tellement forte que des usines ont été construites pour le fabriquer. (Source : wikipédia.org) L’une des variétés de l’attiéké est le Garba. Pour sa préparation vous aurez besoin des ingrédients suivants : ✓ 1 boule d’attiéké, ou 2 sachets d’attiéké déshydraté ✓ 1 cube d’assaisonnement ✓ 3 cuillères à soupe d’huile chaude ✓ 1 petit oignon coupé en dés ✓ 1 tomate coupée en petits dés ✓ 1 piment vert finement haché ✓ Du sel et du poivre MPSI A&C / 2018-2019 Pour l’accompagnement soit du poulet ou du poisson thon (humm !) ✓ 4 tranches conséquentes de thon frais ✓ 1 bonne poignée de farine ✓ Du sel et du poivre Passons maintenant à la préparation L’attiéké : Si vous utilisez l’attiéké déshydraté : Suivez toutes les instructions inscrites sur le paquet. Une fois l’attiéké chaud, saupoudré-le d’assaisonnement Maggi Arrosez l’attiéké de l’huile chaude. Salez, poivrez, puis mélangez vigoureusement le tout. Disposer l’attiéké selon vos convenances et disposer l’oignon, la tomate en dés et le piment par-dessus le plat. Si vous utilisez l’attiéké en boule : Dans un saladier qui va dans le micro-ondes, émiettez grossièrement l’attiéké que vous humidifiez avec 2 à 3 cl d’eau 2 minutes dans le micro-onde suffiront largement. Autrement émiettez grossièrement l’attiéké dans un panier à vapeur. L’attiéké se prépare alors comme uploads/Ingenierie_Lourd/ algo-en-pre-pa-1.pdf