Accesso

Cherubino     Gara nazionale di programmazione della
Macchina di Turing
 
 

 

Esercizi di Gara della XV 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: Stringhe pari. [Punti 1]. Si scriva un programma per macchina di Turing che, ricevuta in ingresso una stringa sull'alfabeto {A, …, G}, lasci sul nastro SI se la stringa era di lunghezza pari, NO se essa era di lunghezza dispari.

NASTRO INIZIALE

NASTRO FINALE

ABC

NO

AB

SI

GGGGGGGG

SI

ABAC

SI

E

NO

Esercizio 2: Ripetizioni. [Punti 2]. Si scriva un programma per macchina di Turing che, ricevuta in ingresso una stringa composta da un numero decimale n fra 0 e 7, seguito da una lettera l fra A e G, lasci sul nastro una stringa composta da n ripetizioni di l.

NASTRO INIZIALE

NASTRO FINALE

3A

AAA

7C

CCCCCCC

0E

 

1B

B

Esercizio 3: Raddoppi. [Punti 4]. Si scriva un programma per macchina di Turing che, ricevuto in ingresso un numero intero, lasci sul nastro il doppio del numero indicato.

NASTRO INIZIALE

NASTRO FINALE

31

62

1

2

1651

3302

9

18

Esercizio 4: Steganomusica. [Punti 5]. Nel sistema anglosassone di notazione musicale, le note sono indicate con delle lettere, secondo la corrispondenza: Do=C, Re=D, Mi=E, Fa=F, Sol=G, La=A, Si=B. Si scriva un programma per macchina di Turing che, ricevuta una stringa sull'alfabeto {A, …, Z}, lasci sul nastro soltanto la sottosequenza della stringa originale composta concatenando i soli simboli corrispondenti a note musicali presenti nella stringa di ingresso. “Nascondere” un messaggio (in questo caso, un motivo musicale) mescolandolo con altri dati irrilevanti, che magari sembrano rappresentare qualcos'altro, è una tecnica crittografica nota col nome di steganografia.

NASTRO INIZIALE

NASTRO FINALE

LAGAZZALADRA

AGAAADA

ILBARBIEREDISIVIGLIA

BABEEDGA

LENOZZEDIFIGARO

EEDFGA

RHAPSODYINBLUE

ADBE

IRIS

 

Esercizio 5: Tempo, tempo! [Punti 18]. Nella musica occidentale, la durata di una nota (chiamata valore) è espressa come una frazione (tipicamente, una potenza di due) di una unità fondamentale. A queste durate si danno nomi convenzionali: massima = 8, lunga = 4, breve = 2, semibreve = 1, minima = 1/2, semiminima = 1/4, croma = 1/8, semicroma = 1/16, biscroma = 1/32, semibiscroma = 1/64, fusa = 1/128. Codifichiamo un brano musicale facendo seguire, al nome della nota secondo la notazione anglosassone, il suo valore (escludendo la massima e la lunga, ormai in disuso, e la breve) codificata da una cifra k, fra 0 e 7, che esprime la durata di 1/2^k.
La varie durate sono normalmente denotate con simboli particolari: per esempio nella figura accanto abbiamo, da sinistra a destra: semibreve, minima, semiminima, croma, semicroma; di ciascun valore viene dato in alto il valore, al centro il simbolo, e in basso la codifica numerica che useremo in questo esercizio (e nei successivi). I simboli per la biscroma, semibiscroma, fusa sono analoghi a quelli della croma e semicroma, ma rispettivamente con 3, 4 e 5 code sul gambo.
Useremo inoltre una Z per indicare una pausa (ovvero, nessuna nota emessa), anch'essa seguita da una codifica della durata. Così, A2 sarà la codifica di un La semiminima (durata 1/4), mentre Z0 indica una pausa semibreve (durata 1). Si scriva un programma per macchina di Turing che, ricevuta in ingresso sul nastro una melodia codificata come sopra descritto, di lunghezza qualunque, lasci sul nastro la lunghezza totale del brano, espressa in unità, e approssimata in alto se necessario.

NASTRO INIZIALE

NASTRO FINALE

A0B1C1D2A1D2

3    (dato da 1+1/2+1/2+1/4+1/2+1/4)

Z0Z0Z0Z0

4    (dato da 1+1+1+1)

C1D1C0D3F2D3Z1C0E1F2A2C3

6    (dato da 1/2+1/2+1+1/8+1/4+1/8+1/2+1+1/2+1/4+1/4+1/8)

