Algorithmique Partie 1 - Cril.univ-artois.fr

ProgrammationRésolutionConstruire un AlgorithmeMaîtriser l’algorithmique requiert deux qualités :L’intuition : savoir décomposer le problème en une série d’instructions.La rigueur : vérifier que la série d’instructions aboutit bien au résultat attendu.Les deux qualités s’acquièrent par l’expérience !Ecriture AlgorithmiqueUn algorithme est un manuel utilisateur pour résoudre un problème. Il ne dépend pasdu langage de programmation dans lequel il sera codéde la machine qui exécutera le programme correspondantLe langage algorithmique (ou pseudo-code) utilise des instructions faciles à comprendre etcalculer.

ProgrammationRésolutionAnalyser un AlgorithmeCorrection : peut-on garantir que pour chaque instance du problème, l’algorithmeretourne le résultat attendu ?Complexité : de combien de temps et d’espace (mémoire) l’algorithme a-t-il besoin pourrésoudre le problème ?NoteDès ce semestre, nous étudierons la correction d’algorithmes simplesLa complexité algorithmique sera étudiée au second semestre

ProgrammationRésolutionAnalyser un AlgorithmeCorrection : peut-on garantir que pour chaque instance du problème, l’algorithmeretourne le résultat attendu ?Complexité : de combien de temps et d’espace (mémoire) l’algorithme a-t-il besoin pourrésoudre le problème ?NoteDès ce semestre, nous étudierons la correction d’algorithmes simplesLa complexité algorithmique sera étudiée au second semestre

ProgrammationCodageCodageProgrammeUn programme est la traduction d’un algorithme dans un langage qui peut être utilisé (compiléou interprété) par la machine.#include iostream using namespace std;float x;float y;main(){cin À x;y x * x;cout ¿ y;}Code C de l’algorithme élèveAuCarré

ProgrammationCodageCodageProgrammeUn programme est la traduction d’un algorithme dans un langage qui peut être utilisé (compiléou interprété) par la machine.#include iostream using namespace std;float x;float y;main(){cin À x;y x * x;cout ¿ y;}Code C de l’algorithme élèveAuCarréLe programme utilise les fonctionsentrées-sorties

ProgrammationCodageCodageProgrammeUn programme est la traduction d’un algorithme dans un langage qui peut être utilisé (compiléou interprété) par la machine.#include iostream using namespace std;float x;float y;main(){cin À x;y x * x;cout ¿ y;}Code C de l’algorithme élèveAuCarréLe programme utilise l’espace denoms de la bliothèque C standard

ProgrammationCodageCodageProgrammeUn programme est la traduction d’un algorithme dans un langage qui peut être utilisé (compiléou interprété) par la machine.#include iostream using namespace std;float x;float y;main(){cin À x;y x * x;cout ¿ y;}Code C de l’algorithme élèveAuCarréLe programme déclare les variables xet y de type réel

ProgrammationCodageCodageProgrammeUn programme est la traduction d’un algorithme dans un langage qui peut être utilisé (compiléou interprété) par la machine.#include iostream using namespace std;float x;float y;main(){cin À x;y x * x;cout ¿ y;}Code C de l’algorithme élèveAuCarréFonction principale du programme ; lecorps de la fonction est défini entreles accolades

ProgrammationCodageCodageProgrammeUn programme est la traduction d’un algorithme dans un langage qui peut être utilisé (compiléou interprété) par la machine.#include iostream using namespace std;float x;float y;main(){cin À x;y x * x;cout ¿ y;}Code C de l’algorithme élèveAuCarréLa valeur de x est reçue depuis l’entrée standard (le clavier)

ProgrammationCodageCodageProgrammeUn programme est la traduction d’un algorithme dans un langage qui peut être utilisé (compiléou interprété) par la machine.#include iostream using namespace std;float x;float y;main(){cin À x;y x * x;cout ¿ y;}Code C de l’algorithme élèveAuCarréLa valeur de y prend le carré de lavaleur de x

