[PDF] Algorithmique et st donnée Algorithmique et structures de données

View - Download Algorithmique et st donnée Algorithmique et structures de données

Previous PDF

Next PDF

Support de cours de la matière :Algorithmique et structures dedonnéesSpécialité :BioinformatiqueNiveau :Troisième année

Dr Chehili HamzaAnnée universitaire 2020-2021

Support de cours de la matière :Algorithmique et structures dedonnéesSpécialité :BioinformatiqueNiveau :Troisième année

Dr Chehili HamzaAnnée universitaire 2020-2021

Support de cours de la matière :Algorithmique et structures dedonnéesSpécialité :BioinformatiqueNiveau :Troisième année

Dr Chehili HamzaAnnée universitaire 2020-2021

Objectifs de l"enseignement:Cette matière vise à amener progressivement l"étudiant à assimiler et utiliser les concepts etles techniques nécessaires pour construire des algorithmes aux problèmes rencontrés. Ceci,doit impérativement passé par la compréhension de la démarche algorithmique et les énoncésnécessaires à sa représentation en pseudo code.Mode d"évaluation:Examens écrits, Contrôle continu

I.CONCEPTS DE BASE1.AlgorithmeUne succession finie d"opérations qui donne la solution d"un problème donné. Pour écrire unalgorithme, on utilise un pseudo-langage compréhensible par une communauté. Donc, l"idéegénérale d"un algorithme est de donnerla solution d"un problème sous forme d"opérations quipeuvent être traduites dans un langage compréhensible par la machine tout en le gardantlisible et compréhensible par une personne ordinaire.

2.ProgrammeUn programme est un assemblage et un enchaînement d"instructions élémentaires écritesdansun langage de programmation, et exécuté par un ordinateur afin de traiter les données d"unproblème et renvoyer un ou plusieurs résultats.3.Langage de programmationUn langage de programmation fournit un ensemble de mots-clés et de règles de syntaxequipermettent de créer des instructions formant des programmes et qui peuvent s"exécuter, sanssouci, sur une machine.II.STRUCTURE D"UN ALGORITHMELa figure suivante donne la structure générale d"un algorithme:

La première lignepermetjuste d"identifier l"algorithme. Donc, le nom attribué ne changepas l"exécution et les résultats.Avant de mettre les instructions, il faut déclarerles constantesetlesvariablesutilisées dans l"algorithme.La partie principale de l"algorithme se trouve entre les mots clés 'début" et'fin". Ellecontient la suite d"instructions à exécuter.Exemple:

4.Notion de variableUne variable estunmotqui permet l"identification de l'emplacement mémoire oùon stockeune valeur à manipuler.

Malgré que le choix est libre du nom de la variable, il préférable, pour desraisons de lisibilitéet de compréhension de choisir des noms de variables en fonctions de ce qu"elles représentent.Par exemple: Moyenne, Poids, Taille,...etc.La notion de type d"une variable est capitale, car elle implique le choix du codage de lavariable (par exemple, un entier sur 32 bits et un caractère sur 16 bits) ainsi que les possibilitéd"usage ( par exemple: on ne peut pas multiplier un caractère par un nombre entier).Exemplededéclarationdes variables:M, Max: EntierPoids, Moyenne: RéelPremier: Bouléen5.Notion de constanteOn peut assimiler la notion d"une constante à une variabledontlavaleurne change pasaucoursde l"exécution de l"algorithme.Exemple de déclaration des constantes:TVA = 0,17N = 50Admis = VraiIII.LESTYPESD"INSTRUCTIONSLa partie principale d"un algorithme contient la suite d"instruction qui va être traduite vers unlangage de programmation. Il existe quatre types d"instruction dont le détail est donné par lasuite:1.Les instructions d"entrée/sortieCe typed"instruction est utilisé pour interagir avec l"utilisateur, en lui permettant d"entrer desvaleurs des variables. Ainsi, le résultat destraitementset des messages d"informationpeuventêtre affichés à l"utilisateur via ce type d"instruction. En réalité,il existe plusieurspériphériques et manières pour échanger des données avec un algorithme ou un programme(via des fichiers, des bases de données, des formulaires,...). Toutefois, pour se concentrer surles principes de l"algorithmique, on se contente parles entrées et les sorties standards, àsavoir,l"écriture sur le clavier et l"affichage sur écran. L"exploitation des autres possibilitésvont être abordées dans la matière dédiée à la programmation.a.Instructiond'entrée

