COURS D’ALGORITHME

ET PROGRAMMATION
ENSET 2025
Initiation à l’algorithmique :

Introduction

L’algorithmique constitue une pierre angulaire de l’ingénierie moderne, offrant des outils et des
méthodes pour analyser et résoudre efficacement des problèmes complexes. Ce cours
d’Initiation à l’algorithmique vise à doter les apprenants des compétences nécessaires pour
adopter une approche structurée dans la modélisation et la résolution de problèmes en
ingénierie.

Objectif général

L’objectif principal de cette unité d’enseignement (UE) est de permettre aux apprenants de
développer une démarche analytique rigoureuse pour décomposer les problèmes d’ingénierie
en tâches élémentaires et les résoudre à l’aide de méthodes algorithmiques.

Objectifs spécifiques

À la fin de cette UE, les participants seront en mesure de :

 Transcrire un problème d’ingénierie en une série de tâches élémentaires clairement

définies ;
 Identifier et utiliser les variables nécessaires à la construction d’algorithmes adaptés ;
 Déterminer et analyser la complexité des algorithmes, en évaluant leur efficacité dans
divers contextes ;
 Trier et hiérarchiser des ensembles de données pour faciliter leur manipulation et leur
traitement ;
 Appliquer des techniques avancées telles que la récursivité et l’approche "divide and
conquer" pour résoudre des problèmes de manière optimisée.

Contenu du cours

Le programme de l’UE est structuré pour fournir une compréhension approfondie des concepts
fondamentaux de l’algorithmique tout en mettant l’accent sur leur application pratique. Il
comprend :

1. Les notions de base, telles que les variables et les structures fondamentales en
algorithmique ;
2. La conception et l’utilisation de fonctions et procédures pour structurer les solutions ;
3. La construction d’algorithmes simples pour résoudre des problèmes courants,
notamment le tri et la gestion des données ;
4. L’analyse de la complexité algorithmique pour évaluer la performance des algorithmes
;
5. Des techniques avancées, notamment la récursivité et l’approche "divide and conquer",
essentielles pour résoudre des problèmes de grande envergure.

Ce cours pose les bases indispensables pour aborder des problématiques plus complexes en
ingénierie, tout en développant chez les apprenants une rigueur intellectuelle et des
compétences en résolution algorithmique.
La notion de variables en algorithme est centrale pour la conception et l'optimisation des
programmes informatiques. Les variables jouent divers rôles, allant de la sélection et de
l'optimisation à l'amélioration de l'efficacité des algorithmes.

Cours : Les Notions de Variable en Algorithmique

1. Introduction aux Variables

Une variable est un concept fondamental en algorithmique et en programmation. Elle permet

de stocker une information qui peut être manipulée et modifiée au cours de l'exécution d'un
algorithme.

Définition : Une variable est un espace mémoire identifié par un nom, qui contient une valeur
pouvant être modifiée au cours du temps.

Exemple : Dans un algorithme qui calcule la somme de deux nombres, les nombres et leur
somme peuvent être stockés dans des variables nommées nombre1, nombre2 et somme.

2. Caractéristiques des Variables

Les variables possèdent plusieurs caractéristiques importantes :

 Nom : Le nom de la variable permet de l’identifier dans l’algorithme. Par exemple : x,

age, ou temperature.
 Type : Chaque variable a un type qui détermine le genre de données qu’elle peut
contenir. Exemples de types :
o Entier (integer) : pour les nombres entiers.
o Réel (float) : pour les nombres décimaux.
o Caractère (char) : pour un caractère unique.
o Chaîne de caractères (string) : pour une séquence de caractères.
o Booléen (boolean) : pour les valeurs vraies ou fausses (true/false).
 Valeur : La valeur est l’information contenue dans la variable.

3. Déclaration et Initialisation des Variables

Dans de nombreux langages d’algorithmes et de programmation, une variable doit être déclarée
avant d’être utilisée.

 Déclaration : Réserve un espace mémoire pour la variable. Cela inclut souvent la

définition de son type.

Exemple :

entier x
caractère lettre
boolean estVrai
  Initialisation : Attribue une valeur initiale à la variable au moment de sa déclaration ou
plus tard dans l’algorithme.

Exemple :

x ← 10
lettre ← 'A'
estVrai ← vrai
4. Manipulation des Variables

Une variable peut être modifiée, lue ou utilisée dans des calculs et des opérations.

 Lecture : Récupération de la valeur de la variable pour une utilisation dans une

expression ou un affichage.

Exemple :

afficher x

 Modification : Mise à jour de la valeur contenue dans la variable.

Exemple :

x←x+5

 Utilisation dans une expression : Les variables peuvent être combinées avec des
opérateurs pour effectuer des calculs.

Exemple :

somme ← x + y
5. Bonnes Pratiques dans l'Utilisation des Variables

 Noms significatifs : Utilisez des noms explicites qui reflètent le rôle de la variable.
Exemple : age, salaire.
 Respect des types : Assurez-vous que les valeurs attribuées à une variable
