Au programme de ce chapitre
- I. La machine de Turing et les limites de la calculabilité
- II. Algorithmes et complexité : le coût du calcul
- III. Réseaux de neurones et apprentissage automatique
- Savoir-faire
- Exercices types corrigés
- Teste-toi — vrai ou faux ?
- Pièges fréquents et astuces
- À retenir
La définition à retenir
Définition Une machine de Turing, décrite par Alan Turing en 1936, est un modèle abstrait de calcul composé d'un ruban infini divisé en cases contenant des symboles, d'une tête de lecture-écriture qui se déplace case par case, et d'une table de transitions qui indique, selon l'état courant de la machine et le symbole lu, quel symbole écrire, dans quel sens se déplacer et dans quel nouvel état passer.
🔒 Illustration du chapitre completIncluse dans le cours complet, avec la méthode et les exercices corrigés.La voir gratuitement pendant 7 jours
Un exemple corrigé
Exemple Pour n = 10, un algorithme linéaire (O(n)) effectue 10 opérations, un algorithme quadratique (O(n²)) en effectue 100, et un algorithme exponentiel (O(2ⁿ)) en effectue 1 024. Pour n = 30, ces nombres deviennent respectivement 30, 900 et plus d'un milliard (2³⁰ = 1 073 741 824) : un algorithme exponentiel devient rapidement inutilisable en pratique, même sur des ordinateurs très puissants, alors qu'un algorithme linéaire ou quadratique reste praticable.
Les erreurs fréquentes à éviter
Piège. L'IA actuelle n'est pas « consciente » : elle traite des données ; ne confonds pas performance et conscience.
Attention Une intelligence artificielle fondée sur l'apprentissage automatique ne « comprend » pas au sens humain du terme : elle généralise des régularités statistiques observées dans ses données d'entraînement, ce qui explique à la fois ses performances impressionnantes sur des tâches bien définies et ses erreurs parfois absurdes (biais des données d'entraînement, incapacité à raisonner hors du domaine appris).
L'astuce du prof
Astuce. Relie l'histoire : machine de Turing (théorie) → algorithmes → apprentissage automatique (IA).
Exercices corrigés
Cherche d'abord seul, puis ouvre la correction.
Exercice 1
Qu'est-ce que la machine de Turing ?
Voir la correction
Un modèle théorique de calcul imaginé par Turing, fondement de l'informatique moderne.
Exercice 2
Qu'est-ce que l'apprentissage automatique (machine learning) ?
Voir la correction
Une approche où la machine apprend à partir de données plutôt que d'être programmée explicitement pour chaque cas.