Monthly Archives: gennaio 2016

Edizione I – Problema 5

Indichiamo con AnBm una sequenza del tipo A…AB…B.

Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza del tipo AnBm, con n>0 e m>0, termina la sua esecuzione lasciando sul nastro

  • una sola A se n>m
  • una sola B se m>n
  • una sola C se n=m.

Esempi

NASTRO INIZIALE NASTRO FINALE
AAAABB A
AAABBBBB B
AAABBB C

0105Algoritmo

  • Cancella una A a sinistra e una B a destra finché è possibile
  • Se finiscono le A cancella le B rimaste e scrive B
  • Se finiscono le B cancella le A rimaste e scrive A
  • Se finiscono sia le A che le B allora scrive C

Codice

(0,A,A,-,>)
(0,B,BB,-,>)
(0,-,H,C,>)
(A,AB,A,AB,>)
(A,-,R,-,<)
(R,A,A,-,<)
(R,-,H,A,>)
(B,AB,B,AB,<)
(B,-,0,-,>)
(BB,B,BB,-,>)
(B,-,H,B,>)
Ha trovato una A, va a destra
Ha trovato una B, cancella tutto
Scrive C
Va a destra
In fondo...
Cancella tutte le A
Scrive A
Va a sinistra
In fondo...
Cancella tutte le B
Scrive B

Edizione I – Problema 4

Una sequenza si dice palindroma se la sua lettura da sinistra verso destra è uguale alla sua lettura da destra verso sinistra.

Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A e B, termina la sua esecuzione lasciando sul nastro la sola sequenza SI se la sequenza iniziale è palindroma, la sola sequenza NO altrimenti.

Esempi

NASTRO INIZIALE NASTRO FINALE
ABABA SI
ABBA SI
BABBA NO
A SI

0104Algoritmo

  • Se la prima lettera è una AB la elimina e va a cercarla a destra
  • Se trova la lettera cercata torna a sinistra e ricomincia
  • Se non trova la lettera cercata elimina tutto e scrive NO
  • Se finiscono le lettere scrive SI

Codice

(0,A,A,-,>)
(A,AB,A,AB,>)
(A,-,AA,-,<)
(AA,[A-],S,-,<)
(AA,B,N,-,<)
(0,B,B,-,>)
(B,AB,B,AB,>)
(B,-,BB,-,<)
(BB,A,N,-,<)
(BB,[B-],S,-,<)
(S,AB,S,AB,<)
(S,-,0,-,>)
(0,-,SI,S,>)
(SI,-,H,I,>)
(N,[AB],N,-,<)
(N,-,NO,N,>)
(NO,-,H,O,>)
A
Va a destra
Torna a sinistra
Ha trovato la A
Ha trovato una B
B
Va a destra
Torna a sinistra
Ha trovato una A
Ha trovato la B
Torna a sinistra
Ricomincia
Scrive SI
...
Cancella tutto
Scrive NO
...

Edizione I – Problema 3

Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di cifre decimali, termina la sua esecuzione lasciando sul nastro la sequenza che si ottiene eliminando tutte le cifre 0 alla sinistra della cifra diversa da 0 più a sinistra.

Se la sequenza iniziale è composta da sole cifre 0, la macchina deve lasciare sul nastro un solo 0.

Esempi

NASTRO INIZIALE NASTRO FINALE
000431 431
0000 0
004031 4031
431 431

0103Algoritmo

  • Elimina gli 0 a partire da sinistra
  • Si ferma se incontra una cifra diversa da 0
  • Se incontra lo spazio scrive 0

Codice

(0,0,0,-,>)
(0,-,H,0,>)
Elimina gli 0
Si ferma e scrive 0

Edizione XVIII

Problema 1 – Lo scorciatore

In Informatica, una struttura dati è un modo di organizzare le informazioni nella memoria di un calcolatore in modo da facilitare l’esecuzione di un insieme predefinito di operazioni.
La struttura dati più semplice è la sequenza, che può essere facilmente rappresentata da una sequenza di simboli sul nastro.
Sulle sequenze si possono facilmente programmare molte operazioni, per esempio lo scorciamento.
Si scriva un programma per macchina di Turing che, ricevuta sul nastro di input una sequenza di simboli A, lasci sul nastro la stessa sequenza, accorciata di una A.