correspondent à son type.
 Initialisation : Toujours initialiser une variable avant de l’utiliser pour éviter des
comportements imprévisibles.
 Documentation : Commentez les variables complexes pour expliquer leur utilité.

6. Exemple d’Algorithme avec Variables

Voici un exemple simple illustrant l'utilisation des variables dans un algorithme qui calcule la
somme de deux nombres donnés par l'utilisateur :

Enoncé : Ecrire un algorithme qui lit deux nombres, calcule leur somme et affiche le résultat.

Algorithme :
Début
entier nombre1, nombre2, somme
afficher "Entrez le premier nombre :"
lire nombre1
afficher "Entrez le second nombre :"
lire nombre2
somme ← nombre1 + nombre2
afficher "La somme est :", somme
Fin
7. Erreurs Courantes avec les Variables

 Non-initialisation : Utiliser une variable sans lui attribuer de valeur initiale.

 Conflit de noms : Utiliser le même nom pour deux variables différentes dans le même
contexte.
 Type incorrect : Essayer de stocker une chaîne dans une variable déclarée comme
entier.

8. Exercices Pratiques

1. Déclarez une variable pour chaque type suivant et attribuez-lui une valeur : entier, réel,
chaîne, et booléen.
2. Écrivez un algorithme qui calcule la moyenne de trois nombres donnés par l’utilisateur.
3. Réalisez un algorithme qui échange les valeurs de deux variables.
Cours : Les Structures de Base en Algorithmique

1. Introduction aux Structures de Base en Algorithmique

En algorithmique, les structures de base permettent de modéliser les opérations fondamentales

de tout algorithme. Ces structures sont essentielles pour organiser et exécuter des étapes de
manière logique et structurée.

Les trois structures de base en algorithmique sont :

1. La séquence
2. La condition (ou sélection)
3. La boucle (ou itération)

Ces structures constituent la base de la résolution algorithmique de tout problème.

2. La Séquence

Définition : La séquence est l’exécution linéaire d’instructions dans l’ordre dans lequel elles
apparaissent. Chaque instruction est exécutée une fois, de haut en bas.

Exemple : Algorithme pour calculer l’aire d’un rectangle :

Début
lire longueur
lire largeur
aire ← longueur × largeur
afficher "L’aire est :", aire
Fin

Description : Les instructions sont exécutées successivement : lecture des dimensions, calcul
de l’aire, puis affichage du résultat.

3. La Condition (ou Sélection)

Définition : La condition permet de choisir une action à effectuer parmi plusieurs possibilités,
en fonction d’un test logique (vrai ou faux).

Syntaxe Générale :

 Si...Alors...Sinon :
 Si condition Alors
 instructions_si_vrai
 Sinon
 instructions_si_faux
 Fin Si
 Cas Multiples :
 Selon variable Faire
  Cas valeur1 : instructions1
 Cas valeur2 : instructions2
 Autre : instructions_defaut
 Fin Selon

Exemple : Algorithme pour vérifier si un nombre est pair ou impair :

Début
lire nombre
Si nombre mod 2 = 0 Alors
afficher "Le nombre est pair"
Sinon
afficher "Le nombre est impair"
Fin Si
Fin

Cas Multiples : Algorithme pour donner le jour correspondant à un chiffre :

Début
lire chiffre
Selon chiffre Faire
Cas 1 : afficher "Lundi"
Cas 2 : afficher "Mardi"
Cas 3 : afficher "Mercredi"
Cas 4 : afficher "Jeudi"
Cas 5 : afficher "Vendredi"
Cas 6 : afficher "Samedi"
Cas 7 : afficher "Dimanche"
Autre : afficher "Entrée invalide"
Fin Selon
Fin

4. La Boucle (ou Itération)

Définition : La boucle permet de répéter un ensemble d’instructions tant qu’une condition est
vraie ou pour un nombre défini d’itérations.

Types de Boucles :

1. Boucle Tant que :

o Syntaxe :
o Tant que condition Faire
o instructions
o Fin Tant que
o Exemple :
o Début
o x ← 1
o Tant que x ≤ 5 Faire
o afficher x
o x ← x + 1
o Fin Tant que
o Fin
2. Boucle Pour :
o Syntaxe :
o Pour variable ← début à fin Faire
o instructions
 o Fin Pour
o Exemple :
o Début
o Pour i ← 1 à 10 Faire
o afficher i
o Fin Pour
o Fin
3. Boucle Répéter...Jusqu’à :
o Syntaxe :
o Répéter
o instructions
o Jusqu’à condition
o Exemple :
o Début
o x ← 0
o Répéter
o afficher x
o x ← x + 2
o Jusqu’à x > 10
o Fin

5. Exemple Combiné : Structures de Base Ensemble

Enoncé : Ecrire un algorithme qui calcule la somme des nombres pairs entre 1 et 10.

Algorithme :

Début
somme ← 0
Pour i ← 1 à 10 Faire
Si i mod 2 = 0 Alors
somme ← somme + i
Fin Si
Fin Pour
afficher "La somme des nombres pairs est :", somme
Fin

