ALGORITHMIQUE

INTRODUCTION AUX INSTRUCTIONS DE BASE MANIPULÉES DANS LES ALGORITHMES

ET À LA REPRÉSENTATION DE CES DERNIERS

COURS D’IDO 2È ANNÉE – LYCÉE-COLLÈGE DE ST-MAURICE

PROF. E. PFYFFER
AGENDA

• DÉFINITIONS ET ORIGINES DES ALGORITHMES

• LES LOGIGRAMMES
• LES INSTRUCTIONS DE BASE DE
L'ALGORITHMIQUE
• QUELQUES EXEMPLES
Les algorithmes

JOUONS…
• LE JEU DU ROBOT (INSTRUCTIONS À DISPOSITION : H – B – G – D )
DEPART ARRIVEE

• RÉPONSE : D D B B G G B B B D D H D D H H H H
• RÉPONSE 2 :
DGDGDDGDGDGDDGDGDBHBHBBHBHBBHBHBGGDGDGDGDGD
BHBHBBHBHBBHBHBDGDGDDGDGDGDHBHBHDDGDGGDGDGDG
HHHBHBHBHBHBHBHBHBHBHBHBHBHH
Les algorithmes

JOUONS ENCORE…
• LE JEU DU ROBOT (INSTRUCTIONS À DISPOSITION : H – B – G – D )
DEPART ARRIVEE

• RÉPONSE 1 : D D D D
• RÉPONSE 2 : D D B B B G G B B B D D H D D H H H H
 Les algorithmes

QU’EST-CE QU’UN ALGORITHME ?

• UN ALGORITHME EST UNS SUITE D’INSTRUCTIONS QUI, UNE FOIS EXÉCUTÉE
CORRECTEMENT ET SELON UN ORDRE PRÉCIS CONDUIT À UN RÉSULTAT DONNÉ
• UN ALGORITHME DOIT CONTENIR UNIQUEMENT DES INSTRUCTIONS COMPRÉHENSIBLES PAR
CELUI QUI DEVRA L’EXÉCUTER (EN INFORMATIQUE : L’ORDINATEUR ! )  SEULEMENT 3
«BRIQUES» : INSTRUCTION, TEST, BOUCLE…
• INSTRUCTIONS DONNÉES INDÉPENDAMMENT DES PARTICULARITÉS DE TEL OU TEL LANGAGE
(ABSTRACTION)

• APPRENDRE L’ALGORITHMIQUE, C’EST APPRENDRE À MANIER LA STRUCTURE

LOGIQUE D’UN PROGRAMME INFORMATIQUE SANS TENIR COMPTE DES PROBLÈMES
SYNTAXIQUES DU LANGAGE

• APPRENDRE L’ALGORITHMIQUE DE MANIÈRE SÉPARÉE, C’EST DONC SÉRIER LES

DIFFICULTÉS POUR MIEUX LES VAINCRE.
Les algorithmes

LES ORIGINES DE L'ALGORITHMIQUE

• L'ORIGINE DE CE QUI DÉFINIT UN ALGORITHME (SUITES D'INSTRUCTIONS
PRÉCISES ET ORDONNÉES PERMETTANT DE RÉSOUDRE UN PROBLÈME OU
D'OBTENIR UN RÉSULTAT PRÉCIS) REMONTE À L'ANTIQUITÉ ! VOICI LES TRACES
LES PLUS ANCIENNES D'ALGORITHMES QUE L'ON RETROUVE :
• LES PLUS ANCIENS SONT DES ALGORITHMES SERVANT À ÉLABORER LE CALCUL DE
L'IMPÔT SOUS LA 2È DYNASTIE DE L'EGYPTE ANCIENNE (-2700)
• LES ALGORITHMES DES MATHÉMATICIENS GRECS (ENV -300) SONT ÉGALMENT TRÈS
CONNUS : EUCLIDE (-300) QUI PERMET DE DÉTERMINER LE PLUS GRAND DIVISEUR
COMMUN SANS FACTORISER, …
• AL KHWARZIMI (780) EST UN MATHÉMATICIEN PERSE (OUZBEKISTAN ACTUEL) QUI A
DONNÉ SON NOM À CETTE SUITE D'INSTRUCTIONS : L'ALGORITHMIQUE
NOUS PARLONS AUJOURD'HUI SPÉCIFIQUEMENT D'ALGORITHMES NUMÉRIQUES
DESTINÉS À ÊTRE EXÉCUTÉS PAR DES ORDINATEURS (PLUS OU MOINS
PUISSANTS…)
Les algorithmes

COMMENT EXPRIMER LES ALGORITHMES

• MOTS ET PHRASES
• INDICATIONS ÉCRITES
• RECETTES DE CUISINE
• MODES D’EMPLOI
• MARCHES À SUIVRE
• ITINÉRAIRE
• INDICATIONS ORALES
• ITINÉRAIRE
• …

• SCHÉMAS
• LOGIGRAMMES
• «NOTICE IKEA»