ProgrammationCodageCodageProgrammeUn programme est la traduction d’un algorithme dans un langage qui peut être utilisé (compiléou interprété) par la machine.#include iostream using namespace std;float x;float y;main(){cin À x;y x * x;cout ¿ y;}Code C de l’algorithme élèveAuCarréLa valeur de y est envoyée à la sortiestandard (l’écran)

DonnéesSommaire1 Modalités2 Programmation3 Données4 Opérateurs5 Instructions

DonnéesDonnéesEn informatique, une donnée est la représentation d’un objet abstrait ou concret dumonde. Dans une machine chaque donnéeest codée et stockée dans une mémoire.Toute donnée est spécifiée par :son nom : il désigne la donnée dans l’algorithme, et doit donc être le plus significatifpossible.son type : il décrit le domaine de valeurs que peut prendre la donnée.sa nature : variable (peut changer de valeur) ou constante (ne peut pas changer devaleur).

DonnéesDonnéesEn informatique, une donnée est la représentation d’un objet abstrait ou concret dumonde. Dans une machine chaque donnéeest codée et stockée dans une mémoire.Toute donnée est spécifiée par :son nom : il désigne la donnée dans l’algorithme, et doit donc être le plus significatifpossible.son type : il décrit le domaine de valeurs que peut prendre la donnée.sa nature : variable (peut changer de valeur) ou constante (ne peut pas changer devaleur).

DonnéesDonnéesEn informatique, une donnée est la représentation d’un objet abstrait ou concret dumonde. Dans une machine chaque donnéeest codée et stockée dans une mémoire.Toute donnée est spécifiée par :son nom : il désigne la donnée dans l’algorithme, et doit donc être le plus significatifpossible.son type : il décrit le domaine de valeurs que peut prendre la donnée.sa nature : variable (peut changer de valeur) ou constante (ne peut pas changer devaleur).

DonnéesType simpleUne donnée de type simple ne contient qu’une seule e de valeurs{vrai,faux}table ASCIIZRReprésentation (finie) en C boolcharintfloat

DonnéesType simpleUne donnée de type simple ne contient qu’une seule e de valeurs{vrai,faux}table ASCIIZRReprésentation (finie) en C boolcharintfloatCodage des types simplesEn programmation (C ) la valeur d’un type simple est codée sur un certain nombre de bits etstockée en mémoire. Pour une machine avec adressage 32 bits, le codage est :Type C boolcharintfloatCodage8 bits8 bits32 bits32 bitsDomaine de valeurs{0, 1}{0, 255}{ 2, 147, 483, 648}{ 3.410 38 } (7 décimales)

DonnéesType simpleUne donnée de type simple ne contient qu’une seule e de valeurs{vrai,faux}table ASCIIZRTable ASCIILa table des codes ASCII (AmericanStandard Code for Information Interchange) utilise un codage 7 bits pournormaliser les caractères (lettres,chiffres, ponctuation) du clavier. Latable étendue (8 bits) permet de coder les caractères accentués, mais ilexiste différentes normes !Représentation (finie) en C boolcharintfloat

DonnéesType structuréUne donnée structurée contient une collection d’informations de type simple.Typetableau (statique)chaîne (dynamique)Exemple de représentation en C int t[10];string c;Un exemple de traitement de chaînesAlgorithme : afficheChaînevariablechaîne nomdébutafficher "Entrez votre nom : "lire nomafficher "Votre nom est : " nomfin#include iostream #include string using namespace std;string nom;main(){cout ¿ "Entrez votre nom: ";cin À nom;cout ¿ "Votre nom est: " ¿ nom ¿ endl;}Code C de afficheChaîne

DonnéesType structuréUne donnée structurée contient une collection d’informations de type simple.Typetableau (statique)chaîne (dynamique)Exemple de représentation en C int t[10];string c;Un exemple de traitement de chaînesAlgorithme : afficheChaînevariablechaîne nomdébutafficher "Entrez votre nom : "lire nomafficher "Votre nom est : " nomfin#include iostream #include string using namespace std;string nom;main(){cout ¿ "Entrez votre nom: ";cin À nom;cout ¿ "Votre nom est: " ¿ nom ¿ endl;}Code C de afficheChaîne

OpérateursSommaire1 Modalités2 Programmation3 Données4 Opérateurs5 Instructions