6. Bonnes Pratiques dans l’Utilisation des Structures de Base

 Lisibilité : Indentez correctement votre algorithme pour faciliter la lecture.

 Tests : Vérifiez vos conditions pour éviter des boucles infinies ou des erreurs de logique.
 Modularité : Divisez un problème complexe en plusieurs parties simples utilisant ces
structures.
 Commentaires : Expliquez les étapes complexes avec des commentaires clairs.

7. Exercices Pratiques

1. Écrivez un algorithme qui vérifie si un nombre donné est un multiple de 3.

2. Réalisez un algorithme qui affiche les nombres impairs entre 1 et 20.
3. Élaborez un algorithme qui calcule la factorielle d’un entier positif donné par l’utilisateur.
4. Rédigez un algorithme qui affiche le plus grand nombre parmi trois nombres donnés.
Cours : Fonctions et Procédures en Algorithmique

1. Introduction aux Fonctions et Procédures

Les fonctions et procédures sont des blocs d’instructions qui permettent de structurer et de
réutiliser le code dans un algorithme. Elles sont essentielles pour simplifier, organiser et
modulariser un programme.

 Procédures : Utilisées pour effectuer une action ou une suite d’actions. Elles ne retournent
pas de valeur.
 Fonctions : Similaires aux procédures, mais elles retournent une valeur à la fin de leur
exécution.

2. Différences entre Fonction et Procédure

Caractéristique Fonction Procédure

Objectif Retourner une valeur Exécuter une ou plusieurs actions

Retour de valeur Oui Non

Usage typique Calculs, opérations qui produisent un résultat Tâches organisationnelles

3. Déclaration et Utilisation
3.1. Déclaration d’une Fonction

Une fonction est déclarée avec un nom, des paramètres (optionnels), un type de retour et un
bloc d’instructions.

Syntaxe :

fonction nom_fonction(paramètres) : type_retour

instructions
retourner valeur
fin fonction

Exemple : Fonction pour calculer le carré d’un nombre

fonction carre(nombre) : entier

retourner nombre × nombre
fin fonction
3.2. Déclaration d’une Procédure

Une procédure est déclarée avec un nom, des paramètres (optionnels), et un bloc
d’instructions.

Syntaxe :

procédure nom_procédure(paramètres)
 instructions
fin procédure

Exemple : Procédure pour afficher un message de bienvenue

procédure afficher_bienvenue()
afficher "Bienvenue dans ce programme"
fin procédure
3.3. Appel d’une Fonction ou Procédure

 Pour une fonction, l’appel se fait dans une expression, par exemple :

x ← carre(5)

- Pour une **procédure**, l’appel se fait directement, par exemple :

afficher_bienvenue()

---

#### **4. Passage de Paramètres**

Les fonctions et procédures peuvent recevoir des paramètres. Ces paramètres
permettent de transmettre des valeurs ou des références aux blocs
d’instructions.

- **Paramètres par valeur :** Une copie de la valeur est passée à la

fonction ou procédure. Toute modification n’affecte pas la variable
originale.
- **Paramètres par référence :** La référence de la variable est passée.
Les modifications affectent directement la variable originale.

**Exemple :**

procédure augmenter_par_valeur(x) x ← x + 1 fin procédure

procédure augmenter_par_reference(ref x) x ← x + 1 fin procédure

---

#### **5. Exemple d’Application**

**Enoncé :** Ecrire un algorithme pour calculer la surface et le périmètre

d’un rectangle en utilisant une fonction et une procédure.

**Algorithme :**

fonction calcul_surface(longueur, largeur) : entier retourner longueur × largeur fin fonction

procédure calcul_perimetre(longueur, largeur) entier perimetre perimetre ← 2 × (longueur +

largeur) afficher "Le périmètre est :", perimetre fin procédure

Début entier l, L, surface afficher "Entrez la longueur :" lire l afficher "Entrez la largeur :" lire
L surface ← calcul_surface(l, L) afficher "La surface est :", surface calcul_perimetre(l, L) Fin
---

#### **6. Avantages des Fonctions et Procédures**

- **Lisibilité :** Facilite la lecture et la compréhension de l’algorithme.
- **Réutilisabilité :** Permet de réutiliser le même bloc d’instructions
plusieurs fois.
- **Modularité :** Divise un problème complexe en sous-problèmes plus
simples.
- **Maintenance :** Rend l’algorithme plus facile à modifier et à tester.

---

#### **7. Exercices Pratiques**

1. Ecrivez une fonction qui calcule le cube d’un nombre.
2. Créez une procédure qui affiche les nombres pairs entre 1 et 20.
3. Réalisez une fonction qui retourne le plus grand de trois nombres donnés
en paramètres.
4. Ecrivez un algorithme qui utilise une procédure pour afficher un message
différent selon l’âge donné par l’utilisateur.

---

Ce cours présente une introduction complète aux fonctions et procédures.

Besoin d’exemples supplémentaires ou de clarifications ?
Cours : Algorithmes Simples

1. Introduction aux Algorithmes Simples

