Introduction à l'Algorithmie

Aide

Recommandé

Alternatif

Optionnel

Mon choix

---

Clic sur un noeud → déplier / replier

↗ → ouvrir le cours

Molette → zoomer

Glisser → déplacer la vue

L’algorithmie est la science de la résolution de problèmes de manière systématique. C’est la base de toute programmation.

Qu’est-ce qu’un algorithme ?

Un algorithme est une suite finie d’instructions permettant de résoudre un problème ou d’accomplir une tâche.

Caractéristiques d’un bon algorithme

1. Finitude : l’algorithme doit se terminer après un nombre fini d’étapes
2. Précision : chaque étape doit être définie clairement
3. Entrées : zéro ou plusieurs valeurs en entrée
4. Sorties : une ou plusieurs valeurs en sortie
5. Efficacité : chaque instruction doit être réalisable

Exemple simple

Voici un algorithme pour trouver le maximum dans une liste :

ALGORITHME TrouverMaximum
ENTRÉE: liste de nombres L
SORTIE: le nombre maximum

DÉBUT
    max ← L[0]
    POUR chaque élément e dans L FAIRE
        SI e > max ALORS
            max ← e
        FIN SI
    FIN POUR
    RETOURNER max
FIN

Complexité algorithmique

La complexité mesure les ressources (temps, mémoire) nécessaires à l’exécution d’un algorithme.

Notation	Nom	Exemple
O(1)	Constante	Accès à un élément d’un tableau
O(log n)	Logarithmique	Recherche binaire
O(n)	Linéaire	Parcours d’une liste
O(n²)	Quadratique	Tri à bulles

:::tip[Conseil] Commencez toujours par écrire un algorithme sur papier avant de coder ! :::

Prochaines étapes

• Structures de données
• Algorithmes de tri
• Récursivité