Remerciez-le!

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

École Nationale d'Ingénieurs de Tunis Université Tunis El Manar COURS ALGORITHM

École Nationale d'Ingénieurs de Tunis Université Tunis El Manar COURS ALGORITHME.STRUCTURE DE DONNÉES ET PROGRAMMATION NOTION DE BASE EN ALGORITHMIQUE Maroua Ben Slimane benslimanemaroua@gmail.com November 12, 2018 1 Concepts Importants en Informatique ▶Un algorithme est une suite ﬁnie et non-ambiguë d’opérations ou d’instructions permettant de résoudre un problème. ▶Provient du nom du mathématicien persan Al-Khawarizmi (±820), le père de l’algèbre ▶Un algorithme est une séquence d’opérations qui transforme des entrées en sortie. ▶Un programme est une série d’instructions pouvant s’exécuter en séquence, ou en parallèle qui réalise un algorithme Déﬁnition Un algorithme est une séquence ﬁnie d’opérations élémentaires, qu’une personne ou une machine peut exécuter, pour résoudre un problème bien déterminé. Maroua Ben Slimane | Notion de Base en Algorithmique 2 Pourquoi un Cours D’ALGO? ▶Pour obtenir de la «machine» qu’elle effectue un travail à notre place ▶Problème: expliquer à la «machine» comment elle doit s’y prendre ▶Besoins : ▶savoir expliciter son raisonnement ▶savoir formaliser son raisonnement ▶concevoir (et écrire) des algorithmes: ▶séquence d’instructions qui décrit comment résoudre un problème particulier Maroua Ben Slimane | Notion de Base en Algorithmique 3 Algorithme ▶Savoir expliquer comment faire un travail sans la moindre ambiguïté ▶langage simple : des instructions ▶suite ﬁnie d’actions à entreprendre en respectant une chronologie imposée ▶L ’écriture algorithmique : un travail de programmation à visée universelle ▶un algorithme ne dépend pas du langage dans lequel il est implanté, ▶ni de la machine qui exécutera le programme correspondant. Maroua Ben Slimane | Notion de Base en Algorithmique 4 Exemple d’Algorithmes ▶Une recette de cuisine (ingrédients →plat préparé) ▶La recherche dans un dictionnaire (mot →déﬁnition) ▶La division entière (deux entiers →leur quotient) ▶Le tri d’une séquence (séquence→séquence ordonnée) Maroua Ben Slimane | Notion de Base en Algorithmique 5 Les Problème Fondamentaux En Algorithmique Complexité ▶En combien de temps un algorithme va -t-il atteindre le résultat escompté? ▶De quel espace a-t-il besoin? Calculabilité ▶Existe-t-il des tâches pour lesquelles il n’existe aucun algorithme ? ▶Étant donnée une tâche, peut-on dire s’il existe un algorithme qui la résolve ? Correction ▶Peut-on être sûr qu’un algorithme réponde au problème pour lequel il a été conçu ? Maroua Ben Slimane | Notion de Base en Algorithmique 6 Exemple de Langage Algorithmique Algorithme Surface d’une cercle {cet algorithme calcule la surface d’une cercle} Constantes (pi:réels)← −3.14 {Déclaration: réservation d’espace-mémoire} Variables Surface,Rayon: réels; Début {Préparation du traitement} Écrire("donner le rayon du cercle") Lire(Rayon) Surface← −pi*rayon*rayon; {Traitement: calcul Surface} Écrire("la surface de la cercle est",Surface){Présentation du résultat} Fin Maroua Ben Slimane | Notion de Base en Algorithmique 7 Étape D’un Algorithme (1) Préparation du traitement ▶données nécessaires à la résolution du problème (2)Traitement ▶résolution pas à pas, ▶après décomposition en sous-problèmes si nécessaire (3) Édition des Résultats ▶impression à l’écran, ▶dans un ﬁchier, etc. Maroua Ben Slimane | Notion de Base en Algorithmique 8 Langage Algorithmique Algorithme NomAlgorithme { ceci est un commentaire} Constantes ... Variables ... Début ... Actions Fin Algorithme Bonjour Constantes (message:chaîne de caractère)← −"Hello world!!" Variables personne: chaîne de caractères {il dit bonjour mais . . . en anglais !} Début Lire(personne) Écrire(message,personne) Fin ▶Il faut avoir une écriture rigoureuse ▶Il faut avoir une écriture soignée : respecter l’indentation ▶Il est nécessaire de commenter les algorithmes ▶Il existe plusieurs solutions à un problème posé ▶Il faut rechercher l’efﬁcacité de ce que l’on écrit Maroua Ben Slimane | Notion de Base en Algorithmique 9 Déclaration Des Données Constantes <nom de donnée>: type← −valeur ou expression ▶Instruction permettant de réserver de l’espace mémoire pour stocker une constante dont la valeur ne varie pas. ▶Exemples : ▶Constantes MAX : entier← −10 TROISFOISMAX : entier← −MAX x 2 Maroua Ben Slimane | Notion de Base en Algorithmique 10 Déclaration Des Données Variables <nom de donnée>: type ▶Instruction permettant de réserver de l’espace mémoire pour stocker des données ▶Dépendant du type des données : ▶entiers ▶réels ▶booléens ▶caractères, etc. ▶Exemples : ▶Variables Val, Nbr:entiers Moyenne: réels adresse, ville : chaînes de caractères Maroua Ben Slimane | Notion de Base en Algorithmique 11 Lecture, Écriture De Données Lire(nom de donnée,. . .) ▶Fonction : Instruction permet de placer en mémoire les informations fournies par l’utilisateur. Écrire(nom de donnée,. . .) ▶Fonction : Instructions qui permet de visualiser des données placées en mémoire ▶Exemples: Lire(Nbr) Écrire("le nom est" , nom, " et le prénom est ",prénom) Lire(adresse) Maroua Ben Slimane | Notion de Base en Algorithmique 12 Phase d’Analyse ▶Consiste à extraire de l’énoncé du problème des éléments de modélisation ▶Technique : Distinguer en soulignant de différentes couleurs quelles sont: ▶Quel est le but du programme (traitement à réaliser) ▶Données en entrée du problème : ▶Où vont se situer les résultats en sortie Maroua Ben Slimane | Notion de Base en Algorithmique 13 Exemple d’Énoncé d’un Problème ▶On souhaite calculer et afﬁcher , à partir d’un prix hors taxe saisi, la TVA ainsi que le prix TTC ▶Le montant TTC dépend de : ▶Du prix HT ▶Du taux de TVA de 20, 6 Traitement à réaliser Maroua Ben Slimane | Notion de Base en Algorithmique 14 Exemple d’Énoncé d’un Problème ▶On souhaite calculer et afﬁcher , à partir d’un prix hors taxe saisi, la TVA ainsi que le prix TTC ▶Le montant TTC dépend de : ▶Du prix HT ▶Du taux de TVA de 20, 6 Données en entrée Maroua Ben Slimane | Notion de Base en Algorithmique 15 Exemple d’Énoncé d’un Problème ▶On souhaite calculer et afﬁcher , à partir d’un prix hors taxe saisi, la TVA ainsi que le prix TTC ▶Le montant TTC dépend de : ▶Du prix HT ▶Du taux de TVA de 20, 6 Données en sortie Maroua Ben Slimane | Notion de Base en Algorithmique 16 Algorithme TVA Algorithme CalculTVA {Saisit un prix HT et afﬁche le prix TTC correspondant} Constantes (TVA : réel)← −20.6 (Titre : chaîne de caractère)← −"Résultat" Variables prixHT : réel prixTTC, montantTVA : réels {déclarations} Début {préparation du traitement} Écrire("Donnez-moi le prix hors taxe :") Lire(prixHT) prixTTC ← −prixHT ∗(1 + TVA/100){calcul du prix TTC} montantTVA ← −prixTTC −prixHT Écrire(Titre) {présentation du résultat} Écrire(prixHT, «prixH.T. + TVA ",TVA, « devient » ,prixTTC, «prixT.T.C.”) Fin Maroua Ben Slimane | Notion de Base en Algorithmique 17 Instructions Séquentielles Résultat D’un Algo- rithme Constante (SEUIL : réel)← −13.25 Variables valA, valB: réels compteur : entier mot , tom : chaînes valA← −0.56 valB← −valA valA← −valA ∗(10.5 + SEUIL) compteur← −1 compteur← −compteur + 10 mot← −"Bonjour" tom ← −"Au revoir ! " Quelles sont les différentes valeurs des variables ? Maroua Ben Slimane | Notion de Base en Algorithmique 18 Simulation d’un Algorithme Algorithme CaDoitEchanger? {Cet algorithme .........................................} Variables valA, valB: réels {déclarations} Début {préparation du traitement} Écrire("Donnez-moi deux valeurs :") Lire(valA, valB) Écrire ("Vous m’avez donné ", valA, " et ", valB) {traitement mystère} valA← −valB valB← −valA {présentation du résultat} Écrire("Maintenant , mes données sont : ", valA, " et ", valB) Fin Que fait cet algorithme? Pas ce qui est prévu ! Maroua Ben Slimane | Notion de Base en Algorithmique 19 CE QU’IL MANQUE ▶Déclarer une variable supplémentaire Variables valA, valB, valTemp: entiers ▶Utiliser cette variable pour stocker provisoirement une des valeurs Lire(valA, valB) valTemp← −valA (1) valA← −valB (2) valB← −valTemp (3) Maroua Ben Slimane | Notion de Base en Algorithmique 20 Exercice 1: Permutation Enoncé On voudrait effectuer une permutation circulaire dans le sens des aiguilles d’une montre sur les valeurs de trois variables a, b et c du type entier. On s’interdit, de surcroît, l’utilisation de variables supplémentaires pour réaliser cette permutation. Proposez un algorithme qui réalise cette tâche. Maroua Ben Slimane | Notion de Base en Algorithmique 20 Exercice 1: Permutation Enoncé On voudrait effectuer une permutation circulaire dans le sens des aiguilles d’une montre sur les valeurs de trois variables a, b et c du type entier. On s’interdit, de surcroît, l’utilisation de variables supplémentaires pour réaliser cette permutation. Proposez un algorithme qui réalise cette tâche. Maroua Ben Slimane | Notion de Base en Algorithmique 20 Exercice 1: Permutation Enoncé On voudrait effectuer une permutation circulaire dans le sens des aiguilles d’une montre sur les valeurs de trois variables a, b et c du type entier. On s’interdit, de surcroît, l’utilisation de variables supplémentaires pour réaliser cette permutation. Proposez un algorithme qui réalise cette tâche. Maroua Ben Slimane | Notion de Base en Algorithmique 21 Solution et Simulation Algorithm Permutation Variables a, b, c: entiers Début Lire(a,b,c){a ← −1,b ← −5,c ← −8} b ← −a + b + c {b ← −14} c ← −a + c {c ← −9} c ← −b −c {c ← −5} b ← −b −c {b ← −9} a ← −b −a {a ← −8} b ← −b −a {b ← −1} Écrire("la valeur de a =",a,"la valeur de b =",b, "et la valeur de c =",c); {la valeur de a = 8,la valeur de b = 1 et la valeur de c = 5} Fin Maroua Ben Slimane | Notion de Base en Algorithmique 22 Structure Alternative « SI . . . ALORS . . uploads/Industriel/ chap1-1ainfo2-algorithmbaseconcepts.pdf