Aller au contenu

Rechercher sur le site

Échap pour fermer · Ctrl K ou ⌘ K pour ouvrir la recherche

CoursProgrammation & PythonNotion transversale

Cours Algorithmique

Autres ressources — Programmation & Python

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)

Retour à Programmation & Python