• LANGAGES SPÉCIFIQUES
• PSEUDO CODE
DANS CE COURS…

NOUS ALLONS APPRENDRE À EXPRIMER LA SÉRIE

D’INSTRUCTIONS QUI, SI ELLES SONT EXÉCUTÉES
CORRECTEMENT ET DANS LE BON ORDRE,
PERMETTENT À UN ORDINATEUR DE RÉSOUDRE DE
PETITS PROBLÈMES…
Les logigrammes

LES LOGIGRAMMES

• AUSSI APPELÉ ALGOGIGRAMME OU ORGANIGRAMME EN FRANÇAIS, ET

FLOWCHART EN ANGLAIS
• PERMET, PAR UNE FORMALISATION SIMPLE, DE REPRÉSENTER
GRAPHIQUEMENT ET CLAIREMENT L’ALGORITHME DÉVELOPPÉ
• NORME ISO 5807  UNIVERSELLEMENT CONNU ET COMPRIS, RÉUTILISABLE…
• LUDICHART (ONLINE)
Les logigrammes

LOGIGRAMMES : UN PREMIER
EXEMPLE
VOUS DEVRIEZ COMPRENDRE ÇA :

A=0
B=0
A = INT(INPUT("ENTREZ LA VALEUR DE A : "))
B = INT(INPUT("ENTREZ LA VALEUR DE B : "))
IF A < B:
PRINT("CROISSANT")
ELSE:
PRINT("DÉCROISSANT")
 Les logigrammes

Début

• LES TERMINATEURS
• DÉBUT DU PROGRAMME
• Tests
• FIN DU PROGRAMME
NON
Test
Fin

• INSTRUCTION
OUI
• CACULS ET TRANSFORMATIONS
• AFFECTATIONS • Entrées / Sorties
Instruction Entrées (utilisateur  ordinateur)
Sorties (ordinateur  utilisateur)
UNE INSTRUCTION EN ALGORITHME DOIT ÊTRE
ÉLÉMENTAIRE ET NON AMBIGUË : AFFECTATION, CALCUL, Afficher
Lire (Entrée)
OU APPEL À UNE PRIMITIVE CONNUE (AFFICHER, (Sortie)
AVANCER, LIRE…). SI UNE INSTRUCTION EST TROP
COMPLEXE (‘DESSINER UN CARRÉ’), ON DOIT LA
DÉCOMPOSER EN INSTRUCTIONS ÉLÉMENTAIRES.
 Les logigrammes

STRUCTURE D'UN ALGORITHME :

UN DÉBUT
Début
UNE DÉCLARATION DES VARIABLES
X0
Nom  ""
UNE OU PLUSIEURS ENTRÉES
Lire
(Entrée) DES TRAITEMENTS (INSTRUCTIONS, CALCULS, COMPARAISONS,

X  3*Y
Tes NON
TESTS, BOUCLES).
t
OUI

UNE OU DES SORTIES (AFFICHER, AVANCER, TOURNER,

Afficher
(Sortie) S’ARRÊTER…)

Fin UNE FIN

Les logigrammes

UN PREMIER EXEMPLE
• MODÉLISEZ LE PROGRAMME QUI PERMET DE CALCULER ET
D'AFFICHER À L'ÉCRAN LA SOMME DE DEUX NOMBRES,
PUIS QUI DEMANDE À L’UTILISATEUR S’IL VEUT
RECOMMENCER OU S’ARRÊTER.
• INFOS :
• N1, N2 ET TOTAL SONT TROIS VARIABLES
• L’UTILISATEUR VA ENTRER N1, PUIS N2
• L’ORDINATEUR PEUT ENSUITE CALCULER LE TOTAL
• UNE FOIS LE TOTAL CALCULÉ IL PEUT L’AFFICHER
• ON POSE ENSUITE LA QUESTION DE RECOMMENCER OU NON.
Les logigrammes

UN PREMIER EXERCICE

• MODÉLISEZ LE PROGRAMME QUI DEMANDE À L’UTILISATEUR

D’ENTRER SON ANNÉE DE NAISSANCE ET L’ANNÉE EN COURS,
PUIS QUI CALCULE L’ÂGE ET QUI DIT À L’UTILISATEUR S’IL SERA
MAJEUR OU MINEUR À LA FIN DE L’ANNÉE EN COURS

• PAR GROUPE DE DEUX, COMPAREZ VOS SOLUTIONS ET

DÉBATTEZ DES DIFFÉRENCES. PROPOSEZ ENSUITE UNE
SOLUTION DE GROUPE QUE L’ON TESTERA ENSEMBLE.
Les logigrammes

UN PREMIER EXERCICE
1. Début
2. Initialisation des variables
1. AnnéeNaiss : année de naissance
2. AnnéeCours: année en cours
3. Age : âge de l’utilisateur (à calculer)
3. Lecture de l’année de naissance (AnnéeNaiss)
4. Lecture de l’année en cours (AnnéeCours)
5. Calcul du de l’âge (Age)
6. On teste si l’âge est sup ou égal à 18
(Age >= 18) ?
1. Si oui, on affiche «Majeur»
2. Si non, on affiche «Mineur»…
7. Fin
Instructions de base des algorithmes

