Algorithmes-2.docx

Les Algorithmes I/ notion générale Phase d’élaboration d’un programme Pour trouver une solution informatique qui a un problème pose le concepteur élabore cette solution en passant par les phases suivantes : phase d’analyse phase de spécification phase de traduction phase d’exécution Phase d’analyse Un problème est donné ou posé par son énoncé sous d’écrit ou de parole. Donc il est exprimé dans un langage évolué (humain) non précis. La phase d’analyse consiste à élaborer un model conceptuel d’analyse a partir de l’énoncé du problème sous forme d’une suite d’action et d’étapes. Deux méthodes se présentent pour obtenir le model d’analyse. méthode ascendante : le concepteur compose la solution du problème a partir d’une boite a outils (algorithme élémentaire), il maîtrise la solution a partir de son expérience et de l’utilisation fréquente de l’outil. SP = sous problème PROBLEME POSE SP1, 2 SP3 SP1 Méthode descendante : elle consiste a subdiviser le problème posé en sous problème. La subdivision se continue jusqu'à avoir des sous problème a solution facile ou connue. On obtient un arbre hiérarchisé en niveau de difficulté Problème poser SP SP SP sp sp sp sp sp sp Feuilles de l’arbre EXEMPLE 1 : Elaborer un modèle d’analyse pour la préparation d’une omelette Exercice 2 : Un étudiant passe un examen de 3 matières a coefficient unitaire. Elaborer un model conceptuel d’analyse permettant le calcul de la moyenne de l’examen ? Exercice d’application : Exos 1 : Elaborer un model d’analyse permettant la transformation d’un temps exprimé en heure, minutes et secondes en un temps total de seconde. Exos 2 : Elaborer le model d’analyse réalisant le travail inverse de l’exos 1. Exos 3 : UN employé est rémunère en fonction du nombre de jours travaillés avec une indemnité journalière. Il perçoit en plus 0.5% du bénéfice mensuel de l’entreprise. Elaborer le model d’analyse pour calculer le salaire mensuel. Exos 4 : Je dispose chez moi d’une connection a 512kbits/s. Elaborer le model d’analyse permettant le calcul du temps (exprimé en heure, min, sec) de téléchargement exprimé en méga octets. Phase de spécification Le model d’analyse décrit la solution avec des termes non informatique (non précis). Il approche la solution avec un niveau sémantique vague. Et donc ne pas être considère comme outil de programmation machine. La phase de spécification permet la description du model d’analyse avec des termes informatique liés au formalise algorithme facilitant le passage au programmes utilisables sur machine. L écriture d’un algorithme suit une syntaxe bien définie pour permettre la communication entre les concepteurs de programmes. Langage humain Analyse + spécification Langage algorithmique Traduction Langage évolué (C, pascal, VB…) Exécution Langage machine binaire. la phase de traduction l’exploitation d’un algorithme une fois écrit sur machine nécessite sa traduction (ou codage) dans un langage évolué compréhensible par la machine (exemple : langage C, VB, C++, Java …) Algorithme Traduction Programme Librairie du langage Algorithme Traduction Programme Librairie du langage Exemple Algorithme | Langage C | Langage Pascal Afficher (« votre prix ») | Printf (« votre prix ») | writeln (« votre prix ») Lire (« votre prix ») | scanf (%d, « &prix ») | readln (prix) phase d’execuction l’exécution d’un programme passe par les étapes suivantes Programme sur papier Edition de texte Fichier source compilation Erreur Correction erreur Editions des liens Fichiers objets Exécutions Résultat Librairie langage Programme sur papier Edition de texte Fichier source compilation Erreur Correction erreur Editions des liens Fichiers objets Exécutions Résultat Librairie langage édition de texte : c’est la saisie du programme dans un éditeur de texte. le fichier est sauvegarder avec une extension du langage de programmation : .c ; .cpp ; .pas. éditions compilation : c'est la recherche des éventuelles erreurs syntaxiques ou sémantique commise dans le programme source ne respectant pas le formalise du langage utilisé. Exemple : oublie de point virgule, non déclaration de variable, utlisation frauduleuse de type… éditions de liens : l’écriture d’un programme nécessite l’utilisation d’une série de fonction prédéfinie dans un langage de programmation. l’éditions de lien permet d’insérer les codes des ces fonctions dans le programme source. Exécution : l’éditions de lien donne un fichier exécutable qui lui fournissant des données nécessaires, gênera des résultats attendus (EXE) Syntaxe générale Un algorithme est écrit par un nom, une partie déclaration, et un corps. La partie déclaration sert à définir les objets de données de l’algorithme. Le corps de l’algorithme rassemble les instructions qui doivent être exécutés sur les objets. Syntaxe Algo : Nom_algorithme Decalartion Objet de données Début Instructions Fin nom_algorithme Algo : Nom_algorithme Decalartion Objet de données Début Instructions Fin nom_algorithme Nom de l’algorithme : c’est un identifiant, composé d’une suite de lettre, chiffre et le caractère «_ » Exemple : calcul_moyenne Tous les mots clés du langage algorithmique doivent être souligné : algo, declaration, si, alors … Les commentaires : pour documenter l’algorithme ou explicité le rôle des variables ou des étapes de traitement on insérera des commentaires. Le commentaire est insère entre deux accolades et peut se tenir sur plusieurs lignes Exemple : {ce ci est un commentaire} objet de donnée et type un objet de donnée est défini par son nom, son type, son utilisation et sa nature. nom : c’est un identificateur (suite de lettre, chiffre et « _ ». il ne faut pas utiliser des blancs ou des symboles (« » ; {}, -) exemple : prix_ht ; prix_2004 le type : définie l’ensemble des valeurs que prend l’objet. Type entier, réel, caractères, chaîne et booléen. Un caractère est une lettre, un chiffre, ou un symbole. Une chaîne est une suite finie de caractères. Booléen: deux valeurs (vrai ou faux) L’utilisation : un objet peut être utilisé sous forme de : donnée ou entrée : reçu par l’algorithme pour réaliser le traitement. Sortie ou résultat : fourni par l’algorithme à son environnement (utilisateur). Intermédiaire : objet servant pour les calculs intermédiaire non visible à l’utilisateur. Algorithme entrée intermédiaire Sortie Algorithme entrée intermédiaire Sortie la nature : un objet qui change de contenue est appelé variable, sa déclaration suit la syntaxe suivante : nom_variable : type exemple : i : entier prix : réel nom : chaîne trouve : booléen un objet qui ne change pas de contenu est appelé une constante : constante nom_variable : valeur exemple : constante TVA = 19.6 max = 15 nom_usine = « Perrier » Entrée / Sortie entrée : pour saisir une donnée et affecter à une variable on utilise l’une des fonctions prédéfinie lire ou saisir. Syntaxe : Lire (nom_variable) Saisir (nom_variable) Lire (nom_variable_1, nom_variable_2,…) sortie : pour afficher à l’écran un texte, message ou le contenue d’une variable on utilise les fonctions prédéfinie écrire ou afficher. Syntaxe : Afficher (« texte ») Ecrire (« nom_variable ») Afficher (nom_variable, « texte »,…) exemples Nb : l’écriture des algos a été testée avec le logiciel alg exec Ecrire un algorithme qui permet de saisir un temps exprimer en heure, minute, seconde et fourni un total en seconde Ecrire l’algo inverse du précèdent Calcul salaire : D’après le cours pour changer un peu ! Algo : calcul_salaire 4572009842500Déclaration Nbre_jours, ind_j, benf, salaire : réel Début 4572002286000 Afficher (« nombre de jours ? ») Lire (Nbre_jours) Afficher (« indemnité ») Lire (ind_j) Afficher (« quel est le bénéfice ») Lire (benf) Salairenbre_jours, * ind_j + 0.005 * benf Afficher (« le salaire mensuel est de : », salaire) Fin calcul_salaire Téléchargement Algo : temps_telechargement Déclaration Taille_fichier, débit, conv, temps, heure, reste, min, sec : entier Début Afficher (« taille du fichier en Mo : ») Lire (taille_fichier) Afficher (« débit ») Lire (débit) Conver taille_fichier * 1024 * 8 Temps conv /débit Heure temps /3600 Restetemps – heure * 3600 Min reste /60 Sec reste - min * 60 Afficher (« temps de téléchargement : », heure, min, sec) fin temps_telechargement L’affectation Pour affecter une valeur à une variable on utilise le signe «  » Ex : nom_variable expression L’ancien contenu de la variable est écrasé avec la nouvelle valeur. A différencie écriture informatique et les écritures mathématique. Informatique | Mathématique x x + 5 | x = x +5 (impossible) A différencier entre affectation et = test d’égalité x y | x = y x va recevoir la valeur y si x est égale a y ? Dans les langages évolués Langage C Pascal Algorithme Affectation = : = Test d’égalité = = = = Il ne faut pas utiliser le signe «  » pour l’affectation (Ne pas faire) 5 y | (faire) y 5 Les opérations : les opérations arithmétiques : Opérateurs Désignations Exemples + Plus unitaire + x - Moins unitaire - x + Addition x + y - Soustraction x – y * Multiplication x * y / Divisions sans reste x /y %div Division avec reste x div y x%y % mod Reste de la division x mod y x%y Exemple : 5/3 = 1.666…. division sans reste 5 div 3 = 1 5 mod 3 = 2 Opérateur de test Opérateurs Désignations Exemples = Test d’égalité x = y Différent de x = y > Supérieur à x > y >= Supérieur ou égale x >= y < Inférieur à x < y <= Inférieur ou égale x <= y Opérateur logique Opérateurs Désignation Exemple Non Négation Non(x) Et Et logique x Et y Ou Ou logique inclusif X ou y X et Y sont des variables booléens. Table de vérité X et y sont des variables booléens : vrai ou faux Non : négation X Non(x) Vrai Faux Faux vrai Et logique : il est vrai si les variables sont vrai X Y X et Y Faux Faux Faux Faux Vrai Faux Vrai Faux Faux Vrai Vrai Vrai Ou inclusif : il est vrai que si l’une au moins des variables est vrai X Y X Ou Y Faux Faux Faut Faux Vrai Vrai Vrai Faux Vrai Vrai Vrai vrai Séries d’exos : Exercices 1 : un employé surveille le fonctionnement d’un moteur en relevant des temps exprimés en heure, minutes et secondes. Ecrire un algorithme lui permettant de faire sommer deux temps. Algo : somme_temps Declaration: H1, h2, h, m1, m2, m, s1, s2, s: entier Debut: Afficher (“temps1”) Lire (h1, m1, s1) Afficher (« temps2 ») Lire (h2, m2, s2) S (s1+s2) % 60 M m1 + m2 + (s1+s2/div60) %60 H h1 + h2 + (m1 + m2 + (s1+s2/div60) div60 Afficher (“la somme des temps est :”h, m, s) Fin : somme_temps Exos 2 : écrire un algorithme qui permet un nombre de jour et une date exprimée en jour, année et siècle et réalise leur somme. Alglo : temps Déclaration Siècle, jour, année, nbr_j : entier Siecle_result, année_result, jour_result : entier Début : Afficher (« donner la date ») Lire (siècle, année, jour) Afficher (« le nombre de Jour ») Lire (nbr_j) J jour + nbr_j mod 365 A année + (jour +nbr_j div 365) mod 100 S siècle + (année + (jour + nbr_ j)/365) div 100 Afficher (« le résultat : »s « ; » a « ; » j) Fin : temps II) les structures de contrôle l’alternative simple Syntaxe : Si condition Alors instruction Fin Si L’alternative simple permet d’exécuter une instruction (ou plusieurs) instruction si une condition est vérifié. L’instruction (ou bloc d’instructions) simplement sauté si la condition n’est pas vérifiée. La condition est une expression booléenne simple ou composée avec des opérateurs logiques (Et, Ou, Non) Représentation en organigramme 285750063500Faux /non Condition Oui / vrai Instructions Faux /non Condition Oui / vrai Instructions Exemple : Condition simple Si prix < 100 Alors afficher (« prix raisonnable ») Fin Si Condition composée Si moyenne < 0 ou moyenne > 20 Alors afficher (« moyenne erronée ») Fin Si l’alternative double Syntaxe : Si condition Alors instruction 1 Sinon instruction 2 Fin Si La première instruction (ou bloc) est exécutée si la condition est vrai (vérifiée). Dans le cas contraires les c’est la 2eme instruction qui est exécutée. L’exécution est exécutive, l’une des instructions qui est exécutée a la fin. Représentation organigramme : Instruction 2 Instruction 1 Condition Faux/non Oui/non Instruction 2 Instruction 1 Condition Faux/non Oui/non Remarque : le « sinon » exprime la négociation de la condition, il n’y a pas lieu de rester le cas contraire. Exemple : Si moyenne>=10 Alors afficher (« élève admit ») Sinon afficher (« élève recalé ») Fin Si Si prix>0 Alors prix_ttc prix *1.196 Afficher (« prix TTC est : », prix_ttc) Sinon afficher (« erreur de saisie ») Fin Si Imbrication d’alternative Dans certains cas de résolution de problème on peu être amenée a imbriqué des alternatives simple ou doubles. Il faut veiller à respecter la syntaxe. a chaque si un alors et fin si sont obligatoire. Un sinon ne peut être entame que si un Si est ouvert au préalable Deux schémas qui se pressentent : Si condition1 Alors si condition 2 Alors si condition 3 Alors…. Sinon instruction Fin si Sinon instruction Fin si Fin si Si condition 1 Alors instruction 1 Sinon si condition 2 Alors instruction Sinon si … Fin si Fin si Fin si Exemple : teste deux nombre a, b Si a>b Alors Afficher (a, « est plus grand », b) Sinon Si a