Calculabilité

Concepts en informatique

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Qu’est-ce que la calculabilité ?

Problème calculable

Existence d’algorithme : Une procédure claire existe.
Temps fini : Produit un résultat en un nombre limité d’étapes.

Problème non calculable

Absence d’algorithme : Impossible à résoudre pour toutes les entrées.
Calcul infini : Peut ne jamais conclure.

¹ Des problèmes non calculables peuvent devenir calculables si l’on trouve un algorithme et/ou si l’on fait terminer un algorithme connu en temps fini.

Automates

Définition d’automate

Machines imaginaires
Aident à comprendre le calcul
Ont des états
Ont des règles de transition entre états

Image d’un feu tricolore comme analogie représentant les automates

Automates finis (FA)

Automates finis (FA)

Machines simples
Nombre d’états fixe
Pas de mémoire au-delà de l’état courant

Image d’un feu tricolore et d’états comme analogie des automates finis

Automates à pile (PDA)

Automates à pile (PDA)

Plus puissants
Ont des états
Mémoire par pile pour des décisions plus complexes

Image d’un feu tricolore et d’états comme analogie des automates à pile

Récapitulatif

Automates finis (FA)

Utiles pour des tâches simples

Automates à pile (PDA)

Plus puissants pour des problèmes plus complexes

Importance

Si un problème se modélise par un automate, on PEUT implémenter un algorithme pour le résoudre

Passons à la pratique !

Concepts en informatique