INFORMATIQUE ET ALGORITHME

SOMMAIRE

Chapitre 1 : Introduction à l'algorithmique

1. Définition d'un algorithme
2. Les caractéristiques d'un bon algorithme
3. Représentation des algorithmes

Chapitre 2 : Les variables

1. A quoi servent les variables
2. Déclaration des variables
2.1- Les types de variables
2.2- Les bonnes pratiques

Chapitre 3 : Les structures de contrôle

1. Les structures conditionnelles
◦ Structure Si...Alors...Sinon
◦ Structure Si...Alors...SinonSi...Sinon
2. Les structures itératives (Boucles)
◦ Boucle Pour (répétition avec un compteur)
◦ Boucle Tant que (répétition sous condition)
3. Structure de séquence (Exécution linéaire)

Chapitre 4 : Résolution de problèmes avec des algorithmes

1. Décomposer un problème :
• Analyser un problème, le diviser en sous-problèmes simples.
• Exemple : Calculer la moyenne d'une série de nombres.
2. Algorithmes itératifs et conditionnels :
• Utiliser les boucles pour effectuer des actions répétitives.
• Appliquer des conditions pour prendre des décisions pendant
l'exécution

Chapitre 5 : Les algorithmes de tri et de recherche

1. Algorithme de recherche :
• Recherche linéaire : Parcourir une liste pour trouver un élément.
• Recherche binaire : Diviser une liste triée en deux pour réduire le
nombre d’opérations.
2. Algorithmes de tri :
 • Tri par sélection : Choisir le plus petit élément et le placer à la
bonne position.
• Tri par insertion : Insérer chaque élément à sa place dans une liste
triée.

Chapitre 6 : Introduction à la programmation structurée

1. Concept de modularité :
• Diviser un problème en sous-problèmes indépendants.
• Organiser un programme sous forme de fonctions et
procédures.
2. Les fonctions :
• Définir des fonctions pour éviter la répétition du code.
• Exemple : Fonction pour calculer la somme de plusieurs
nombres.
Chapitre 1 :Introduction à l'algorithmique
Objectifs :
1. Comprendre ce qu'est un algorithme.
2. Apprendre à résoudre des problèmes en suivant des étapes logiques,
indépendamment du langage de programmation utilisé.

1. Définition d'un algorithme

Un algorithme est une suite finie et ordonnée d’instructions ou d’étapes précises

qui permettent de résoudre un problème ou d'accomplir une tâche spécifique.
Il décrit la procédure à suivre pour obtenir un résultat donné.
Exemple de la vie quotidienne : L’un des exemples les plus simples et concrets
d’algorithme est une recette de cuisine.
Voici un exemple simple pour préparer une tasse de thé :
1. Faire chauffer de l'eau.
2. Placer un sachet de thé dans une tasse.
3. Verser l'eau chaude dans la tasse.
4. Laisser infuser pendant 3 à 5 minutes.
5. Retirer le sachet de thé.
6. Ajouter du sucre ou du lait (optionnel).
7. Boire le thé.
Chaque étape doit être suivie dans l'ordre, et elle est nécessaire pour que
l'objectif final (avoir une tasse de thé) soit atteint. C'est un algorithme, car
chaque action est clairement définie, et elles doivent être exécutées dans un
ordre précis.
Exemple d’algorithme informatique : Prenons l'exemple d'un algorithme
simple pour trier une liste de nombres en ordre croissant
1. Comparer le premier élément avec le deuxième.
2. Si le premier est plus grand, les échanger.
3. Comparer le deuxième élément avec le troisième, et ainsi de suite
jusqu'à la fin de la liste.
4. Répéter le processus jusqu'à ce que la liste soit triée.

2. Les caractéristiques d'un bon algorithme

Un algorithme éfficace doit respecter un certain nombre de propriétés pour être

bien conçu et fonctionnel :
 1. Précision : L’algorithme doit être précis. Chaque étape doit être