C"est l'instruction delecturede données sur le périphérique d'entrée.Structure générale:Exemple:Lire(Taille)Lire (x, y)b.Instructionde sortieC"est l'instruction de restitution de résultats sur le périphérique de sortie.Structure générale:

Exemple:Écrire (moyenne)Écrire(' entrer la taille")Écrire ('lerésultat est:",max)2.L"instruction d"affectationCette instruction permet d"affecter unevaleur à une variable, après l"évaluation d"uneexpression logique ou arithmétique.Ala place d"une expression, on peut utiliser une simple valeur ou une variableIl faut noter que le résultat de l"évaluation de l"expression doit avoir le même type que lavariable qui va le recevoir.Structure générale:Exemple1:x15,2xyxy+4

3.Test sur l"instruction d"affectationObjectif: auto-évaluation de la compréhension de l'effet des instructions d'affectation surl'état des variables.Exercice 1Quelles sont les valeurs des variables a,b et c écrites par l'algorithme suivant ?

oa= 10, b=20, c=40oa=-5, b=20, c= 10oa= 0, b=20, c=20Exercice 2Quelle est l'objectif de cette séquence d'instructions ?

oCalculer la différence entre deux variables.oPermuter les valeurs de deux variables.

oSans objectif.4.Les instructions conditionnellesCesinstructionssont utilisées pourfaire le choix entrel"exécutionou non des blocsd"instructions suite à l"évaluationd"une condition. On en distingue trois types:a.L"instruction conditionnelle simpleCe type d"instructionspermet de faire le choix entre l"exécution ou non d"un seul bocd"instructions.

Structure:

Exemple:A5B12SI (B>A*2) alorsBAFin SiEcrire (B)b.L"instruction conditionnelle alternativeCe type d"instructions permet de faire le choixdel"exécutionentre deux blocsd"instructions.Structure :

Exemple:A5B12SI (B>A*2) alorsBASinonBA+4Fin SiEcrire (B)c.L"instruction conditionnelle de choixCe type d"instructions permet de faire le choixdel"exécutionentreplusieurs blocs selon lavaleur d"une variable donnée.Structure :

Exemple:Lire (x)Selon le cas (x)x = 1:Ecrire ('Très Faible")

Selon le cas (variable)Variable = valeur 1: instructionsVariable= valeur 2: instructions...Variable= valeur n: instructionsSinonInstructionsFin Si

x= 2 :Ecrire ('Faible)x=3:Ecrire ('Moyen)x=4:Ecrire ('Bien")x=5:Ecrire ('Excellent")SinonEcrire('Valeur hors intervalle acceptée")Fin Si1.Test sur l'utilisation des instructionsconditionnellesObjectif: auto-évaluation de la compréhension.ExerciceSoit l"algorithme suivant:Algorithme Test2Déclarations:a, b, c: EntierDébut1: Lire (a, b)Si (b/2>a) Alors :2 : cb-aSinon3 : cb + a4 : ab-cFin si5 :Ecrire (a, b, c)Fin.Quelles sont les instructions exécutées pour les valeurs: a = 5, b = 10 ?2.Les instructionsitératives

Les instructionsitératives ourépétitives, appelées aussi communément par les développeursles boucles, permettent d"exécuterplusieursle même blocd"instructions. On en distinguetrois types:a.L"instruction 'Pour"Dans ce type d"instructionsitératives on connait à l"avance le nombre d"itérations.En effet,on doit préciser, dans l"entête de l"instruction 'Pour",la valeur initiale et la valeur finale etéventuellement le pas(lorsqu"il est différent de 1).Structure :

VI: valeur initialede la variable i,VF; valeur finale de la variable i,V:valeur à ajouter la variable i après chaque itération (par défaut 1).Exemple:Pouriallant de 1à 10faireEcrire ('L3 Bioinformatique")Fin poura.L"instruction 'Tant queDans ce type d"instructions itératives on ne connait pasforcementà l"avance le nombred"itérations.En effet, on continue la répétition del"exécution du bloc d"instructions tantqu"une condition est encore satisfaite.Tant que (condition) faireInstructionsFin Tant que

Pour i allant deVI à VF (pas = V) faireInstructionsFin Pour

Exemple:i =1Tant que (i <= 10) faireEcrire ('L3 bioinformatique")ii + 1Fin Tant quea.L"instruction 'Répéter"Comme le cas pour l"instruction 'Tant que", l"instruction 'Répéter" ne permet pas de connaitreforcement à l"avance le nombre d"itérations. En effet, on continue la répétition de l"exécutiondu bloc d"instructions jusqu"à la satisfaction d"une condition.Structure :

Exemple:i =1RépéterEcrire ('L3 bioinformatique")ii + 1Jusqu"à (i > 10)Remarque:L"instruction 'Tant que" s"exécute zéro ou plusieurs fois, au moment où,l"instruction 'Répéter" s"exécute une ou plusieurs fois.

RépéterInstructionsJusqu"à (Condition)

Série de TD 1Exercice1:Écrireun algorithme qui calcule le carré d'un nombre entier donnépar l'utilisateur.Exercice2:Écrireunl'algorithmequiéchange les valeurs des variables A et B.Exercice3:Écrireun algorithme qui résout une équation dupremierdegré ax+b=0.Exercice4:Ecrire un algorithme quidonnela valeur absolue d'un entier.Exercice5:Écrire un algorithme qui convertitun nombre de secondesen heures: minutes: secondes.Exercice6:Écrireun algorithme qui résout une équation du second degré ax2+ bx +c=0.Exercice7:Ecrire un algorithme quidéterminesi la valeur d'un entier est paire ou impaire.Exercice8:Ecrire un algorithme quidonne tousles diviseursd'un entier positif.Exercice9:Ecrire un algorithmequi calcule lefactorield'un entier positif.Exercice10:Ecrire un algorithme qui calculea puissance b avec a réel et b entier par multiplicationsuccessives.Exercice11:Ecrire un algorithmequivérifie si ce nombre est premier ou non.

Exercice12:Ecrire un algorithmequi calcule lePGCDdedeux entiers positifs.Exercice13:Ecrire un algorithme quidétermine si un entier positif estparfait.Un nombre parfait est un nombre présentant la particularité d'être égal à la somme detous sesdiviseurs, excepté lui-même.Exercice14:Ecrire un algorithme quidonne le nombre d'occurrences d'un caractère donné dans une chainelue caractère par caractère et qui se termine par un point.Exercice15:Ecrire un algorithme qui affiche tous les nombres parfaits inférieurs à 1000.Exercice16:Ecrire un algorithme qui affiche tous les nombres parfaits inférieurs à 1000.Exercice17:Ecrire un algorithme qui calcule les 10 premiers termes de la suite deFibonacci.La suite deFibonacci est définie par :F0 = 1F1= 1Fn=Fn-2+Fn-1 pour n>1

quotesdbs_dbs17.pdfusesText_23

[PDF] algorithme et structure de données exercices corrigés pdf

[PDF] algorithme et structure de données pdf

[PDF] algorithme et structure de données pointeur

[PDF] algorithme exercice

[PDF] algorithme plus court chemin

[PDF] algorithme problème du plus court chemin

[PDF] algorithme programmation c

[PDF] algorithme programmation calculatrice

[PDF] algorithme programmation cours pdf gratuit

[PDF] algorithme programmation pascal exercices pdf

[PDF] algorithme programmation python

[PDF] algorithme tri à bulle java

[PDF] algorithme tri à bulle langage c

[PDF] algorithme tri a bulle python

[PDF] algorithme tri par selection python