NASTRO INIZIALE NASTRO FINALE
AAAA AAA
A
AAAAAAAAAA AAAAAAAAA

Problema 2 – L’inseritore

Si scriva un programma per macchina di Turing che, ricevuta sul nastro di input una sequenza di simboli sull’alfabeto {A, B}, lasci sul nastro la stessa sequenza, in cui dopo ogni A è stata inserita una C.

NASTRO INIZIALE NASTRO FINALE
ABABAAB ACBACBACACB
BBBB BBBB
BBABAAA BBACBACACAC
A AC

Problema 3 – Il sommatore

Si scriva un programma per macchina di Turing che, ricevuta in ingresso una sequenza di simboli sull’alfabeto {0, 1, 2, 3, 4} di lunghezza pari, lasci sul nastro la sequenza ottenuta sommando a due a due gli elementi della sequenza di output (usando come alfabeto le cifre decimali}.

NASTRO INIZIALE NASTRO FINALE
12344321 3773
0413223240 44454
00114140223244 0254458
00 0

Problema 4 – La pila

Un’altra struttura dati molto popolare è la pila o stack.
Una pila è una sequenza in cui nuovi elementi vengono aggiunti all’inizio della sequenza (operazione push, che indicheremo con P seguito da un valore sull’alfabeto 09), e prelevati dall’inizio (operazione pop, che indicheremo con Q), col che vengono rimossi dalla pila.

Si scriva un programma per macchina di Turing che, ricevuta sul nastro di input una sequenza di operazioni di push e pop, lasci sul nastro la sequenza di valori che descrivono lo stato finale della pila, dopo aver applicato tutte le operazioni di push e pop, da sinistra a destra, partendo dalla pila vuota.
Viene garantito che la sequenza di operazioni non tenterà di eseguire delle pop con la pila vuota.

NASTRO INIZIALE NASTRO FINALE
P3P4P1 143
P3P4QP1 13
P8P3QQP3P8P8 883
P2P4P5QQQ
P1QP1QP1P2P3Q 21

Problema 5 – Un calcolatore modulare

Un uso frequente delle pile consiste nel valutare espressioni (per esempio, espressioni aritmetiche).
In questa applicazione, gli operandi vengono inseriti su una pila, mentre gli operatori (per esempio: +) estraggono due operandi dalla pila, calcolano il risultato, e lo inseriscono in cima alla pila.
Nel nostro caso, vogliamo effettuare operazioni in aritmetica modulare, in cui i risultati sono sempre calcolati modulo un valore detto base.
In particolare, in ℤ4 gli unici valori possibili sono 0, 1, 2 e 3 (ciascuno rappresentato dalla cifra corrispondente); le operazioni vengono calcolate come di consueto, ma poi il risultato è dato modulo 4 (ovvero: resto della divisione per 4).
Per esempio, in ℤ4 abbiamo che

  • 1+1=2,
  • 3+2=1,
  • 3-1=2,
  • 2-2=0,
  • 1-2=3,
  • 3×3=1,
  • 2×2=0.

Si scriva un programma per macchina di Turing che, data una pila sull’alfabeto 03, seguita da un simbolo $ e da una sequenza di operatori sull’alfabeto {A, S, M} (che stanno per: Addizione, Sottrazione, Moltiplicazione), lasci sul nastro la pila risultante dopo aver eseguito le operazioni, in ordine da sinistra a destra, oppure “E” (che sta per: Errore) nel caso si tenti di eseguire un’operazione senza che siano presenti almeno due operandi sulla pila.

NASTRO INIZIALE NASTRO FINALE
01$A 1
0123$AAA 2
22$M 0
2323$M 223
321$SA 2
3031$MMA 1
21$SA E

Problema 6 – L’albero