clairement définie et ne doit pas prêter à ambiguïté. Par exemple, il est essentiel
de dire précisément ce que l'on entend par "chauffer de l'eau" (quelle
température, combien de temps, etc.).
2. Finitude : L’algorithme doit avoir un nombre fini d’étapes. Autrement
dit, il doit terminer après un certain nombre d'opérations. Un algorithme infini
(qui ne se termine jamais) ne serait pas utile.
3. Effectivité : Les étapes doivent être effectives et réalisables dans un
délai raisonnable. Cela signifie qu'il doit être possible de réaliser chaque étape
avec les ressources disponibles (temps, outils, compétences).
4. Unicité : Il doit exister une seule manière de réaliser l'algorithme à
partir du moment où il est formulé. Cela garantit qu’il n'y a pas d’ambiguïté
dans les étapes à suivre et que l'algorithme mènera toujours au même résultat
lorsqu’il sera appliqué aux mêmes entrées.

3. Représentation des algorithmes

Pour mieux comprendre et concevoir des algorithmes, il est important de

pouvoir les représenter sous différentes formes. Cela permet de rendre plus clair
leur fonctionnement et d’aider à leur mise en œuvre dans un langage de
programmation.

a) Notation textuelle : La représentation la plus simple d'un algorithme

est la notation textuelle. On décrit chaque étape sous forme de phrases simples.
Exemple :

Début
Lire le nombre A
Lire le nombre B
Si A est plus grand que B alors
Afficher "A est plus grand"
Sinon
Afficher "B est plus grand"
Fin

Ici, l'algorithme est écrit en utilisant des instructions simples qui peuvent être
comprises facilement, même par des personnes qui ne sont pas familiarisées
avec la programmation.
 b) Organigrammes (Diagrammes de flux)
Les organigrammes ou diagrammes de flux sont des représentations graphiques
des étapes d'un algorithme. Ils utilisent des symboles standard pour indiquer les
différents types d'actions (entrées, sorties, calculs, décisions, etc.).
Exemple d'un organigramme pour comparer deux nombres :

[Début] --> [Lire A et B]

|
[A > B?] --Oui---> [Afficher "A est plus grand"] --> [Fin]
|
Non
|
[Afficher "B est plus grand"] --> [Fin]

Les flèches indiquent le flux du programme, et chaque boîte représente une

étape précise (lire des valeurs, faire une comparaison, afficher un message,
etc.).

c) Pseudocode
Le pseudocode est un moyen de décrire un algorithme avec un langage proche
de l’humain, tout en étant suffisamment formel pour pouvoir être facilement
traduit en code dans n'importe quel langage de programmation. Il est comme un
mélange entre la notation textuelle et la structure de code informatique.
Exemple de pseudocode pour l'algorithme de comparaison de deux
nombres :

Début
Lire A
Lire B
Si A > B alors
Afficher "A est plus grand"
Sinon
Afficher "B est plus grand"
Fin
Le pseudocode permet de se concentrer sur la logique de l'algorithme sans se
soucier de la syntaxe d'un langage de programmation particulier.

4. Conclusion
Ce chapitre introduit les bases de l’algorithmique. Il permet aux étudiants de
comprendre que la résolution de problèmes repose sur des algorithmes qui
peuvent être formulés de manière simple ou plus formelle à l'aide
d'organigrammes ou de pseudocode. L’objectif est que les étudiants soient
capables de concevoir des algorithmes simples pour résoudre des problèmes de
la vie courante, puis qu'ils puissent les traduire en code dans un langage de
programmation de leur choix plus tard.

Exercices pratiques :

1. Exercice 1 : Rédigez l’algorithme pour calculer la somme de deux nombres

donnés par l'utilisateur.
2. Exercice 2 : Dessinez l’organigramme de l’algorithme qui permet de
déterminer si un nombre est pair ou impair.
3. Exercice 3 : Écrivez un pseudocode pour calculer le produit de deux
nombres et afficher le résultat
Chapitre 2 : Les variables

Objectifs :
1. Maîtriser les concepts de base pour écrire des algorithmes simples.
2. Travailler sur des exemples concrets pour mieux comprendre l'application
des algorithmes dans la résolution de problèmes.

A quoi servent les variables ?

