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'un 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 aboutir.

¹ Les problèmes non calculables peuvent devenir calculables dès qu'on trouve un algorithme et/ou qu'on fait en sorte qu'un algorithme connu termine en temps fini.

Automates

Définition des automates

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

Image d'un feu de circulation comme analogie représentant les automates

Automate fini (FA)

Automate fini (FA)

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

Image d'un feu de circulation et d'états comme analogie pour l'automate fini

Automate à pile (PDA)

Automate à pile (PDA)

Plus puissant
Possède des états
Mémoire à pile pour des décisions plus complexes

Image d'un feu de circulation et d'états comme analogie pour l'automate à pile

Résumé

Automate fini (FA)

Utile pour des tâches simples

Automate à pile (PDA)

Plus puissant pour des problèmes plus complexes

Importance

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

Passons à la pratique !

Concepts en informatique