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