Home

Cours introductif à l`Algorithmique

1. 1 Introduction Notion d algorithme 1 1 D finitions Informatique domaine concernant le traitement de l information l aide d un ordinateur Ordinateur dispositif permettant de manipuler des informations les donn es en vue d obtenir de nouvelles informations les r sultats Pourquoi un cours d Algorithmique Objectif obtenir de l ordinateur qu il effectue un travail notre place Probl me expliquer l ordinateur comment il doit s y prendre Informations parses R sultats mis en donn es forme Traitement calcul des r sultats 1 1 D finitions action indicateur Action v nement produit par un acteur l ex cutant Elle prend place pendant une p riode finie et produit un r sultat bien d fini et pr vu Indicateur un indicateur est caract ris par son nom et sa valeur il repr sente une information Une action agit sur un ensemble d indicateurs pouvant prendre des valeurs diff rentes Etat du syst me tat du syst me l ensemble des valeurs des indicateurs l instant t est appel l tat du syst me l instant t Effet d une action l effet est caract ris par 2 tats du syst me A lo t t tat initial de l action A t tat final de l action A Algorithme Sp cification d une action c est la description des tats initial et final de l action Algorithme suite logique d actions permettant d arriver u
2. Exemple e afficher Total TTC tt 1 196 2 2 Lecture de donn es et criture de r sultats On dispose de deux op rations saisir saisie de donn es du clavier cl Forme cl saisir liste des informations saisies Exemple cl saisir a b afficher affichage des r sultats sur l cran e Forme e afficher liste des valeurs affich es Noms d informations r sultats calcul s Constantes chaines de caract res par exemple Expressions Exemple e afficher Total TTC tt 1 196 Illustration sur l exemple lexique ajout cl clavier p riph rique d entr e e cran p riph rique de sortie Algorithme ns j h m sz e afficher entrez un nombre de secondes inf rieur 1000000 cl saisir ns ns n j lt ns div 86400 r1 lt ns mod 86400 ns n j j h m s nszj4 86400 r h lt r1 div 3600 r2 lt ri mod 3600 ns n j j h h m s ns j 86400 h 3600 r m lt r2 div 60 lt r2 mod 60 ns n j j h h mms S S NS jo 86400 hy 3600 m 60 So e afficher ns Jours h heures m minutes s secondes s Types de base les entiers Entiers Z constantes 156 12 1998 op rations div mod Z X Z gt gt Z div mod Z X Z gt Z Z X Z gt R comparaisons lt gt lt gt ZX Z B vrai faux Types de base les r els R els R constantes 3 14159 0 00
3. f h r1 div 3600 r2 lt r1 mod 3600 ns n j h h h m s rl r F n J 86400 h 3600 r m lt r2 div 60 s lt r2 mod 60 ns n j j h h MEM s s 1r1 r r2 f n jo 86400 h 3600 m 60 So 20 Illustration sur l exemple lexique principal compl t ns entier entre 0 et 999999 donn e nombre de secondes j entier gt O r sultat nombre de jours h entier entre 0 et 23 r sultat nombre d heures m entier entre 0 et 59 r sultat nombre de minutes S entier entre 0et59 r sultat nombre de secondes r1 entier entre O et 86399 interm diaire ns modulo 86400 r2 entier entre O et 3599 interm diaire r1 modulo 3600 21 2 2 Lecture de donn es et criture de r sultats On dispose de deux op rations saisir permet la saisie de donn es du clavier Cl Forme cl saisir liste des informations saisies Exemple cl saisir a b afficher affichage des r sultats sur l cran e Forme e afficher liste des valeurs affich es Exemple e afficher Total TTC tt 1 196 2 2 Lecture de donn es et criture de r sultats On dispose de deux op rations saisir permet la saisie de donn es du clavier Cl Forme cl saisir liste des informations saisies um D finies dans le lexique Exemple cl saisir a b les donn es afficher affichage des r sultats sur l cran e Forme e afficher liste des valeurs affich es
4. il est possible de d finir des indicateurs dont la valeur est fix e pour tout l algorithme Leur valeur n est pas modifiable constante nom le type valeur Exemples constante PI le r el 3 14159265 constante MAX l entier 100 constante DOUBLEMAX l entier MAX 2 constante MESSAGE la chaine Hello world Conventions d criture Les constantes peuvent tre nomm es par des noms form s uniquement de majuscules standard en C et C Les autres variables par des noms commen ant par une minuscule standard Java Les noms de types et de classe peuvent tres des noms commen ant par une majuscule standard Java II n y a pas de r gle absolue mais des habitudes ou des standards respecter ll faut tre coh rent en suivant toujours les m mes principes
5. p riph rique d entr e a b entiers donn es valeurs manipuler c entier interm diaire pour quoi faire Algorithme cl saisir a cl saisir b a agb bg cea a agb DoC ag a lt b a bo bD Do C a bh lt C Ja b b ac a 36 Exercice 3 Trouvez ce que fait l algorithme suivant en d crivant les tats interm diaires lexique cl clavier p riph rique d entr e a b entiers donn es valeurs manipuler Algorithme cl saisir a cl saisir b aca h b a b a a b 37 Affectation compl ment Il est possible d crire plusieurs instructions sur une m me ligne Dans ce cas on s pare les Instructions par un Exemples cl saisir a e ecrire a ic1 1 k lt w 1 Types de base chaines de caract res Cha nes de caract res C constantes A Bon op ration de concat nation amp C X C 5 C concatenation Bon amp jour a pour r sultat Bonjour amp hello a pour r sultat hello si m1 m2 et m3 sont des chaines quel est l effet de cette s quence d instructions m1 soir m2 lt tao m3 m2 amp m1 Types de base chaines de caract res comparaisons de chaines C X C B Attention aux notations X repr sente la chaine de caract res comprenant un X majuscule X est le nom d une information X repr sente le caract re X majuscule Fonctions et op rations pr d finies sur les ch
6. ch Longueur hello 5 Longueur 0 Longueur SousChaine hello 3 10 3 44 Fonctions et op rations pr d finies sur les cha nes s lection d un caract re dans une chaine non vide S lection d un caract re particulier d une chaine non vide ni me C X N 5C Soit ch une chaine non vide ni me ch 1 d signe le 1er caract re de ch nieme ch i d signe le i me caractere de ch 1 lt i S longueur ch nieme ch longueur ch d signe le dernier caract re de la chaine ch Exemple ch hello nieme ch 2 e 45 Exercice Ecrire un algorithme qui saisit un verbe du premier groupe et affiche sa conjugaison au pr sent de l indicatif Conjugaison d un verbe du premier groupe au pr sent de l indicatif lexique cl clavier p riph rique d entr e e cran p riph rique de sortie verbe chaine donn e verbe conjuguer radical chaine interm diaire radical du verbe conjuguer Algorithme e afficher entrez un verbe du premier groupe cl saisir verbe verbe v radical sousChaine verbe 1 longueur verbe 2 radical radical de v e afficher je radical e e afficher tu radical amp es e afficher il ou e radical e e afficher nous radical ons U e afficher vous radical e Z e afficher ils ou elles radical e amp nt 47 Constantes nomm es Dans le lexique d un algorithme
7. 1 1 2E5 op rations R X R gt R R X R gt R comparaisons lt gt lt 2 R X R 5 B vrai faux Partie enti re et partie d cimale d un r el Fonctions pr d finies pent et pdec pent R Z V X R pent x partie enti re de x Exemple pent 34 12 34 pdec R 0 1 V xe R pdec x partie d cimale de x Exemple pdec 34 12 0 12 Exemples d utilisation de pent et pdec a c entiers b d r els entre O et 1 a lt pent 12 56 l a 12 b lt pdec 12 56 b 0 56 c lt pent 12 56 100 c 1256 attention 12 56 100 1256 0 un r el et non un entier d lt pdec 12 56 100 d 0 0 Types de base les bool ens Bool ens B vrai faux constantes vral faux op rations et ou binaires non unaire et ou B X B B non B B comparaisons B XB B Rappel Table de v rit A A et B A ou Binon A non B non Aet non B B V F V F Exemple d utilisation de bool ens lexique principal cl clavier p riph rique d entr e e cran p riph rique de sortie a b c entiers donn es valeurs examiner aEstMax bool en r sultat vrai si a plus grand que b et c k bool en k est vrai si Algorithme principal e afficher entrez 3 entiers cl saisir a b c a ag b b c Cg aEstMax aEstMax lt a gt b et a gt c aEstMax vrai si
8. a gt b et si a gt c faux sinon e afficher a plus grand que b et c aEstMax k lt b gt c ou aEstMax e afficher k on affiche vrai si 32 Types de base caract res Ensemble des caract res C constantes A s op rations n ant comparaisons z CXC gt B Attention aux notations X repr sente le caract re X majuscule X est le nom d une information indicateur espace SI b est un bool en et c un caract re que signifie cette instruction b lt c A Retour sur l affectation d une valeur un indicateur une variable Forme g n rale Nomindicateur lt expression arithm tique ou logique OU Nomindicateur lt nom d un autre indicateur OU Nomindicateur lt constante Instruction permettant d attribuer un indicateur identifi par le nom plac gauche du symbole lt la valeur de l l ment plac droite de ce symbole La valeur droite du symbole doit tre du m me type que celui de l indicateur plac gauche de ce symbole p Exercice Trouvez le type de l indicateur auquel on donne une valeur Trouvez les erreurs valA lt 0 56 valB lt a gt b valC lt valC 1 mot lt Hello world valD Z valE valA valB ValC 2 valF lt ValD ValC valD lt 1 valD X 35 Exercice 2 Trouvez ce que fait l algorithme suivant en d crivant les tats interm diaires lexique cl clavier
9. a nes concat nation ajout d un caract re concat nation amp CH amp jour ajout d un caractere a gauche d une chaine c CX C C Ctrepr sente les cha nes non vides c e abcd cabca Q om _ en ajout d un caract re droite d une chaine C X C C C repr sente les cha nes non vides abcd c abcdc Exercice Parmi les expressions suivantes lesquelles sont incorrectes 123 A TUE A B amp c A B amp c abc amp def abc def abc amp amp def e abc e abc 23 Exercice Parmi les expressions suivantes lesquelles sont incorrectes 123 A A B s applique entre une chaine et un caract re A B amp c amp s applique entre deux chaines A B amp c abc amp def def ne correspond rien abc def ce n est ni un caract re ni un chaine abc amp amp def o abc aucun caract re entre les ce n est pas un car e abc 23 23 est un entier 43 Fonctions et op rations pr d finies sur les cha nes sous chaine longueur Fonctions pr d finies SousChaine C x N x N gt C SousChaine ch d long d signe la sous cha ne de ch de longueur long et commen ant avec le d me caract re SousChaine hello 2 3 ell SousChaine hello 3 10 llo Longueur C gt N Longueur ch d signe la longueur de la chaine ch c est dire le nombre de caract res composant
10. ant ni de la machine qui ex cutera le programme correspondant tapes de construction d un algorithme 1 Pr ciser les conditions de travail du probl me objets caract risant les informations manipuler r pertoire d actions dont on dispose 2 R fl chir une m thode bien d finie pour r soudre le probl me 3 D crire cette m thode sans ambigu t tapes de construction d un algorithme 4 valuer la m thode d crite temps d ex cution nombre d op rations taille etc 5 R fl chir aux qualit s et aux d fauts de la m thode choisie 6 R fl chir d autres m thodes et les comparer selon les crit res de qualit d finis Jouons un peu Trouver une solution pour gagner au Jeu des plaquettes dont voici la r gle Ill y a un meneur de jeu et 5 joueurs Le meneur de jeu annonce un nombre entre 0 et 45 Les joueurs doivent chacun choisir un nombre entre 0 et 9 Le total des chiffres choisis doit tre gal au nombre annonc par le meneur de jeu Les joueurs n ont pas le droit de se concerter pendant le choix du nombre qu ils vont annoncer Jouons un peu faire une partie pour comprendre le jeu vous allez perdre r fl chir une strat gie gagnante vous ne devez plus perdre faire une partie pour v rifier que votre strat gie permet de gagner pour toutes les valeurs possibles 2 Organisation s quentielle d un calcul 2 Organisation s quent
11. ielle d un calcul Exemple crire un algorithme qui pour un nombre donn de secondes inf rieur un million calcule son quivalent en nombre de jours d heures de minutes et de secondes 2 1 Sp cification d signation typage tapes de la construction d un algorithme Sp cifier un probl me consiste expliciter les informations pertinentes pour une mod lisation algorithmique notamment les donn es et les r sultats puis formuler les relations qui les caract risent D signer les informations c est leur donner un nom 2 1 Sp cification d signation typage tapes de la construction d un algorithme Typer les informations c est donner leurs domaines de valeurs Formuler la solution algorithmique Illustration sur l exemple Informations manipul es le lexique de l algorithme Lexique ns entier entre O et 999999 donn e nombre de secondes j entier gt 0 r sultat nombre de jours h entier entre O et 23 r sultat nombre d heures m entier entre O et 59 r sultat nombre de minutes S entier entre O et 59 r sultat nombre de secondes Relation entre donn es et r sultats ns 86400 j 3600 h 60 m s Illustration sur l exemple Algorithme ns n j h m Sz j lt ns div 86400 div repr sente la division euclidienne ri ns mod 86400 mod repr sente le modulo reste de la division ns zn j h h m s rl r n J 86400
12. n r sultat d termin Un algorithme d crit un comportement en termes d actions r alisables a priori et d informations identifi es dans le lexique de l algorithme les indicateurs Construction d un algorithme Construire un algorithme consiste d couvrir les actions qu il faut organiser dans le temps et choisir la mani re de les organiser pour obtenir le r sultat escompt par leurs effets cumul s tat A Etat initial final Les indicateurs ou variables Variable les valeurs des indicateurs changent varient sous l effet des actions de l algorithme C est pourquoi les indicateurs sont aussi appel s des variables Chaque information nombre entier caract re que l on veut utiliser doit tre stock e dans un emplacement m moire Exemples d algorithmes Une recette de cuisine Un mode d emploi Une strat gie gagnante pour un jeu simple Une m thode syst matique pour r soudre un probl me math matique par exemple la r solution d un syst me d quations Une notice de montage d un meuble en kit Importance de l algorithme Savoir expliquer comment faire un travail sans la moindre ambigu t langage simple des instructions op rations 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 a priori ni du langage dans lequel il sera impl

Cours introductif à l`Algorithmique

Contents

Download Pdf Manuals

Related Search

Related Contents

Cours introductif &agrave; l`Algorithmique

Contents

Download Pdf Manuals

Related Search

Related Contents

Cours introductif à l`Algorithmique