Vai al contenuto

Edizione XI

  • di

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 INIZIALENASTRO FINALE
330
4504500
1234561234560
00

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 INIZIALENASTRO FINALE
14514
53462353462
101
00

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 INIZIALENASTRO FINALE
34SI
-342.123SI
-343-342NO
234.234.23NO
+12.45SI
-38SI
–34NO
0SI

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 INIZIALENASTRO FINALE
14514
-3017-301
-3.14159260
31.4159263
-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 INIZIALENASTRO FINALE
14514
145.115
137.8114
-218.0001-22
50
61

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 INIZIALENASTRO FINALE
AB$ABBACCHIA1
BA$BABA2
AB$CABABBAABDABBBABABBBBE6
AA$AAABBAA2
F$ABCDE0
AAA$AAABBAA1

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 INIZIALENASTRO FINALE
10%505
25%10025
33%1000333
4%189075
0%32400
100%1212
50%00

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 INIZIALENASTRO FINALE
PEFA$PELO:PERA:PASSAPERA
PASSARE$FIUTARE:PASSATA:PASSAREPASSARE
NULLA$ 
SQUOLA$SQUALO:SCUOLA:STUOLO:STOLASCUOLA

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:

AB
CD

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:

32
66

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 INIZIALENASTRO FINALE
123*456=56088SI
123*456=56089NO
123*456=56097SI
0*12=0SI
150*30=4500SI
150*30=9SI
150*30=4300NO

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 INIZIALENASTRO FINALE
CIAO$CIAOONO
CIAO$CIAOSI
C*I*A*O*$SI
C*I*A*O*$IIAAASI
C*I*A*O*$ICIAONO
C+I*AO$CIAOSI
C+I*AO$CCIIIAOSI
C+I*AO$CIAOONO
C.AO$CIAOSI
C.AO$CEAOSI
C.AO$EEAONO
.*$SI
.*$BUONLAVOROSI
.*A$BUONLAVORONO

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *