par Mark Shead
Une introduction aux concepts informatiques
L’informatique nous permet de programmer, mais il est possible de faire beaucoup de programmation sans comprendre les concepts informatiques sous-jacents.
Ce n’est pas toujours une mauvaise chose. Lorsque nous programmons, nous travaillons à un niveau d’abstraction beaucoup plus élevé.
Lorsque nous conduisons une voiture, nous ne nous préoccupons que de deux ou trois pédales, d’un levier de vitesse et d’un volant. Vous pouvez conduire une voiture en toute sécurité sans avoir une idée précise de son fonctionnement.
Cependant, si vous voulez conduire une voiture aux limites de ses capacités, vous devez en savoir beaucoup plus sur les automobiles que les trois pédales, le changement de vitesse et le volant.
C’est la même chose pour la programmation. Un grand nombre de travaux quotidiens peuvent être accomplis avec peu ou pas de compréhension de l’informatique. Vous n’avez pas besoin de comprendre la théorie du calcul pour construire un formulaire « Contact Us » en PHP.
Cependant, si vous envisagez d’écrire du code qui nécessite un calcul sérieux, vous devrez comprendre un peu plus comment le calcul fonctionne sous le capot.
Le but de cet article est de fournir un contexte fondamental pour le calcul. S’il y a de l’intérêt, je pourrais suivre avec des sujets plus avancés, mais pour le moment, je veux examiner la logique derrière l’un des dispositifs de calcul abstraits les plus simples – une machine à états finis.
Machines à états finis
Une machine à états finis est une abstraction mathématique utilisée pour concevoir des algorithmes.
En termes plus simples, une machine à états va lire une série d’entrées. Lorsqu’elle lit une entrée, elle va passer à un état différent. Chaque état spécifie vers quel état basculer, pour une entrée donnée. Cela semble compliqué mais c’est en réalité très simple.
Imaginez un appareil qui lit une longue feuille de papier. Pour chaque pouce de papier, il y a une seule lettre imprimée dessus – soit la lettre ‘a’, soit la lettre ‘b’.
Lorsque la machine à états lit chaque lettre, elle change d’état. Voici une machine à états très simple :
Les cercles sont les « états » dans lesquels peut se trouver la machine. Les flèches sont les transitions. Ainsi, si vous êtes dans l’état s et que vous lisez un ‘a’, vous passerez à l’état q. Si vous lisez un ‘b’, vous resterez dans l’état s.
Donc, si nous commençons sur s et que nous lisons la bande de papier ci-dessus de gauche à droite, nous lirons le ‘a’ et passerons à l’état q.
Puis, nous lirons ‘b’ et reviendrons à l’état s.
Un autre ‘b’ nous maintiendra sur s, suivi d’un ‘a’ – qui nous ramène à l’état q. C’est assez simple, mais quel est l’intérêt ?
Eh bien, il s’avère que vous pouvez faire passer une bande par la machine à états et dire quelque chose sur la séquence de lettres, en examinant l’état sur lequel vous finissez.
Dans notre machine à états simple ci-dessus, si nous finissons dans l’état s, la bande doit se terminer par une lettre ‘b’. Si nous terminons dans l’état q, la bande se termine par la lettre ‘a’.
Cela peut sembler inutile, mais il y a énormément de problèmes qui peuvent être résolus avec ce type d’approche. Un exemple très simple serait de déterminer si une page de HTML contient ces balises dans cet ordre :
<html> <head> </head> <body> </body> </html>La machine à états peut se déplacer vers un état qui montre qu’elle a lu la balise html, boucler jusqu’à ce qu’elle arrive à la balise head, boucler jusqu’à ce qu’elle arrive à la balise head close, et ainsi de suite.
Si elle parvient avec succès à l’état final, alors vous avez ces balises particulières dans le bon ordre.
Les machines à états finis peuvent également être utilisées pour représenter de nombreux autres systèmes – comme la mécanique d’un parcmètre, d’un distributeur de boissons gazeuses, d’une pompe à essence automatisée, et toutes sortes d’autres choses.
Machines à états finis déterministes
Les machines à états que nous avons examinées jusqu’à présent sont toutes des machines à états déterministes. À partir de n’importe quel état, il n’y a qu’une seule transition pour toute entrée autorisée. En d’autres termes, il ne peut pas y avoir deux chemins menant hors d’un état lorsque vous lisez la lettre ‘a’. Au début, cela semble même idiot de faire cette distinction.
À quoi sert un ensemble de décisions si la même entrée peut entraîner le passage à plus d’un état ? Vous ne pouvez pas dire à un ordinateur, if x == true puis exécuter doSomethingBig ou exécuter doSomethingSmall, vous le pouvez ?
Et bien, vous le pouvez en quelque sorte avec une machine à états.
La sortie d’une machine à états est son état final. Il passe par tous ses traitements, puis l’état final est lu, et ensuite une action est prise. Une machine à états ne fait rien lorsqu’elle passe d’un état à l’autre.
Elle traite, et lorsqu’elle arrive à la fin, l’état est lu et quelque chose d’externe déclenche l’action souhaitée (par exemple, distribuer une canette de soda). C’est un concept important lorsqu’il s’agit d’automates finis non déterministes.
Les automates finis non déterministes
Les automates finis non déterministes sont des automates finis où une entrée donnée d’un état particulier peut conduire à plus d’un état différent.
Par exemple, disons que nous voulons construire une machine à états finis capable de reconnaître des chaînes de lettres qui :
- commencent par la lettre ‘a’
- et sont ensuite suivies par zéro ou plusieurs occurrences de la lettre ‘b’
- ou, zéro ou plusieurs occurrences de la lettre ‘c’
- se terminent par la lettre suivante de l’alphabet.
Les chaînes de caractères valides seraient :
- abbbbbbbc
- abbbc
- acccd
- acccccd
- ac (zéro occurrences de b)
- ad (zéro occurrences de c)
Il reconnaîtra donc la lettre ‘a’ suivie de zéro ou plus de la même lettre de ‘b’ ou ‘c’, suivie de la lettre suivante de l’alphabet.
Une façon très simple de représenter cela est avec une machine à états qui ressemble à celle ci-dessous, où un état final de t signifie que la chaîne a été acceptée et correspond au motif.
Vous voyez le problème ? À partir du point de départ s, nous ne savons pas quel chemin prendre. Si nous lisons la lettre ‘a’, nous ne savons pas s’il faut aller à l’état q ou r.
Il existe plusieurs façons de résoudre ce problème. La première est le retour en arrière. Il suffit de prendre tous les chemins possibles, et d’ignorer ou de faire marche arrière sur ceux où l’on est bloqué.
C’est en gros comme cela que fonctionnent la plupart des ordinateurs qui jouent aux échecs. Ils examinent toutes les possibilités – et toutes les possibilités de ces possibilités – et choisissent le chemin qui leur donne le plus grand nombre d’avantages sur leur adversaire.
L’autre option consiste à convertir la machine non déterministe en une machine déterministe.
L’un des attributs intéressants d’une machine non déterministe est qu’il existe un algorithme permettant de transformer toute machine non déterministe en une machine déterministe. Cependant, c’est souvent beaucoup plus compliqué.
Heureusement pour nous, l’exemple ci-dessus n’est que légèrement plus compliqué. En fait, celui-ci est suffisamment simple pour que nous puissions le transformer en une machine déterministe dans notre tête, sans l’aide d’un algorithme formel.
La machine ci-dessous est une version déterministe de la machine non déterministe ci-dessus. Dans la machine ci-dessous, un état final de t ou v est atteint par toute chaîne de caractères qui est acceptée par la machine.
Le modèle non déterministe a quatre états et six transitions. Le modèle déterministe a six états, dix transitions et deux états finaux possibles.
Ce n’est pas beaucoup plus, mais la complexité croît généralement de façon exponentielle. Une machine non déterministe de taille modérée peut produire une machine déterministe absolument énorme.
Expressions régulières
Si vous avez fait un quelconque type de programmation, vous avez probablement rencontré des expressions régulières. Les expressions régulières et les machines à états finis sont fonctionnellement équivalentes. Tout ce que vous pouvez accepter ou faire correspondre avec une expression régulière, peut être accepté ou mis en correspondance avec une machine à états.
Par exemple, le motif décrit ci-dessus pourrait être mis en correspondance avec l’expression régulière : a(b*c|c*d)
Les expressions régulières et les machines à états finis ont également les mêmes limites. En particulier, elles ne peuvent toutes deux correspondre ou accepter que des motifs qui peuvent être traités avec une mémoire finie.
Alors, quel type de motifs ne peuvent-elles pas correspondre ? Disons que vous voulez seulement faire correspondre des chaînes de ‘a’ et ‘b’, où il y a un certain nombre de ‘a’ suivis d’un nombre égal de ‘b’. Ou n ‘a’ suivis de n ‘b’, où n est un nombre quelconque.
Des exemples seraient :
- ab
- aabb
- aaaaabbbb
- aaaaaaaaaaaaaaaabbbbbbbbbbbbbb
Au début, cela semble être un travail facile pour une machine à états finis. Le problème est que vous allez rapidement manquer d’états, ou vous devrez supposer un nombre infini d’états – à quel point ce n’est plus une machine à états finis.
Disons que vous créez une machine à états finis qui peut accepter jusqu’à 20 ‘a’ suivis de 20 ‘b’. Cela fonctionne bien, jusqu’à ce que vous obteniez une chaîne de 21 ‘a’ suivis de 21 ‘b’ – à ce moment-là, vous devrez réécrire votre machine pour gérer une chaîne plus longue.
Pour toute chaîne que vous pouvez reconnaître, il y en a une juste un peu plus longue que votre machine ne peut pas reconnaître parce qu’elle manque de mémoire.
C’est ce qu’on appelle le lemme de pompage qui dit essentiellement : » si votre motif a une section qui peut être répétée (comme celle) ci-dessus, alors le motif n’est pas régulier « .
En d’autres termes, on ne peut construire ni une expression régulière ni une machine à états finis qui reconnaîtra toutes les chaînes qui correspondent au motif.
Si vous regardez attentivement, vous remarquerez que ce type de motif où chaque » a » a un » b » correspondant, ressemble beaucoup à HTML. Dans toute paire de balises, vous pouvez avoir un nombre quelconque d’autres paires de balises correspondantes.
Donc, alors que vous pouvez être capable d’utiliser une expression régulière ou une machine à états finis pour reconnaître si une page de HTML possède les balises <html>, <head> ; et <body> éléments dans le bon ordre, vous ne pouvez pas utiliser une expression régulière pour dire si une page HTML entière est valide ou non – car le HTML n’est pas un motif régulier.
Machines de Turing
Alors, comment reconnaître les motifs non réguliers ?
Il existe un dispositif théorique similaire à une machine à états, appelé machine de Turing. Elle est similaire à une machine à états finis en ce sens qu’elle possède une bande de papier qu’elle lit. Mais, une machine de Turing peut effacer et écrire sur la bande de papier.
Expliquer une machine de Turing prendra plus d’espace que nous avons ici, mais il y a quelques points importants pertinents pour notre discussion sur les machines à états finis et les expressions régulières.
Les machines de Turing sont complètes sur le plan computationnel – ce qui signifie que tout ce qui peut être calculé, peut être calculé sur une machine de Turing.
Puisqu’une machine de Turing peut écrire aussi bien que lire sur la bande de papier, elle n’est pas limitée à un nombre fini d’états. On peut supposer que la bande de papier est d’une longueur infinie. Bien sûr, les ordinateurs actuels ne disposent pas d’une quantité infinie de mémoire. Mais, en général, ils contiennent suffisamment de mémoire pour ne pas atteindre la limite pour le type de problèmes qu’ils traitent.
Les machines deTuring nous donnent un dispositif mécanique imaginaire qui nous permet de visualiser et de comprendre le fonctionnement du processus de calcul. C’est particulièrement utile pour comprendre les limites du calcul. S’il y a de l’intérêt, je ferai un autre article sur les machines de Turing à l’avenir.
Pourquoi est-ce important ?
Alors, quel est l’intérêt ? Comment cela va-t-il vous aider à créer ce prochain formulaire PHP ?
Malgré leurs limites, les machines à états sont un concept très central en informatique. En particulier, il est significatif que pour toute machine à états non déterministe que vous pouvez concevoir, il existe une machine à états déterministe qui fait la même chose.
C’est un point clé, car cela signifie que vous pouvez concevoir votre algorithme de la manière la plus facile à penser. Une fois que vous avez un algorithme fonctionnel, vous pouvez le convertir dans n’importe quelle forme la plus efficace.
La compréhension du fait que les machines à états finis et les expressions régulières sont fonctionnellement équivalentes ouvre la voie à des utilisations incroyablement intéressantes pour les moteurs d’expression régulière – en particulier lorsqu’il s’agit de créer des règles commerciales qui peuvent être modifiées sans recompiler un système.
Une base en informatique vous permet de prendre un problème que vous ne savez pas résoudre et de raisonner : « Je ne sais pas comment résoudre X, mais je sais comment résoudre Y. Et je sais comment convertir une solution pour Y en une solution pour X. Par conséquent, je sais maintenant comment résoudre X. »
Si vous aimez cet article, vous apprécierez peut-être ma chaîne YouTube où je crée occasionnellement une vidéo ou un dessin animé sur un aspect de la création de logiciels. J’ai également une liste de diffusion pour les personnes qui souhaitent recevoir un courriel occasionnel lorsque je produis quelque chose de nouveau.
Originally published at blog.markshead.com on February 11, 2018.