Un algorithme simple est une suite finie et ordonnée d’instructions destinée à résoudre un
problème basique ou à exécuter une tâche précise. Ces algorithmes constituent la base de
toute démarche algorithmique et permettent d’acquérir les fondamentaux avant de passer à
des problèmes plus complexes.

Exemples d’applications :

 Calcul de la somme de deux nombres

 Recherche d’un élément dans une liste
 Conversion d’unités
 Calcul du factoriel d’un nombre

2. Structure de Base d’un Algorithme Simple

Un algorithme typique comporte trois parties principales :

1. Début : Indique le début de l’algorithme.

2. Corps : Contient les instructions à exécuter dans l’ordre.
3. Fin : Indique la fin de l’algorithme.

Exemple général :

Début
Instruction 1
Instruction 2
...
Fin

3. Opérations Fondamentales

Un algorithme simple repose souvent sur les opérations suivantes :

1. Lecture et Affichage :
o Permet de recevoir des entrées utilisateur et d’afficher les résultats.
o Exemple :
o afficher "Entrez un nombre :"
o lire nombre
2. Calculs :
o Réalisation d’opérations arithmétiques (addition, multiplication, etc.).
o Exemple :
o somme ← nombre1 + nombre2
3. Conditions :
o Exécution conditionnelle selon des critères.
o Exemple :
o si nombre > 0 alors
o afficher "Le nombre est positif"
 o fin si
4. Boucles :
o Répétition d’instructions un certain nombre de fois ou jusqu’à une condition.
o Exemple :
o pour i de 1 à 10 faire
o afficher i
o fin pour

4. Exemples d'Algorithmes Simples

4.1. Somme de Deux Nombres

Enoncé : Ecrire un algorithme qui lit deux nombres, calcule leur somme et affiche le résultat.

Algorithme :

Début
entier nombre1, nombre2, somme
afficher "Entrez le premier nombre :"
lire nombre1
afficher "Entrez le second nombre :"
lire nombre2
somme ← nombre1 + nombre2
afficher "La somme est :", somme
Fin
4.2. Maximum de Deux Nombres

Enoncé : Ecrire un algorithme qui détermine le plus grand de deux nombres donnés par
l’utilisateur.

Algorithme :

Début
entier a, b
afficher "Entrez le premier nombre :"
lire a
afficher "Entrez le second nombre :"
lire b
si a > b alors
afficher "Le maximum est :", a
sinon
afficher "Le maximum est :", b
fin si
Fin
4.3. Calcul du Factoriel

Enoncé : Ecrire un algorithme qui calcule le factoriel d’un nombre entier positif donné par
l’utilisateur.

Algorithme :

Début
entier n, factoriel, i
afficher "Entrez un nombre :"
lire n
 factoriel ← 1
pour i de 1 à n faire
factoriel ← factoriel × i
fin pour
afficher "Le factoriel de", n, "est :", factoriel
Fin

5. Bonnes Pratiques pour Rédiger des Algorithmes Simples

1. Clarifier le Problème : Bien comprendre le problème avant de commencer la rédaction.

2. Diviser le Problème : Identifier les sous-tâches à réaliser.
3. Tester avec des Exemples : Valider l’algorithme avec des cas pratiques pour vérifier son
exactitude.
4. Utiliser des Noms Significatifs : Donner des noms explicites aux variables pour améliorer la
lisibilité.
5. Documenter : Ajouter des commentaires pour expliquer les étapes importantes.

6. Exercices Pratiques

1. Ecrire un algorithme qui convertit une température de degrés Celsius en Fahrenheit.

2. Réaliser un algorithme qui détermine si un nombre donné par l’utilisateur est pair ou impair.
3. Créer un algorithme qui calcule la moyenne de trois nombres donnés par l’utilisateur.
4. Ecrire un algorithme qui affiche les 10 premiers multiples d’un nombre donné.
5. Rédiger un algorithme qui compte le nombre de voyelles dans une chaîne de caractères
saisie par l’utilisateur.
Cours : Les Problèmes de Tri en Algorithmique

1. Introduction aux Problèmes de Tri

Le tri est une opération fondamentale en algorithmique. Il consiste à réorganiser les éléments
d’une liste ou d’un tableau selon un ordre prédéfini (croissant, décroissant ou selon des
critères spécifiques).

Applications courantes du tri :

 Recherche rapide dans une liste ordonnée

 Organisation de données pour des analyses statistiques
 Optimisation des opérations de fusion et de comparaison

Exemple : Trier une liste de notes d’étudiants par ordre croissant.

2. Propriétés des Algorithmes de Tri

Un bon algorithme de tri se distingue par :

 Complexité temporelle : Temps d’exécution en fonction de la taille des données (O(n), O(n²),
etc.).
 Stabilité : Maintien de l’ordre relatif des éléments égaux.
 Efficacité mémoire : Quantité de mémoire supplémentaire nécessaire.

3. Principaux Algorithmes de Tri

Voici quelques algorithmes de tri classiques classés selon leur complexité et leur mode de
fonctionnement :

3.1. Tri par Insertion

Principe :

 Insère chaque élément de la liste à sa position correcte dans une partie déjà triée.

