Remerciez-le!

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

iUT ORSAY Université Paris XI I.U.T. d'Orsay Département Informatique Année sco

iUT ORSAY Université Paris XI I.U.T. d'Orsay Département Informatique Année scolaire 2003-2004 Algorithmique : Volume 1 • Introduction • Instructions de base • Logique propositionnelle Cécile Balkanski, Nelly Bensimon, Gérard Ligozat Algorithmique 1 : Introduction 1 Pourquoi un cours d’ "Algo" ? • Objectif : obtenir de la «machine» qu’elle effectue un travail à notre place • Problème : expliquer à la «machine» comment elle doit s'y prendre Mais... comment le lui dire ? Comment le lui apprendre ? Comment s'assurer qu'elle fait ce travail aussi bien que nous ? Mieux que nous? Algorithmique 1 : Introduction 2 Objectif de cet enseignement • résoudre des problèmes «comme» une machine • 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 Algorithmique 1 : Introduction 3 Thèmes abordés en «Algo» • Apprentissage d’un langage • Notions de base - algorithmes de « base » pour problèmes élémentaires • Structures de données - des plus simples aux plus complexes • Résolution de problèmes complexes - algorithmes astucieux et efficaces Algorithmique 1 : Introduction 4 L'algorithmique, vous la pratiquez tous les jours et depuis longtemps... Briques de LEGO Camion de pompiers suite de dessins Meuble en kit Cuisine équipée notice de montage Cafetière Expresso instructions Laine Pull irlandais modèle Farine, oeufs, chocolat, etc.... Forêt noire recette Algorithmique 1 : Introduction 5 De l'importance de l'algorithme Informations éparses Machine Données structurées Traitement Obtention de résultats Résultats mis en forme Un algorithme, traduit dans un langage compréhensible par l’ordinateur (ou langage de programmation, ici le C++), donne un programme, qui peut ensuite être exécuté, pour effectuer le traitement souhaité. Algorithmique 1 : Introduction 6 • Savoir expliquer comment faire un travail sans la moindre ambiguïté - langage simple : des instructions (pas élémentaires) - suite finie 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. Algorithmique 1 : Introduction 7 Les problèmes 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 ? - Etant 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? Algorithmique 1 : Instructions de base 8 Les instructions de base Algorithmique 1 : Instructions de base 9 Un premier algorithme Algorithme ElèveAuCarré {Cet algorithme calcule le carré du nombre que lui fournit l'utilisateur} variables unNombre, sonCarré: entiers {déclarations: réservation d'espace-mémoire} début {préparation du traitement} afficher("Quel nombre voulez-vous élever au carré?") saisir(unNombre) {traitement : calcul du carré} sonCarré ← unNombre × unNombre {présentation du résultat} afficher("Le carré de ", unNombre) afficher("c'est ", sonCarré) fin Algorithmique 1 : Instructions de base 10 Les trois étapes d’un algorithme • Préparation du traitement - données nécessaires à la résolution du problème • Traitement - résolution pas à pas, après décomposition en sous- problèmes si nécessaire • Edition des résultats - impression à l’écran, dans un fichier, etc. Algorithmique 1 : Instructions de base 11 Déclarer une variable variable <liste d’identificateurs> : type • Fonction : Instruction permettant de réserver de l’espace mémoire pour stocker des données (dépend du type de ces données : entiers, réels, caractères, etc.) • Exemples : variables val, unNombre : entiers nom, prénom : chaînes de caractères Algorithmique 1 : Instructions de base 12 Saisir une donnée saisir(<liste de noms de variables>) • Fonction : Instruction permettant de placer en mémoire les informations fournies par l'utilisateur. • Exemples: saisir(unNombre) saisir(nom, prénom) saisir(val) Algorithmique 1 : Instructions de base 13 Afficher une donnée, un résultat afficher(<liste de noms de variables, de constantes ou d ’expressions>) • Fonction : Instruction permettant de visualiser les informations placées en mémoire. • Exemples: afficher(unNombre, "est différent de 0") afficher("La somme de", unNombre, "et" , val , "est", unNombre + val) Algorithmique 1 : Instructions de base 14 Déclarer une constante constante (<identificateur> : type) ←<expression> • Fonction : Instruction permettant de réserver de l’espace mémoire pour stocker des données dont la valeur est fixée pour tout l’algorithme • Exemples : constantes (MAX : entier) ←100 (DOUBLEMAX : entier) ←MAX × 2 Algorithmique 1 : Instructions de base 15 Saisies et affichages : exemples Algorithme ParExemple {Saisit un prix HT et affiche le prix TTC correspondant} constantes (TVA : réel) ←20.6 (Titre : chaîne) ←"Résultat" variables prixHT, prixTTC : réels {déclarations} début {préparation du traitement} afficher("Donnez-moi le prix hors taxe :") saisir(prixHT) prixTTC ←prixHT * (1+TVA/100) {calcul du prix TTC} afficher(Titre) {présentation du résultat} afficher(prixHT, « euros H.T. devient ", prixTTC, « euros T.T.C.") Fin Affichage : Algorithmique 1 : Instructions de base 16 Affecter une valeur à une variable <identificateur> ← <expression> ou <constante> ou <identificateur> • Fonction : Instruction permettant d’attribuer à la variable identifiée par l'élément placé à gauche du symbole ←la valeur de l'élément placé à droite de ce symbole. • Exemple: nom ←"Venus" val ←50 val ←val × 2 Algorithmique 1 : Instructions de base 17 Affectation : exemples constante (SEUIL : réel) ←13.25 variables valA, valB : réels compteur : entier mot , tom : chaînes valA ←0.56 valB ←valA tableau de simulation : valA ←valA × (10.5 + SEUIL) valA valB comp- mot tom compteur ←1 teur compteur ←compteur + 10 mot ←" Bonjour " tom ←"Au revoir ! " Algorithmique 1 : Instructions de base 18 Affectation : exemples (suite) afficher(mot) afficher(" valA = ", valA) afficher(" valB = ", valB) afficher(" compteur =", compteur ) afficher(tom) Affichage : Algorithmique 1 : Instructions de base 19 Simulation d'un algorithme Algorithme CaFaitQuoi? {Cet algorithme .........................................} variables valA, valB : réels {déclarations} début {préparation du traitement} afficher("Donnez-moi deux valeurs :") saisir (valA, valB) afficher("Vous m'avez donné ", valA, " et ", valB) {traitement mystère} valA ←valB valB ←valA {présentation du résultat} afficher("Maintenant , mes données sont : ", valA, " et ", valB) Fin Affichage : Algorithmique 1 : Instructions de base 20 Ce qu’il fallait faire … • Déclarer une variable supplémentaire variables valA, valB, valTemp : entiers • Utiliser cette variable pour stocker provisoirement une des valeurs saisir(valA, valB) valTemp ←valA valA ←valB valB ←valTemp Algorithmique 1 : Instructions de base 21 Traitement à faire si … Algorithme SimpleOuDouble {Cet algorithme saisit une valeur entière et affiche son double si cette donnée est inférieure à un seuil donné.) constante (SEUIL : entier) ←10 variable val : entier début afficher("Donnez-moi un entier : ") { saisie de la valeur entière} saisir(val) si val < SEUIL { comparaison avec le seuil} alors afficher ("Voici son double :" , val × 2) sinon afficher ("Voici la valeur inchangée :" , val) fsi fin Algorithmique 1 : Instructions de base 22 L’instruction conditionnelle si <expression logique> alors instructions [sinon instructions] fsi Si l’expression logique (la condition) prend la valeur vrai, le premier bloc d’instructions est exécuté; si elle prend la valeur faux, le second bloc est exécuté (s’il est présent, sinon, rien). Algorithmique 1 : Instructions de base 23 Une autre écriture Algorithme SimpleOuDouble {Cet algorithme saisit une valeur entière et affiche son double si cette donnée est inférieure à un seuil donné.) constante (SEUIL : entier) ←10 variable val : entier début afficher("Donnez-moi un entier : ") { saisie de la valeur entière} saisir(val) si val < SEUIL alors val ←val × 2 {comparaison avec le seuil } fsi afficher("Voici la valeur finale : ", val) fin Algorithmique 1 : Instructions de base 24 Quand la condition se complique : les conditionnelles emboîtées Problème : afficher "Reçu avec mention" si une note est supérieure ou égale à 12, "Passable" si elle est supérieure à 10 et inférieure à 12, et "Insuffisant" dans tous les autres cas. si note ≥12 alors afficher( "Reçu avec mention" ) sinon si note ≥10 alors afficher( "Passable" ) sinon afficher( "Insuffisant" ) fsi fsi Algorithmique 1 : Instructions de base 25 La sélection sur choix multiples selon <identificateur> (liste de) valeur(s) : instructions (liste de) valeur(s) : instructions … [autres : instructions] S’il y a plus de deux choix possibles, l’instruction selon permet une facilité d’écriture. Algorithmique 1 : Instructions de base 26 L’instruction selon : exemple selon abréviation "M" : afficher( " Monsieur " ) "Mme" : afficher( " Madame " ) "Mlle" : afficher( " Mademoiselle " ) autres : afficher( " Monsieur, Madame " ) Comparer : si abréviation = "M" alors afficher( "Monsieur" ) sinon si abréviation = "Mme" alors afficher("Madame") sinon si abréviation = "Mlle" alors afficher( "Mademoiselle" ) sinon afficher( "Monsieur,Madame " ) fsi fsi fsi Algorithmique 1 : Instructions de base 27 Quand il faut répéter un traitement ... Algorithme FaitLeTotal {Cet algorithme fait la somme des nbVal données qu'il saisit} variables uploads/Industriel/ cours-algo-1-2.pdf