XVIII-img1Le strutture dati ad albero sono anch’esse molto popolari in Informatica.
Gli alberi sono insiemi di nodi, in cui ogni nodo (tranne uno, detto radice) ha esattamente un padre, e può avere 0 o più figli (di cui, ovviamente, sarà padre).
La radice non ha padre, ma può avere figli. I nodi con 0 figli sono detti foglie.
Un tipo particolare di albero, detto albero binario è definito con il vincolo aggiuntivo che ogni nodo può avere al più 2 figli.
Possiamo rappresentare su nastro un albero con la convenzione seguente: una foglia è rappresentata da un simbolo sull’alfabeto A-Z; gli altri nodi sono rappresentati da un simbolo sullo stesso alfabeto, seguito da una coppia di parentesi che racchiudono 1 o 2 figli.
Per esempio, la sequenza F(B(AD(CE))G(I(H))) rappresenta l’albero dato, in forma grafica, nella figura accanto.
Sugli alberi si definiscono molti algoritmi interessanti.
Uno dei più semplici è il calcolo della profondità, che si ottiene contando la lunghezza del più lungo cammino dalla radice a una foglia.
Per esempio, l’albero in figura ha profondità 4 (che è la lunghezza dei cammini equivalenti F-B-D-C, F-B-D-E o F-G-I-H).

Si scriva un programma per macchina di Turing che, ricevuta sul nastro di input la rappresentazione di un albero come descritto sopra, lasci sul nastro la sua profondità.

NASTRO INIZIALE NASTRO FINALE
F(B(AD(CE))G(I(H))) 4
R 1
R(AB) 2
R(A(BC(D(F(G))E))H(IJ)) 6
X(A(A)Z(Z)) 3

Problema 7 – Visita per livelli

Sugli alberi, definiti come nell’esercizio precedente, sono definite anche varie operazioni di visita, che consistono nell’elencare i nomi dei nodi che si incontrano seguendo una determinata procedura.
Per esempio, la visita in profondità, o in post-ordine, consiste nel visitare prima i figli di un nodo, e poi il nodo stesso, partendo dalla radice dell’albero.
Una visita in profondità applicata all’albero illustrato nella figura relativa all’Esercizio 6 produrrebbe quindi la sequenza: ACEDBHIGF.
La visita per livelli consiste invece nell’elencare i nodi a seconda della loro distanza dalla radice (ovvero: la profondità di cui all’esercizio precedente), partendo dalla radice stessa.
Una visita per livelli applicata all’albero illustrato nella figura relativa all’Esercizio 6 produrrebbe quindi la sequenza: FBGADICEH.

Si scriva un programma per macchina di Turing che, ricevuto sul nastro di input un albero codificato come sopra, lasci come risultato la relativa visita per livelli.

NASTRO INIZIALE NASTRO FINALE
F(B(AD(CE))G(I(H))) FBGADICEH
R(A(BC(D(F(G))E))H(IJ)) RAHBCIJDEFG
X(AB(C)) XABC
X(A(C)B) XABC
R R

Problema 8 – Potature e innesti

Sugli alberi, definiti come nell’esercizio precedente, definiamo le operazioni pota e innesta come segue: dato un albero T, e un nodo n (rappresentato da un simbolo sull’alfabeto A-Z), l’operazione di pota elimina da T tutti i sottoalberi radicati in nodi etichettati n, incluso il nodo n stesso, e restituisce l’albero potato risultante.
L’operazione innesta ha come argomenti un albero T, un nodo n (che deve essere una foglia) e un secondo albero T’.
L’operazione sostituisce ogni occorrenza di n in T con una copia di T’, e restituisce l’albero innestato risultante.

