Esercizi di Gara della XIV edizione

Esercizio 1: Numeri pari [Punti 3]. Si scriva un programma per macchina di Turing che, ricevuto in ingresso sul nastro un numero decimale lasci sul nastro “P” se il numero era pari, “D” se era dispari.

Esercizio 2: ZUDTQCSSON [Punti 4]. Il Sistema Sbilenco di Numerazione (SSN) prevede che ogni cifra venga indicata con l'iniziale del suo nome in Italiano. Quindi, 0=Z, 1=U, 2=D, ecc. È semplice trasformare un numero decimale in un codice SSN, ma può essere complicato, dato un codice SSN, ricostruire il numero originale. Si scriva un programma per macchina di Turing che, dato un codice SSN (senza Z iniziali), lasci sul nastro il numero decimale corrispondente, se unico, oppure “X” se non è possibile ricostruire il numero.

Esercizio 3: Modulo tre [Punti 5]. Si scriva un programma per macchina di Turing che, ricevuto in ingresso sul nastro un numero decimale lasci sul nastro il valore del numero modulo tre (ovvero, il resto della divisione per tre).

Esercizio 4: Numeri ascendenti [Punti 6]. Un numero si dice ascendente se ogni sua cifra ha un valore strettamente superiore a quello di ciascuna delle cifre che lo precedono. Per esempio, 368 è un numero ascendente (infatti, 3 < 6 < 8). Si scriva un programma per macchina di Turing che, ricevuto in ingresso sul nastro un numero decimale, lasci sul nastro “A” se il numero era ascendente, “N” in caso contrario.

Esercizio 5: Numeri discendenti [Punti 7]. Similmente alla definizione data all'esercizio precedente, un numero si definisce discendente se ciascuna delle sue cifre è strettamente minore delle precedenti. Per esempio, 8652 è un numero discendente. Si scriva un programma per macchina di Turing che, ricevuto in ingresso sul nastro un numero decimale maggiore o uguale a 10, lasci sul nastro “A” se il numero era ascendente, “D” se era discendente, “V” altrimenti.

Esercizio 6: La Sequenza Generalizzata Essaria di Fibonacci [Punti 12]. La Sequenza Generalizzata di Fibonacci SGF(n,m) è la sequenza di numeri generati sommando i due precedenti elementi della sequenza, assumendo che i primi due elementi siano n e m. Avremo quindi SGF₁(n,m)=n, SGF₂(n,m)=m, SGF₃(n,m)=n+m, SGF₄(n,m)=m+(n+m), SGF₅(n,m)=(n+m)+(m+(n+m)), ecc. La normale sequenza di Fibonacci è uguale a SGF(1,1), e genera i valori 1, 1, 2, 3, 5, 8, 13, 21, ecc.

La notazione essaria consiste nel denotare un numero non con la consueta notazione posizionale, ma semplicemente indicando il simbolo S tante volte quant'è il valore del numero. Per esempio, la stringa SSSSS denota il numero 5, mentre SS rappresenta il numero 2.

Si scriva un programma per Macchina di Turing che, ricevuta su nastro una sequenza non vuota di numeri positivi in notazione essaria, separati da un singolo simbolo N, lasci sul nastro il simbolo T se la sequenza descrive una sottosequenza di una qualche SGF, o F in caso contrario.

Esercizio 7: Steganografia [Punti 14]. La steganografia è una tecnica per trasmettere un messaggio (anche non cifrato) nascondendolo all'osservatore non autorizzato “confondendolo” all'interno di altra informazione. Per esempio, si può inviare una lunga missiva, con la convenzione che solo la quinta lettera di ogni paragrafo è parte del messaggio “vero”, mentre tutto il resto è solo materiale di copertura, destinato a confondere l'avversario-spione. Per questo esercizio prenderemo in esame una forma semplice di steganografia, consistente nell'inviare una stringa quasi-simmetrica (intendendo che normalmente su un input di dimensione n, il simbolo alla posizione k-esima è uguale al simbolo in posizione (n-k+1)-esima), con l'intesa che solo i punti in cui la stringa non è simmetrica costituiscono il messaggio “vero”.

Si scriva quindi un programma per macchina di Turing che, ricevuta sul nastro una stringa quasi-simmetrica sull'alfabeto A-Z, contenente un messaggio steganografico dato dalle sole lettere non-simmetriche nella sequenza, lasci sul nastro il messaggio decodificato. In caso di stringa di lughezza dispari, il simbolo centrale si considera facente parte del messaggio da recuperare.

Esercizio 8: I conti del SSN [Punti 16]. Come si può comprendere facilmente, il SSN (introdotto nell'Esercizio 2) ha grossi problemi a far tornare i conti. Si scriva un programma per macchina di Turing che, ricevuta sul nastro un'espressione nella forma n+m, in cui n e m sono numeri in notazione SSN (senza limiti di valore), lasci sul nastro l'espressione n+m=r (in cui r è il risultato della somma fra n e m espresso in SSN), se è possibile determinarlo univocamente, oppure il simbolo “?” in caso contrario.

Esercizio 9: I conti del SSN – parte 2 [Punti 18]. Si scriva un programma per macchina di Turing che, ricevuta sul nastro un'espressione nella forma n+m=r in cui n, m e r sono numeri di esattamente tre cifre espressi in SSN, e con la garanzia che la somma sia corretta, lasci sul nastro la stessa espressione con i numeri in notazione decimale, se è possibile ricavarli, oppure “X” in caso contrario.

Esercizio 10: Numeri appaSSioNanti [Punti 25]. Un numero in notazione SSN è detto appaSSioNante se è divisibile per S, ovvero se il resto della divisione per S è 0 – per una qualche interpretazione di S. In altri termini, sono appaSSioNanti tutti i numeri SSN che hanno almeno una interpretazione decimale che è divisibile per 6 oppure per 7. Per esempio,  USO è appaSSioNante (si può interpretare come 168, che è divisibile per 6 e per 7), come anche SO (interpretabile come 78, che è divisibile per 6) o UZZU (1001, divisibile per 7). Non sono invece appaSSioNanti NTC (935, non divisibile per 6 né per 7) o USZZ (interpretabile come 1600 o come 1700, nessuno dei quali è divisibile né per 6, né per 7).

Si scriva un programma per Macchina di Turing che, ricevuto in input un numero appaSSioNante in notazione SSN (di cui è quindi garantita la divisibilità per S), lasci sul nastro la sua interpretazione decimale di valore minore (che dovrà ancora essere divisibile per S).