Complexité :

 Meilleur cas : O(n) (si la liste est déjà triée)

 Pire cas : O(n²)

Exemple :

Début
pour i de 2 à longueur(liste) faire
x ← liste[i]
j ← i - 1
tant que j > 0 et liste[j] > x faire
 liste[j+1] ← liste[j]
j ← j - 1
fin tant que
liste[j+1] ← x
fin pour
Fin
3.2. Tri par Sélection

Principe :

 Trouve le plus petit élément de la liste et l’échange avec le premier, puis répète pour les
sous-listes restantes.

Complexité :

 O(n²) dans tous les cas.

Exemple :

Début
pour i de 1 à longueur(liste) - 1 faire
min ← i
pour j de i+1 à longueur(liste) faire
si liste[j] < liste[min] alors
min ← j
fin si
fin pour
échanger liste[i] et liste[min]
fin pour
Fin
3.3. Tri à Bulles (Bubble Sort)

Principe :

 Compare les éléments adjacents et les échange si nécessaire. Répète jusqu’à ce que la liste
soit triée.

Complexité :

 O(n²) dans le pire des cas.

Exemple :

Début
pour i de 1 à longueur(liste) - 1 faire
pour j de 1 à longueur(liste) - i faire
si liste[j] > liste[j+1] alors
échanger liste[j] et liste[j+1]
fin si
fin pour
fin pour
Fin
3.4. Tri Rapide (Quick Sort)

Principe :

 Divise pour régner. Sélectionne un pivot, partitionne la liste en deux (les éléments inférieurs
et supérieurs au pivot), puis trie récursivement.

Complexité :

 Meilleur cas : O(n log n)

 Pire cas : O(n²) (si le pivot est mal choisi)

Exemple :

Fonction quickSort(liste)
si longueur(liste) ≤ 1 alors
retourner liste
sinon
pivot ← liste[1]
gauche ← [x pour x dans liste si x < pivot]
droite ← [x pour x dans liste si x > pivot]
retourner quickSort(gauche) + [pivot] + quickSort(droite)
Fin
3.5. Tri par Fusion (Merge Sort)

Principe :

 Divise la liste en deux moitiés, trie chacune récursivement, puis fusionne les moitiés triées.

Complexité :

 O(n log n) dans tous les cas.

Exemple :

Fonction mergeSort(liste)
si longueur(liste) ≤ 1 alors
retourner liste
sinon
milieu ← longueur(liste) // 2
gauche ← mergeSort(liste[1 à milieu])
droite ← mergeSort(liste[milieu+1 à fin])
retourner fusion(gauche, droite)
Fin

Fonction fusion(gauche, droite)

résultat ← []
tant que gauche n’est pas vide et droite n’est pas vide faire
si gauche[0] ≤ droite[0] alors
ajouter gauche[0] à résultat
enlever gauche[0] de gauche
sinon
ajouter droite[0] à résultat
enlever droite[0] de droite
fin si
 fin tant que
retourner résultat + gauche + droite
Fin

4. Comparaison des Algorithmes de Tri

Algorithme Complexité Meilleur Cas Complexité Pire Cas Stable ?

Tri par Insertion O(n) O(n²) Oui

Tri par Sélection O(n²) O(n²) Non

Tri à Bulles O(n) O(n²) Oui

Tri Rapide O(n log n) O(n²) Non

Tri par Fusion O(n log n) O(n log n) Oui

5. Exercices Pratiques

1. Implémentez un algorithme de tri par sélection pour trier une liste de 10 éléments.
2. Réalisez un algorithme de tri rapide pour trier un tableau d’entiers donné par l’utilisateur.
3. Comparez le temps d’exécution entre le tri par insertion et le tri à bulles pour un tableau de
100 éléments aléatoires.
4. Implémentez une version modifiée du tri par fusion pour trier des chaînes de caractères.
Cours : Analyse de la Complexité Algorithmique

1. Introduction à la Complexité Algorithmique

L'analyse de la complexité algorithmique est un outil fondamental pour évaluer les

performances d'un algorithme. Elle permet de prédire les ressources nécessaires, comme le
temps d'exécution et l'espace mémoire, en fonction de la taille des données d'entrée.

Objectifs :

 Comparer différents algorithmes en termes d'efficacité.

 Identifier les goulots d'étranglement potentiels.
 Optimiser les solutions pour résoudre des problèmes de manière plus efficace.

2. Types de Complexité
a) Complexité temporelle

Elle mesure le temps nécessaire pour exécuter un algorithme en fonction de la taille de

l'entrée.

Exemple : La complexité temporelle d'une recherche linéaire est proportionnelle au nombre

d'éléments dans la liste.

b) Complexité spatiale

Elle évalue la quantité de mémoire requise par l'algorithme, y compris les données d'entrée et
les structures auxiliaires utilisées.

Exemple : Un algorithme de tri par insertion utilise un espace constant en plus des données
d'entrée.

3. Notations Asymptotiques

Les notations asymptotiques permettent de représenter la complexité d'un algorithme de

