Accesso

Cherubino     Gara nazionale di programmazione della
Macchina di Turing
 
 

Esercizi di Gara della V edizione


AVVISI:

  • Se non specificato altrimenti negli esercizi, le sequenze iniziali su nastro si intendono non vuote, ovvero contenenti almeno un simbolo.

  • Per numero decimale si intende un numero positivo o nullo rappresentato con le cifre 0, 1, 2, ..., 9, senza zeri iniziali non significativi; per esempio 0 e 19 sono numeri validi, mentre 0032 deve essere scritto come 32.

  • Nel fornire le soluzioni, ricordarsi di pulire il nastro finale da ogni simbolo che non costituisca la risposta!



Esercizio 1 [Sostituzione di caratteri]. Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza arbitraria di simboli A e B, sostituisca ogni occorrenza di due simboli consecutivi AB con due simboli CD. Esempi:

NASTRO INIZIALE

NASTRO FINALE

AABABBBAABAAABAABAA

ACDCDBBACDAACDACDAA

BBBBAAA

BBBBAAA

AABB

ACDB



Esercizio 2 [Parentesi bilanciate]. Una sequenza di parentesi quadre e graffe annidate si dice bilanciata secondo la seguente definizione: (i) la sequenza vuota è bilanciata; (ii) se S e T sono sequenze bilanciate allora anche le due sequenze { S } T e [ S ] T sono bilanciate. Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza (non vuota) di parentesi quadre e graffe, termini la sua esecuzione lasciando sul nastro la sola sequenza SI se la sequenza iniziale è bilanciata e la sola sequenza NO altrimenti. Esempi:

NASTRO INIZIALE

NASTRO FINALE

[]{[]}

SI

[{]}

NO

[[{}][]{}]

SI



Esercizio 3 [Schedina]. Una colonna di schedina S è una sequenza simboli 1, 2 e X. Data la colonna vincente V, anch'essa costituita da una sequenza di altrettanti simboli scelti tra 1, 2 e X, si vuole verificare che S sia vincente, ovvero ci siano almeno 12 risultati indovinati tra quelli riportati in V. Programmare una macchina di Turing che, dato un nastro iniziale contenente le sequenze S e V separate dal simbolo *, termini la sua esecuzione lasciando sul nastro la sola sequenza SI se S è vincente e la sola sequenza NO altrimenti. Esempi:

NASTRO INIZIALE

NASTRO FINALE

1X1X2X21X1X12*1X1X2X21X1X12

SI

1X1X2X21X1X12*1X1X2X21X1X21

NO

1X1X2X21X1X12*1X1X2X21X1112

SI



Esercizio 4 [Divisione per due]. Programmare una macchina di Turing che, dato un nastro iniziale contenente un numero pari decimale N, termini la sua esecuzione lasciando sul nastro il risultato della divisione di N per 2. Esempi:

NASTRO INIZIALE

NASTRO FINALE

1234

617

130

65

0

0



Esercizio 5 [Raddoppio di sequenza]. Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza arbitraria S di simboli A, B e C, termini la sua esecuzione lasciando sul nastro la sequenza SS, cioè la sequenza originale duplicata. Esempi:

NASTRO INIZIALE

NASTRO FINALE

ABACB

ABACBABACB

AB

ABAB

C

CC



Esercizio 6 [Divisibilità per sei]. Programmare una macchina di Turing che, dato un nastro iniziale contenente un numero decimale N, termini la sua esecuzione lasciando sul nastro la sola sequenza SI se N è divisibile per 6 e la sola sequenza NO altrimenti. Esempi:

NASTRO INIZIALE

NASTRO FINALE

30

SI

16

NO

0

SI



Esercizio 7 [Espressioni booleane]. Si vogliono applicare ripetutamente le seguenti regole di sostituzione, dove la sequenza di due o tre simboli (in neretto) a sinistra di ogni freccia va sostituita con il simbolo corrispondente a destra della freccia:

  • Sostituzioni NOT: !0 -> 1, !1 -> 0

  • Sostituzioni AND: *00 -> 0, *01 -> 0, *10 -> 0, *11 -> 1

  • Sostituzioni OR: +00 -> 0, +01 -> 1, +10 -> 1, +11 -> 1

