Edizione XI

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)

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 divisione del numero di ingresso per 10, approssimato in basso.

NASTRO INIZIALE NASTRO FINALE
145 14
534623 53462
10 1
0 0

Problema 3 – Riconoscimento numeri reali

Si scriva un programma per Macchina di Turing che, ricevuta sul nastro una stringa qualunque sull’alfabeto { 0-9, +, , . } lasci sul nastro la scritta SI se la stringa di ingresso rappresenta un numero reale in notazione decimale, definito come

[ + o - ] <sequenza di cifre> [ . <sequenza di cifre> ]

Se la stringa di ingresso non è un numero reale in notazione decimale, il programma deve lasciare sul nastro la stringa NO.

Si noti che, sotto l’assunzione che l’input sia finito, tutti i numeri esprimibili in questa notazione sono in realtà numeri razionali: come tutti i sistemi di elaborazione digitali, la Macchina di Turing può solo trattare approssimazioni razionali dei numeri reali.

NASTRO INIZIALE NASTRO FINALE
34 SI
-342.123 SI
-343-342 NO
234.234.23 NO
+12.45 SI
-38 SI
–34 NO
0 SI

Problema 4 – Divisore per 10 (II)

Si scriva un programma analogo a quello dell’esercizio 2, in grado però di operare su numeri reali (con opzionalmente segno e parti decimali) e approssimante verso lo 0.
Il segno va preservato nel risultato.

NASTRO INIZIALE NASTRO FINALE
145 14
-3017 -301
-3.1415926 0
31.415926 3
-100.5 -10

Problema 5 – Divisore per 10 (III)

Si scriva un programma analogo a quello dell’esercizio 4, che approssimi il risultato all’intero più vicino anziché verso lo 0.

NASTRO INIZIALE NASTRO FINALE
145 14
145.1 15
137.81 14
-218.0001 -22
5 0
6 1

Problema 6 – Conteggio di sottostringhe

Si scriva il programma di una Macchina di Turing che, date sul nastro due stringhe formate da lettere nell’alfabeto { A..J } separate da$, conta le occorrenze distinte della stringa a sinistra del $ all’interno di quella a destra del $.

Il programma deve lasciare sul nastro il numero di occorrenze trovate, espresso in notazione decimale.

NASTRO INIZIALE NASTRO FINALE
AB$ABBACCHIA 1
BA$BABA 2
AB$CABABBAABDABBBABABBBBE 6
AA$AAABBAA 2
F$ABCDE 0
AAA$AAABBAA 1

Problema 7 – Percentuale

Si scriva un programma per Macchina di Turing che, ricevuta in ingresso una stringa della forma a%b, in cui a e b sono numeri decimali e a è compreso fra 0 e 100 (inclusi), lasci sul nastro al termine della computazione il numero naturale corrispondente all’a%di b, approssimato in basso.

NASTRO INIZIALE NASTRO FINALE
10%50 5
25%100 25
33%1000 333
4%1890 75
0%3240 0
100%12 12
50%0 0

Problema 8 – Parole simili

Definiamo la distanza tra due parole composte di lettere A..Z come il numero di posizioni in cui le lettere corrispondenti nelle due parole differiscono.

  • Nel caso una parola sia più corta dell’altra, si assume che essa differisca in tutte le posizioni rimaste.
  • Per esempio, ABACO e ABATE sono a distanza 2, mentre ACANTO e ABATE sono a distanza 4.
  • Una nozione di distanza simile a questa (ma leggermente più complessa) è usata, fra l’altro, dai correttori ortografici forniti con i programmi di videoscrittura.

Si scriva il programma di una macchina di Turing che, dato sul nastro di input una parola seguita dal simbolo $ e una lista di parole separate da :, lasci sul nastro alla fine della computazione la parola della lista più “vicina” alla prima (ovvero, la cui distanza rispetto alla prima parola è minima).

Nel caso vi siano più parole con pari distanza minima, il programma dovrà restituire come risultato la prima della lista (ovvero, quella più a sinistra).
Si assuma che ciascuna parola sia lunga al più 9 caratteri.

NASTRO INIZIALE NASTRO FINALE
PEFA$PELO:PERA:PASSA PERA
PASSARE$FIUTARE:PASSATA:PASSARE PASSARE
NULLA$
SQUOLA$SQUALO:SCUOLA:STUOLO:STOLA SCUOLA

Problema 9 – La prova del 9

La prova del 9 è un metodo per verificare la correttezza di una moltiplicazione, basato sulle proprietà dell’aritmetica modulare.
Il metodo di prova si basa sul fatto che per ogni n, 10n mod 9 = 1; tecnicamente, diciamo che la somma delle cifre di un numero decimale mantiene l’equivalenza al numero in Z9 (l’anello degli interi modulo 9).

