Accesso

Cherubino     Gara nazionale di programmazione della
Macchina di Turing
 
 

Esercizi di Gara della VI 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!

  • Ogni volta che si salva la soluzione di un esercizio con il simulatore della macchina di Turing, il “timestamp” dell’esercizio viene aggiornato con il tempo trascorso fino a quel momento.

Esercizio 1 [Punti 1]. Si vuole realizzare l’odometro di Erone da Alessandria, ovvero un contatore a cifre decimali a lunghezza fissa che incrementa di uno il numero N. Quando raggiunge il valore massimo 99…9, ritorna a 00…0. Programmare una macchina di Turing che, dato un nastro iniziale contenente un numero decimale N, termini la sua esecuzione lasciando sul nastro l’incremento di N con l’odometro. Esempi:

NASTRO INIZIALE

NASTRO FINALE

3578

3579

10199

10200

999

000



Esercizio 2 [Punti 1]. Data una sequenza binaria, si vuole definire una operazione RUOTA che sposta ciclicamente lo 0 iniziale in fondo fino a che il bit iniziale è 1 (in caso di tutti 0, non fa nulla). Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza binaria di 0 e 1, applichi l’operazione RUOTA alla sequenza. Esempi:

NASTRO INIZIALE

NASTRO FINALE

000

000

1001011

1001011

000101001

101001000



Esercizio 3 [punti 1]. Nelle sequenze di DNA, composte dalla concatenazione dei simboli A, C, G e T, ciascun simbolo ha un proprio complemento. In particolare, il complemento per A, C, G e T è dato, rispettivamente, da T, G, C e A. Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza arbitraria di simboli A, C, G e T, appenda alla fine della sequenza una ulteriore sequenza con il complemento dei simboli. Esempi:

NASTRO INIZIALE

NASTRO FINALE

ATTCGACGATAT

ATTCGACGATATTAAGCTGCTATA

CCCCAAA

CCCCAAAGGGGTTT

ACGT

ACGTTGCA



Esercizio 4 [Punti 1]. Programmare una macchina di Turing che, dato un nastro iniziale contenente due sequenze di DNA (simboli A, C, G e T) di uguale lunghezza e separate da X, termini la sua esecuzione lasciando sul nastro il numero di posizioni in cui le due sequenze differiscono. Esempi:

NASTRO INIZIALE

NASTRO FINALE

AACGATXAAGGAC

2

AAXAA

0

ACACGTXCACAGT

4



Esercizio 5 [Punti 1]. 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 è una potenza del due e la sola sequenza NO altrimenti. Esempi:

NASTRO INIZIALE

NASTRO FINALE

0

NO

128

SI

161

SI



Esercizio 6 [Punti 2]. Un insieme PQ di stringhe formate dai simboli P, Q e X soddisfa le seguenti proprietà:

  • Le stringhe sPXQsX appartengono a PQ, per ogni sequenza s di X.

  • Se sPtQz appartiene a PQ per le stringhe s, t e z di sole X, allora anche sPtXQzX appartiene a PQ.

Programmare una macchina di Turing che, dato un nastro iniziale contenente una stringa formata dai simboli P, Q e X, termina la sua esecuzione lasciando sul nastro la sola lettera S se la stringa appartiene all’insieme PQ, e la sola lettera N altrimenti. Esempi:

NASTRO INIZIALE

NASTRO FINALE

PXQX

S

XXXXXPXXQXXXXXXX

S

XXXXPXXQXXXXX

N



Esercizio 7 [Punti 2*]. Dati due numeri decimali maggiori o uguali a 0, separati da M, con il primo numero maggiore o uguale al secondo, si vuole calcolare la differenza. Programmare una macchina di Turing che, dato un nastro iniziale contenente i due numeri decimali separati dal simbolo M, termini la sua esecuzione lasciando sul nastro la loro differenza. Esempi:

NASTRO INIZIALE

NASTRO FINALE

120M4

116

373M373

0

1057M0

1057



Esercizio 8 [Punti 3]. Data una sequenza di DNA formata dai simboli A, C, G e T, si vuole ottenere la sua rappresentazione LRE sostituendo ogni stringa di simboli consecutivi uguali con un solo simbolo seguito dalla rappresentazione decimale della lunghezza della stringa (tale rappresentazione va omessa se la lunghezza è 1). Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza di DNA, termini la sua esecuzione lasciando sul nastro la sua rappresentazione LRE. Esempi:

NASTRO INIZIALE

NASTRO FINALE

AAACGGGGAAT

A3CG4A2T

CCCCCCCCCCCCCCA

C14A

ACGT

ACGT



Esercizio 9 [Punti 3]. La doppia inversione di una stringa si ottiene dividendo la stringa in due parti uguali (tranne il carattere centrale nel caso la stringa abbia lunghezza dispari) e invertendo l’ordine dei simboli in ciascuna parte. Programmare una macchina di Turing che, dato un nastro iniziale contenente una stringa di simboli A, B e C, termini la sua esecuzione lasciando sul nastro la doppia inversione della stringa. Esempi:

NASTRO INIZIALE

NASTRO FINALE

ABAABCCC

AABACCCB

ABCAB

BACBA

ACABAAA

ACABAAA



Esercizio 10 [Punti 3]. Si considerino le seguenti due operazioni M e S su un numero decimale. L’operazione M moltiplica il numero per 2, mentre l’operazione S somma 1. Programmare una macchina di Turing che, dato un nastro iniziale contenente un numero decimale positivo N > 1, termini l’esecuzione lasciando sul nastro la più breve sequenza di operazioni M e S che produce N a partire da 2. Esempi:

NASTRO INIZIALE

NASTRO FINALE

4

M

2

(nastro vuoto)

12

SMM

43

MSMMSMS

  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...)