Una sequenza S di simboli 0, 1, !, * e + si dice risolvibile se applicando ripetutamente le sostituzioni suddette, in qualunque ordine, si ottiene alla fine un unico simbolo, chiamato soluzione, ovvero il simbolo 0 oppure il simbolo 1. Per esempio, se S è la sequenza +*1+01*0!*01, si possono applicare le sostituzioni riportate sotto, ottenendo 1 come soluzione (si noti che, nel caso in cui più sostituzioni siano applicabili, l'ordine di applicazione non è rilevante):



+*1+01*0!*01 -> +*11*0!*01

+*11*0!*01 -> +1*0!*01

+1*0!*01 -> +1*0!0

+1*0!0 -> +1*01

+1*01 -> +10

+10 -> 1



Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza S risolvibile, termini la sua esecuzione lasciando sul nastro la soluzione di S. Non importa come le sostituzioni vengano realizzate ed eseguite sulla macchina di Turing; è sufficiente che la soluzione finale calcolata (0 oppure 1) sia corretta. Esempi:

NASTRO INIZIALE

NASTRO FINALE

1

1

*1!*1+01

0

!!1

1



Esercizio 8 [Somma]. Programmare una macchina di Turing che, dato un nastro iniziale contenente due numeri decimali N e M, separati dal simbolo +, termini la sua esecuzione lasciando sul nastro la somma di N e M. Esempi:

NASTRO INIZIALE

NASTRO FINALE

30+85

115

23+0

23

0+0

0



Esercizio 9 [Sequenza prefissa]. Una sequenza di simboli A, B, e C si dice prefissa secondo la seguente definizione: (i) la sequenza composta di un solo simbolo (A, B oppure C) è prefissa; (ii) se S è una sequenza prefissa allora anche le sequenze SSA, SSB e SSC, costruite duplicando S e aggiungendo un simbolo in fondo, sono sequenze prefisse. Per esempio, A, AAA, AAC, AACAACC e AACAACCAACAACCA sono prefisse, mentre AA, ABA, AABA e ABAABAC non lo sono (ABAABAC non è prefissa perché ABA non è prefissa). Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza di simboli A, B, e C, termini la sua esecuzione lasciando sul nastro la sola sequenza SI se la sequenza è prefissa e la sola sequenza NO altrimenti. Esempi:

NASTRO INIZIALE

NASTRO FINALE

B

SI

AB

NO

AABAABC

SI



Esercizio 10 [Crivello di Eratostene]. Un intero q > 1 si dice primo se è divisibile solo per 1 e per se stesso. Per esempio, 2, 3, 5, 7, 11, 13, 17 e 19 sono primi. Dato un numero decimale M, si vogliono individuare tutti i numeri primi q <= M usando il seguente algoritmo, che rappresenta una versione semplificata del "crivello di Eratostene". Si marcano inizialmente come primi tutti i numeri da 2 a M. Sia q l'ultimo numero primo trovato (inizialmente q = 2). Si marcano come "non primi" tutti i numeri maggiori di q che sono multipli di q. Per esempio, se q = 2, si marcano 4, 6, 8, 10, 12, 14, ecc. Quindi, si pone q uguale al successivo numero che risulta marcato come primo, e si ripete la marcatura finché non ci sono ulteriori primi da esaminare. Usando il simbolo P per marcare un primo e il simbolo N per un "non primo", i numeri che rimangono marcati con P alla fine del crivello sono i numeri primi. Per esempio, per M = 20, il crivello esegue i seguenti passi:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

N P P P P P P P P  P  P  P  P  P  P  P  P  P  P  P


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20      q = 2

N P P N P N P N P  N  P  N  P  N  P  N  P  N  P  N


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20       q = 3

N P P N P N P N N  N  P  N  P  N  N  N  P  N  P  N


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20       q = 5,7,11,13,17,19

N P P N P N P N N  N  P  N  P  N  N  N  P  N  P  N



Per M >= 2, sia data una sequenza formata da un simbolo N seguito da M - 1 simboli P, dove l'i-esimo simbolo (P o N) corrisponde al numero 1 <= i <= M. Programmare una macchina di Turing che, dato un nastro iniziale contenente la suddetta sequenza di M simboli NPPPPPPPPPPPPPPP..., esegua il crivello di Eratostene e termini l'esecuzione lasciando sul nastro la sequenza di M simboli NPPNPNPNNNPNPNNNPNPN... in cui ciascuna P corrisponde a un numero primo q <= M. Esempi:

NASTRO INIZIALE

NASTRO FINALE

NPPPPPPPPPPP

NPPNPNPNNNPN

NPPPPPPPPPPPPPPP

NPPNPNPNNNPNPNNN

NP

NP

  I GARA
  II GARA
  III GARA
  IV GARA
  V GARA
  VI GARA
  VII GARA
  VIII GARA
  IX GARA
  GARA ROTARY 2006
  X GARA
  XI GARA
  XII Gara
  XIII Gara
  XIV Gara
  XV Edizione
  XVI Edizione
  XVII Edizione
  XVIII Edizione
  XIX Edizione
(Altri collegamenti...)