Si scriva un programma per macchina di Turing che, ricevuti sul nastro un albero iniziale T, e una sequenza di operazioni di pota (codificata come: “$n”) e innesta (codificata come: “#nT’”), lasci sul nastro l’albero risultante dopo aver applicato tutte le operazioni in sequenza.

NASTRO INIZIALE NASTRO FINALE
F(B(AD(CE))G(I(H)))$D F(B(A)G(I(H)))
F(B(AD(CE))G(I(H)))#CX(YZ) F(B(AD(X(YZ)E))G(I(H)))
F(B(AD(CE))G(I(H)))$C$E#DW F(B(AW)G(I(H)))
X(AB)#AA(RS(T))$R X(A(S(T))B)

Problema 9 – La mappa

Una mappa (anche detta array associativo) è una struttura dati che associa un elemento, detto chiave, a un altro, detto valore.
Noi useremo chiavi sull’alfabeto A-Z, e valori sull’alfabeto 0-9. Sulle mappe sono definite due operazioni: put, che riceve come argomento una chiave e un valore e stabilisce l’associazione fra la chiave e il valore nella mappa, e get, che riceve come argomento una chiave, e restituisce il valore corrispondente alla chiave nella mappa, se presente, oppure il valore 0 nel caso la chiave non sia presente.
Per questo esercizio, aggiungeremo una operazione non standard, add, che riceve come argomento una chiave e un valore, e inserisce nella mappa, in corrispondenza della chiave, il valore precedentemente contenuto, sommato al valore dato in modulo 10. Se la chiave non era presente nella mappa, add si comporta come put.
In questo esercizio, la codifica della mappa sul nastro è a vostra discrezione: dovete progettare voi la struttura dati.
La codifica delle operazioni è invece come segue: put è indicato da Pkv, get è indicato da Gk, e add è indicato da Akv, dove k è la chiave, e v è il valore.

Si scriva un programma per macchina di Turing che, ricevuta sul nastro una sequenza di operazioni put, get e add, codificate come sopra, le esegua in ordine da sinistra a destra, partendo dalla mappa vuota, e lasci sul nastro al termine della computazione la sequenza di valori estratti dalle operazioni get, in ordine di esecuzione.

NASTRO INIZIALE NASTRO FINALE
PA3PB4AA3GAGB 64
AX5
AX5AX4GXAX1GX 90
PS3GSGSGSAS1GSGQ 33340
PA0AA0PB3GAGBPB8GBGA 0380

Problema 10 – L’albero binario di ricerca

Un albero binario di ricerca è un albero binario con la proprietà che, in ogni nodo, il figlio sinistro (se esiste) ha un valore minore del padre, e il figlio destro (se esiste) ha un valore maggiore del padre. Se un nodo ha un solo figlio, assumiamo che sia quello sinistro.
Ovviamente, sui valori associati ai nodi deve essere definito un ordinamento di qualche tipo, per esempio alfabetico o numerico.
Dato un insieme di nodi, esistono molti possibili alberi binari di ricerca che soddisfano il criterio enunciato.

XVIII-img2Per esempio, l’insieme di nodi {A, B, C, D} con ordinamento alfabetico sul nome potrebbe essere rappresentato da uno qualunque di questi alberi:

Per questo esercizio, considereremo come albero canonico quello in cui tutti i livelli sono riempiti, tranne al più l’ultimo: e in questo caso, tutti i nodi del livello più basso sono accumulati a sinistra. In un albero canonico di profondità n, tutti i nodi nei livelli da 1 a n-2 hanno esattamente due figli; i nodi del livello n-1 avranno: i nodi più a sinistra esattamente due figli (che saranno foglie, al livello n), poi se il numero totale di nodi è dispari avremo un nodo con un solo figlio (che sarà una foglia, al livello n), e infine tutti i nodi più a destra avranno zero figli – ovvero, saranno foglie essi stessi, al livello n-1. Nell’esempio precedente, l’albero centrale è canonico, mentre i due laterali non lo sono.

Si scriva un programma per macchina di Turing che, ricevuta sul nastro di input una sequenza di operazioni put e add su una mappa (come nell’Esercizio 9), lasci sul nastro l’albero binario di ricerca canonico i cui nodi sono le chiavi della mappa costruita applicando la sequenza di operazioni data, partendo dalla mappa vuota, e l’ordinamento fra i nodi segua l’ordine numerico dei valori corrispondenti alle chiavi nella mappa. L’albero dovrà essere codificato come descritto nell’Esercizio 6. Si assuma che al termine della costruzione della mappa, non vi saranno nella mappa due chiavi con lo stesso valore numerico.

NASTRO INIZIALE NASTRO FINALE
PA1PB2PC3 B(AC)
PA1PB2PC3PD4PE5 D(B(AC)E)
PA3PB2PC1 B(CA)
PA1PB2PC3AA5 C(BA)
AA8PB3PC1PD1AC5PD4PE0PF9 C(B(ED)F(A))
PR3 R

Edizione I

Problema 1

Programmare una Macchina di Turing che, dato un nastro iniziale contenente la rappresentazione decimale di un numero intero positivo n, <> 0, termina la sua esecuzione lasciando sul nastro la rappresentazione decimale di n*100.

NASTRO INIZIALE NASTRO FINALE
431 43100
6 600

Problema 2

Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A e B, termina la sua esecuzione lasciando sul nastro una sola T se la sequenza iniziale contiene almeno una B, una sola F altrimenti.

NASTRO INIZIALE NASTRO FINALE
BABBAB T
B T
AAA F

Problema 3

Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di cifre decimali, termina la sua esecuzione lasciando sul nastro la sequenza che si ottiene eliminando tutte le cifre 0 alla sinistra della cifra diversa da 0 più a sinistra.

Se la sequenza iniziale è composta da sole cifre 0, la macchina deve lasciare sul nastro un solo 0.

NASTRO INIZIALE NASTRO FINALE
000431 431
0000 0
004031 4031
431 431

Problema 4

Una sequenza si dice palindroma se la sua lettura da sinistra verso destra è uguale alla sua lettura da destra verso sinistra.

Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A e B, termina la sua esecuzione lasciando sul nastro la sola sequenza SI se la sequenza iniziale è palindroma, la sola sequenza NO altrimenti.
NASTRO INIZIALE NASTRO FINALE
ABABA SI
ABBA SI
BABBA NO
A SI

Problema 5

Indichiamo con AnBm una sequenza del tipo A…AB…B.

Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza del tipo AnBm, con n>0 e m>0, termina la sua esecuzione lasciando sul nastro

  • una sola A se n>m
  • una sola B se m>n
  • una sola C se n=m.
NASTRO INIZIALE NASTRO FINALE
AAAABB A
AAABBBBB B
AAABBB C

Problema 6

Indichiamo con s e t due generiche sequenze formate da A e B.

Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza del tipo sCtC, termina la sua esecuzione lasciando sul nastro la sequenza SI se S e T sono uguali, la sequenza NO altrimenti.

NASTRO INIZIALE NASTRO FINALE
ABACABAC SI
BBBCBBBC SI
BABACBBAC NO
BBBCABC NO

Problema 7

Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A e B, con almeno una B, termina la sua esecuzione lasciando sul nastro la sequenza di sole B consecutive (cioè non separate da alcuno spazio) che si ottiene da quella iniziale eliminando tutte le A.

NASTRO INIZIALE NASTRO FINALE
ABAABA BB
BAAABABB BBBB
BBB BBB

Problema 8

Dato un numero intero positivo n, (n div 2) è il quoziente della divisione intera.
Ad esempio, (6 div 2) è il numero 3, mentre (9 div 2) è il numero 4.

Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza composta da n A consecutive (con n > 1), termina la sua esecuzione lasciando sul nastro la sequenza composta da (n div 2) A consecutive.

NASTRO INIZIALE NASTRO FINALE
AAAA AA
AAAAA AA
AAA A
AA A

Problema 9

Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A e B, termina la sua esecuzione lasciando sul nastro la sequenza che si ottiene da quella iniziale rimpiazzando due o più A consecutive con una sola A e due o più Bconsecutive con una sola B.

NASTRO INIZIALE NASTRO FINALE
ABAABBBA ABABA
BBAABBBAB BABAB
AAA A
BB B

Alan Turing

alanturing140Alan Mathison Turing

  • 1912-06-23: Nasce a Londra
  • 1926 – 1931: Frequenta la Sherborne School
  • 1930-02-13: Muore il compagno di studi Christopher Morcom
  • 1931 – 1934: Undergraduate al King’s College, Cambridge University
  • 1934: Si laurea con il massimo dei voti
  • 1932 – 1935: Studia meccanica quantistica, probabilità, logica
  • 1935: Eletto fellow del King’s College
  • 1936: Vince il premio Smith’s Prize
  • 1937: Scrive On computable numbers, with an application to the Entscheidungsproblem
  • 1939: Diventa crittoanalista
  • 1939 – 1940: Collabora allo sviluppo di Bombe, macchina utilizzata per decifrare i messaggi segreti codificati con Enigma
  • 1941: Formalizza l’idea di una macchina per gli scacchi
  • 1942: Collabora alla realizzazione di Colossus, macchina utilizzata per decifrare i messaggi segreti codificati con Enigma
  • 1946-02-19: Presenta il progetto di ACE, Automatic Computing Engine, il primo computer elettronico sviluppato nel Regno Unito
  • 1947-02-20: Scrive Lecture to the London Mathematical Society
  • 1948: Scrive Intelligent Machinery
  • 1950: Scrive Computing Machinery and Intelligence
  • 1951: Scrive Paper on non-linear morphogenesis theory
  • 1952: Arrestato, processato e condannato perché omosessuale
  • 1953 – 1954: Lavori incompiuti in biologia e fisica
  • 1954-06-07: Muore a 42 anni per avvelenamento (suicida?)