ALGORITHMIQUE
Cours Résumé
Licence 1 — Informatique
1. Introduction à l'Algorithmique
Un algorithme est une suite finie et ordonnée d'instructions permettant de résoudre un
problème. C'est la base de tout programme informatique.
1.1 Propriétés d'un bon algorithme
• Fini : il se termine en un nombre fini d'étapes
• Défini : chaque instruction est précise et sans ambiguïté
• Entrées : il peut recevoir des données en entrée
• Sorties : il produit au moins un résultat
• Efficace : il utilise les ressources de manière optimale
1.2 Représentations d'un algorithme
• Langage naturel : description en français/anglais
• Pseudo-code : notation structurée proche d'un langage de programmation
• Organigramme (flowchart) : représentation graphique avec symboles standards
2. Variables et Types de Données
Une variable est un espace mémoire nommé qui contient une valeur pouvant changer au
cours de l'exécution.
2.1 Types de base
Type Exemple Description
Entier age = 25 Nombre sans virgule
Réel prix = 3.14 Nombre avec virgule
Caractère lettre = 'A' Un seul caractère
Chaîne nom = "Ali" Suite de caractères
Booléen ok = VRAI VRAI ou FAUX
2.2 Déclaration de variables (pseudo-code)
VARIABLE age : Entier
VARIABLE nom : Chaîne
VARIABLE prix : Réel
VARIABLE actif : Booléen
3. Structures de Contrôle
3.1 Structure Séquentielle
Les instructions s'exécutent l'une après l'autre dans l'ordre.
DEBUT
Lire(nom)
Afficher("Bonjour, ", nom)
FIN
3.2 Structure Conditionnelle
SI ... SINON (if/else)
SI (note >= 10) ALORS
Afficher("Admis")
SINON
Afficher("Ajourné")
FIN SI
SI ... SINON SI (if/else if)
SI (note >= 16) ALORS
Afficher("Très Bien")
SINON SI (note >= 14) ALORS
Afficher("Bien")
SINON SI (note >= 10) ALORS
Afficher("Passable")
SINON
Afficher("Ajourné")
FIN SI
Selon (switch/case)
SELON (jour) FAIRE
CAS 1 : Afficher("Lundi")
CAS 2 : Afficher("Mardi")
CAS 3 : Afficher("Mercredi")
AUTRE : Afficher("Autre jour")
FIN SELON
3.3 Structures de Boucles (Répétitives)
TANT QUE (while) — condition vérifiée avant
i <- 0
TANT QUE (i < 5) FAIRE
Afficher(i)
i <- i + 1
FIN TANT QUE
FAIRE ... TANT QUE (do-while) — condition vérifiée après
FAIRE
Afficher("Saisir un nombre positif : ")
Lire(n)
TANT QUE (n <= 0)
POUR (for) — nombre d'itérations connu
POUR i DE 1 A 10 FAIRE
Afficher(i)
FIN POUR
Conseil : Utiliser POUR quand le nombre d'itérations est connu, TANT QUE sinon.
4. Tableaux (Structures de Données)
Un tableau est une collection d'éléments du même type, accessibles via un indice.
4.1 Tableau à une dimension
VARIABLE notes : Tableau[10] d'Entier
// Remplissage
POUR i DE 0 A 9 FAIRE
Lire(notes[i])
FIN POUR
// Affichage
POUR i DE 0 A 9 FAIRE
Afficher(notes[i])
FIN POUR
4.2 Tableau à deux dimensions (matrice)
VARIABLE matrice : Tableau[3][3] d'Entier
POUR i DE 0 A 2 FAIRE
POUR j DE 0 A 2 FAIRE
Lire(matrice[i][j])
FIN POUR
FIN POUR
5. Fonctions et Procédures
5.1 Procédure (sans retour)
Une procédure effectue des actions mais ne retourne pas de valeur.
PROCEDURE afficherBonjour(nom : Chaîne)
DEBUT
Afficher("Bonjour, ", nom, " !")
FIN
// Appel
afficherBonjour("Marie")
5.2 Fonction (avec retour)
Une fonction effectue un calcul et retourne une valeur.
FONCTION maximum(a : Entier, b : Entier) : Entier
DEBUT
SI (a > b) ALORS
RETOURNER a
SINON
RETOURNER b
FIN SI
FIN
// Appel
resultat <- maximum(5, 8) // resultat = 8
6. Algorithmes Classiques
6.1 Recherche du Maximum
FONCTION maxTableau(T : Tableau, n : Entier) : Entier
DEBUT
max <- T[0]
POUR i DE 1 A n-1 FAIRE
SI (T[i] > max) ALORS
max <- T[i]
FIN SI
FIN POUR
RETOURNER max
FIN
6.2 Tri par Sélection
POUR i DE 0 A n-2 FAIRE
min_idx <- i
POUR j DE i+1 A n-1 FAIRE
SI (T[j] < T[min_idx]) ALORS
min_idx <- j
FIN SI
FIN POUR
// Echanger T[i] et T[min_idx]
temp <- T[i]
T[i] <- T[min_idx]
T[min_idx] <- temp
FIN POUR
6.3 Recherche Séquentielle
FONCTION recherche(T : Tableau, n : Entier, valeur : Entier) : Entier
DEBUT
POUR i DE 0 A n-1 FAIRE
SI (T[i] = valeur) ALORS
RETOURNER i // Indice trouvé
FIN SI
FIN POUR
RETOURNER -1 // Non trouvé
FIN
7. Complexité Algorithmique
La complexité mesure le coût (temps, mémoire) d'un algorithme en fonction de la taille des
données n.
Notation Nom Exemple
O(1) Constante Accès direct à un tableau
O(log n) Logarithmique Recherche binaire
O(n) Linéaire Recherche séquentielle
O(n log n) Quasi-linéaire Tri rapide (quicksort)
O(n²) Quadratique Tri à bulles, tri sélection
O(2ⁿ) Exponentielle Problèmes combinatoires
Objectif : toujours choisir l'algorithme avec la complexité la plus faible pour les grandes
valeurs de n.
8. Récapitulatif — Points Clés
• Un algorithme doit être fini, défini et efficace
• Variables : typage fort, noms explicites
• Structures conditionnelles : SI, SELON
• Boucles : POUR (itérations connues), TANT QUE (condition)
• Fonctions : décomposer le problème en sous-problèmes
• Tableaux : structure de base pour les collections
• Complexité : mesure l'efficacité d'un algorithme
Méthode de résolution : 1) Comprendre le problème 2) Identifier les données 3) Écrire
le pseudo-code 4) Tester avec des exemples 5) Implémenter en code