Machine de Turing et paradigmes de programmation : fondements de l'informatique théorique

Francés6,55 KB

La machine de Turing

La machine de Turing est une machine théorique, inventée par Alan Turing en 1936, pour servir de modèle idéal lors d'un calcul mathématique. Ce modèle est toujours largement utilisé en informatique théorique, en particulier pour résoudre les problèmes de complexité algorithmique et de calculabilité.

Les composants d'une machine de Turing

  • Un ruban divisé en cases adjacentes. Chaque case contient un symbole parmi un alphabet fini. L'alphabet contient un symbole spécial « blanc » et un ou plusieurs autres symboles. Le ruban est de longueur infinie vers la gauche ou vers la droite. On considère que les cases non encore écrites du ruban contiennent le symbole « blanc ».
  • Une tête de lecture qui peut lire et écrire les symboles sur le ruban, et se déplacer vers la gauche ou vers la droite du ruban.
  • Un registre d'état qui mémorise l'état courant de la machine de Turing. Le nombre d'états possibles est toujours fini, et il existe un état spécial appelé état de départ, qui est l'état initial de la machine avant son exécution.
  • Une table d'actions qui indique à la machine quel symbole écrire, comment déplacer la tête de lecture d'une case vers la droite ou vers la gauche, et quel est le nouvel état, en fonction du symbole lu sur le ruban et de l'état courant de la machine. Si aucune action n'existe pour une combinaison donnée d'un symbole lu et d'un état courant, la machine s'arrête.

Les machines de Turing : une abstraction des ordinateurs

  • Le ruban représente la mémoire de l'ordinateur. Ceci comprend la mémoire centrale ainsi que les mémoires externes telles que les disques durs. Contrairement à un ordinateur, la mémoire d'une machine de Turing est infinie.
  • La tête de lecture représente le bus qui relie le microprocesseur à la mémoire. Une autre différence entre une machine de Turing et un ordinateur est que l'ordinateur peut accéder à la mémoire de manière directe, alors que la tête de lecture de la machine de Turing ne se déplace que d'une position à la fois.
  • Le registre d'état et la table d'actions représentent le microprocesseur. Le nombre d'états est fini, comme dans la réalité.

Pseudo-code

En programmation, le pseudo-code est une façon de décrire un algorithme en respectant certaines conventions, mais sans référence à un langage de programmation en particulier. L'écriture en pseudo-code permet de développer une démarche structurée, en oubliant temporairement la syntaxe rigide d'un langage de programmation.

Transformation du code source

Le code source n'est jamais utilisable tel quel. Il est généralement écrit dans un langage de haut niveau, compréhensible pour l'homme, mais pas pour la machine. Il existe deux stratégies de traduction, ces deux stratégies étant parfois disponibles au sein du même langage :

  • L'interprétation : le langage traduit les instructions au fur et à mesure qu'elles se présentent. Cela s'appelle la compilation à la volée, ou l'interprétation.
  • La compilation : le langage commence par traduire l'ensemble du programme en langage machine, constituant ainsi un deuxième programme distinct physiquement et logiquement du premier. Ensuite, et ensuite seulement, il exécute ce second programme.

Compilation

Certains langages sont compilés. En toute généralité, la compilation est l'opération qui consiste à transformer un langage source en un langage cible. Dans le cas d'un programme, le compilateur va transformer tout le texte représentant le code source du programme en code compréhensible pour la machine, appelé code machine.

Interprétation

D'autres langages ne nécessitent pas de phase spéciale de compilation. La méthode employée pour exécuter le programme est alors différente. Le programme entier n'est jamais compilé. Chaque ligne de code est compilée en temps réel par un programme. On dit de ce programme qu'il interprète le code source.

Avantages et inconvénients

Les avantages généralement retenus pour l'utilisation de langages compilés sont qu'ils sont plus rapides à l'exécution que les langages interprétés, car l'interpréteur doit être lancé à chaque exécution du programme, ce qui mobilise systématiquement les ressources.

Les langages interprétés offrent en revanche une certaine portabilité, ainsi qu'une facilité pour l'écriture du code. En effet, il n'est pas nécessaire de passer par la phase de compilation pour tester le code source.

Paradigmes de programmation

Un paradigme est une façon de programmer, un modèle qui oriente notre manière de penser pour formuler et résoudre un problème.

Programmation impérative

C'est le paradigme le plus ancien. Les recettes de cuisine et les itinéraires routiers sont deux exemples familiers qui s'apparentent à de la programmation impérative.

  • La programmation structurée constitue un sous-ensemble de la programmation impérative.

Programmation orientée objet

La programmation orientée objet est un paradigme de programmation informatique qui consiste en la définition et l'assemblage de briques logicielles appelées objets.

Programmation fonctionnelle

La programmation fonctionnelle est un paradigme de programmation qui considère le calcul en tant qu'évaluation de fonctions mathématiques et rejette le changement d'état et la mutation des données. Elle souligne l'application des fonctions, contrairement au modèle de programmation impérative qui met en avant les changements d'état.

Les notions principales de la programmation

La plupart des langages de programmation ont des caractéristiques communes que nous allons passer rapidement en revue ici.

L'affectation

Une affectation est une opération qui permet d'attribuer une valeur à une variable. Pour expliquer ce qui se passe lors d'une affectation, il faut imaginer qu'il existe, dans un recoin de l'ordinateur, une case mémoire appelée x.

L'incrémentation

Il arrive fréquemment que l'on doive incrémenter une variable, c'est-à-dire augmenter sa valeur d'une ou plusieurs unités.

Descargar

PDF Word HTML