A7

1    (dato da 1/128)

C7D4E5

1    (dato da 1/128+1/16+1/32)

A0B1C1D2A1D2

3    (dato da 1+1/2+1/2+1/4+1/2+1/4)

 

Esercizio 6: La metà della metà. [Punti 9]. Sempre nella notazione musicale occidentale, si usa un “.” (detto punto di valore) per indicare che la durata della nota precedente deve essere aumentata della metà del suo valore. Quindi, un solo punto equivale a moltiplicare la durata per 3/2; un doppio punto moltiplica per 7/4; un triplo punto per 15/8, ecc. Si scriva un programma per macchina di Turing che, ricevuta sul nastro di ingresso una melodia codificata come nell'esercizio precedente, con la possibile aggiunta di un numero qualunque di punti dopo le durate (ma tale da non superare la “grana” minima di 1/128 di durata), lasci sul nastro la stessa melodia, codificata senza fare uso di punti.

 

NASTRO INIZIALE

NASTRO FINALE

A0B1C1D2A1D2

A0B1C1D2A1D2

A0.

A0A1

C2A3..D2

C2A3A4A5D2

D6.Z2.D2..

D6D7Z2Z3D2D3D4

A0.A1...A4Z3

A0A1A1A2A3A4A4Z3

A0B1C1D2A1D2

A0B1C1D2A1D2

G0.B2

G0G1B2

C2A3..D2

C2A3A4A5D2

Esercizio 7: Fuga in Do Maggiore per Macchina di Turing e Cervello Solo. [Punti 15]. Una fuga è una composizione musicale polifonica (cioè, con più voci o strumenti) in cui un dato tema (cioè, un frammento di melodia) viene presentato più volte, affidato a varie voci, alterato e ripetuto in vari modi. Nella sua forma più semplice, le varie voci entrano una alla volta (le altre voci hanno soltanto pause fino alla loro entrata), ciascuna esponendo lo stesso soggetto, ovvero un breve tema musicale (si dice allora che la seconda voce entra con una risposta reale, identica al soggetto); dopo l'esposizione, le varie voci progrediscono in maniera differenziata, secondo le regole del contrappunto. Noi codificheremo un brano musicale a più voci indicando ciascuna voce nella notazione vista sopra, data dal nome di una nota (A-G) oppure Z per una pausa, seguita da una durata (0-7) e da zero o più punti. Le varie voci saranno separate dal simbolo $. Si scriva un programma per Macchina di Turing che, ricevuta sul nastro la codifica di una composizione musicale a un numero qualunque di voci, lasci sul nastro il solo soggetto, oppure lasci il nastro vuoto se la composizione non ha le caratteristiche della fuga in forma semplice presentate sopra.

 

NASTRO INIZIALE

NASTRO FINALE

C1D1E1F1.E2D2$Z0C1D1E1F0.$Z0Z0C1D1E1A2

C1D1E1

A0B1C0..D3$Z0Z0A0B1E2.C0

A0B1

A0B1C0..D3$Z0Z0A0B1E2.C0$Z1A0C0D1

A0

A0.B1C0.D3$Z0.A0.B1C0.D3$Z0.Z1A0.B1C0.

A0.B1C0.

A0.B1C0.D3$Z0.A1.B1C0.D3$Z0.Z1A0.B1C0.

 

C1D1E1F1.E2D2$Z0C1D1E1F0.$Z0Z0C1D1E1A2

C1D1E1

Esercizio 8: Il Codice Parsons - indicizzazione. [Punti 10]. Il codice Parsons è stato inventato per permettere la ricerca approssimata di temi in database musicali. Si basa su una semplice codifica, in cui ogni nota (ignorando le pause) è codificata in base alla sua altezza rispetto alla precedente.
Il codice utilizza soltanto i seguenti quattro simboli:

  • * = la prima nota del tema
  • u = la nota è più alta rispetto alla precedente
  • r = la nota ha la stessa altezza della precedente
  • d = la nota è più bassa rispetto alla precedente

Ai fini dell'esercizio, considereremo una sola ottava di musica, in cui A (=la) è la nota più bassa, mentre G (=sol) è la nota più alta. Si scriva un programma per macchina di Turing che, data sul nastro una melodia (a una sola voce), codificata secondo le convenzioni di cui agli esercizi precedenti, lasci sul nastro come risultato il corrispondente codice Parsons.

NASTRO INIZIALE

NASTRO FINALE

C1D1E1F1.E2D2

*uuudd

A0B1C0..D3

