Les Bases des Algorithmes

Abdeljalil BOUZINE & Mohamed BEL-ASSAL

Code Crafters

16 novembre 2024

Code Crafters Algorithm Basics 1 / 43

Table des matières
1 Qu’est-ce qu’un algorithme ?
2 Opérations Arithmétiques de Base
3 Variables et Constantes
4 Structures Conditionnelles
5 Boucles
6 Tableaux
7 Fonctions et Procédures
8 Structures de Données Avancées
Listes Chaînées
Piles (Stacks)
Files d’attente (Queues)
9 Conclusion

Code Crafters Algorithm Basics 2 / 43

 Qu’est-ce qu’un algorithme ?

Définition d’un Algorithme

Un algorithme est une suite finie d’instructions permettant de résoudre un

problème ou d’accomplir une tâche spécifique.
Caractéristiques d’un algorithme
Finitude : Doit avoir un nombre d’étapes défini.
Précision : Chaque étape doit être claire et non ambiguë.
Entrées et Sorties : Doit avoir des données d’entrée et fournir un
résultat en sortie.
Efficacité : Doit être réalisable en un temps raisonnable.
Généralité : Doit pouvoir s’appliquer à une classe de problèmes.

Code Crafters Algorithm Basics 3 / 43

 Qu’est-ce qu’un algorithme ?

Exemples d’Algorithmes

Algorithme d’Euclide : Calcul du plus grand commun diviseur

(PGCD) de deux entiers.
Algorithme de Tri : Méthodes pour organiser des données (tri à
bulles, tri rapide, etc.).
Algorithme de Recherche : Techniques pour trouver un élément
dans une structure de données (recherche linéaire, binaire).

Code Crafters Algorithm Basics 4 / 43

 Opérations Arithmétiques de Base

Opérations Arithmétiques

Les opérations arithmétiques sont des actions fondamentales en

programmation.
Addition : a + b
Soustraction : a − b
Multiplication : a × b
Division : a/b
Modulo : a mod b (reste de la division)

Code Crafters Algorithm Basics 5 / 43

 Opérations Arithmétiques de Base

Propriétés des Opérations

Associativité : (a + b) + c = a + (b + c)
Commutativité : a + b = b + a
Distributivité : a × (b + c) = a × b + a × c
Identités : a + 0 = a, a × 1 = a

Code Crafters Algorithm Basics 6 / 43

 Variables et Constantes

Variables

Les variables sont des éléments utilisés pour stocker des valeurs qui
peuvent changer pendant l’exécution d’un algorithme.
Exemple : age, qui peut être modifié au cours de l’algorithme.
Déclaration : Définition du type et du nom, comme int
nombre_utilisateur;
Initialisation : Attribution d’une valeur initiale, par exemple int
compteur = 0;

Code Crafters Algorithm Basics 7 / 43

 Variables et Constantes

Constantes

Les constantes sont des valeurs fixes, définies une fois pour toutes dans
l’algorithme.
Exemple : const float PI = 3.14159;
Utilisation : Les constantes sont utiles pour les valeurs qui ne
changent jamais.

Code Crafters Algorithm Basics 8 / 43

 Variables et Constantes

Types de Variables

Types Numériques : int, float, double

Types Caractères : char
Types Booléens : bool (vrai ou faux)
Types Complexes : Structures, tableaux

Code Crafters Algorithm Basics 9 / 43

 Variables et Constantes

Opérations sur les Variables

Les variables peuvent être manipulées à l’aide d’opérateurs.

Opérateurs Arithmétiques : +, −, ∗, /, %
Opérateurs d’Assignation : =, + =, − =, ∗ =, / =
Opérateurs de Comparaison : == (égal à), ! = (différent de), <,
>, ≤, ≥
Opérateurs Logiques : && (ET), || (OU), ! (NON)

Code Crafters Algorithm Basics 10 / 43

 Variables et Constantes

Exemples d’Opérations sur les Variables

Assignation Simple : a = 5;
Assignation Combinée : a += 3; (équivalent à a = a + 3;)
Incrémentation/Décrémentation : a++; ou a--;
Comparaison : if (a == b) { ... }
Opérations Logiques : if ((a > 0) && (b < 10)) { ... }

Code Crafters Algorithm Basics 11 / 43

 Variables et Constantes

Exercice sur les Variables

Exercice : Écrire un algorithme qui échange les valeurs de deux variables a

et b.
Données : Deux variables entières a et b.
Résultat : Les valeurs de a et b sont échangées.

Code Crafters Algorithm Basics 12 / 43

 Variables et Constantes

Solution de l’Exercice

Data : Entiers a, b
temp ← a ;
a ← b;
b ← temp ;
Afficher "Après échange, a =", a, ", b =", b ;

Code Crafters Algorithm Basics 13 / 43

 Structures Conditionnelles

Instruction si...alors...sinon

Les structures conditionnelles permettent d’exécuter certaines parties du