Dans un programme informatique, on va avoir en permanence besoin de
stocker provisoirement des valeurs. Il peut s’agir de données issues du disque
dur, fournies par l’utilisateur (frappées au clavier), etc. Il peut aussi s’agir de
résultats obtenus par le programme, intermédiaires ou définitifs. Ces données
peuvent être de plusieurs types (on en reparlera) : elles peuvent être des
nombres, du texte, etc. Toujours est-il que dès que l’on a besoin de stocker une
information au cours d’un programme, on utilise une variable.

1) Déclaration des variables

La première chose à faire avant de pouvoir utiliser une variable est de créer la
boîte et de lui coller une étiquette. Ceci se fait tout au début de l’algorithme,
avant même les instructions proprement dites. C’est ce qu’on appelle la
déclaration des variables. C’est un genre de déclaration certes moins
romantique qu’une déclaration d’amour, mais d’un autre côté moins
désagréable qu’une déclaration d’impôts. Le nom de la variable (l’étiquette de
la boîte) obéit à des impératifs changeant selon les langages. Toutefois, une
règle absolue est qu’un nom de variable peut comporter des lettres et des
chiffres, mais qu’il exclut la plupart des signes de ponctuation, en particulier les
espaces. Un nom de variable correct commence également impérativement par
une lettre. Quant au nombre maximal de signes pour un nom de variable, il
dépend du langage utilisé.

NB : En pseudo-code, l'instruction d'affectation se note avec le signe ←

2.1- Les types de variables

a) Entier (entier)
• Un nombre entier est un nombre sans partie décimale.

• Il peut être positif, négatif ou nul.

• Exemples : 5, -10
b) Réel (Réel)
• Un nombre réel est un nombre qui peut contenir une partie décimale.
• Il est utilisé pour représenter les valeurs fractionnaires.
• Exemples : 3.14; -2.5; 0.0

c) Caractère (Caractère)
• Un caractère représente une seule lettre, chiffre ou symbole.
• Il est encadré par des apostrophes ('A').
• Exemples : 'A', 'b', '7', '%'

d) Chaîne de caractères (Chaîne)

• Une chaîne est une suite de caractères regroupés.
• Elle est entourée de guillemets ("Bonjour").
• Exemples : "Hello", "12345", "Nom : Toto"
e) Booléen (Booléen)
• Un booléen ne peut avoir que deux valeurs : Vrai ou Faux.
• Il est utilisé pour les conditions logiques.
f) Tableau (Tableau)
• Un tableau est une structure qui stocke plusieurs valeurs du même type
sous un seul nom.
• Les éléments sont indexés (numérotés à partir de 1 ou 0 selon le langage).

2.2- Bonne pratiques

Il faut bien nommer ses variables et respecter surtout les conventions de
nommages.
- Eviter de nommer les variables par: a, b, c, A, B, C, etc .

a ← 25

b ← "Alice"

c ← True
- Privilégier plutôt: nom_utilisateu, prix_article, age_personne, etc.

age _ utilisateur ←25

nom _ utilisateur ← "Alice"

est _ connecté ← True

Bien que cela n’ait pas vraiment d’incidence sur le code, un bon nom de
variable permet de comprendre immédiatement son rôle sans devoir analyser
tout le code.
Dans un projet en équipe, un bon nommage permet aux autres développeurs de
comprendre facilement le code et d’y apporter des modifications sans
confusion.
Exemple : Un collègue qui voit une variable nommée t ne sait pas si elle
représente un "temps", un "total", une "température", etc. En revanche, avec
temps_d_execution, il comprend immédiatement que c'est la durée d'exécution
d'un programme .
Parfois, un mauvais nom peut induire des erreurs logiques dans le code.
Exemple :

prixTotal ← prix _ unitaire

prix _ unitaire ← prixTotal * quantite

Dans l'algorithme, on essaie d'affecter prixTotal à prix_unitaire, puis juste après,

on recalcule prix_unitaire en multipliant prixTotal par quantite. Cela crée une
incohérence logique.

Chaque langage de programmation a ses propres conventions pour le nommage

