Accesso

Cherubino     Gara nazionale di programmazione della
Macchina di Turing
 
 

Esercizi di Gara della III edizione


     

  1. Programmare una macchina di Turing che, dato un nastro iniziale contenente un numero intero n compreso tra 1 e 9, termina la sua esecuzione lasciando sul nastro n A consecutive.
  2. Esempi

    nastro iniziale

    nastro finale

    1

    A

    5

    AAAAA

    9

    aaaaaaaaa

     

  3. Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza di n A consecutive (con n>0), termina la sua esecuzione lasciando sul nastro il numero n.
  4. Esempi

    nastro iniziale

    nastro finale

    A

    1

    AAAAAA

    6

    AAAAAAAAAAA

    11

     

  5. Programmare una macchina di Turing che, dato un nastro iniziale contenente due numeri interi positivi x e y separati da una cella vuota tali che x>y e 9>=y>0, termina la sua esecuzione lasciando sul nastro soltanto la differenza tra x e y.
  6. Esempi

    nastro iniziale

    nastro finale

    9-4

    5

    13-6

    7

    302-3

    299

     

  7. Indichiamo con S una sequenza formata da A, B o C ed indichiamo con x e y un simbolo che sia A o B. Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza del tipo xyS termina la sua esecuzione lasciando sul nastro la sequenza ottenuta da S rimpiazzando tutte le occorrenze di x con y.
  8. Esempi

    nastro iniziale

    nastro finale

    ABcAB

    CBB

    BBABC

    ABC

    BA

     

     

     

     

  9. Programmare una macchina di Turing che, dato un nastro iniziale contenente due sequenze di A separate da una D, termina la sua esecuzione lasciando sul nastro la sequenza che contiene il maggior numero di A.
  10. Esempi

    nastro iniziale

    nastro finale

    AADA

    AA

    AADAAA

    AAA

    AADAA

    DA

    AA

    A

     

  11. Indichiamo con S e T due sequenze non vuote e della stessa lunghezza formate da A o B. Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza del tipo SDT, termina la sua esecuzione lasciando sul nastro nastro la sola sequenza SI se T è un anagramma di S, la sola sequenza NO altrimenti.
  12. Esempi

    nastro iniziale

    nastro finale

    ABADBAA

    SI

    BABADABBA

    SI

    ABBDBAA

    ABADABB

    NO

    NO

     

  13. Programmare una macchina di Turing che, dato un nastro iniziale contenente un numero intero (arbitrariamente grande), termina la sua esecuzione lasciando sul nastro la sola sequenza SI se il numero è divisibile per 3, la sola sequenza NO altrimenti.
  14. Esempi

    nastro iniziale

    nastro finale

    3

    SI

    27

    SI

    81

    SI

    20

    NO

    7676585

    NO

     

  15. Una sequenza di parentesi si dice bilanciata secondo la seguente definizione induttiva:

    1. la sequenza vuota è bilanciata,
    2. se S e T sono sequenze bilanciate allora anche la sequenza ( S ) T è bilanciata.

Rappresentando ( con B e ) con E, programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza di B ed E, termina la sua esecuzione lasciando sul nastro la sola sequenza SI se la sequenza è bilanciata, la sola sequenza NO altrimenti.

Esempi

nastro iniziale

nastro finale

BEBE

SI

BBBEEE

SI

BBEBEE

BBBEBEEBEE

SI

SI

BEE

NO

BBEEEB

NO

  I GARA
  II GARA
  III GARA
  IV GARA
  V GARA
  VI GARA
  VII GARA
  VIII GARA
  IX GARA
  GARA ROTARY 2006
  X GARA
  XI GARA
  XII Gara
  XIII Gara
  XIV Gara
  XV Edizione
  XVI Edizione
  XVII Edizione
  XVIII Edizione
  XIX Edizione
(Altri collegamenti...)