{"id":159,"date":"2022-01-25T18:53:54","date_gmt":"2022-01-25T18:53:54","guid":{"rendered":"https:\/\/9h15.net\/activ\/?p=159"},"modified":"2022-01-25T19:50:06","modified_gmt":"2022-01-25T19:50:06","slug":"c-et-c-tp2","status":"publish","type":"post","link":"https:\/\/9h15.net\/activ\/c-et-c-tp2\/","title":{"rendered":"C et C++ TP2"},"content":{"rendered":"<p><code>Par O. Bailleux, Ma\u00eetre de conf\u00e9rences HDR \u00e0 l'universit\u00e9 de Bourgogne.<\/code><\/p>\n<h1><a id=\"tp2\" class=\"anchor\" aria-hidden=\"true\"><\/a>TP2<\/h1>\n<p>Le but de ce TP est de r\u00e9aliser un simulateur de machine de Turing en langage C.<\/p>\n<h2><a id=\"1-la-machine-de-turing%C3%A0-r%C3%A9aliser\" class=\"anchor\" aria-hidden=\"true\"><\/a>1. La machine de Turing \u00e0 r\u00e9aliser<\/h2>\n<p>La machine que nous allons simuler est constitu\u00e9e :<\/p>\n<ul>\n<li>d&rsquo;une <strong>bande<\/strong> comportant des cases contenant des symboles,<\/li>\n<li>d&rsquo;une <strong>variable d&rsquo;\u00e9tat<\/strong> contenant un entier positif ou nul,<\/li>\n<li>d&rsquo;une <strong>t\u00eate<\/strong> de lecture \/ \u00e9criture qui se situe en face d&rsquo;une des cases de la bande,<\/li>\n<li>d&rsquo;un <strong>programme<\/strong>.<\/li>\n<\/ul>\n<p>La <strong>bande<\/strong> comporte 32 cases. Chaque case contient un symbole parmi trois possibles : <code>#<\/code>, <code>0<\/code> et <code>1<\/code>. Le symbole <code>#<\/code> a pour r\u00f4le de d\u00e9limiter les donn\u00e9es plac\u00e9es sur la bande. Ces donn\u00e9es sont cod\u00e9es avec les symboles <code>0<\/code> et <code>1<\/code>.<\/p>\n<p>La <strong>variable d&rsquo;\u00e9tat<\/strong> peut prendre une valeur entre 0 et 7. L&rsquo;\u00e9tat 0 est appel\u00e9 <strong>\u00e9tat initial<\/strong>. C&rsquo;est l&rsquo;\u00e9tat de la machine au d\u00e9but de l&rsquo;ex\u00e9cution d&rsquo;un programme. L&rsquo;\u00e9tat 7 est appel\u00e9 <strong>\u00e9tat final<\/strong>. On le note <code>STOP<\/code> Il indique la fin de l&rsquo;ex\u00e9cution du programme de la machine.<\/p>\n<p>La <strong>t\u00eate<\/strong> est repr\u00e9sent\u00e9e par une variable dont la valeur, comprise entre 0 et 31, repr\u00e9sente la position sur la bande.<\/p>\n<p>Voici une repr\u00e9sentation sch\u00e9matique de la machine juste avant l&rsquo;ex\u00e9cution de son programme. Sa t\u00eate de lecture est en position 0 (visualis\u00e9e par le point sous la premi\u00e8re case). Son \u00e9tat est 0. Sa bande contient des valeurs qui repr\u00e9sentent la donn\u00e9e d&rsquo;entr\u00e9e du programme. Le programme n&rsquo;apparait pas sur le dessin.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/01\/1-8.png\" alt=\"image-20220116152617550\" \/><\/p>\n<p>On appelle <strong>situation<\/strong> le couple \\((v,e)\\) o\u00f9 \\(v\\) est la valeur de la case d\u00e9sign\u00e9e par la t\u00eate et \\(e\\) l&rsquo;\u00e9tat courant de la machine. La machine repr\u00e9sent\u00e9e ci-dessus est dans la situation <code>(valeur : #, \u00e9tat : 0)<\/code>.<\/p>\n<p>Le <strong>programme<\/strong> associe une <strong>action<\/strong> \u00e0 chaque <strong>situation<\/strong>. Une action indique ce que doit faire la machine \u00e0 la prochaine \u00e9tape d&rsquo;ex\u00e9cution du programme. Elle consiste en trois ordres :<\/p>\n<ul>\n<li>Une valeur \u00e0 \u00e9crire sur la bande \u00e0 l&#8217;emplacement actuel de la t\u00eate (qui peut \u00eatre identique ou diff\u00e9rente de la valeur actuelle).<\/li>\n<li>Un sens de d\u00e9placement de la t\u00eate : gauche ou droite. Le d\u00e9placement sera r\u00e9alis\u00e9 apr\u00e8s l&rsquo;\u00e9criture de la valeur.<\/li>\n<li>La valeur du nouvel \u00e9tat de de la machine (qui peut \u00eatre identique ou diff\u00e9rente de celle de l&rsquo;\u00e9tat actuel)<\/li>\n<\/ul>\n<p>Voici un exemple de programme&#8230;<\/p>\n<table>\n<thead>\n<tr>\n<th>Situation<\/th>\n<th>Action<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td><code>\u00e9tat = 0, valeur = #<\/code><\/td>\n<td><code>#, droite, 1<\/code><\/td>\n<\/tr>\n<tr>\n<td><code>\u00e9tat = 0, valeur = 0<\/code><\/td>\n<td><code>0, droite, STOP<\/code><\/td>\n<\/tr>\n<tr>\n<td><code>\u00e9tat = 0, valeur = 1<\/code><\/td>\n<td><code>1, droite, STOP<\/code><\/td>\n<\/tr>\n<tr>\n<td><code>\u00e9tat = 1, valeur = #<\/code><\/td>\n<td><code>#, gauche, 2<\/code><\/td>\n<\/tr>\n<tr>\n<td><code>\u00e9tat = 1, valeur = 0<\/code><\/td>\n<td><code>0, droite, 1<\/code><\/td>\n<\/tr>\n<tr>\n<td><code>\u00e9tat = 1, valeur = 1<\/code><\/td>\n<td><code>1, droite, 1<\/code><\/td>\n<\/tr>\n<tr>\n<td><code>\u00e9tat = 2, valeur = #<\/code><\/td>\n<td><code>#, droite, STOP<\/code><\/td>\n<\/tr>\n<tr>\n<td><code>\u00e9tat = 2, valeur = 0<\/code><\/td>\n<td><code>1, gauche, 3<\/code><\/td>\n<\/tr>\n<tr>\n<td><code>\u00e9tat = 2, valeur = 1<\/code><\/td>\n<td><code>0, gauche, 2<\/code><\/td>\n<\/tr>\n<tr>\n<td><code>\u00e9tat = 3, valeur = #<\/code><\/td>\n<td><code>#, droite, STOP<\/code><\/td>\n<\/tr>\n<tr>\n<td><code>\u00e9tat = 3, valeur = 0<\/code><\/td>\n<td><code>0, gauche, 3<\/code><\/td>\n<\/tr>\n<tr>\n<td><code>\u00e9tat = 3, valeur = 1<\/code><\/td>\n<td><code>1, gauche, 3<\/code><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>&#8230;qui peut \u00eatre repr\u00e9sent\u00e9 graphiquement comme ci-dessous :<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/01\/2-7.png\" alt=\"image-20220117150716016\" \/><\/p>\n<p>Pour ex\u00e9cuter ce programme, on regarde la situation actuelle, qui est <code>(valeur : #, \u00e9tat : 0)<\/code>. D&rsquo;apr\u00e8s le programme, l&rsquo;action \u00e0 r\u00e9aliser qui est <code>#, droite, 1<\/code>. La valeur <code>#<\/code> est plac\u00e9e dans la case d\u00e9sign\u00e9e par la t\u00eate, qui contenait d\u00e9j\u00e0 cette valeur, le nouvel \u00e9tat est 1 et la t\u00eate se d\u00e9place \u00e0 droite.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/01\/3-7.png\" alt=\"image-20220116162414446\" \/><\/p>\n<p>On regarde la nouvelle situation, <code>(valeur : 0, \u00e9tat : 1)<\/code>. D&rsquo;apr\u00e8s le programme, l&rsquo;action \u00e0 r\u00e9aliser est <code>0, droite, 1<\/code>.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/01\/4-8.png\" alt=\"image-20220116163234076\" \/><\/p>\n<p>Continuez \u00e0 ex\u00e9cuter le programme \u00e0 la main. Vous devriez obtenir la donn\u00e9e <code>#0100#<\/code> en d\u00e9but de bande lorsque l&rsquo;\u00e9tat final est atteint.<\/p>\n<h2><a id=\"2-conception-d-un-programme-de-simulation\" class=\"anchor\" aria-hidden=\"true\"><\/a>2. Conception d&rsquo;un programme de simulation<\/h2>\n<p>Nous sommes face \u00e0 un probl\u00e8me d&rsquo;ing\u00e9nierie logicielle. Nous devons r\u00e9aliser un programme qui <strong>simule la machine de Turing<\/strong> pr\u00e9sent\u00e9e dans le section pr\u00e9c\u00e9dente. La premi\u00e8re \u00e9tape consiste \u00e0 d\u00e9terminer comment la machine et son programme seront repr\u00e9sent\u00e9s. Ensuite, il faudra impl\u00e9menter les fonctions permettant de simuler l&rsquo;ex\u00e9cution du programme.<\/p>\n<h3><a id=\"repr%C3%A9sentation-de-la-machine\" class=\"anchor\" aria-hidden=\"true\"><\/a>Repr\u00e9sentation de la machine<\/h3>\n<p>Dans le cadre de ce TP, nous utiliseront la repr\u00e9sentation suivante de la machine sans son programme :<\/p>\n<ul>\n<li>La bande est repr\u00e9sent\u00e9e par un mot binaire de 64 bits plac\u00e9 dans une variable globale de type <code>uint64_t<\/code>.<\/li>\n<li>La position de la t\u00eate est repr\u00e9sent\u00e9e par une variable de type <code>int<\/code>.<\/li>\n<li>L&rsquo;\u00e9tat est repr\u00e9sent\u00e9 par une variable de type <code>int<\/code>.<\/li>\n<\/ul>\n<pre><code class=\"language-c\">uint64_t Tape = 0;\nint Head = 0;\nint State = 0;\n<\/code><\/pre>\n<p>Chaque case de la bande est repr\u00e9sent\u00e9e par 2 bits cons\u00e9cutifs avec la convention suivante :<\/p>\n<ul>\n<li><code>00<\/code> repr\u00e9sente la valeur 0,<\/li>\n<li><code>01<\/code> repr\u00e9sente la valeur 1,<\/li>\n<li><code>10<\/code> repr\u00e9sente la valeur #.<\/li>\n<\/ul>\n<p>Voici la mani\u00e8re d&rsquo;initialiser la bande avec l&rsquo;exemple pr\u00e9sent\u00e9 dans la section pr\u00e9c\u00e9dente.<\/p>\n<pre><code class=\"language-C\">Tape = 0b1000000101100000000000000000000000000000000000000000000000000000;\n\/\/        # 0 0 1 1 # 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0\n<\/code><\/pre>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/01\/5-7.png\" alt=\"image-20220116173408523\" \/><\/p>\n<blockquote><p>Il est crucial, en ing\u00e9nierie logicielle, de bien distinguer les donn\u00e9es repr\u00e9sent\u00e9es et les repr\u00e9sentations de ces donn\u00e9es utilis\u00e9es par un programme. Ici, par exemple, la valeur 0 d&rsquo;une case de la bande est repr\u00e9sent\u00e9e par la s\u00e9quence de deux bits 00, la valeur 1 est repr\u00e9sent\u00e9e par la s\u00e9quence 01, la valeur # par la s\u00e9quence 10.<\/p><\/blockquote>\n<h3><a id=\"repr%C3%A9sentation-du-programme\" class=\"anchor\" aria-hidden=\"true\"><\/a>Repr\u00e9sentation du programme<\/h3>\n<h4><a id=\"repr%C3%A9sentation-d-une-action\" class=\"anchor\" aria-hidden=\"true\"><\/a>Repr\u00e9sentation d&rsquo;une action<\/h4>\n<p>Les actions sont repr\u00e9sent\u00e9es par des octets (type <code>uint8_t<\/code>) avec la convention suivantes :<\/p>\n<ul>\n<li>Les bits de rangs 0 \u00e0 2 repr\u00e9sentent le nouvel \u00e9tat.<\/li>\n<li>Le bit de rang 3 repr\u00e9sente le sens de d\u00e9placement de la t\u00eate (1 pour droite, 0 pour gauche).<\/li>\n<li>Les bits de rangs 4 et 5 repr\u00e9sentent la valeur \u00e0 \u00e9crire sur la bande.<\/li>\n<li>Les bits de rangs 6 et 7 ne sont pas utilis\u00e9s.<\/li>\n<\/ul>\n<p>\u00c0 titre d&rsquo;exemple, voici le codage de l&rsquo;action <code>#, droite, 3<\/code> :<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/01\/6-7.png\" alt=\"image-20220116175112134\" \/><\/p>\n<p>Pour faciliter le codage d&rsquo;une action, on utilise les masques suivants, d\u00e9finis sous forme de constantes :<\/p>\n<pre><code class=\"language-C\">#define BLANK 0b100000  \/\/ Valeur #\n#define ZERO  0b000000  \/\/ Valeur 0\n#define ONE   0b010000  \/\/ Valeur 1\n\n#define LEFT  0b000000  \/\/ D\u00e9placement \u00e0 gauche\n#define RIGHT 0b001000  \/\/ D\u00e9placement \u00e0 droite\n<\/code><\/pre>\n<p>Par exemple, l&rsquo;action <code>#, droite, 3<\/code> se code :<\/p>\n<pre><code class=\"language-C\">uint8_t action = BLANK | RIGHT | 3;\n<\/code><\/pre>\n<p>Vous pouvez le v\u00e9rifier en combinant les masques \u00e0 l&rsquo;aide du ou bitwise <code>|<\/code>.<\/p>\n<h5><a id=\"exercice\" class=\"anchor\" aria-hidden=\"true\"><\/a>Exercice<\/h5>\n<p>Essayez de coder de cette mani\u00e8res chacune des actions suivantes et donnez le mots binaire correspondant.<\/p>\n<ol>\n<li><code>1, gauche, 2<\/code><\/li>\n<li><code>0, droite, 4<\/code><\/li>\n<\/ol>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">R\u00e9ponse1<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-C\">uint8_t action = ONE | LEFT | 2;  \/\/ 00010010\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">R\u00e9ponse2<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-C\">uint8_t action = ZERO | RIGHT | 4; \/\/ 00001100\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h4><a id=\"repr%C3%A9sentation-du-programme-de-la-machine\" class=\"anchor\" aria-hidden=\"true\"><\/a>Repr\u00e9sentation du programme de la machine<\/h4>\n<p>Le programme de la machine de Turing est repr\u00e9sent\u00e9 par un <strong>tableau d&rsquo;actions<\/strong>. Voici le programme d&rsquo;exemple donn\u00e9 dans la section 1 :<\/p>\n<pre><code class=\"language-C\">uint8_t Prog[] =\n{\n    ZERO|RIGHT|STOP, ONE|RIGHT|STOP, BLANK|RIGHT|1,    \/\/ Si \u00e9tat 0\n    ZERO|RIGHT|1,    ONE|RIGHT|1,    BLANK|LEFT|2,     \/\/ Si \u00e9tat 1\n    ONE|LEFT|3,      ZERO|LEFT|2,    BLANK|LEFT|STOP,  \/\/ Si \u00e9tat 2\n    ZERO|LEFT|3,     ONE|LEFT|3,     BLANK|LEFT|STOP   \/\/ Si \u00e9tat 3\n};\n<\/code><\/pre>\n<p>Les trois premi\u00e8res actions du tableau sont celles \u00e0 r\u00e9aliser dans les situations ou l&rsquo;\u00e9tat est 0 et la valeur lue sur la bande respectivement <code>0<\/code>, <code>1<\/code> et <code>#<\/code>.<\/p>\n<p>Les trois suivantes sont celles \u00e0 r\u00e9aliser dans les situations ou l&rsquo;\u00e9tat est 1 et la valeur lue sur la bande respectivement <code>0<\/code>, <code>1<\/code> et <code>#<\/code>.<\/p>\n<p>Etc.<\/p>\n<p>D&rsquo;une mani\u00e8re plus g\u00e9n\u00e9rale, si l&rsquo;\u00e9tat courant est <code>etat<\/code> et la valeur lue sur la bande est <code>val<\/code>, alors l&rsquo;action \u00e0 r\u00e9aliser est <code>Prog[(3 * etat) + val]<\/code>.<\/p>\n<p><strong>Exemple<\/strong> : Si la situation est <code>(valeur : 0, \u00e9tat : 1)<\/code>, alors l&rsquo;action \u00e0 r\u00e9aliser est <code>Prog[3]<\/code>, c&rsquo;est \u00e0 dire <code>ZERO|RIGHT|1<\/code> : \u00e9criture d&rsquo;un 0 sur la bande, d\u00e9placement \u00e0 droite, le nouvel \u00e9tat est 1.<\/p>\n<h5><a id=\"exercice\" class=\"anchor\" aria-hidden=\"true\"><\/a>Exercice<\/h5>\n<p>Quelle est l&rsquo;action \u00e0 r\u00e9aliser, d&rsquo;apr\u00e8s le programme d&rsquo;exemple, si la situation est <code>(valeur : 1, \u00e9tat : 2)<\/code> ?<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">R\u00e9ponse<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>L&rsquo;action est <code>Prog[7]<\/code>, c&rsquo;est \u00e0 dire <code>ZERO|LEFT|2<\/code> : \u00e9criture d&rsquo;un 0, d\u00e9placement \u00e0 gauche, le nouvel \u00e9tat est 2.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h3><a id=\"constantes-et-variables-globales\" class=\"anchor\" aria-hidden=\"true\"><\/a>Constantes et variables globales<\/h3>\n<p>Voici le d\u00e9but du programme de simulation avec les constantes et variables globales que nous avons d\u00e9j\u00e0 pr\u00e9sent\u00e9es, plus la constante <code>STOP<\/code> qui repr\u00e9sente la valeur de l&rsquo;\u00e9tat final de la machine (celui qui termine l&rsquo;ex\u00e9cution du programme).<\/p>\n<pre><code class=\"language-C\">#include &lt;stdio.h&gt;\n#include &lt;stdint.h&gt;\n#include &lt;stdlib.h&gt;\n\n#define BLANK 0b100000\n#define ZERO  0b000000\n#define ONE   0b010000\n\n#define LEFT  0b0000\n#define RIGHT 0b1000\n\n#define STOP 7\n\nint Head = 0;\nuint64_t Tape = 0;\nint State = 0;\nuint8_t Prog[] =\n{\n    ZERO|RIGHT|STOP, ONE|RIGHT|STOP, BLANK|RIGHT|1,    \/\/ Si \u00e9tat 0\n    ZERO|RIGHT|1,    ONE|RIGHT|1,    BLANK|LEFT|2,     \/\/ Si \u00e9tat 1\n    ONE|LEFT|3,      ZERO|LEFT|2,    BLANK|LEFT|STOP,  \/\/ Si \u00e9tat 2\n    ZERO|LEFT|3,     ONE|LEFT|3,     BLANK|LEFT|STOP   \/\/ Si \u00e9tat 3\n};\n<\/code><\/pre>\n<h3><a id=\"fonctions%C3%A0-d%C3%A9finir\" class=\"anchor\" aria-hidden=\"true\"><\/a>Fonctions \u00e0 d\u00e9finir<\/h3>\n<h4><a id=\"lecture-d-une-valeur-sur-la-bande\" class=\"anchor\" aria-hidden=\"true\"><\/a>Lecture d&rsquo;une valeur sur la bande<\/h4>\n<pre><code class=\"language-C\">int read(int i);\n<\/code><\/pre>\n<p>Lit la valeur situ\u00e9e en position <code>i<\/code> sur la bande. La valeur de retour peut \u00eatre 0, 1 ou 2 (qui repr\u00e9sente la valeur <code>#<\/code>).<\/p>\n<h4><a id=\"affichage\" class=\"anchor\" aria-hidden=\"true\"><\/a>Affichage<\/h4>\n<pre><code class=\"language-C\">void print();\n<\/code><\/pre>\n<p>Affiche la bande, la t\u00eate de lecture et l&rsquo;\u00e9tat courant. Avec les valeurs des variables donn\u00e9es pr\u00e9c\u00e9demment, les lignes&#8230;<\/p>\n<pre><code class=\"language-C\">Tape = 0b1000000101100000000000000000000000000000000000000000000000000000;\nprint();\n<\/code><\/pre>\n<p>&#8230;doivent produire l&rsquo;affichage suivant :<\/p>\n<pre><code class=\"language-plain_text\"># 0 0 1 1 # 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  [0]\nT\n<\/code><\/pre>\n<p>La lettre <code>T<\/code> repr\u00e9sente la position de la t\u00eate (ici au d\u00e9but de la bande). La valeur entre crochet est celle de l&rsquo;\u00e9tat courant, donn\u00e9e par la variable <code>State<\/code>.<\/p>\n<blockquote><p>Cette fonction appelle la fonction <code>read<\/code>.<\/p><\/blockquote>\n<h4><a id=\"%C3%89criture-d-une-valeur-sur-la-bande\" class=\"anchor\" aria-hidden=\"true\"><\/a>\u00c9criture d&rsquo;une valeur sur la bande<\/h4>\n<pre><code class=\"language-C\">void write(int i, int val);\n<\/code><\/pre>\n<p>\u00c9crit la valeur <code>val<\/code> (0, 1 ou 2) en position <code>i<\/code> sur la bande. La valeur 2 se repr\u00e9sente aussi <code>0b10<\/code> et correspond \u00e0 la valeur not\u00e9e <code>#<\/code>.<\/p>\n<h4><a id=\"ex%C3%A9cution-du-programme\" class=\"anchor\" aria-hidden=\"true\"><\/a>Ex\u00e9cution du programme<\/h4>\n<pre><code class=\"language-C\">uint8_t nextAction();\n<\/code><\/pre>\n<p>Retourne la prochaine action \u00e0 r\u00e9aliser qui d\u00e9pend :<\/p>\n<ul>\n<li>de l&rsquo;\u00e9tat courant (variable <code>State<\/code>),<\/li>\n<li>de la valeur d\u00e9sign\u00e9e par la t\u00eate de lecture sur la bande<\/li>\n<li>et du programme.<\/li>\n<\/ul>\n<pre><code class=\"language-C\">void operate(uint8_t action);\n<\/code><\/pre>\n<p>R\u00e9alise l&rsquo;action d\u00e9sign\u00e9e par le param\u00e8tre <code>action<\/code>. Cette fonction \u00e9crit une valeur sur la bande, modifie la position de la t\u00eate (variable <code>Head<\/code>), et met \u00e0 jour la valeur de l&rsquo;\u00e9tat courant (variable <code>State<\/code>).<\/p>\n<p>Si la t\u00eate de lecture est en d\u00e9but de bande et si l&rsquo;action suppose un d\u00e9placement \u00e0 gauche alors la t\u00eate doit garder sa position. Si la t\u00eate est en fin de bande et si l&rsquo;action impose un d\u00e9placement \u00e0 droite alors la t\u00eate doit garder sa position.<\/p>\n<p>Ces deux fonctions sont appel\u00e9es par la fonction <code>run<\/code>, d\u00e9finie ci-dessous, qui assure l&rsquo;ex\u00e9cution du programme.<\/p>\n<pre><code class=\"language-C\">void run()\n{\n    print();\n    State = 0;\n    while(State != END_STATE)\n    {\n        uint8_t action = nextAction();\n        operate(action);\n        print();\n        getchar();  \/\/ Il faut presser la touche entr\u00e9e pour continuer\n    }\n    printf(\"Ex\u00e9cution termin\u00e9e\\n\");  \n}\n<\/code><\/pre>\n<h3><a id=\"travail%C3%A0-r%C3%A9aliser\" class=\"anchor\" aria-hidden=\"true\"><\/a>Travail \u00e0 r\u00e9aliser<\/h3>\n<p>Vous devez d\u00e9finir les fonctions dont le code n&rsquo;a pas \u00e9t\u00e9 donn\u00e9 pr\u00e9c\u00e9demment, les tester s\u00e9par\u00e9ment, puis tester l&rsquo;ex\u00e9cution du programme d&rsquo;exemple. Ce programme r\u00e9alise une incr\u00e9mentation de la valeur en base 2 situ\u00e9e en d\u00e9but de bande entre les 2 symboles <code>#<\/code>.<\/p>\n<h2><a id=\"modifications-du-simulateur\" class=\"anchor\" aria-hidden=\"true\"><\/a>Modifications du simulateur<\/h2>\n<p>\u00c0 ce stade, vous devez avoir un simulateur fonctionnel et comprendre les moindres d\u00e9tails de son impl\u00e9mentation et des repr\u00e9sentations des donn\u00e9es utilis\u00e9es. Les modifications \u00e0 r\u00e9aliser devront \u00eatre test\u00e9es avec des programmes de machine de Turing con\u00e7us \u00e0 cette fin.<\/p>\n<h3><a id=\"augmentation-du-nombre-d%C3%A9-tats\" class=\"anchor\" aria-hidden=\"true\"><\/a>Augmentation du nombre d&rsquo;\u00e9tats<\/h3>\n<p>La machine simul\u00e9e pr\u00e9c\u00e9demment peut admettre au plus 7 \u00e9tats, num\u00e9rot\u00e9s de 0 \u00e0 6, plus l&rsquo;\u00e9tat final qui arr\u00eate le programme.<\/p>\n<p>Vous devez modifier le simulateur, en r\u00e9utilisant au maximum le code existant et les principes et repr\u00e9sentation utilis\u00e9s, pour que le nombre maximum d&rsquo;\u00e9tats soit \u00e9gal \u00e0 32 (\u00e9tats 0 \u00e0 30 plus l&rsquo;\u00e9tat final cod\u00e9 par l&rsquo;entier 31). Dans la nouvelle version, tous les bits des octets repr\u00e9sentant les actions seront utilis\u00e9s, ce qui permettra de repr\u00e9senter les \u00e9tats sur 5 bits.<\/p>\n<h3><a id=\"augmentation-de-la-taille-de-la-bande\" class=\"anchor\" aria-hidden=\"true\"><\/a>Augmentation de la taille de la bande<\/h3>\n<p>La machine simul\u00e9e pr\u00e9c\u00e9demment a une bande de 32 cases repr\u00e9sent\u00e9e par un seul entier de type <code>uint64_t<\/code>.<\/p>\n<p>Vous devez r\u00e9aliser une version dans laquelle la taille de la bande, multiple de 32, est d\u00e9finie par une constante <code>SIZE_TAPE<\/code>. Le nombre de cases de la bande sera \u00e9gal \u00e0 <code>SIZE_TAP * 32<\/code> et la bande sera repr\u00e9sent\u00e9e par le tableau :<\/p>\n<pre><code class=\"language-C\">uint64_t Tape[SIZE_TAPE] = {0};\n<\/code><\/pre>\n<p>Le codage du programme de la machine de Turing simul\u00e9e doit \u00eatre identique et vous devez r\u00e9utiliser autant que possible les principes et la structures du simulateur pr\u00e9c\u00e9dent en modifiant certaines fonctions.<\/p>\n<p>L&rsquo;affichage doit \u00eatre modifi\u00e9 de mani\u00e8re \u00e0 que la t\u00eate apparaisse au milieu de l&rsquo;\u00e9cran et que seules les parties de la bande situ\u00e9e autour, dans la limite de 16 cases de chaque cot\u00e9, soient affich\u00e9es.<\/p>\n<hr \/>\n","protected":false},"excerpt":{"rendered":"<p>Par O. Bailleux, Ma\u00eetre de conf\u00e9rences HDR \u00e0 l&rsquo;universit\u00e9 de Bourgogne. TP2 Le but de ce TP est de r\u00e9aliser un simulateur de machine de Turing en langage C. 1. La machine de Turing \u00e0 r\u00e9aliser La machine que nous allons simuler est constitu\u00e9e : d&rsquo;une bande comportant des cases contenant des symboles, d&rsquo;une variable [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[2],"tags":[],"class_list":["post-159","post","type-post","status-publish","format-standard","hentry","category-c-et-cpp","entry"],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/posts\/159","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/comments?post=159"}],"version-history":[{"count":2,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/posts\/159\/revisions"}],"predecessor-version":[{"id":161,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/posts\/159\/revisions\/161"}],"wp:attachment":[{"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/media?parent=159"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/categories?post=159"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/tags?post=159"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}