code en fonction de conditions.
Syntaxe : si (condition) alors ... sinon ...
Exemple : Vérifier si un nombre est pair ou impair.
Data : Nombre entier x
if x mod 2 = 0 then
Afficher "Le nombre est pair"
else
Afficher "Le nombre est impair"
end

Code Crafters Algorithm Basics 14 / 43

 Structures Conditionnelles

Opérateurs Logiques et Relationnels

Opérateurs Relationnels : <, >, == (égal à), ! = (différent de), ≤,

≥
Opérateurs Logiques : et (&&), ou (||), non (!)

Code Crafters Algorithm Basics 15 / 43

 Boucles

Boucle pour

Une boucle permet de répéter une série d’instructions un certain nombre

de fois.
Exemple : Afficher les nombres de 1 à 10.
for i ← 1 to 10 do
Afficher i
end

Code Crafters Algorithm Basics 16 / 43

 Boucles

Boucle tant que

Cette boucle exécute des instructions tant qu’une condition est vraie.
Exemple : Compter jusqu’à 5 tant que la condition est vraie.
i ← 1;
while i ≤ 5 do
Afficher i ;
i ← i + 1;
end

Code Crafters Algorithm Basics 17 / 43

 Boucles

Boucle faire...tant que

La boucle do...while exécute le bloc d’instructions au moins une fois,

puis répète tant que la condition est vraie.
Exemple : Demander à l’utilisateur de saisir un nombre positif.

Code Crafters Algorithm Basics 18 / 43

 Boucles

Exercice sur les Boucles

Exercice : Écrire un programme qui calcule la somme des entiers de 1 à n

en utilisant une boucle do...while.
Données : Un entier positif n.
Résultat : La somme 1 + 2 + · · · + n.

Code Crafters Algorithm Basics 19 / 43

 Boucles

Solution de l’Exercice

somme ← 0 ;
i ← 1;
repeat
until somme ← somme + i ;
i ← i + 1;
;
i > n Afficher "La somme est :", somme ;

Code Crafters Algorithm Basics 20 / 43

 Tableaux

Qu’est-ce qu’un Tableau ?

Un tableau est une structure de données permettant de stocker une

collection d’éléments, souvent du même type, accessibles via des indices.
Déclaration : int tableau[5]; (exemple en C).
Accès : Utilisation de l’indice pour accéder à un élément, comme
tableau[0].
Utilisation : Très pratique pour stocker des données telles qu’une
liste de notes, noms, ou coordonnées.

Code Crafters Algorithm Basics 21 / 43

 Tableaux

Exemple Simple : Déclaration et Accès

Exemple en Pseudo-Code :
Déclarer un tableau de 3 éléments : tableau = [10, 20, 30].
Accéder au premier élément : tableau[0] retourne 10.
Modifier le deuxième élément : tableau[1] = 25.
Illustration :
Indice 0 1
2
Valeur 10 25
30

Code Crafters Algorithm Basics 22 / 43

 Tableaux

Opérations de Base sur un Tableau

Initialisation : int tableau[3] = {10, 20, 30};

Parcours : Utiliser une boucle pour afficher chaque élément.
Modification : Changer la valeur d’un élément via son indice.
Exemple en Pseudo-Code :
for i ← 0 to 2 do
Afficher tableau[i] ;
end
Résultat : 10, 20, 30.

Code Crafters Algorithm Basics 23 / 43

 Tableaux

Exercice Simple : Trouver le Maximum

Exercice : Écrire un algorithme qui trouve le plus grand élément d’un

tableau de 5 nombres.
Données : Un tableau de 5 entiers, par exemple [5, 8, 3, 12, 7].
Résultat attendu : Le maximum est 12.

Code Crafters Algorithm Basics 24 / 43

 Tableaux

Solution : Trouver le Maximum

max ← tableau[0] ;
for i ← 1 to 4 do
if tableau[i] > max then
max ← tableau[i] ;
end
end
Afficher "Le maximum est :", max ;
Résultat : 12.

Code Crafters Algorithm Basics 25 / 43

 Tableaux

Tableaux Multidimensionnels

Un tableau peut être à plusieurs dimensions, par exemple une matrice.

Déclaration : int matrice[2][2] = {{1, 2}, {3, 4}};
Accès : matrice[0][1] retourne 2.
Illustration : [ ]
1 2
3 4

Code Crafters Algorithm Basics 26 / 43

 Tableaux

Exercice : Somme des Éléments d’une Matrice

Exercice : Écrire un algorithme qui calcule la somme de tous les éléments

d’une matrice 2 × 2.
Données : Une matrice matrice = [[1, 2], [3, 4]].
Résultat attendu : La somme est 10.

Code Crafters Algorithm Basics 27 / 43

 Tableaux

Solution : Somme des Éléments d’une Matrice

somme ← 0 ;
for i ← 0 to 1 do
for j ← 0 to 1 do
somme ← somme + matrice[i][j] ;
end
end
Afficher "La somme est :", somme ;
Résultat : 10.