LES QUATRE INSTRUCTIONS DE BASE

• LES INSTRUCTIONS DE BASE DES ALGORITHMES SONT :

• LA SÉQUENCE,
• LA VARIABLE,
• LE BRANCHEMENT CONDITIONNEL (TEST),
• LA BOUCLE

• AVEC CES QUATRE INGRÉDIENTS, ON PEUT FABRIQUER TOUS LES

ALGORITHMES POSSIBLES.
ATTENTION ! NE PAS TOUT MÉLANGER…

• POUR DÉCOMPOSER UN PROGRAMME, ON A 4 INSTRUCTIONS DE BASE (

COMMENT RÉSOUDRE LE PROBLÈME, BRIQUES LOGIQUES)
• SÉQUENCE
• VARIABLE
• TEST
• BOUCLE
• POUR LE DESSINER, ON A 4 FORMES À DISPOSITION ( COMMENT LE
REPRÉSENTER)
• OVALE (TERMINATEURS)
• RECTANGLE (INSTRUCTIONS)
• LOSANGE (TESTS)
• PARALLÉLOGRAMME (ENTRÉES / SORTIES)
LA SÉQUENCE
Instructions de base des algorithmes

LA SÉQUENCE
• PLUS QU’UNE INSTRUCTION DE BASE, LA SÉQUENCE EST UNE
NOTION SIMPLE SUR LAQUELLE REPOSENT TOUS LES ALGORITHMES.
• LA FORME LA PLUS SIMPLE D'ENCHAÎNEMENT D'INSTRUCTIONS EST
LA SÉQUENCE, DANS LAQUELLE LES INSTRUCTIONS ÉLÉMENTAIRES
SONT ÉCRITES L'UNE APRÈS L'AUTRE (SÉQUENTIELLEMENT).
• LES INSTRUCTIONS D'UNE SÉQUENCE SONT TOUTES EXÉCUTÉES,
DANS L'ORDRE OU ELLES SONT ÉCRITES, PAR L’ORDINATEUR.
• LA SÉQUENCE SE LIT, EN PRINCIPE, TOUJOURS DE HAUT EN BAS ET
DE GAUCHE À DROITE

• EX : DANS LE JEU DU ROBOT, DANS UNE RECETTE DE CUISINE OU

DANS UN ITINÉRAIRE SI LA SÉQUENCE N’EST PAS RESPECTÉE LE
RÉSULTAT ATTENDU N’ES PAS AU RENDEZ-VOUS…
LA VARIABLE
Instructions de base des algorithmes

LA VARIABLE
• DANS UN PROGRAMME INFORMATIQUE, ON VA AVOIR EN PERMANENCE
BESOIN DE STOCKER PROVISOIREMENT DES VALEURS :
• DONNÉES DU DISQUE DUR
• DONNÉES ENTRÉES PAR L’UTILISATEUR
• RÉSULTATS INTERMÉDIAIRES OBTENUS PAR UN PROGRAMME

• LA VARIABLE EST UNE BOÎTE QUE LE PROGRAMME VA REPÉRER PAR UNE

ÉTIQUETTE. POUR AVOIR ACCÈS AU CONTENU DE LA BOÎTE IL SUFFIT DE
LA DÉSIGNER PAR SON ÉTIQUETTE.

• A DÉCLARER EN DÉBUT D'ALGORITHME, AVEC SON TYPE ! TOUJOURS !

Instructions de base des algorithmes

LA VARIABLE
Les variables sont
déclarées en
• LES DIFFÉRENTS TYPES DE VARIABLES début
(CRÉÉS AU MOMENT DE L’INITIALISATION) : d'algorithme, en
• NOMBRE ENTIER (INTEGER) une seule fois :
X0
• PERMET DE STOCKER ET DE MANIPULER DES NOMBRES ENTIERS

Age  0
Hauteur  0.0
Nom_Parent1  " "
Nom_Parent2  " "
• NOMBRE YÀ VIRGULE
0.0 (REL)
• PERMET DE STOCKER ET DE REPRÉSENTER DES NOMBRES RÉELS (À VIRGULE)

• CHAÎNE DE CARACTÈRES
• Nom DE
PERMET " STOCKER
" DES DONNÉES DE TYPE TEXTE (UN NOM, ETC…) OU DES
CHIFFRES MAIS TRAITÉS COMME DES CARACTÈRES (PAS DE CALCULS POSSIBLES…)
• MAJUSCULE AU DÉBUT DE CHAQUE MOT, ESPACES REMPLACÉS PAR DES _
Instructions de base des algorithmes

QUELQUES NOTIONS DE VOCABULAIRE