La forma tradizionale della prova del 9 è la seguente.
Innanzitutto si traccia una croce, che delimita quattro spazi che chiameremo A, B, C e D:

A B
C D

Nelle quattro zone si scrive (volendo verificare per esempio se è corretto il risultato 1902×1964=3735528):

  • In A: si sommano ripetutamente le cifre del moltiplicando, il primo fattore, finché non resta un numero ad una sola cifra:
    • 1902 => 1+9+0+2=12
    • 12 => 1+2=3
  • In B: si applica lo stesso procedimento con il moltiplicatore, il secondo fattore:
    • 1964 => 1+9+6+4=20
    • 20 => 2+0=2
  • In C: si moltiplicano i 2 numeri appena ottenuti e posti in alto sulla croce.
    Se il risultato della moltiplicazione ha più cifre, esse sono ripetutamente sommate come prima:

    • es. 3*2=6.
  • In D: si sommano le cifre del risultato presunto della moltiplicazione:
    • 3735528 => 3+7+3+5+5+2+8=33
    • 33 => 3+3=6

Nel caso del nostro esempio avremo dunque:

3 2
6 6

Quando, come in questo caso, i due numeri in basso sono uguali allora la prova ha esito positivo, altrimenti ha esito negativo.
Si noti però che:

  • se la prova ha esito negativo allora la moltiplicazione è sicuramente errata
  • se la prova ha esito positivo, il risultato trovato potrebbe essere errato, e differire dal risultato reale per un multiplo di 9. Infatti, se al risultato si sommasse o sottraesse 9 o un suo multiplo, il test sarebbe ancora superato (9 è infatti equivalente a 0 in Z9)!

Si scriva un programma per Macchina di Turing che, ricevuta sul nastro una moltiplicazione con un risultato presunto, nella formaa*b=c (con a, b e c numeri decimali) lasci sul nastro la stringa SI se la prova del 9 ha esito positivo, NO in caso contrario.
Come già osservato, il programma deve rispondere SI anche se la moltiplicazione è errata, ma la prova del 9 è superata.

NASTRO INIZIALE NASTRO FINALE
123*456=56088 SI
123*456=56089 NO
123*456=56097 SI
0*12=0 SI
150*30=4500 SI
150*30=9 SI
150*30=4300 NO

Problema 10 – Espressioni regolari

Una espressione regolare identifica un insieme di stringhe, ovvero un linguaggio.
Un’espressione regolare è denotata da un pattern, ovvero da una sequenza di caratteri, alcuni dei quali dotati di una particolare interpretazione, che indica quali stringhe appartengono all’insieme e quali no.
Ad esempio il pattern CIAO+ denota l’insieme di tutte le stringhe formate dai caratteri C, I, A e che terminano con una sequenza di uno o più caratteri O.
Ecco quindi che le stringhe CIAO, CIAOO, CIAOOOOO ecc. apparterranno all’insieme (si usa dire che esse soddisfano l’espressione regolare), mentre XX, CIA, CIAOA ecc. non vi apparterranno.

Consideriamo pattern formati da sequenze di caratteri da interpretare come segue:

  • Ogni carattere nell’alfabeto { A..Z } indica che nella stringa da verificare deve essere presente lo stesso carattere
  • Il carattere . indica che nella stringa da verificare deve essere presente un carattere qualsiasi
  • Se un carattere è seguito dal carattere * si intende che nella stringa da verificare il carattere precedente l’* può occorrere 0 o più volte (es. CI*AO indica le stringhe della forma CAO, CIAO, CIIAO, …)
  • Se un carattere è seguito dal carattere + si intende che nella stringa da verificare il carattere precedente il + può occorrere 1 o più volte (es. CI+AO indica le stringhe della forma CIAO, CIIAO, …). Si noti che per ogni carattere c, il pattern c+ è equivalente al pattern cc*.

Si scriva il programma di una Macchina di Turing che data sul nastro un pattern nel formato descritto, seguito dal simbolo $ di separazione e da una stringa (anche vuota) sull’alfabeto { A..Z }, lasci sul nastro

  • SI se la stringa soddisfa l’espressione regolare denotata dal pattern,
  • NO altrimenti.
NASTRO INIZIALE NASTRO FINALE
CIAO$CIAOO NO
CIAO$CIAO SI
C*I*A*O*$ SI
C*I*A*O*$IIAAA SI
C*I*A*O*$ICIAO NO
C+I*AO$CIAO SI
C+I*AO$CCIIIAO SI
C+I*AO$CIAOO NO
C.AO$CIAO SI
C.AO$CEAO SI
C.AO$EEAO NO
.*$ SI
.*$BUONLAVORO SI
.*A$BUONLAVORO NO
Notice: This work is licensed under a BY-NC-SA. Permalink: Edizione XI

Comments are closed.