1 Notion d`algorithme
Contents
1. Turing tout proc d de calcul pouvant tre d crit de fa on syst matique peut l tre avec ces cinq instructions Ann e scolaire 2014 2015 PCSI Informatique Cours 5 PRATIQUE 4 Exemple a input entrer le germe n input indice k 0 u a while k lt n if u 2 0 u u 2 else u 3 xu l k k 1 print u 1 Quelles variables et quel type 2 Rep rer les instructions 3 On donne a 25 et n 6 donner l tat des variables au cours de la r alisation du programme 4 Documenter le programme 5 Pratique 1 Documenter un programme Il est indispensable que le programme soit lisible pour pouvoir le reprendre plus tard pour qu il puisse tre compris par une tierce personne Les mani res de rendre un programme lisible a choisir des noms de variables parlants Ann e scolaire 2014 2015 PCSI Informatique Cours 5 PRATIQUE b ajouter des commentaires qui expliquent le r le des diff rentes parties d un programme En Python une ligne de commentaire commence par le symbole 2 Mettre un programme au point en le testant V rifier si un programme ne produit pas d erreur au cours de son ex cution et qu il effectue bien la t che que l on attend de lui Pour cela on le teste on ex cute plusieurs fois le programme en lui fournissant des entr es appel es tests qui permettent de d tecter les erreurs ventuelles On choisit ces valeurs de tests pour que a2. Ann e scolaire 2014 2015 PCSI Informatique Cours 1 NOTION D ALGORITHME Programmation G n ralit s 1 Notion d algorithme e Exemples 1 Recette de cuisine 2 Mode d emploi d un appareil 3 R solution de ax bz c 0 Un algorithme est une proc dure permettant de r soudre une classe de probl mes crite de fa on suffisamment d taill e pour pouvoir tre suivie sans poss der de comp tences particuli res ni m me comprendre le probl me que l on est en train de r soudre UN PEU DE CULTURE D o vient ce mot Al Khawarizmi n en 783 en Ouzbekistan mort en 850 Bagdad lt le p re de l alg bre gt L activit de l informaticien 1 Analyser le probl me 2 Mod liser le probl me choisir des structures adapt es la repr sentation des donn es concevoir une strat gie de traitement D finition 1 Algorithme ensemble des tapes permettant d atteindre un but en r p tant un nombre fini de fois un nombre fini d instructions 3 coder le probl me en traduisant l algorithme dans un langage donn D finition 2 Programme traduction d un algorithme en langage compilable ou in terpr table par l ordinateur Un peu plus th orique D finition 3 Un algorithme est une m thode g n rale pour r soudre un ensemble de probl mes Il est dit correct lorsque pour chaque instance du probl me il se termine en produisant la bonne sortie c est dire qu il r sout l
3. b c les cas limites Il ne suffit pas que le programme renvoie une valeur pour que le programme soit juste Il ne suffit pas que le programme marche une fois pour qu il soit juste La suite de Syracuse Pour les 10 premiers entiers pris comme germe rep rer s il y en a pour lesquels la suite n atteint pas 1
4. d instructions regroup es dans un fichier texte appel code source ou script Interpr teur Python gt V rification gt traduction en langage Assembleur Programme crit script Ex cution des commandes L ex cution d un programme commence la premi re instruction continue en ex cutant d autres instructions en suivant des r gles pr cises o flot d ex cution Le parcours des instructions au cours de l ex cution e l tat de l ex cution du programme l instant t L ensemble des variables d finies un instant donn t de l ex cution d un programme 3 Les instructions d un programme Dans un programme une instruction est un ordre de modification de l tat courant de l ex cution d un programme Deux grandes familles d instructions 1 Les instructions simples qui manipulent directement l tat courant d clarations et affec tations 2 les instructions compos es qui permettent d assembler d autres instructions et de modifier le flot d instructions en fonction de l tat courant Il y en a trois a la s quence qui permet d ex cuter deux instructions l une la suite de l autre b le test ou instruction conditionnelle qui permet de n ex cuter une instruction que dans certains cas c la boucle qui permet d ex cuter plusieurs fois la m me instruction dans un programme Th or me 1 Th or me de Church
5. e probl me pos On mesure l efficacit d un algorithme notamment par sa dur e de calcul en partant du principe que chaque instruction a un temps d ex cution constant par la pr cision des r sultats obtenus etc L analyse de la complexit algorithmique permet de pr dire l volution en temps calcul n cessaire pour amener un algorithme son terme en fonction de la quantit de donn es traiter Donald Knuth 1938 professeur l universit de Stanford lista les propri t s suivantes comme tant les pr requis d un algorithme La finitude un algorithme doit se terminer apr s un nombre fini d tapes d finition pr cise Chaque tape d un algorithme doit tre d finie pr cis ment les actions transposer doivent tre sp cifi es rigoureusement et sans ambigu t pour chaque cas rendement toutes les op rations que l algorithme doit accomplir doivent tre suffisamment basiques pour pouvoir tre en principe r alis es dans une dur e finie par une personne utilisant un papier et un crayon Il y a des m thodes qui permettent de v rifier qu un algorithme fait ce que l on veut Ann e scolaire 2014 2015 PCSI Informatique C amp ur ES INSTRUCTIONS D UN PROGRAMME 2 Notion de programme compr hensible par l homme Un programme est la traduction d un algorithme dans un langage 4 3 interpr table par une machine Il est constitu d un assemblage
Download Pdf Manuals
Related Search