Esercizi di Gara della XV edizione

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

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.

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.