manière approximative pour des entrées de grande taille.

 Notation O ("Big O") : Donne une limite supérieure de la complexité, représentant le

pire cas. Exemple : O(n²) pour le tri par sélection.
 Notation Θ ("Theta") : Donne une borne précise (cas moyen). Exemple : Θ(n log n)
pour le tri fusion.
 Notation Ω ("Omega") : Donne une limite inférieure de la complexité (meilleur cas).
Exemple : Ω(n) pour une recherche linéaire.

4. Complexité des Algorithmes Courants

Algorithme Complexité (Temps) Complexité (Espace)

Recherche linéaire O(n) O(1)

Recherche binaire O(log n) O(1)

 Algorithme Complexité (Temps) Complexité (Espace)

Tri par sélection O(n²) O(1)

Tri fusion O(n log n) O(n)

Tri rapide (QuickSort) O(n log n) (moyen) O(log n)

5. Comparaison des Algorithmes

a) Cas simple : Recherche dans un tableau

 Recherche linéaire : Parcourt tous les éléments, complexité O(n).

 Recherche binaire : Fonctionne sur un tableau trié, complexité O(log n).

b) Cas complexe : Tri d’un tableau

 Tri par insertion : Simple, mais inefficace pour de grandes données (O(n²)).
 Tri fusion : Plus adapté aux grandes données (O(n log n)).

6. Étapes pour Analyser la Complexité

1. Identifier les opérations dominantes (celles qui consomment le plus de ressources).

2. Exprimer le nombre d'opérations en fonction de la taille de l'entrée (‘n’).
3. Simplifier en utilisant les notations asymptotiques pour obtenir une estimation générale.

7. Exemples d'Analyse de Complexité

Exemple 1 : Calcul de la somme des éléments d'un tableau

Algorithme :

Début
somme ← 0
Pour chaque élément e dans le tableau faire
somme ← somme + e
FinPour
Fin

 Nombre d'opérations : Une addition par élément → O(n).

 Complexité spatiale : Une seule variable auxiliaire (‘somme’) → O(1).

Exemple 2 : Recherche de la valeur maximale

Algorithme :

Début
max ← tableau[0]
Pour chaque élément e dans le tableau faire
Si e > max alors
max ← e
FinSi
FinPour
Fin
  Nombre d'opérations : Une comparaison par élément → O(n).
 Complexité spatiale : Une seule variable auxiliaire (‘max’) → O(1).

8. Exercices Pratiques

1. Analyser la complexité temporelle et spatiale de l’algorithme de tri par bulle.

2. Comparer la recherche linéaire et binaire sur un tableau trié.
3. Déterminer la complexité d’un algorithme qui parcourt une matrice de taille n x m.

9. Conclusion

L’analyse de la complexité algorithmique est essentielle pour concevoir des solutions

optimisées et adaptées aux contraintes des systèmes modernes. Une bonne compréhension des
notions de complexité temporelle et spatiale permet de choisir les algorithmes les plus
efficaces pour chaque situation.
Cours : Algorithmes de type "Divide and Conquer"

1. Introduction au Paradigme "Divide and Conquer"

Le paradigme "Divide and Conquer" (Diviser pour Régner) est une stratégie algorithmique
puissante qui consiste à résoudre un problème en le décomposant en sous-problèmes plus
petits, à résoudre ces sous-problèmes, puis à combiner leurs solutions pour obtenir la solution
globale.

Étapes principales :

1. Diviser : Séparer le problème initial en sous-problèmes indépendants et de taille plus

réduite.
2. Régner : Résoudre récursivement chaque sous-problème.
3. Combiner : Combiner les solutions des sous-problèmes pour obtenir la solution finale.

2. Avantages et Limites

Avantages :

 Permet de concevoir des algorithmes efficaces, notamment pour les grands problèmes.
 Exploite la récursivité, ce qui rend certains algorithmes plus naturels à concevoir et à
comprendre.
 Bien adapté aux architectures parallèles.

Limites :

 Peut engendrer une surcharge en termes de mémoire et d'appels récursifs si le problème

n'est pas bien structuré.
 L'étape de combinaison peut parfois être coûteuse.

3. Exemples Classiques d'Algorithmes "Divide and Conquer"

a) Tri Fusion (Merge Sort)

Principe :

 Diviser : Diviser le tableau en deux moitiés.

 Régner : Trier récursivement chaque moitié.
 Combiner : Fusionner les deux moitiés triées pour obtenir un tableau trié.

Complexité :

 Temps : O(n log n)

 Espace : O(n)

Algorithme :

Début
Si la taille du tableau ≤ 1 alors
retourner le tableau
FinSi
 Diviser le tableau en deux moitiés : gauche et droite
Trier récursivement la moitié gauche et la moitié droite
Fusionner les deux moitiés triées
Fin
b) Recherche Binaire

Principe :

 Diviser : Diviser la liste triée en deux moitiés.

 Régner : Vérifier si l'élément recherché se trouve dans la moitié gauche ou droite.
 Combiner : Reprendre la recherche dans la moitié concernée.

