Introduction à l'Algorithmie
0.1 Qu'est-ce qu’un Algorithme ?
Un algorithme est un ensemble de règles logiques et chronologiques qu'on doit suivre pour résoudre un problème particulier. C'est comme une recette de cuisine précise qui, suivie étape par étape, aboutit toujours au même résultat.
Caractéristiques essentielles d'un algorithme :
- Finitude : il se termine après un nombre fini d'étapes
- Précision : chaque étape est définie sans ambiguïté
- Entrée : il peut recevoir des données en entrée
- Sortie : il produit un résultat
- Efficacité : il résout le problème en un temps raisonnable
0.2 L'Algorithmie dans la vie quotidienne
Nous utilisons des algorithmes tous les jours :
- Suivre un itinéraire sur GPS
- Préparer une recette de cuisine
- Lacer ses chaussures
- Trier des cartes à jouer
- Chercher un mot dans un dictionnaire
0.3 Le Langage de Description d'Algorithme (LDA)
Le LDA est un langage intermédiaire entre langage humain et langage de programmation.
Il sert à :
- Se détacher d’un langage de programmation spécifique
- Se concentrer sur la logique
- Faciliter la communication
- Organiser ses idées avant de coder
0.4 Exemple concret : Préparation d'un gâteau
Un algorithme avec gestion des ingrédients manquants. (Code à insérer ici selon exercice.)
1. Les Structures de Données
Une structure de données permet d’organiser et stocker efficacement les données.
Objectifs
- Efficacité des opérations (recherche, insertion, suppression)
- Stockage adapté à l’usage
- Optimisation mémoire et temps
Structures principales
- Pile (Stack) : LIFO
- File (Queue) : FIFO
- Liste chaînée
- Tableau (Array)
- Dictionnaire (HashMap)
- Arbre binaire / de recherche
- Tas (Heap)
- Graphe
2. La Pile (Stack)
LIFO – Le dernier élément ajouté est le premier retiré.
Analogie : Pile d’assiettes.
Opérations :
push
: ajouterpop
: retirerpeek
outop
: lire le hautisEmpty
: test de vide
Applications :
- Annulation (
Ctrl+Z
) - Historique de navigation
- Analyse syntaxique
- Pile d'appels
Complexité :
- Toutes les opérations : O(1)
3. La File (Queue)
FIFO – Premier entré, premier sorti.
Analogie : File d’attente.
Opérations :
enqueue
: ajouter à la findequeue
: retirer en têtefront
: lire la têteisEmpty
Applications :
- Requêtes serveur
- File d’impression
- UI : gestion des événements
- Parcours BFS
Complexité :
- O(1) si implémentée de façon circulaire
4. Les Listes Chaînées
4.1 Définition
Nœuds contenant :
- une valeur
- un ou plusieurs pointeurs
4.2 Types :
- Liste simplement chaînée
- Liste doublement chaînée
- Liste circulaire
Avantages :
- Taille dynamique
- Insertion/suppression efficaces
Inconvénients :
- Accès non direct
- Plus de mémoire utilisée
- Moins efficace en cache
Complexité :
- Accès / Recherche : O(n)
- Insertion/Suppression début : O(1)
- Fin : O(n) ou O(1) si doublement chaînée
- Milieu : O(n)
5. Les Tableaux (Arrays)
5.1 Définition
Structure contiguë en mémoire.
5.2 Caractéristiques :
- Accès par index
- Taille fixe
- Stockage contigu
Avantages :
- Accès direct O(1)
- Cache efficace
- Parcours rapide
Inconvénients :
- Taille non dynamique
- Insertion/suppression coûteuse
- Réallocation
Complexité :
- Accès : O(1)
- Recherche non triée : O(n)
- Insertion/Suppression début/milieu : O(n)
- Fin : O(1) amortie
6. Le Dictionnaire (HashMap)
Définition
Associe des clés à des valeurs via une fonction de hachage.
Fonctionnement
- Clé → hash → index
- Gestion des collisions : chaînage, adressage
Avantages :
- Accès/Insertion/Suppression O(1) en moyenne
Inconvénients :
- Collisions = ralentissement
- Plus de mémoire
- Pas d’ordre
Complexité :
- Moyenne : O(1)
- Pire cas : O(n)
7. Structures Avancées
Arbres Binaires
Chaque nœud a 0 à 2 enfants.
Utilisation :
- Recherche rapide
- Hiérarchies
- Compression
Tas (Heap)
Arbre binaire partiellement ordonné.
- Min Heap : parents ≤ enfants
- Max Heap : parents ≥ enfants
Utilisation :
- Files de priorité
- Tri (heapsort)
- Algos : Dijkstra, Prim
Graphes
Sommets + arêtes
Types :
- Orienté / non orienté
- Pondéré / non pondéré
- Cyclique / acyclique
Applications :
- Réseaux sociaux
- GPS
- Planification