Cours n◦1- Algorithmes de base

julien.brajard@upmc.fr, maria.potop-butucaru@lip6.fr

Polytech’Sorbonne

2018-2019

(Polytech’Sorbonne) cours n◦1 2018-2019 1 / 23

1 Les algorithmesIntroductionConstruction d’un algorithmeStructures de base d’un algorithmeTester un algorithmeExemples

(Polytech’Sorbonne) cours n◦1 2018-2019 2 / 23

Pourquoi faire appel à des algorithmes ?

Pour automatiser des tâchesExemples :

Métier à tisserMéthode de calcul à la main d’une divisionRecette de cuisine...

(Polytech’Sorbonne) cours n◦1 2018-2019 3 / 23

Qu’est-ce qu’un algorithme ?

DéfinitionUn algorithme est un ensemble ordonné d’instructions simples permettantde résoudre un problème.

(Polytech’Sorbonne) cours n◦1 2018-2019 4 / 23

Remarques

Un algorithme nécessite :Des objets sur lesquels travailler,Un langage non ambigu,Des spécifications (description de l’algorithme).

Il n’existe généralement pas un unique algorithme pour traiter un problème.

(Polytech’Sorbonne) cours n◦1 2018-2019 5 / 23

Historique

3ème siècle avant JC Livre VII des Eléments d’Euclide

Détermination du plus grand diviseur communentre deux nombres : PGCD(12,8)=4

8ème siècle après JC Al-Khawarizmi : Méthodes de résolutiond’équations. Son nom est à l’origine du mot "algorithme".

(Polytech’Sorbonne) cours n◦1 2018-2019 6 / 23

1 Les algorithmesIntroductionConstruction d’unalgorithmeStructures de base d’unalgorithmeTester un algorithmeExemples

(Polytech’Sorbonne) cours n◦1 2018-2019 7 / 23

Construction d’un algorithme

Pour chaque problème, il vous est demandé de définir clairement :Les éventuelles données d’entrée du problème en précisant leurs typeset leur rôle,les éventuelles données de sortie du problème en précisant leurs types,les différentes instructions permettant d’obtenir les données de sortiesà partir des données d’entrée.

(Polytech’Sorbonne) cours n◦1 2018-2019 8 / 23

Exemple

Algorithme qui détermine le prix d’entrée dans un musée (les mineurspayent moitié prix)

DonnéesDonnées d’entrée : age (entier)

{age du client}Données de sortie : tarif (décimal)

{prix de l’entrée}

InstructionsSi age < 18 Alorstarif ← 4

Sinontarif ← 8

Fin SiRenvoyer tarif

(Polytech’Sorbonne) cours n◦1 2018-2019 9 / 23

Exemple

Algorithme qui détermine le prix d’entrée dans un musée (les mineurspayent moitié prix)

DonnéesDonnées d’entrée : age (entier)

{age du client}Données de sortie : tarif (décimal)

{prix de l’entrée}

InstructionsSi age < 18 Alorstarif ← 4

Sinontarif ← 8

Fin SiRenvoyer tarif

(Polytech’Sorbonne) cours n◦1 2018-2019 9 / 23

Exemple

Algorithme qui détermine le prix d’entrée dans un musée (les mineurspayent moitié prix)

DonnéesDonnées d’entrée : age (entier)

{age du client}Données de sortie : tarif (décimal)

{prix de l’entrée}

InstructionsSi age < 18 Alors

tarif ← 4Sinon

tarif ← 8Fin SiRenvoyer tarif

(Polytech’Sorbonne) cours n◦1 2018-2019 9 / 23

1 Les algorithmesIntroductionConstruction d’unalgorithmeStructures de base d’unalgorithmeTester un algorithmeExemples

(Polytech’Sorbonne) cours n◦1 2018-2019 10 / 23

Instructions élémentaires

Opérations arithmétiques de base (+, −, ×, /, mod, ...)Affectation de valeurs (ex : x ← 2)Afficher, lireStructures conditionnellesStructures répétitives

(Polytech’Sorbonne) cours n◦1 2018-2019 11 / 23

Structures conditionnelles 1/2

condition

Action F Action V

vraiefausse

Si condition AlorsAction V

SinonAction F

Fin Si

Un exempleSi age < 18 Alors

tarif ← 4Sinon

tarif ← 8Fin Si

(Polytech’Sorbonne) cours n◦1 2018-2019 12 / 23

Structures conditionnelles 2/2

condition

Action V

vraie

fausse

Si condition AlorsAction V

Fin Si