OpérateursOpérateursUn opérateur est une fonction qui prend en entrée une liste de valeurs et retourne en sortieune valeur. La position d’un opérateur par rapport à ses opérandes peut être :préfixe : par exemple, l’inversion de signe -x.infixe : par exemple, l’addition x y.postfixe : par exemple, l’incrémentation x .

OpérateursOpérateursUn opérateur est une fonction qui prend en entrée une liste de valeurs et retourne en sortieune valeur. La position d’un opérateur par rapport à ses opérandes peut être :préfixe : par exemple, l’inversion de signe -x.infixe : par exemple, l’addition x y.postfixe : par exemple, l’incrémentation x .

OpérateursOpérateurs arithmétiques sur les entiersLes entrées et la sortie sont des on entièreResteInversion de signePseudo-code /mod C /% Exempleiii55 */% ijjj22Opérateurs arithmétiques sur les réelsAu moins une des entrées est un réel et la sortie est un réelNomAdditionSoustractionMultiplicationDivision réelleInversion de signePseudo-code / C Exemple */-x x x *5.0-xyyy/ 2

OpérateursOpérateurs arithmétiques sur les entiersLes entrées et la sortie sont des on entièreResteInversion de signePseudo-code /mod C /% Exempleiii55 */% ijjj22Opérateurs arithmétiques sur les réelsAu moins une des entrées est un réel et la sortie est un réelNomAdditionSoustractionMultiplicationDivision réelleInversion de signePseudo-code / C Exemple */-x x x *5.0-xyyy/ 2

OpérateursOpérateurs de comparaisonLes entrées sont des caractères ou nombres et la sortie est un booléenNomEst égal àPlus petit quePlus grand quePlus petit ou égal àPlus grand ou égal àPseudo-code C Exemple iiiiiOpérateurs logiquesLes entrées et la sortie sont des booléensNomEtOuNonPseudo-codeetounonC Exemple&& !a && ba b! a j j j j j

OpérateursOpérateurs de comparaisonLes entrées sont des caractères ou nombres et la sortie est un booléenNomEst égal àPlus petit quePlus grand quePlus petit ou égal àPlus grand ou égal àPseudo-code C Exemple iiiiiOpérateurs logiquesLes entrées et la sortie sont des booléensNomEtOuNonPseudo-codeetounonC Exemple&& !a && ba b! a j j j j j

InstructionsSommaire1 Modalités2 Programmation3 Données4 Opérateurs5 Instructions

InstructionsInstructionsUne instruction est une action que doit accomplir l’algorithme. Il existe cinq catégoriesd’instructions :La déclarationL’affectationLa lecture/écritureLes testsLes boucles

InstructionsDéclarationToute donnée utilisée par un algorithme doit être déclarée, afin que la machine puisse luiréserver un espace mémoire.Déclaration d’une variable réelle :Pseudo-codevariable réel xDéclaration d’une constante réelle :Pseudo-codeconstante réel pi 3.14C float x;C const float pi 3.14;NoteEn pseudo-code les variables (constantes) sont regroupées sous un bloc variablesEn C les variables de même type peuvent être déclarées ensembles. Par exemple,float x,y,z;

InstructionsDéclarationToute donnée utilisée par un algorithme doit être déclarée, afin que la machine puisse luiréserver un espace mémoire.Déclaration d’une variable réelle :Pseudo-codevariable réel xDéclaration d’une constante réelle :Pseudo-codeconstante réel pi 3.14C float x;C const float pi 3.14;NoteEn pseudo-code les variables (constantes) sont regroupées sous un bloc variablesEn C les variables de même type peuvent être déclarées ensembles. Par exemple,float x,y,z;

InstructionsDéclarationToute donnée utilisée par un algorithme doit être déclarée, afin que la machine puisse luiréserver un espace mémoire.Déclaration d’une variable réelle :Pseudo-codevariable réel xDéclaration d’une constante réelle :Pseudo-codeconstante réel pi 3.14C float x;C const float pi 3.14;NoteEn pseudo-code les variables (constantes) sont regroupées sous un bloc variablesEn C les variables de même type peuvent être déclarées ensembles. Par exemple,float x,y,z;

