Meilleur cas
Situation la plus favorable. Une recherche séquentielle trouve par exemple la valeur dès la première case : O(1).
Terminale NSI • Algorithmique • Langages
Complexité et calculabilité
Mesurer le coût d’un algorithme, comprendre ce qui est calculable, découvrir la machine de Turing et distinguer calculabilité, décidabilité et efficacité.
⚙️ 🧠
1. Complexité algorithmique
Combien de ressources faut-il quand la taille n de l’entrée augmente ?
La complexité en temps estime le nombre d’opérations élémentaires effectuées par un algorithme en fonction de la taille n de l’entrée. On s’intéresse surtout à l’ordre de grandeur, pas au temps en secondes, qui dépend de la machine.
Idée clé : pour de grandes entrées, on conserve le terme dominant. Ainsi
3n² + 5n + 12 est de complexité quadratique, notée O(n²).| Complexité | Nom | Exemple typique |
|---|---|---|
| O(1) | constante | accéder à L[0] |
| O(log n) | logarithmique | recherche dichotomique |
| O(n) | linéaire | parcourir une liste |
| O(n log n) | quasi-linéaire | tri fusion |
| O(n²) | quadratique | deux boucles imbriquées sur n |
| O(2ⁿ) | exponentielle | exploration exhaustive de sous-ensembles |
POUR i allant de 0 à n-1
afficher(T[i])
// n passages : coût linéaire O(n)POUR i allant de 0 à n-1
POUR j allant de 0 à n-1
traiter(T[i], T[j])
// n × n passages : coût quadratique O(n²)2. Cas favorable, moyen et pire cas
Une même taille d’entrée peut conduire à des coûts différents
Pire cas
Situation la plus coûteuse. Pour une recherche séquentielle, la valeur est absente ou en dernière position : O(n).
Comparaison
Deux algorithmes qui résolvent le même problème peuvent avoir des complexités très différentes. La recherche dichotomique est O(log n), mais exige une collection triée.
3. Calculabilité : qu’est-ce qu’une machine peut calculer ?
Une limite fondamentale, différente de la vitesse
Une fonction est dite calculable s’il existe un algorithme permettant d’obtenir son résultat pour toute entrée de son domaine en un nombre fini d’étapes. Les langages usuels comme Python sont considérés comme ayant, en théorie, la même puissance de calcul que le modèle de la machine de Turing.
Calculable
Il existe une procédure algorithmique qui termine et fournit le résultat attendu pour toutes les entrées autorisées.
Non calculable
Il n’existe aucun algorithme capable de résoudre le problème demandé dans tous les cas. Ajouter de la puissance de calcul ne règle pas cette impossibilité théorique.
Attention
Difficile ne signifie pas non calculable. Un algorithme exponentiel peut être très lent tout en calculant effectivement le résultat.
Thèse de Church-Turing : intuitivement, tout ce qui est calculable par une procédure effective peut être calculé par une machine de Turing. C’est une thèse fondatrice, pas un théorème démontré à partir d’une définition indépendante de « procédure effective ».
4. Alan Turing et la machine de Turing
Un modèle théorique volontairement très simple
En 1936, Alan Turing décrit un modèle abstrait permettant de formaliser la notion de calcul. Une machine de Turing possède un ruban théoriquement infini découpé en cases, une tête de lecture-écriture, un ensemble fini d’états et une table de transitions.
□
1
0
▲
▲
1
□
À chaque étape, la machine : lit le symbole sous la tête → selon l’état courant, écrit éventuellement un symbole → se déplace d’une case à gauche ou à droite → change éventuellement d’état.
Lire un simulateur de machine de Turing
Repère toujours : l’état courant, le symbole lu, puis applique exactement la transition « symbole écrit, déplacement, nouvel état ». Répète jusqu’à atteindre un état d’arrêt. Le simulateur ne fait qu’automatiser cette succession de transitions.
// Exemple de règle de transition
(q0, 0) → (q1, 1, Droite)
// En état q0, si la tête lit 0 :
écrire 1
déplacer la tête vers la droite
passer dans l’état q15. Décidabilité et problème de l’arrêt
Certains problèmes n’admettent aucun algorithme général
Un problème de décision attend une réponse oui/non. Il est décidable s’il existe un algorithme qui termine pour toute entrée et donne toujours la bonne réponse.
Le problème de l’arrêt
Peut-on écrire un programme universel qui reçoit n’importe quel programme P et une entrée E et détermine toujours si P finira par s’arrêter sur E ? Non. Turing a montré qu’un tel algorithme général n’existe pas : le problème de l’arrêt est indécidable.
Cela ne signifie pas qu’on ne peut jamais savoir si un programme particulier s’arrête. Pour beaucoup de programmes, on peut le démontrer. L’impossibilité porte sur l’existence d’un algorithme universel correct pour tous les programmes et toutes les entrées.
6. Écrire du pseudo-code
Décrire un algorithme sans dépendre de la syntaxe d’un langage
Le pseudo-code doit être lisible, précis et non ambigu. On y décrit les entrées, les sorties, les affectations, conditions, boucles et appels de fonctions. Il n’existe pas une syntaxe universelle unique : l’important est la cohérence.
ALGORITHME maximum
ENTRÉE T, tableau non vide
SORTIE la plus grande valeur de T
max ← T[0]
POUR chaque valeur x de T à partir de la deuxième
SI x > max ALORS
max ← x
FIN SI
FIN POUR
RENVOYER max← n’est pas =
x ← 3 signifie « affecter 3 à x ». Une comparaison peut s’écrire x = 3 ? ou avec une convention clairement définie.
Indenter
L’indentation rend visibles les blocs d’une condition ou d’une boucle, comme en Python.
Rester abstrait
Éviter les détails propres à Python si le but est d’exprimer l’algorithme indépendamment du langage.
7. Les distinctions à connaître au bac
Terminaison
Un algorithme termine-t-il après un nombre fini d’étapes ?
Correction
S’il termine, produit-il le résultat spécifié ? Correction + terminaison donnent un algorithme correct.
Complexité
Combien de ressources consomme un algorithme qui existe ?
Calculabilité
Existe-t-il seulement un algorithme capable de résoudre le problème dans tous les cas ?
QCM : complexité et calculabilité
20 questions • score sur 20