Code Crafters Algorithm Basics 28 / 43

 Fonctions et Procédures

Fonctions

Une fonction est un bloc d’instructions qui retourne une valeur.

Exemple : Fonction de somme.
Syntaxe : int somme(int a, int b) { return a + b; }

Code Crafters Algorithm Basics 29 / 43

 Fonctions et Procédures

Procédures

Une procédure exécute un ensemble d’instructions sans retourner de

valeur.
Exemple : Procédure pour afficher un message.
Syntaxe : void afficherMessage() { printf("Bienvenue !");
}

Code Crafters Algorithm Basics 30 / 43

 Fonctions et Procédures

Paramètres des Fonctions

Passage par Valeur : Les paramètres sont copiés, les modifications

n’affectent pas les variables originales.
Passage par Référence : Les paramètres sont des références, les
modifications affectent les variables originales.
Exemple : Échanger les valeurs de deux variables en utilisant une fonction.

Code Crafters Algorithm Basics 31 / 43

 Fonctions et Procédures

Exemple de Fonction avec Passage par Référence

echanger(&a, &b) temp ← a ;

a ← b;
b ← temp ;

Code Crafters Algorithm Basics 32 / 43

 Fonctions et Procédures

Exercice sur les Fonctions

Exercice : Écrire une fonction récursive pour calculer le n-ième terme de

la suite de Fibonacci.
Données : Un entier n.
Résultat : Le n-ième terme de la suite de Fibonacci.

Code Crafters Algorithm Basics 33 / 43

 Fonctions et Procédures

Solution de l’Exercice

fibonacci(n) if n ≤ 1 then
return n ;
else
return fibonacci(n − 1) + fibonacci(n − 2) ;
end

Code Crafters Algorithm Basics 34 / 43

 Structures de Données Avancées Listes Chaînées

Listes Chaînées

Une liste chaînée est une collection d’éléments appelés nuds, où chaque
nud contient des données et un pointeur vers le nud suivant.
Structure d’un Nud :
Donnée : Valeur stockée dans le nud.
Pointeur : Référence au nud suivant.
Types de Listes Chaînées : Simplement chaînée, doublement
chaînée, circulaire.

Code Crafters Algorithm Basics 35 / 43

 Structures de Données Avancées Listes Chaînées

Opérations sur les Listes Chaînées

Insertion : Ajouter un nouvel élément.

Suppression : Retirer un élément existant.
Recherche : Trouver un élément dans la liste.
Parcours : Visiter chaque nud de la liste.

Code Crafters Algorithm Basics 36 / 43

 Structures de Données Avancées Listes Chaînées

Exemple d’Insertion en Tête

Data : Liste L, valeur valeur

créer un nouveau nud nouveauNoeud ;
[Link]ée ← valeur ;
[Link] ← L.tête ;
L.tête ← nouveauNoeud ;

Code Crafters Algorithm Basics 37 / 43

 Structures de Données Avancées Piles (Stacks)

Piles (Stacks)

Une pile est une structure de données linéaire qui suit le principe LIFO
(Last In, First Out).
Opérations Principales :
empiler (push) : Ajouter un élément au sommet de la pile.
dépiler (pop) : Retirer l’élément au sommet de la pile.
sommet (top) : Obtenir la valeur de l’élément au sommet sans le retirer.

Code Crafters Algorithm Basics 38 / 43

 Structures de Données Avancées Piles (Stacks)

Exemple d’Utilisation d’une Pile

Conversion d’un nombre décimal en binaire :

Diviser le nombre par 2 et empiler le reste.
Répéter jusqu’à ce que le quotient soit 0.
Dépiler les éléments pour obtenir le nombre binaire.

Code Crafters Algorithm Basics 39 / 43

 Structures de Données Avancées Files d’attente (Queues)

Files d’attente (Queues)

Une file d’attente est une structure de données linéaire qui suit le principe
FIFO (First In, First Out).
Opérations Principales :
enfiler (enqueue) : Ajouter un élément à la fin de la file.
défiler (dequeue) : Retirer l’élément au début de la file.
tête (front) : Obtenir la valeur de l’élément au début sans le retirer.

Code Crafters Algorithm Basics 40 / 43

 Structures de Données Avancées Files d’attente (Queues)

Exemple d’Utilisation d’une File

Gestion des tâches d’une imprimante :

Les travaux d’impression sont ajoutés à la file.
L’imprimante traite les travaux dans l’ordre d’arrivée.

Code Crafters Algorithm Basics 41 / 43

 Conclusion

Conclusion

Les algorithmes sont fondamentaux pour la résolution de problèmes.

Comprendre leurs caractéristiques aide à choisir la meilleure approche
pour un problème donné.
La maîtrise des structures de données améliore l’efficacité des
algorithmes.

Code Crafters Algorithm Basics 42 / 43

 Conclusion

Questions et Réponses

Merci pour votre attention !

Des questions ?

Code Crafters Algorithm Basics 43 / 43