Un exempleSi age < 18 AlorsAfficher "Réduction de50%"

Fin Si

(Polytech’Sorbonne) cours n◦1 2018-2019 13 / 23

Structures à choix multiple

Selon le cas

Cas 1

Cas 2

Cas n

défaut

Action 1

Action 2

Action n

Actionpar défaut

Selon le casCas 1 : Action 1Cas 2 : Action 2...Cas n : Action nDéfaut : Action par défaut

Fin Selon

Un exempleSelon valeur de age

0..6 : tarif ← 07..18 : tarif ← 4Défaut : tarif ← 8

Fin Selon

(Polytech’Sorbonne) cours n◦1 2018-2019 14 / 23

Structures répétitives 1/2

Répéter tant quecondition

Actions

vraie

fausse

Tant que condition FaireActions

Fin Tant que

Les actions peuvent ne pasêtre exécutées si la conditionest fausse au départ.

Un exempleTant que tickets>0 Faire

vendre un ticketFin Tant que

(Polytech’Sorbonne) cours n◦1 2018-2019 15 / 23

Structures répétitives 2/2

Actions

Répéter tant quecondition

vraie

fausse

RépéterActions

Tant que condition

Les actions sont exécutées aumoins une fois.

Un exempleRépéter

vendre un ticketTant que ticket>0

(Polytech’Sorbonne) cours n◦1 2018-2019 16 / 23

Structures itératives

Répéter n fois

Actions

compteur>n

Pour i = 1 à n FaireActions

Fin Pour

On connaît le nombre d’itérations àl’avance.

Un exemplePour i = 1 à nbre_guide FaireSi place pour guide i>0 AlorsAfficher "Il reste des placespour le guide i"

Fin SiFin Pour

(Polytech’Sorbonne) cours n◦1 2018-2019 17 / 23

1 Les algorithmesIntroductionConstruction d’unalgorithmeStructures de base d’unalgorithmeTester un algorithmeExemples

(Polytech’Sorbonne) cours n◦1 2018-2019 18 / 23

Jeu d’essais

Faire fonctionner l’algorithme avec des valeurs.Traiter tous les cas possibles.En particulier les cas pouvant nécessaiter à traitement spécifique.

(Polytech’Sorbonne) cours n◦1 2018-2019 19 / 23

Un exemple :Calcul de la valeur absolue d’un nombre

DonnéesDonnées d’entrée : X (entier)

{nombre dont on veut calculer la valeur absolue}Données de sortie : Val_abs (entier)

{valeur absolue de X}

InstructionsSi X ≥ 0 Alors

Val_abs ← XSinon

Val_abs ← -XFin SiRenvoyer Val_abs

Jeu d’essaisX ← un entier négatifX ← un entier positifX ← 0

(Polytech’Sorbonne) cours n◦1 2018-2019 20 / 23

Un exemple :Calcul de la valeur absolue d’un nombre

DonnéesDonnées d’entrée : X (entier)

{nombre dont on veut calculer la valeur absolue}Données de sortie : Val_abs (entier)

{valeur absolue de X}

InstructionsSi X ≥ 0 Alors

Val_abs ← XSinon

Val_abs ← -XFin SiRenvoyer Val_abs

Jeu d’essaisX ← un entier négatifX ← un entier positifX ← 0

(Polytech’Sorbonne) cours n◦1 2018-2019 20 / 23

1 Les algorithmesIntroductionConstruction d’unalgorithmeStructures de base d’unalgorithmeTester un algorithmeExemples

(Polytech’Sorbonne) cours n◦1 2018-2019 21 / 23

Exemple 1

Un colis est conforme si ses trois dimensions (L× l × h avec h ≤ l ≤ L)vérifient les conditions suivantes :

Un rectangle de 10cm × 7cm doit pouvoir s’inscrire dans une face ducolis,L+ l + h ≤ 100 cm,L ≤ 60cm.

ExerciceEcrire l’algorithme permettant de savoir si un colis est conforme ou non.

(Polytech’Sorbonne) cours n◦1 2018-2019 22 / 23

Exemple 2Que fait cet algo ?

Données d’entrée :X, tableau à 2 dimension de n×n réels,v, vecteur de n réels

Données de sortie : s, vecteur de n réelsPour i variant de 1 à n Faire

s(i) ← 0Pour j variant de 1 à n Faire

s(i) ← s(i) + X(i,j).v(j)Fin Pour

Fin PourRenvoyer s

(Polytech’Sorbonne) cours n◦1 2018-2019 23 / 23