• AFFECTATION
• L'AFFECTATION EST L'OPÉRATION CONSISTANT À INSÉRER UNE VALEUR DANS UNE
VARIABLE.
• ELLE EST REPRÉSENTÉE PAR LE SIGNE ←
• EXEMPLE : TOTAL ← 10 PERMET DE FAIRE PASSER LA VALEUR DE TOTAL À 10
• EXEMPLE 2 TOTAL ← TOTAL + 5 PERMET D'AUGMENTER LE TOTAL DE 5
• DANS CERTAINS LANGAGES DE PROGRAMMATION LE SIGNE D'AFFECTATION EST
REPRÉSENTÉ PAR LE SIGNE =
• TEST D’ÉGALITÉ
• LE SIGNE D'ÉGALITÉ == PERMET DE TESTER SI LA PARTIE GAUCHE DU SIGNE À
LA MÊME VALEUR QUE LA PARTIE DROITE. IL RETOURNE VRAI OU FAUX
• EN INFORMATIQUE ET EN ALGORITHMIQUE, ON UTILISE LE "DOUBLE ÉGAL" POUR
TESTER L'ÉGALITÉ DE DEUX EXPRESSIONS ==
• EXEMPLE : TOTAL == 10 RETOURNE "VRAI" SI LA VALEUR DE TOTAL ÉTAIT DE 10
 LE TEST
QU’ON APPELLE AUSSI «BRANCHEMENT CONDITIONNEL»
Instructions de base des algorithmes

LE TEST
• UN TEST (OU BRANCHEMENT CONDITIONNEL) EST UNE
STRUCTURE DANS LAQUELLE UNE INSTRUCTION OU UNE
SÉQUENCE D’INSTRUCTIONS EST EXÉCUTÉE SELON SI UNE
CONDITION EST VRAIE OU FAUSSE. Condition

• UNE CONDITION EST UNE EXPRESSION QUI PEUT PRENDRE

Condition Condition
L’UNE DES DEUX VALEURS "OUI" OU "NON" (PARFOIS vraie / fausse /
APPELÉ "VRAI" OU "FAUX"). OUI NON

• OUI TOUJOURS VERS LE BAS

• NON TOUJOURS SUR LE CÔTÉ Instruction

• PENSEZ À ADAPTER LA QUESTION AU BESOIN…

• UN TEST EST UNE INSTRUCTION QUI DÉTERMINE SI UNE
CONDITION EST VRAIE OU FAUSSE.
Instructions de base des algorithmes

LE TEST
• LA CONDITION EST TOUJOURS UNE COMPARAISON QUI A LA FORME :
VALEURX OPÉRATEUR DE COMPARAISON VALEURY

• LES OPÉRATEURS DE COMPARAISON DISPONIBLES SONT LES SUIVANTS :

• == EST ÉGAL À
• != EST DIFFÉRENT DE
• < EST PLUS PETIT QUE
• <= EST PLUS PETIT OU ÉGAL À
• > EST PLUS GRAND QUE
• >= EST PLUS GRAND OU ÉGAL À
Instructions de base des algorithmes

LE TEST
• IL N'EST PAS POSSIBLE D'UTILISER DEUX OPÉRATEURS DE COMPARAISON !

1 < X < 10  VALIDE EN MATHÉMATIQUES MAIS PAS EN INFORMATIQUE !

• QUELLE SOLUTION POUR TESTER PLUSIEURS CONDITIONS ? COMBINER LES