Complexité :

 Temps : O(log n)
 Espace : O(1) ou O(log n) avec une implémentation récursive.

Algorithme :

Début
Si la liste est vide alors
retourner "Non trouvé"
FinSi
Milieu ← indice du milieu de la liste
Si l'élément du milieu = valeur recherchée alors
retourner "Trouvé"
Sinon Si l'élément du milieu > valeur recherchée alors
Rechercher récursivement dans la moitié gauche
Sinon
Rechercher récursivement dans la moitié droite
FinSi
Fin
c) Algorithme de Strassen pour la Multiplication de Matrices

Principe :

 Diviser : Diviser les matrices en sous-matrices de taille plus petite.

 Régner : Calculer récursivement les produits des sous-matrices.
 Combiner : Combiner les résultats pour former la matrice produit finale.

Complexité :

 Temps : O(n⁸⁺⁳···⁶)
 Espace : Dépend de la taille de la mémoire auxiliaire utilisée.

4. Analyse de Complexité

L'efficacité des algorithmes "Divide and Conquer" peut souvent être évaluée en utilisant une
relation de récurrence.

Forme générale : T(n) = aT(n/b) + O(n^d)

 a : Nombre de sous-problèmes.
  b : Facteur de réduction de la taille des sous-problèmes.
 d : Coût de la division et de la combinaison.

Exemple : Tri Fusion T(n) = 2T(n/2) + O(n)

 a = 2, b = 2, d = 1
 Solution : T(n) = O(n log n)

5. Cas Pratiques et Applications

 Tri de grandes bases de données (Tri Fusion).

 Recherche dans des ensembles triés (Recherche Binaire).
 Multiplication rapide de matrices (Algorithme de Strassen).
 Calcul rapide de transformations comme la Transformée de Fourier Rapide (FFT).

6. Exercices Pratiques

1. Implémentez le tri fusion pour un tableau donné.

2. Analysez la complexité temporelle de la recherche binaire sur une liste de taille n.
3. Modifiez l'algorithme de Strassen pour des matrices de taille 4x4.
4. Élaborez un algorithme "Divide and Conquer" pour trouver la somme maximale d'une sous-
séquence contiguë d'un tableau (Problème de la Sous-Séquence Maximale).

7. Conclusion

Les algorithmes "Divide and Conquer" exploitent une approche modulaire et récursive pour
résoudre des problèmes complexes de manière efficace. Leur maîtrise est essentielle pour
aborder des problématiques avancées en algorithmique et en ingénierie des systèmes.
Cours : Récursivité en Algorithmique

1. Introduction à la Récursivité

La récursivité est une approche algorithmique où une fonction ou un algorithme s’appelle lui-
même directement ou indirectement. Elle permet de résoudre des problèmes complexes en les
décomposant en sous-problèmes similaires mais plus simples.

Définition : Un algorithme est dit récursif lorsqu’il contient une ou plusieurs instructions qui
mènent à son propre appel.

2. Éléments Clés d’une Fonction Récursive

1. Cas de base (ou condition d’arrêt) :

o Condition qui met fin à la récursion.
o Sans condition d’arrêt, une récursivité mène à une boucle infinie.
2. Appel récursif :
o Une ou plusieurs instructions où la fonction s’appelle elle-même.
o Chaque appel doit progresser vers le cas de base.

3. Exemple Simple : Factorielle d’un Nombre

Définition : La factorielle d’un nombre entier positif n est définie comme :

 n! = n × (n-1)! si n > 0
 n! = 1 si n = 0

Algorithme :

Fonction factorielle(n : entier) : entier

Si n = 0 alors
retourner 1
Sinon
retourner n × factorielle(n - 1)
FinSi
FinFonction
4. Types de Récursivité

1. Récursivité directe :
o Une fonction s’appelle directement elle-même.
o Exemple : La factorielle vue précédemment.
2. Récursivité indirecte :
o Une fonction A appelle une fonction B, qui à son tour appelle la fonction A.
3. Récursivité terminale :
o L’appel récursif est la dernière instruction de la fonction.
o Exemple : Calcul de la somme des n premiers nombres naturels.

Algorithme :

Fonction somme(n : entier, acc : entier) : entier

Si n = 0 alors
retourner acc
 Sinon
retourner somme(n - 1, acc + n)
FinSi
FinFonction
5. Avantages et Inconvénients de la Récursivité

Avantages :

 Simplifie la conception des algorithmes pour certains problèmes comme les parcours
d’arbres ou les problèmes de type "Divide and Conquer".
 Réduit la complexité du code dans des cas où une solution itérative serait plus complexe.

Inconvénients :

 Peut entraîner une surcharge mémoire due à la pile d’appels.

 Moins efficace que les solutions itératives dans certains cas en raison des appels récursifs.

6. Applications de la Récursivité

1. Parcours des Structures de Données :

o Arbres : Parcours infixe, préfixe, suffixe.
o Graphes : Algorithme DFS (Depth First Search).
2. Problèmes de Tri :
o Tri rapide (Quick Sort).
o Tri fusion (Merge Sort).
3. Problèmes Combinatoires :
o Calcul des permutations et combinaisons.
4. Algorithmes de Recherche :
o Recherche binaire sur une liste triée.