InstructionsDéclarationToute donnée utilisée par un algorithme doit être déclarée, afin que la machine puisse luiréserver un espace mémoire.Déclaration d’une variable réelle :Pseudo-codevariable réel xDéclaration d’une constante réelle :Pseudo-codeconstante réel pi 3.14C float x;C const float pi 3.14;NoteEn pseudo-code les variables (constantes) sont regroupées sous un bloc variablesEn C les variables de même type peuvent être déclarées ensembles. Par exemple,float x,y,z;

InstructionsAffectationL’instruction d’affectation permet de changer la valeur d’une variable en appliquant unopérateur d’affectationL’affectation standardPseudo-codey xL’incrémentation et la décrémentationPseudo-codex x 1x x 1C y x;C x ;x--;NoteEn C il existe de nombreux autres opérateurs d’affectation permettant d’appliquer uneopération arithmétique (ou logique) sur l’entrée et d’affecter le résultat sur l’entrée.Par exemple, l’instruction x x 2 peut être traduite en C par x 2;Pour des raisons de lisibilité, il est conseillé d’utiliser ces opérateurs avec parcimonie !

InstructionsAffectationL’instruction d’affectation permet de changer la valeur d’une variable en appliquant unopérateur d’affectationL’affectation standardPseudo-codey xL’incrémentation et la décrémentationPseudo-codex x 1x x 1C y x;C x ;x--;NoteEn C il existe de nombreux autres opérateurs d’affectation permettant d’appliquer uneopération arithmétique (ou logique) sur l’entrée et d’affecter le résultat sur l’entrée.Par exemple, l’instruction x x 2 peut être traduite en C par x 2;Pour des raisons de lisibilité, il est conseillé d’utiliser ces opérateurs avec parcimonie !

InstructionsAffectationL’instruction d’affectation permet de changer la valeur d’une variable en appliquant unopérateur d’affectationL’affectation standardPseudo-codey xL’incrémentation et la décrémentationPseudo-codex x 1x x 1C y x;C x ;x--;NoteEn C il existe de nombreux autres opérateurs d’affectation permettant d’appliquer uneopération arithmétique (ou logique) sur l’entrée et d’affecter le résultat sur l’entrée.Par exemple, l’instruction x x 2 peut être traduite en C par x 2;Pour des raisons de lisibilité, il est conseillé d’utiliser ces opérateurs avec parcimonie !

InstructionsLecture/écritureDans un premier temps, la lecture et l’écriture vont se limiter à la communication parl’intermédiaire du clavier et de l’écran.La lecture standard (clavier)Pseudo-codelire xC cin À x;L’affichage standard (écran)Pseudo-codeafficher x yC cout ¿ x ¿ y;NoteDans la suite, nous verrons que la lecture (écriture) de fichiers est similaire à la lecture(écriture) standard.

InstructionsLecture/écritureDans un premier temps, la lecture et l’écriture vont se limiter à la communication parl’intermédiaire du clavier et de l’écran.La lecture standard (clavier)Pseudo-codelire xC cin À x;L’affichage standard (écran)Pseudo-codeafficher x yC cout ¿ x ¿ y;NoteDans la suite, nous verrons que la lecture (écriture) de fichiers est similaire à la lecture(écriture) standard.

InstructionsLecture/écritureDans un premier temps, la lecture et l’écriture vont se limiter à la communication parl’intermédiaire du clavier et de l’écran.La lecture standard (clavier)Pseudo-codelire xC cin À x;L’affichage standard (écran)Pseudo-codeafficher x yC cout ¿ x ¿ y;NoteDans la suite, nous verrons que la lecture (écriture) de fichiers est similaire à la lecture(écriture) standard.

Modalités du cours Algorithmique: matière fondamentale de l'informatique, nécessaire pour aborder la plupart des autres matières 1,5h de cours, 3h de TD et 1,5h de TP par semaine Il faut travailler les cours, TD et TP, et surtout bien les comprendre. Donc n'hésitez pas à poser des questions à vos enseignants! Modalités Modalités du cours Algorithmique: matière fondamentale de l .