CONDITIONS !
• ET  RETOURNE VRAI SI LES DEUX TESTS SONT VRAIS (X>1 ET X<10)
• OU  RETOURNE VRAI SI L'UN DES DEUX TEST AU MOINS EST VRAI (DIRE "OU BIEN")
• XOR (OU EXCLUSIF) ET NOT (INVERSION D'UNE CONDITION) : MOINS UTILISÉS

 NB : ON PEUT COMBINER PLUSIEURS TESTS AVEC DES ET ET DES OU…

(X < 10 ET X > 5) OU (X < 100 ET X > 95)  VRAI POUR LES NOMBRES 6, 7,
8, 9, 96, 97, 98 ET 99…
Instructions de base des algorithmes

LE TEST

Et comment gérer plus de

deux cas sont possibles ?

de 0 à 13 ans c'est un enfant

de 13 à 18 c'est un adolescent
de 18 à 67 c'est un actif
dès 67 ans c'est un retraité

 tests imbriqués !
 Instructions de base des algorithmes

LE TEST
Tests combinés – tests imbriqués : comment choisir ?
Tests imbriqués : Tests combinés :
Utilisation : Lorsque les conditions sont
Utilisation : Lorsque les décisions dépendent les unes
indépendantes ou doivent être vérifiées
des autres. Autrement dit, vous devez vérifier une
simultanément.
condition avant d’en tester d’autres.
Quand les utiliser :
Quand les utiliser :
• Les conditions peuvent être vérifiées
• Les conditions sont hiérarchisées ou
ensemble dans une seule phrase logique.
interdépendantes.
• Aucune dépendance entre les conditions,
• La première condition doit être vraie avant d’évaluer
elles peuvent être évaluées en même
la suivante.
temps.
• Vous devez organiser les vérifications de manière
séquentielle, par étapes logiques.
Règles simples pour guider le choix:
• Si la logique impose un ordre dans l'évaluation des conditions → tests imbriqués.
• Si les conditions peuvent être testées en même temps ou sont indépendantes → tests combinés.
• Pour des tests simples et clairs, les conditions combinées sont souvent préférables, car elles rendent le code plus facile à lire.
• Si plusieurs conditions doivent être vraies pour continuer, mais qu'elles dépendent l'une de l'autre, des tests imbriqués sont mieux
 LA BOUCLE
AUSSI APPELÉE «STRUCTURE RÉPÉTITIVE» OU «STRUCTURE
ITÉRATIVE»
Instructions de base des algorithmes

LA BOUCLE

• SEULE STRUCTURE LOGIQUE CARACTÉRISTIQUE DE LA PROGRAMMATION

(ALORS QUE LES VARIABLES ET LES TESTS ONT PU ÊTRE UTILISÉES DANS
D’AUTRES LOGICIELS TELS QUE EXCEL)
• FACILE À COMPRENDRE
• PARFOIS DIFFICILE À MAÎTRISER…
• UNE BOUCLE EST UNE STRUCTURE DANS LAQUELLE UNE INSTRUCTION
OU UNE SÉQUENCE D’INSTRUCTIONS EST RÉPÉTÉE UN CERTAIN
NOMBRE DE FOIS. ELLE ÉVITE PAR EXEMPLE D’ÉCRIRE LA MÊME
INSTRUCTION PLUSIEURS FOIS À LA SUITE DANS UNE SÉQUENCE.
Instructions de base des algorithmes

LA BOUCLE
IL Y A DEUX TYPES DE BOUCLES :

1. LA BOUCLE "TANT QUE…"

LORSQUE L'ON NE SAIT PAS À L'AVANCE COMBIEN DE FOIS JOUER LES
INSTRUCTIONS
EX : CALCUL D'UNE MOYENNE DONT L'UTILISATEUR INDIQUE LA FIN PAR UNE
TOUCHE SPÉCIFIQUE (ENTREZ T POUR TERMINER)

2. LA BOUCLE "POUR… DE… À … FAIRE … « (BOUCLE AVEC COMPTEUR)

LORSQUE L'ON SAIT AU DÉBUT DE LA BOUCLE COMBIEN DE FOIS JOUER LES
INSTRUCTIONS
EX : CALCUL D'UNE MOYENNE DONT ON CONNAÎT LE NOMBRE DE NOTES
Instructions de base des algorithmes

LA BOUCLE
1. « TANT QUE »
• LORSQUE LE NOMBRE DE FOIS QU'ON JOUERA LA BOUCLE
EST INCONNU AU MOMENT DU LANCEMENT DE LA BOUCLE.
 UNE VALEUR DOIT AVOIR ÉTÉ AFFECTÉE À LA VARIABLE
TESTÉE AVANT LE TEST DE DÉBUT DE BOUCLE !
- SOIR PAR L’UTILISATEUR
- SOIT PAR LE PROGRAMMATEUR VIA L'AFFECTATION D'UNE VALEUR
QUELCONQUE QUI PERMET D'ENTRER DANS LA BOUCLE…
 IL FAUT IMPÉRATIVEMENT POUVOIR METTRE À JOUR LA VALEUR
TESTÉE POUR ÉVITER UNE BOUCLE INFINIE !
• EXEMPLES :
• TOUCHE D'ARRÊT D'UN JEU (PRESS "X" TO STOP)
• NOMBRE DE COMPOSANTS D'UN CALCUL INCONNU À L'AVANCE, ON
VALIDE LA FIN PAR UN 0
• …
Instructions de base des algorithmes

LA BOUCLE
1. « TANT QUE » : QUE FAIT CE PROGRAMME ?

1. DÉBUT
2. INITIALISATION DE LA VARIABLE NBRE
3. AFFECTATION D'UNE VALEUR À NBRE
4. SI NBRE EST DIFFÉRENT DE 999 :
1. AFFICHER LE DOUBLE DU NOMBRE
2. AFFECTER UNE VALEUR À NBRE
3. RETOUR À 4.
5. SI NBRE = 999 DIRE BYE
6. FIN
 TANT QUE LE NBRE N'EST PAS ÉGAL À 999, AFFICHER SON DOUBLE…
Instructions de base des algorithmes

LA BOUCLE
2. « POUR…DE… À … FAIRE »
(APPELÉE BOUCLE AVEC COMPTEUR)
• LORSQU’ON CONNAÎT LE NOMBRE D’ITÉRATIONS À RÉALISER
DÈS LE DÉBUT DE LA BOUCLE, ON PEUT UTILISER UN
COMPTEUR POUR EFFECTUER LE BON NOMBRE D'ITÉRATIONS

NB : C’EST UN CAS PARTICULIER DE LA BOUCLE « TANT QUE »

DANS LEQUEL LE PROGRAMMEUR CONNAÎT LE NOMBRE DE FOIS
QU'ELLE SERA JOUÉE.

EN ALGO, NÉCESSITE LA REPRÉSENTATION DE LA MISE À JOUR

DU COMPTEUR POUR SAVOIR COMBIEN D'OCCURRENCES ONT
ÉTÉ JOUÉES.
CETTE ÉTAPE EST AUTOMATIQUE EN LANGAGE DE
PROGRAMMATION.
Instructions de base des algorithmes

LA BOUCLE
2. « POUR…DE… À … FAIRE » : QUE FAIT CE PROGRAMME ?
Compteur
 Compteur+1
1. DÉBUT
2. INITIALISATION DES VARIABLES
3. DEMANDE À L'UTILISATEUR UN NBRE
4. AFFECTATION DE 1 À COMPTEUR
5. SI COMPTEUR != NBRE,
1. AFFICHER COMPTEUR
2. INCRÉMENTER COMPTEUR
3. RETOUR À 5
6. SINON, DIRE "BYE
 POUR COMPTEUR ALLANT DE 1 À (NBRE-1), AFFICHER COMPTEUR,
TERMINER AVEC « BYE »…
Instructions de base des algorithmes

QUELQUES ALGORITHMES
Instructions de base des algorithmes

LE TRI D’UN TABLEAU

• IL EST TRÈS FRÉQUENT DE DEVOIR ORDONNER UNE LISTE DE DONNÉES
CONTENUE DANS UN TABLEAU
• ARTICLES SELON DES DATES DE PUBLICATION
• PRODUITS PAR PRIX
• LISTE DE PERSONNES SELON LEUR NOM…

• PLUSIEURS STRATÉGIES EXISTENT ET PRÉSENTENT DES

APPROCHES DIFFÉRENTES (CHERCHER « ALGORITHMES DE TRI »
SUR INTERNET), RENDANT LA MÉTHODE PLUS OU MOINS
EFFICACE AU NIVEAU DU TEMPS D’EXÉCUTION (COMPLEXITÉ
TEMPORELLE) ET DE LA QUANTITÉ DE MÉMOIRE NÉCESSAIRE
(COMPLEXITÉ SPATIALE). NOUS VERRONS ICI DEUX EXEMPLES :
• LE TRI PAR SÉLECTION
• LE TRI À BULLE
Instructions de base des algorithmes

LE TRI PAR SÉLECTION

• CET ALGORITHME SIMPLE (MAIS INEFFICACE) CONSISTE À PARCOURIR L’ENTRÉE

DU DÉBUT À LA FIN EN RECHERCHANT LE PLUS PETIT ÉLÉMENT, QUI SERA EN
FIN DE BOUCLE ÉCHANGÉ AVEC L’ÉLÉMENT D’INDICE 0, PUIS DE
RECOMMENCER AVEC LE SECOND PLUS PETIT ÉLÉMENT QU’ON ÉCHANGERA
AVEC L’ÉLÉMENT D’INDICE 1 ETC… JUSQU’À CE QUE LE TABLEAU SOIT
ENTIÈREMENT TRIÉ.
• UNE VARIANTE CONSISTE À PROCÉDER DE FAÇON SYMÉTRIQUE, EN PLAÇANT
D'ABORD LE PLUS GRAND ÉLÉMENT À LA FIN, PUIS LE SECOND PLUS GRAND
ÉLÉMENT EN AVANT-DERNIÈRE POSITION, ETC.
 Instructions de base des algorithmes

Par Joestape89, CC BY-SA 3.0, [Link]

LE TRI PAR SÉLECTION

• PRINCIPE :
procédure tri_selection(tableau t, entier n)
• RECHERCHE DU PLUS PETIT ÉLÉMENT DU TABLEAU ET L’ÉCHANGER AVEC
pour i de 0 à n - 2 boucle principale : le point de départ se décale à chaque tour
L’ÉLÉMENT D’INDICE 0 (PREMIÈRE PLACE)
min ← i on considère provisoirement que t(i) est le plus
• RECHERCHER
pour j deLEi SECOND PLUS
- 1 PETIT
+ 1 à npetit ÉLÉMENT DU TABLEAU ET L’ÉCHANGER
élément on examine tous les éléments suivants
AVEC L’ÉLÉMENT D’INDICE
si t[j] 1
< t[min],
alors min ← j
• CONTINUER DE CETTE FAÇON JUSQU’À CE QUE LE TABLEAU SOIT ENTIÈREMENT
j suivant
TRIÉ A cet endroit, on sait maintenant où est le
fin pour
si min ≠ i, plus petit élément. Il ne reste plus qu'à
effectuer la permutation.
alors échanger t[i] et t[min]
i suivantOn a placé correctement l'élément numéro i, on passe à
fin pour présent au suivant
fin procédure
Instructions de base des algorithmes

LE TRI PAR SÉLECTION

• VARIANTE (SIMPLIFICATION)
procédure tri_selection(tableau t, entier n)
• LORSQU'ON CHERCHAIT À POSITIONNER LA CASE NUMÉRO I, ON PARCOURAIT
pour i de 0 à n - 2
TOUT LE TABLEAU À PARTIR DE LA CASE I+1, ET CE N'EST QU'APRÈS AVOIR
pour j de i + 1 à n - 1
LOCALISÉ LA VALEUR LA PLUS PETITE QU'ON PROCÉDAIT À L'ÉCHANGE.
si t[j] < t[i],
• ON POURRAIT TOUT AUSSI BIEN EFFECTUER
alors échangerCET ÉCHANGE
t[i] et t[j]AU FUR ET À MESURE,
À CHAQUE FOIS QU'ON TROUVE UNE VALEUR PLUS PETITE.
j suivant
fin pour
i suivant
fin pour
fin procédure
Instructions de base des algorithmes

LE TRI PAR SÉLECTION

• LIENS VIDÉO INTÉRESSANTS :

• HTTPS://[Link]/WATCH?V=NS4TPTC8WHW

• HTTPS://[Link]/WATCH?V=G-PGLBMTH_G
Instructions de base des algorithmes

LE TRI A BULLES
• TRI DE TABLEAU + FLAG = TRI À BULLES !
• HYPOTHÈSE DE BASE : UN TABLEAU TRIÉ EN ORDRE CROISSANT, C’EST
UN TABLEAU DANS LEQUEL TOUT ÉLÉMENT EST PLUS PETIT QUE
CELUI QUI LE SUIT.
• CET ALGORITHME CONSISTE À PARCOURIR L’ENTRÉE DU DÉBUT À LA FIN
ET, POUR CHAQUE COUPLE D’ÉLÉMENTS CONSÉCUTIFS, À LES
INTERVERTIR S’ILS SONT MAL ORDONNÉS. CETTE OPÉRATION EST
RÉPÉTÉE JUSQU’À CE QUE LA STRUCTURE SOIT TRIÉE (AUCUNE
INTERVERSION LORS DU DERNIER PASSAGE)
• EN QUOI LE TRI À BULLES IMPLIQUE-T-IL L’UTILISATION D’UN FLAG ? ON NE
SAIT JAMAIS PAR AVANCE COMBIEN DE REMONTÉES DE BULLES ON DOIT
EFFECTUER. TOUT CE QU’ON PEUT DIRE, C’EST QU’ON DEVRA EFFECTUER
LE TRI JUSQU’À CE QU’IL N’Y AIT PLUS D’ÉLÉMENTS QUI SOIENT MAL
CLASSÉS.
Instructions de base des algorithmes

LE TRI A BULLES
• UTILISONS UN FLAG ILYAPERMUTATION, UNE VARIABLE BOOLÉENNE VA NOUS
INDIQUER SI NOUS AVONS OU NON PROCÉDÉ À UNE PERMUTATION AU COURS DU
DERNIER BALAYAGE DU TABLEAU (DANS LE CAS CONTRAIRE, C’EST SIGNE QUE LE
TABLEAU EST TRIÉ, ET DONC QU’ON PEUT ARRÊTER LA MACHINE À BULLES)
• IL FAUT CRÉER UNE BOUCLE À L’INTÉRIEUR DE LAQUELLE ON VA PRENDRE LES
ÉLÉMENTS DU TABLEAU, DU PREMIER JUSQU’À L’AVANT-DERNIER, ET PROCÉDER
À UN ÉCHANGE SI NÉCESSAIRE.
• NE PAS OUBLIER DE GÉRER NOTRE FLAG…
• LUI ATTRIBUER LA VALEUR VRAI DÈS QU’UNE PERMUTATION A ÉTÉ FAITE (IL SUFFIT
QU’IL Y EN AIT EU UNE SEULE POUR QU’ON DOIVE TOUT RECOMMENCER ENCORE UNE
FOIS).
• LA REMETTRE À FAUX À CHAQUE TOUR DE LA BOUCLE PRINCIPALE (QUAND ON
RECOMMENCE UN NOUVEAU TOUR GÉNÉRAL DE BULLES, IL N’Y A PAS ENCORE EU
D’ÉLÉMENTS ÉCHANGÉS),
• NEPAS OUBLIER DE LANCER LA BOUCLE PRINCIPALE, ET POUR CELA DE DONNER LA
VALEUR VRAI AU FLAG AU TOUT DÉPART DE L’ALGORITHME.
Instructions de base des algorithmes

LE TRI A BULLES

Variable Illyapermutation en
Booléen
Début
… Pour lancer la boucle principale
Ilyapermutation ← Vrai
TantQue Ilyapermutation Remise à Faux tant qu’il n’y a pas eu de
• L’ALGORITHME : TRI À BULLES SUR UN TABLEAU T(N)
permutation
Ilyapermutation ← Faux
Pour i ← 0 à n
Si t(i) > t(i+1) alors
On permute…
temp ← t(i)
t(i) ← t(i+1)
t(i+1) ← temp Il y a eu permutation, on met à Vrai
Ilyapermutation ← Vrai
Finsi
i suivant
FinTantQue
Instructions de base des algorithmes

LE TRI A BULLES

• HTTPS://[Link]/WATCH?V=HNXMICW60LG

• HTTPS://[Link]/WATCH?V=XLI_FI7CUZA

• HTTPS://[Link]/WATCH?V=LYZQPJUT5B4
Instructions de base des algorithmes

COMPARAISON DE QUELQUES ALGO DE TRI

• HTTPS://[Link]/WATCH?V=ZZUD6IUE3PC

• HTTPS://[Link]/WATCH?V=BEOCBJPUVSE
Instructions de base des algorithmes

ALGORITHME DE RECHERCHE
• LA RECHERCHE DICHOTOMIQUE
• TRÈS UTILE POUR CHERCHER UN ÉLÉMENT DANS UNE LISTE TRIÉE
• TRÈS EFFICACE POUR DE GRANDS ENSEMBLES
• TRÈS ROBUSTE

• PRINCIPE :
• NE PAS EFFECTUER UNE RECHERCHE SÉQUENTIELLE : CHERCHER UN ÉLÉMENT DANS
UNE LISTE CLASSÉE EN PARTANT DU PREMIER JUSQU’À TROUVER (OU NON) L’ÉLÉMENT
RECHERCHÉ (CE QUI DONNERAIT UNE MOYENNE DE RECHERCHES DE N/2)
• PRENDRE LE MILIEU EXACT DE LA LISTE TRIÉE, PUIS REGARDER SI L’ÉLÉMENT CHERCHER
EST DANS LA 1È OU DANS LA 2È PARTIE.
• NE CONSERVER QUE CETTE PARTIE, PUIS RECOMMENCER…
• RÉCURSIVITÉ : L’ALGORITHME RÉSOUT UN PROBLÈME EN CALCULANT DES
SOLUTIONS D'INSTANCES PLUS PETITES DU MÊME PROBLÈME.
Instructions de base des algorithmes

ALGORITHME DE RECHERCHE

• LA RECHERCHE DICHOTOMIQUE : ON CHERCHE LE «1»

Instructions de base des algorithmes

ALGORITHME DE RECHERCHE DICHOTOMIQUE

EFFICACITÉ :
• LA FORMULE SUIVANTE PEUT S’APPLIQUER POUR TROUVER LE
NOMBRE MAXIMAL (N) D’OPÉRATIONS À EFFECTUER DANS
UNE SÉRIE DE X ÉLÉMENTS :
N ⩽ LOG(X) / LOG(2) = LOG2(X)

• EXEMPLE : TROUVER UN CHIFFRE ENTRE 0 ET 1‘000‘000‘000 SERA POSSIBLE EN

MAX. LOG(1‘000‘000‘000)/LOG(2) = 9 / 0.301 = 29.89 = 30 ESSAIS ! (CONTRE
500‘000‘000 AVEC UNE RECHERCHE SÉQUENTIELLE…)
• EXEMPLE 2 : TROUVER UN CHIFFRE ENTRE 0 ET 999‘999‘999‘999 (=1‘000
MILLIARDS) SERA POSSIBLE EN MAX. LOG(999‘999‘999‘999) / LOG(2) = 12/0.301 =
39.86 -> 40 ESSAIS (CONTRE 500 MILLIARDS EN RECH. SÉQUENTIELLE … )
Instructions de base des algorithmes

ALGORITHME DE RECHERCHE DICHOTOMIQUE

• L’ALGORITHME DE RECHERCHE DICHOTOMIQUE :

• HYPOTHÈSES DE BASE
• TABLEAU(N-1)
• ON CHERCHE X
• 3 VARIABLES NUMÉRIQUES:
• DEBUT (= VALEUR DE DÉBUT)
• FIN (= VALEUR DE FIN)
• MILIEU (= VALEUR MÉDIANE)
• 1 VARIABLE BOOLÉEN
• TROUVÉ (FLAG)
Instructions de base des algorithmes

ALGORITHME DE RECHERCHE DICHOTOMIQUE

Séquentiel Récursif

Début Début
… Entrées: Un tableau trié de taille n, un élément x, un
Trouvé ← Faux flag Trouvé
Debut ← 0 indice <- n / 2
Fin ← N-1 si tab[indice] = élément alors
TantQue Non Trouvé ET Debut <= Fin Trouvé <- Vrai
milieu ← (début + fin)/2 Sinon si tab[indice] > élément alors
Si Tableau(milieu)=X Alors rejouer l’algorithme sur la portion de 0 à indice
Trouvé ← Vrai sinon
SinonSi Tableau(milieu) < X Alors rejouer l’algorithme sur la portion de l’indice à la
Debut ← milieu + 1 fin du tableau
Sinon FinSi
Fin ← milieu - 1 Fin
FinSi
FinTantQue
À l'issue de la boucle, la variable Trouvé contient
le résultat
...
Instructions de base des algorithmes

ALGORITHME DE RECHERCHE

• HTTPS://[Link]/WATCH?V=ULR_8OCZ0AU