Cours Algorithmique
Autres ressources — Programmation & Python
- Cours ProgrammationCours · Cours détaillé
- Travaux dirigés AlgorithmiqueActivités
- Travaux dirigés ProgrammationActivités
- Quiz fondamental AlgorithmiqueQuiz
- Quiz approfondi AlgorithmiqueQuiz
- Quiz fondamental ProgrammationQuiz
- Quiz approfondi ProgrammationQuiz
- Vidéos AlgorithmiqueVidéos
- Vidéos ProgrammationVidéos
- Bibliographie AlgorithmiqueRessources et sources
- Bibliographie ProgrammationRessources et sources
1. Algorithmes et Complexité
Apprenez les bases de l'algorithmique.
Qu'est-ce qu'un algorithme ?
Un algorithme est une suite d'ÉTAPES pour résoudre un problème :
- Précis : Instructions claires
- Complet : résout le problème entièrement
- Efficace : Utilise peu de ressources
- Correct : Donne le bon résultat
Exemple : Recherche linéaire
def recherche_lineaire(liste, cible): for i in range(len(liste)): if liste[i] == cible: return i return -1 # Non trouvé # Complexité : O(n)
Complexité algorithmique
- O(1) : Accès direct (très rapide)
- O(log n) : Recherche binaire
- O(n) : Boucle simple
- O(n) : Boucles imbriquées
- O(2^n) : Exponentielle (très lent)
2. Tri et Recherche
Les algorithmes de tri et recherche essentiels.
Tri par sélection
Trouve le minimum et le place au début :
def tri_selection(liste): for i in range(len(liste)): min_idx = i for j in range(i+1, len(liste)): if liste[j] < liste[min_idx]: min_idx = j liste[i], liste[min_idx] = liste[min_idx], liste[i] return liste # Complexité : O(n)
Recherche binaire
Divise l'espace de recherche par 2 à chaque ÉTAPE :
- Plus rapide que recherche linéaire
- Nécessite une liste triée
- Complexité : O(log n)
Tri par fusion (Merge sort)
- Diviser pour conquérir
- Complexité : O(n log n)
- Très utilisé en pratique
3. Structures de données avancées
Graphes, arbres et structures spécialisées.
Arbres binaires
Structure hiérarchique avec jusqu'à 2 enfants par nœud :
- Racine : Nœud supérieur
- Feuilles : Nœuds sans enfants
- BST : Arbre binaire de recherche
Graphes
Ensemble de nœuds connectés par des arêtes :
- Orienté vs Non-orienté
- Pondéré vs Non-pondéré
- Applications : réseaux sociaux, GPS
Parcours de graphes
- BFS (Breadth-First) : Par largeur
- DFS (Depth-First) : Par profondeur
- Dijkstra : Plus court chemin
Crédits et Licences
Ce cours intègre du contenu libres de droits :
- Contenu original : CC-BY-SA 4.0 (SNT Seconde Platform)
- Références de programmation : Open source (Python.org, MDN)
- Images et icônes : Domaine public ou CC0
- Vidéos : Licences libres (indiquées dans video)