ESERCIZI di GARA

Problema 1 – La morra cinese Nel gioco della Morra cinese due giocatori scelgono ciascuno un simbolo fra Carta, Forbice, Pietra (di solito, indicandolo in contemporanea con un gesto della mano): Forbice vince su Carta Carta vince su Pietra Pietra vince su Forbice. Si scriva un programma per macchina di Turing che, ricevuto in ingresso sul … Leggi tutto

Problema 1 – Notazione unaria Un numero intero n è rappresentato in notazione unaria da una sequenza di n simboli uguali, per esempio U. Si scriva un programma per macchina di Turing che, ricevuto sul nastro un intero positivo in notazione decimale, lasci come risultato lo stesso numero, scritto in notazione unaria. NASTRO INIZIALE NASTRO FINALE … Leggi tutto

Problema 1 – Moltiplicatore per 10 Si scriva un programma per Macchina di Turing che, ricevuto sul nastro un numero decimale, lasci sul nastro alla fine della computazione il risultato della moltiplicazione del numero di ingresso per 10. NASTRO INIZIALE NASTRO FINALE 3 30 450 4500 123456 1234560 0 0 Problema 2 – Divisore per 10 (I) … Leggi tutto

Problema 1 – Stringhe Trine Una stringa si dice trina se è della forma aaa, ovvero se è composta da tre parti uguali. Si scriva un programma che, ricevuta in ingresso una stringa sull’alfabeto {a, b, c}, lasci sul nastro al termine della computazione la stringa trina ottenuta triplicando la stringa di ingresso. NASTRO INIZIALE NASTRO … Leggi tutto

Problema 1 – Quadristringhe Una quadristringa è una stringa su un alfabeto dato che ha la forma XXXX, ovvero, che è composta di quattro parti uguali ripetute. Per esempio, abcabcabcabc è una quadristringa. Si scriva un programma che, data in ingresso una stringa sull’alfabeto a, b, c, lasci sul nastro SI se la stringa di ingresso … Leggi tutto

Edizione patrocinata dal Rotary Club di Pisa e aperta alle scuole della provincia di Pisa. Problema 1 – Ababa NO Scrivere un programma per macchina di Turing che, ricevuta in ingresso sul nastro una stringa composta di A e B, lasci sul nastro la scritta SI se la sequenza conteneva un numero uguale di A e … Leggi tutto

Problema 1 – Addizione unaria Nei sistemi di numerazione posizionale, il valore denotato da un numero è ottenuto moltiplicando ogni cifra per la corrispondente potenza di una base.Nel caso della notazione decimale, la base è 10; la cifra più a destra è moltiplicata per 100=1, quella successiva per 101=10, la terza da destra per 102=100, e … Leggi tutto

Problema 1 – Musica, musica! Tradizionalmente, le sette note della scala musicale vengono denominate in Italia do, re, mi, fa, sol, la, si.Le stesse note nel sistema anglosassone vengono indicate con le prime lettere dell’alfabeto: A, B, … G, con do re mi fa sol la si C D E F G A B Si scriva … Leggi tutto

Problema 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 … Leggi tutto

Problema 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. NASTRO INIZIALE NASTRO FINALE AABABBBAABAAABAABAA ACDCDBBACDAACDACDAA BBBBAAA BBBBAAA AABB ACDB Problema 2 – Parentesi bilanciate Una sequenza di parentesi quadre … Leggi tutto