des variables.
Conventions courantes :
- camelCase (JavaScript, Java, C++) : monPrenom
- snake_case (Python) : mon_prenom
- PascalCase (C#, TypeScript) : MonPrenom
- MAJUSCULES_POUR_LES_CONSTANTES : TAUX_TVA = 0.2

Exercices pratiques :
1. Exercice 1 : Écrire un algorithme pour déterminer si un nombre est positif,
négatif ou nul.
2. Exercice 2 : Créer un algorithme qui calcule la somme de tous les nombres
de 1 à N (N étant un nombre entier donné par l'utilisateur).
3. Exercice 3 : Écrire un algorithme qui recherche un nombre donné dans une
liste de nombres.
4. Exercice 4 : Implémenter un algorithme qui affiche les 10 premiers multiples
de 3.
Chapitre 3 : Les structures de contrôles .

Objectifs :
1. Maîtriser les concepts de base pour écrire des algorithmes simples.
2. Travailler sur des exemples concrets pour mieux comprendre l'application
des algorithmes dans la résolution de problèmes.

Les structures de contrôle permettent d’organiser le déroulement d’un

algorithme en modifiant l’ordre d’exécution des instructions en fonction de
certaines conditions.
Il existe trois types principaux de structures de contrôle :
1. Les structures conditionnelles (prendre des décisions)
2. Les structures itératives (répéter une action)
3. Les structures de séquence (exécuter des instructions dans l'ordre)

1. Les structures conditionnelles (Tests et décisions)

Les structures conditionnelles permettent d'exécuter une instruction seulement
si une condition est remplie. Une condition est une comparaison c’est à dire
qu’elles est constituée de 3 éléments:
→une valeur ;
→un opérateur de comparaison ;
→une autre valeur.
Les valeurs peuvent être a priori de n’importe quel type (numériques,
caractères…). Mais si l’on veut que la comparaison ait un sens, il faut que les
deux valeurs de la comparaison soient du même type !

1.1. Structure Si ... Alors ... Sinon

Elle permet de tester une condition et d'exécuter un bloc d’instructions selon
que la condition est vraie ou fausse.
- Syntaxe en pseudo-code :
 Si condition Alors
// Instructions si la condition est vraie
Sinon
// Instructions si la condition est fausse
FinSi

- Exemple :Vérifier si un nombre est positif ou négatif

Début
Variable x : Entier
x ← -5

Si x >= 0 Alors
Afficher "Le nombre est positif"
Sinon
Afficher "Le nombre est négatif"
FinSi
Fin

Dans ce code, si x est supérieur ou égal à 0, on affiche qu'il est positif, sinon il
est négatif.

1.2. Structure Si ... Alors ... SinonSi ... Sinon

Permet de tester plusieurs conditions successives.
Exemple : Donner une appréciation selon la note d’un élève
 Début
Variable note : Entier
note ← 15

Si note >= 16 Alors

Afficher "Très bien"
SinonSi note >= 12 Alors
Afficher "Bien"
SinonSi note >= 10 Alors
Afficher "Moyen"
Sinon
Afficher "Insuffisant"
FinSi
Fin

Dans ce code,
• Si la note est ≥ 16, on affiche "Très bien".
• Sinon, si la note est ≥ 12, on affiche "Bien".
• Sinon, si la note est ≥ 10, on affiche "Moyen".
• Sinon, on affiche "Insuffisant".

Il existe aussi des boucles qui sont dites imbriquées, il s’agit d’une boucle
placée à l’intérieur d’une autre boucle. Cela permet d'exécuter plusieurs
répétitions dans une autre série de répétitions.

- Syntaxe en pseudo-code :
Si condition Alors
Si sous condition1 Alors
// Instructions si la sous condition1 est vraie
Sinon si sous condition2 Alors
// Instructions si la sous condition2 est vraie
Sinon
// Instructions si aucune des deux sous conditions précédentes n’est vraie
Sinon
// Instructions si la condition est fausse
FinSi

2. Les structures itératives (Boucles)

Les boucles permettent de répéter une ou plusieurs instructions plusieurs
fois.

2.1. Boucle Pour (répétition avec un compteur)

Utilisée quand on connaît à l’avance le nombre de répétitions.
- syntaxe en pseudo-code:

Pour variable ← début Jusqu'à fin Faire

// Instructions à exécuter
FinPour

- Exemple : Afficher les nombres de 1 à 5

Pour i ← 1 Jusqu'à 5 Faire

Afficher i
FinPour
La boucle affiche 1, 2, 3, 4, 5 en répétant l'affichage 5 fois.

2.2. Boucle Tant que (répétition sous condition)

Utilisée quand on ne sait pas à l'avance combien de fois l’action doit être
répétée.
- Syntaxe en pseudo-code :

Tant que condition Faire

// Instructions à exécuter
FinTantQue

- Exemple:Répéter une saisie jusqu'à obtenir un nombre positif

Variable x : Entier

Afficher "Entrer un nombre positif :"

Lire x

Tant que x < 0 Faire

Afficher "Erreur ! Entrer un nombre positif :"
Lire x
FinTantQue

Afficher "Nombre valide :", x

Dans ce code,
• Tant que x est négatif, on demande une nouvelle saisie
 • Dès que x est positif, la boucle s’arrête.

3. Structure de séquence (Exécution linéaire)

Une séquence est l'exécution linéaire des instructions, l'une après l'autre, dans
l’ordre où elles apparaissent.
Exemple :

Afficher "Début du programme"

a ← 10
b←5
somme ← a + b
Afficher "La somme est :", somme
Afficher "Fin du programme"

Dans ce code, Les instructions s’exécutent dans l’ordre sans interruption.

Résumé des structures de contrôle

Type Utilisation Exemple

Conditionnelle (Si … Prendre des décisions Vérifier si un nombre est
positif
Alors ... Sinon)
Boucle Pour Répétition avec un compteur Afficher les nombres de 1 à
10
Boucle Tant que Répétition sous condition Demander un mot de passe
jusqu'à sa validité
Boucle Répéter ... Exécuter au moins une fois Saisir un nombre jusqu'à ce
avant de vérifier qu'il soit positif
Jusqu'à
Séquence Exécution normale des Calculer une somme
instructions
Chapitre 4 : Résolution de problèmes avec des
algorithmes
Objectifs :
1. Apprendre à décomposer des problèmes complexes en sous-problèmes
simples pour faciliter leur résolution.

1. Décomposer un problème
Principe :
Lorsqu’un problème est trop complexe pour être résolu directement, il peut être
utile de le diviser en étapes ou sous-problèmes plus simples. Ces étapes
permettent de mieux organiser les idées et de trouver une solution logique.
Méthode générale :
1. Analyser le problème : Identifier clairement ce qu’il faut résoudre.
2. Diviser en sous-problèmes : Fractionner le problème global en tâches
élémentaires.
3. Résoudre chaque sous-problème : Trouver un algorithme pour chaque
partie.
4. Assembler les solutions : Combiner les solutions des sous-problèmes
pour obtenir la solution finale.
Exemple1 : Calculer la moyenne d'une série de nombres
Énoncé : Écrire un algorithme qui calcule la moyenne d'une liste de nombres
donnée par l'utilisateur.
1. Analyse du problème :
▪ Entrée : Une liste de nombres.
▪ Sortie : La moyenne des nombres de la liste
2. Décomposition en sous-problèmes :
▪ Étape 1 : Lire les nombres (entrée utilisateur).
▪ Étape 2 : Calculer la somme de tous les nombres.
 ▪ Étape 3 : Diviser cette somme par le nombre d’éléments pour
obtenir la moyenne.
▪ Étape 4 : Afficher le résultat.
Algorithme

Début

Lire N (le nombre d'éléments dans la liste)

Somme ←0

Pour i allant de 1 à N faire

Lire Nombre

Somme← Somme + Nombre

Fin Pour

Moyenne ←Somme / N

Afficher "La moyenne est :", Moyenne Fin

Exemple2 : Trouver le plus grand nombre dans une liste

1. Analyse du problème :
• Entrée : Une liste de nombres.
• Sortie : Le plus grand nombre de la liste.
2. Décomposition :
• Étape 1 : Lire les nombres (entrée).
• Étape 2 : Initialiser une variable Max avec le premier nombre.
• Étape 3 : Comparer chaque nombre de la liste avec Max et le
mettre à jour si un nombre plus grand est trouvé.
• Étape 4 : Afficher le résultat.
Algorithme :

Début

Lire N (le nombre d'éléments dans la liste)

Lire Max (le premier nombre)

Pour i allant de 2 à N faire

Lire Nombre

Si Nombre > Max alors

Max ← Nombre

Fin Si

Fin Pour

Afficher "Le plus grand nombre est :", Max

Fin

Conclusion
En résumé, ce chapitre montre comment décomposer un problème en étapes
simples et comment utiliser efficacement les structures de contrôle comme les
boucles et les conditions pour résoudre des problèmes concrets .
Chapitre 5 : Les Algorithmes de Tri et de Recherche
Objectifs :
• Comprendre les algorithmes fondamentaux utilisés pour rechercher ou
trier des données.
• Analyser et appliquer des techniques simples de tri et de recherche sur
des ensembles de données.
I- Complexité
La complexité en informatique mesure l'efficacité d'un algorithme,
principalement en termes de temps et d'espace. Elle décrit comment les
ressources nécessaires à l'exécution d'un algorithme augmentent en fonction de
la taille de l'entrée. Il existe deux types principaux de complexité :
1. Complexité en Temps
Elle évalue le nombre d'opérations qu'un algorithme effectue en fonction de la
taille de l'entrée, notée généralement n. On utilise des notations asymptotiques
pour exprimer cette complexité :
• O(1) : Temps constant, l'algorithme exécute un nombre fixe
d'opérations, quelle que soit la taille de l'entrée.
• O(log(n)) : Logarithmique, le temps augmente logarithmiquement avec
la taille de l'entrée.
• O(n) : Linéaire, le temps augmente proportionnellement à la taille de
l'entrée.
• O(nlog(n)) : Quasi-linéaire, typique de certains algorithmes de tri
efficaces.
• O(n2 ) : Quadratique, le temps augmente proportionnellement au carré
de la taille de l'entrée, souvent vu dans les algorithmes de tri simples.
• O(2n ) ou O(n!) : Exponentielle ou factorielle, très inefficace pour les
grandes tailles d'entrée.
2. Complexité en Espace
Elle mesure la quantité de mémoire supplémentaire requise par l'algorithme par
rapport à la taille de l'entrée.
• O(1) : L'algorithme utilise un espace constant, quel que soit la taille de
l'entrée.
• O(n) : L'espace utilisé augmente proportionnellement à la taille de
l'entrée.
• O(n2 ) : L'espace utilisé augmente proportionnellement au carré de la
taille de l'entrée.
3. Importance de la Complexité
• Optimisation : Comprendre la complexité permet de choisir l'algorithme
le plus efficace pour un problème donné, surtout lorsque les ressources
sont limitées.
• Comparaison : La complexité est une métrique standard pour comparer
la performance de différents algorithmes.
• Scalabilité : Elle aide à prédire comment un algorithme se comporte à
mesure que la taille de l'entrée augmente.

II- Les algorithmes de tri et de recherche

1- Les Algorithmes de Recherche
(Dans ce chapitre le “n” représente le nombre d'éléments ou la taille de l'entrée
sur laquelle l'algorithme opère).
1.1 Recherche linéaire
Principe : La recherche linéaire consiste à parcourir chaque élément d'une liste,
un par un, pour trouver l'élément cible.
Algorithme avec les étapes detaillés
1. Début

2. Lire la liste des éléments.

3. Lire l'élément à rechercher (appelé cible).

4. Pour chaque élément de la liste :

• Si l'élément est égal à la cible :

 • Afficher "Élément trouvé".

• Fin.

5. Si aucun élément n'est trouvé, afficher "Élément non trouvé".

6. Fin.

Algorithme en pseudo-code

Entrée : une liste d'éléments “liste”, un élément “cible” à rechercher

Sortie : l'index de “cible” si trouvé, précédé de "Élément trouvé" et “ Élément
non trouvé” si non trouvé.

Début

Pour i de 0 à longueur(liste) - 1 faire

Si liste[i] est égal à cible alors

Afficher "Élément trouvé à l'index “ i

Fin Si

Fin Pour

Afficher "Élément non trouvé"

Fin

Exemple d'exécution :
• Liste : [3, 7, 2, 9, 4].
• Élément cible : 9.
• Résultat : La recherche trouve 9 à la 4ᵉ position.
Complexité :
 • Temps : O(n), car on parcourt chaque élément une fois.
• Espace : O(1), car aucun espace supplémentaire n'est requis.

1.2 Recherche binaire

Principe :
La recherche binaire fonctionne sur une liste triée. On divise la liste en deux
parties à chaque étape, en comparant l'élément cible avec l'élément au milieu.
Algorithme avec les étapes detaillés
1. Début

2. Lire une liste triée et l'élément cible.

3. Initialiser deux indices : debut et fin.

4. Tant que debut ≤ fin :

• Calculer le milieu : milieu = ( debut+fin 2 ).

• Si l'élément au milieu est égal à la cible :

• Afficher "Élément trouvé".

• Fin

• Sinon, si la cible est plus petite que l'élément au milieu :

• Mettre à jour fin = milieu - 1.

• Sinon :

• Mettre à jour debut = milieu + 1.

5. Si la boucle se termine, afficher "Élément non trouvé".

6. Fin.

Algorithme en pseudo-code
 Entrée: liste, cible

gauche← 0

droite← longueur(liste) - 1

Tant que gauche ≤ droite faire

milieu ← (gauche + droite) / 2

Si liste[milieu] = cible alors

Retourner milieu // Élément trouvé

Sinon si liste[milieu] > cible alors

droite← milieu - 1 // Rechercher dans la moitié gauche

Sinon

gauche ← milieu + 1 // Rechercher dans la moitié droite

Fin Si

Fin Tant Que

Retourner -1 // Élément non trouvé

FinAlgorithme

Exemple d'exécution :
• Liste : [2, 3, 5, 7, 9, 12].
• Élément cible : 7.
• Étapes :
• milieu=3, liste[milieu] = 5 (trop petit, avancer debut).
• milieu=4, liste[milieu] = 7 (élément trouvé).
 • Résultat : "Élément trouvé".
Complexité :
• Temps : O(log(n)), car la liste est divisée par deux à chaque étape.
• Espace : O(1).

2- Les Algorithmes de Tri

2.1 Tri par sélection
Principe : Le tri par sélection consiste à trouver le plus petit élément de la liste
et à le placer en première position. On répète ce processus pour les sous-listes
restantes.
Algorithme(explication de déroulé) :
1. Début

2. Lire une liste.

3. Pour chaque position de la liste (de I = 0 à n−2) :

• Trouver le plus petit élément dans la sous-liste à partir de la position i.

• Échanger cet élément avec celui à la position i.

4. Afficher la liste triée.

5. Fin.

Algorithme en pseudo-code
 Début

Entrée : liste

Pour i de 0 à longueur(liste) - 2 faire

min_index ← i

Pour j de i + 1 à longueur(liste) - 1 faire

Si liste[j] < liste[min_index] alors

min_index← j

Fin Si

Fin Pour

Échanger liste[i] et liste[min_index]

Fin Pour

Fin.

Exemple d'exécution :
• Liste : [3, 7, 2, 9].
• Étapes :
1. Trouver le plus petit élément : 2, l'échanger avec 3 → [2, 7, 3, 9].
2. Trouver le plus petit élément restant : 3, l'échanger avec 7 →
[2, 3, 7, 9].
3. Liste triée : [2, 3, 7, 9].
Complexité :
• Temps : O(n2 ), car il y a deux boucles imbriquées.
• Espace : O(1), car le tri est fait sur place.
 2.2 Tri par insertion
Principe : Le tri par insertion consiste à prendre chaque élément de la liste et à
l'insérer à la bonne position dans une sous-liste triée.
Algorithme (avec explication) :
1. Début

2. Lire une liste.

3. Pour I = 1 à n−1 :

• Prendre l'élément courant.

• Le comparer aux éléments de la sous-liste triée (à gauche).

• Le déplacer à la bonne position.

4. Afficher la liste triée.

5. Fin.

Algorithme en pseudo-code :

Début

Entrée : liste

Pour i de 1 à longueur(liste) - 1 faire

clé← liste[i]

j← i - 1

Tant que j >= 0 et liste[j] > clé faire

liste[j + 1] ←liste[j]

j← j - 1

Fin Tant que

liste[j + 1] ← clé

Fin Pour

Fin
Exemple d'exécution :
• Liste : [4, 3, 7, 2].
• Étapes :
1. Prendre 3: 3<4, insérer avant 4 → [3, 4, 7, 2].
2. Prendre 7 : 7>4, pas de changement → [3, 4, 7, 2].
3. Prendre 2 : 2<3, insérer avant 3 → [2, 3, 4, 7].
Complexité :
• Temps :
• Meilleur cas : O(n), si la liste est déjà triée.
• Pire cas : O(n2 ), si la liste est triée à l'envers.
• Espace : O(1).

Conclusion
Ce chapitre fournit les bases pour manipuler et organiser efficacement les
données. Les algorithmes de recherche et de tri sont des outils fondamentaux
pour résoudre des problèmes complexes et optimiser les performances des
programmes.
Chapitre 6 : Introduction à la Programmation
Structurée
Objectifs :
• Comprendre l'importance d'organiser un programme en blocs logiques.
• Maîtriser les concepts de modularité pour écrire des programmes clairs
et réutilisables.
• Apprendre à concevoir des algorithmes structurés avec des fonctions et
procédures.
1. Concept de Modularity
• Définition : La modularité consiste à diviser un problème complexe en
sous-problèmes plus simples et indépendants. Chaque sous-problème est
résolu individuellement, puis les solutions sont combinées pour résoudre
le problème global.
• Avantages de la modularité :
• Simplifie la compréhension du programme.
• Favorise la réutilisation du code.
• Facilite le débogage et les modifications.
• Approche :
• Identifier les différentes parties du problème.
• Associer chaque partie à un bloc logique (fonction ou procédure).
2. Organisation d’un programme
• Structure d’un programme structuré :
• Entrée : Collecter les données nécessaires.
• Traitement : Exécuter des opérations sur les données à l’aide de
fonctions/procédures.
• Sortie : Fournir les résultats sous une forme compréhensible.
• Représentation schématique :
• Programme principal (Main) : Coordonne l'exécution des blocs.
 • Blocs logiques (fonctions ou procédures) : Effectuent des tâches
spécifiques.
3. Les Fonctions
• Définition : Une fonction est un bloc de code qui effectue une tâche
spécifique. Elle prend des paramètres d’entrée et retourne une valeur de
sortie.
• Avantages des fonctions :
• Évite la répétition de code.
• Facilite les tests et la maintenance.
• Rend le programme plus lisible.
• Structure générale d’une fonction :

Fonction Nom_Fonction(Paramètres)
Instructions
Retourner Résultat
Fin Fonction

• Exemple d’algorithme avec une fonction : Calculer la somme de plusieurs

nombres.

Fonction CalculerSomme(Liste)
Somme ←0
Pour Chaque Élément dans Liste Faire
Somme← Somme + Élément
Fin Pour
Retourner Somme
Fin Fonction

Début
Liste← [2, 4, 6, 8]
Résultat ←CalculerSomme(Liste)
Afficher "La somme est : ", Résultat
Fin
• Explication :
• La fonction CalculerSomme reçoit une liste.
• Elle parcourt chaque élément, ajoute sa valeur à une variable Somme, et
retourne le résultat.
4. Différence entre Fonctions et Procédures
• Fonctions : Retournent toujours une valeur.
• Procédures : Ne retournent pas de valeur, mais effectuent des actions.
• Exemple de procédure : Afficher un message.

Procédure AfficherMessage(Message)
Afficher Message
Fin Procédure