*uuu

E2F3F3Z0.F1B0Z1A1

*urrdd

G0..A2Z0G0..A2G2Z2G0

*dudur

C4E4F4C4C4E4F4C4E4F4G2

*uudruuduuu

C1D1E1F1.E2D2

*uuudd

A0B1C0..D3

*uuu

E2F3F3Z0.F1B0Z1A1

*urrdd

Esercizio 9: Il Codice Parsons - ricerca. [Punti 21]. Si scriva un programma per macchina di Turing che, data sul nastro la codifica Parsons di una melodia cercata, seguita da un simbolo $ e poi da un brano musicale (a una voce) codificato come di consueto, lasci sul nastro il primo frammento di musica all'interno della melodia che corrisponde al codice Parsons fornito, oppure lasci il nastro vuoto se il brano non contiene nessun frammento che corrisponde al codice dato.

NASTRO INIZIALE

NASTRO FINALE

*uuu$C1D1E1F1.E2D2

C1D1E1F1.

*udd$C1D1E1F1.E2D2

E1F1.E2D2

*urdd$E2F3F3Z0.F1B0Z1A1

 

*ruru$A0Z0C2C2D2D0.Z0E1F1D2

C2D2D0.Z0E1

*ruru$A0Z0A2C2C0.Z2G1F1D2

A0Z0A2C2C0.Z2G1

*uuu$F1D1E1F1.G2D2

D1E1F1.G2

*udd$C1D1E1F1.E2D2

E1F1.E2

Esercizio 10: Tanti auguri a te. [Punti 30]. Nel giorno in cui scriviamo (22 Febbraio 2011) cade il 154° compleanno di Heinrich Rudolf Hertz, il fisico tedesco che ha dato il nome all'unità di misura della frequenza - l'Hertz appunto, abbreviato Hz. Ogni nota musicale corrisponde a un suono a una determinata frequenza: per esempio, il La della cosiddetta "ottava centrale" (che è numerata per convenzione con il numero 4) corrisponde esattamente a 440Hz. Indicheremo questo La con la notazione "4A".
 
Ogni ottava è composta da 12 semitoni, corrispondenti ai tasti bianchi e neri del pianoforte, e va da Do a Do. Due note consecutive saranno separate a volte da un semitono, a volte da un tono (ovvero, due semitoni), secondo lo schema mostrato in figura. Le stesse note, ma all'ottava più grave, hanno esattamente la metà della frequenza della nota all'ottava superiore, quindi "3A" ha frequenza 220Hz, e "2A" corrisponde a 110Hz. D'altra parte, "5A" corrisponde a 880Hz, e così via. Fra un semitono e il successivo la frequenza aumenta di un fattore moltiplicativo pari av(12&2)(è il cosiddetto temperamento equabile, a cui  Johan Sebastian Bach – il cui 325° compleanno cadrà il prossimo 21 Marzo – dedicò il suo “Clavicembalo ben temperato”). Sciaguratamente, si tratta di un valore irrazionale, pari a

1.0594630943592952645618252949463417007792043174941856285592084314587616460632557223837683768639455
690077407643263828173662417375208278510396447239851142711154329904702397149338041654256876420976329
379895947129709947064800938991173847686705520689400326781575138330323131995539095901458748459550068
180652177280236281045557138695532017548026400571795958795845375678298300209773792500536874403398881
93760632343525439900632883084612552948088872148233044140741848931081...

Così, se 4A corrisponde a 440Hz, 4B (che è due semitoni sopra 4A) varrà 494Hrz, 5C (che è un semitono sopra 4B) varrà 523Hz, 3B (che è un ottava esatta sotto 4B) varrà 247Hz, e così via. Si scriva un programma per macchina di Turing che, ricevuto sul nastro di ingresso il nome di una nota preceduto dal numero dell'ottava, nell'intervallo 2A-6G (per confronto: la maggior parte dei pianoforti hanno tasti da 0A a 8C; gli strumenti elettronici MIDI vanno da -1C a 9G), lasci sul nastro di uscita la sua frequenza calcolata come indicato sopra, approssimata all'intero più vicino.
Suggerimento: nell'effettuazione dei calcoli, si consiglia di usare una precisione sufficiente per il fattore di cui sopra, per esempio 1.059463, onde evitare errori di approssimazione.

NASTRO INIZIALE

NASTRO FINALE

6E

1319

4A

440

4B

494

4C

262

5C

523

3E

165

2A

110

6G 1568

 

 I testi

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