Cours Complet en Algorithmique avec Python
Modules du Cours
Module 1 : La récursivité
1.1 Introduction à la récursivité
- Définition : une fonction qui s’appelle elle-même pour résoudre un problème.
- Cas de base : condition d’arrêt qui empêche les appels infinis.
- Cas récursif : décomposition du problème en sous-problèmes.
1.2 Exemple simple
def factorielle(n):
if n == 0 or n == 1:
return 1
return n * factorielle(n - 1)
1.3 Concepts clés
- Pile d’appels (stack).
- Récursivité terminale (tail recursion).
- Optimisation : mémoïsation avec functools.lru_cache.
Exercice : Écrire une fonction récursive pour calculer la suite de Fibonacci avec et sans
mémoïsation.
Module 2 : Les algorithmes de tri
2.1 Tri à bulles
- Complexité : O(n²)
- Exemple : comparer et échanger deux éléments adjacents.
def bubble_sort(tab):
n = len(tab)
for i in range(n):
for j in range(0, n-i-1):
if tab[j] > tab[j+1]:
tab[j], tab[j+1] = tab[j+1], tab[j]
return tab
2.2 Tri rapide (QuickSort)
- Complexité moyenne : O(n log n)
- Principe : diviser pour régner.
def quick_sort(tab):
if len(tab) <= 1:
return tab
pivot = tab[len(tab) // 2]
gauche = [x for x in tab if x < pivot]
milieu = [x for x in tab if x == pivot]
droite = [x for x in tab if x > pivot]
return quick_sort(gauche) + milieu + quick_sort(droite)
Exercice : Implémenter le tri par insertion et comparer sa performance avec le tri rapide.
Module 3 : Les algorithmes de recherche
3.1 Recherche linéaire
def recherche_lineaire(tab, x):
for i in range(len(tab)):
if tab[i] == x:
return i
return -1
3.2 Recherche binaire (sur tableau trié)
def recherche_binaire(tab, x):
g, d = 0, len(tab) - 1
while g <= d:
m = (g + d) // 2
if tab[m] == x:
return m
elif tab[m] < x:
g=m+1
else:
d=m-1
return -1
3.3 Recherche dans les graphes : BFS et DFS
from collections import deque
def bfs(graph, start):
visite = set([start])
file = deque([start])
while file:
sommet = [Link]()
print(sommet, end=" ")
for voisin in graph[sommet]:
if voisin not in visite:
[Link](voisin)
[Link](voisin)
Exercice : Implémenter DFS récursif et itératif sur un graphe.
Module 4 : Programmation générique en Python
4.1 Fonctions génériques
def identite(x):
return x
4.2 Décorateurs (fonction prenant une autre fonction en paramètre)
def mon_decorateur(f):
def wrapper(*args, **kwargs):
print("Avant l’exécution")
result = f(*args, **kwargs)
print("Après l’exécution")
return result
return wrapper
@mon_decorateur
def dire_bonjour():
print("Bonjour!")
4.3 Types génériques avec [Link]
from typing import TypeVar, Generic, List
T = TypeVar('T')
class Boite(Generic[T]):
def __init__(self, contenu: T):
[Link] = contenu
ma_boite = Boite[int](5)
4.4 Fonctions d’ordre supérieur et itertools/functools
- map, filter, reduce
- [Link], permutations, combinations
Exercice : Créer une fonction générique qui prend une liste et applique une opération donnée
(lambda) à chaque élément.
---
Fin du cours. Chaque module inclut explications, code, et exercices pratiques.