7. Comparaison : Récursivité vs Itération

Aspect Récursivité Itération

Simplicité Plus lisible pour certains problèmes Peut être complexe pour certains cas

Performance Plus lente (surcharge de la pile) Plus rapide

Utilisation de mémoire Plus grande (pile d’appels) Moins gourmande

Conditions d’arrêt Cas de base requis Contrôlé par des boucles

8. Exercices Pratiques

1. Écrire un algorithme récursif pour calculer la somme des n premiers nombres naturels.
2. Implémenter un algorithme récursif pour vérifier si une chaîne de caractères est un
palindrome.
3. Élaborer un algorithme récursif pour parcourir un arbre en profondeur.
4. Comparer les temps d’exécution de l’algorithme de la factorielle en récursif et en itératif.
9. Conclusion

La récursivité est un outil puissant en algorithmique, utile pour décomposer et résoudre des
problèmes complexes. Cependant, elle doit être utilisée avec prudence, en évaluant ses
implications sur la mémoire et la performance. Sa compréhension approfondie est essentielle
pour tout programmeur ou analyste en algorithmique.
Cours : Complexité Algorithmique

1. Introduction à la Complexité Algorithmique

La complexité algorithmique mesure l'efficacité d'un algorithme en termes de temps et

d'espace requis pour résoudre un problème en fonction de la taille de son entrée. Elle est
essentielle pour comparer différentes approches et choisir la plus adaptée à un contexte donné.

Pourquoi évaluer la complexité ?

 Optimiser les performances d'un programme.

 Prévoir le comportement de l'algorithme avec des entrées de grande taille.
 Comparer différents algorithmes pour un même problème.

2. Types de Complexité

1. Complexité temporelle : Quantifie le temps d'exécution d'un algorithme en fonction de la

taille de l'entrée.
2. Complexité spatiale : Quantifie la mémoire utilisée par un algorithme en fonction de la taille
de l'entrée.

3. Notations Asymptotiques

Les notations asymptotiques permettent de décrire la croissance de la complexité d'un

algorithme lorsque la taille de l'entrée augmente.

1. O-Grande (Big-O) : Représente la limite supérieure de la complexité.

o Exemple : T(n) = O(n²) signifie que le temps d'exécution croît au plus comme n².
2. Θ (Theta) : Représente la limite exacte de la complexité.
o Exemple : T(n) = Θ(n) signifie que le temps d'exécution est proportionnel à n.
3. Ω (Omega) : Représente la limite inférieure de la complexité.
o Exemple : T(n) = Ω(n log n) signifie que le temps d'exécution ne peut être inférieur à
n log n.

4. Catégories de Croissance de la Complexité

1. Constante : O(1) — Indépendant de la taille de l'entrée.

2. Logarithmique : O(log n) — Croît lentement avec la taille de l'entrée.
3. Linaire : O(n) — Croît proportionnellement à la taille de l'entrée.
4. Quadratique : O(n²) — Croît quadratiquement avec la taille de l'entrée.
5. Exponentielle : O(2ⁿ) — Croît très rapidement.
6. Factorielle : O(n!) — Croît encore plus rapidement que l'exponentielle.

5. Analyse de la Complexité d'un Algorithme

1. Mesurer les Opérations Dominantes : Identifier les instructions principales qui influencent le
temps d'exécution.
2. Calculer la Fréquence d'Exécution : Compter le nombre de fois qu'une instruction est
exécutée en fonction de la taille de l'entrée.
3. Utiliser les Notations Asymptotiques : Exprimer le résultat en termes de O, Θ ou Ω.
Exemple : Recherche linéaire

Algorithme :

Début
Pour chaque élément de la liste
Si l'élément correspond à la valeur recherchée
Retourner l'indice
FinPour
Fin

Analyse :

 Temps : O(n) dans le pire cas (on parcourt toute la liste).

 Espace : O(1) (utilisation de mémoire constante).

6. Cas Pratiques

1. Tri par Insertion :

o Temps : O(n²) dans le pire cas.
o Espace : O(1).
2. Recherche Binaire :
o Temps : O(log n).
o Espace : O(1).
3. Tri Fusion :
o Temps : O(n log n).
o Espace : O(n).

7. Exercices

1. Analysez la complexité temporelle et spatiale de l'algorithme suivant :

2. Début
3. Pour i de 1 à n
4. Pour j de 1 à i
5. écrire(i, j)
6. FinPour
7. FinPour
8. Fin
9. Comparez la complexité du tri à bulles et du tri par sélection.
10. Implémentez un algorithme avec une complexité logarithmique.

8. Conclusion

L'analyse de la complexité algorithmique est un outil essentiel pour déterminer l'efficacité d'un
algorithme. En comprenant les notations asymptotiques et les principes sous-jacents, on peut
conçoitre des solutions plus optimales pour les problèmes complexes. La maîtrise de ce
domaine est indispensable pour tout informaticien ou ingénieur logiciel.