Sezione di VALCON.IT
admin Problema 1 – Lo scorciatore In Informatica, una struttura dati è un modo di organizzare le informazioni nella memoria di un calcolatore in modo da facilitare l’esecuzione di un insieme predefinito di operazioni. La struttura dati più semplice è la sequenza, che può essere facilmente rappresentata da una sequenza di simboli sul nastro. Sulle sequenze … Leggi tutto
Problema 1 Programmare una Macchina di Turing che, dato un nastro iniziale contenente la rappresentazione decimale di un numero intero positivo n, <> 0, termina la sua esecuzione lasciando sul nastro la rappresentazione decimale di n*100. NASTRO INIZIALE NASTRO FINALE 431 43100 6 600 Problema 2 Programmare una Macchina di Turing che, dato un nastro … Leggi tutto
Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A e B, termina la sua esecuzione lasciando sul nastro una sola T se la sequenza iniziale contiene almeno una B, una sola F altrimenti. Esempi NASTRO INIZIALE NASTRO FINALE BABBAB T B T AAA F Algoritmo Lo stato 0 indica … Leggi tutto
Programmare una Macchina di Turing che, dato un nastro iniziale contenente la rappresentazione decimale di un numero intero positivo n, <> 0, termina la sua esecuzione lasciando sul nastro la rappresentazione decimale di n*100. Esempi NASTRO INIZIALE NASTRO FINALE 431 43100 6 600 Algoritmo Si posiziona a destra Scrive due volte 0 Codice #1 Commenti … Leggi tutto
Date due sequenze di 1 separate da *, scrive 1 se sono uguali, 0 altrimenti Esempi NASTRO INIZIALE NASTRO FINALE 11*11 1 11*111 0 Algoritmo Elimina un 1 a sinistra e un 1 a destra finché non rimane soltanto * Nei casi di errore cancella tutto e scrive 0 Codice Commenti (0,1,D,-,>) Elimina un 1 … Leggi tutto
Se sul nastro trova CIAO scrive 0, se sul nastro trova BYE scrive 1 Esempi NASTRO INIZIALE NASTRO FINALE CIAO 0 BYE 1 Algoritmo Ci sono due percorsi distinti di lettura controllata del nastro Input iniziale è CIAO allora scrive 0 input iniziale è BYE allora scrive 1 Codice Commenti (0,C,1,-,>) Inizia con C (1,I,2,-,>) … Leggi tutto
Se sul nastro trova 0 scrive CIAO, se trova 1 scrive BYE Esempi NASTRO INIZIALE NASTRO FINALE 0 CIAO 1 BYE Algoritmo Ci sono due percorsi distinti di scrittura su nastro Input iniziale è 0 allora scrive CIAO input iniziale è 1 allora scrive BYE Codice Commenti (0,0,1,C,>) Inizia con C (1,-,2,I,>) … (2,-,3,A,>) … … Leggi tutto
Scrivere CIAO con il nastro inizialmente vuoto Esempi NASTRO INIZIALE NASTRO FINALE CIAO Algoritmo Codice Commenti (0,-,1,C,>) Scrive C (1,-,2,I,>) Scrive I (2,-,3,A,>) Scrive A (3,-,H,O,>) Scrive O
Tratto dal sito ufficiale Consideriamo una macchina che modifica una sequenza di A rimpiazzando ogni A in posizione dispari con una B.La prima A ha posizione pari uguale a 0. Esempi NASTRO INIZIALE NASTRO FINALE A A AA AB AAA ABA AAAA ABAB Algoritmo Lo stato 0 è pari, A rimane Lo stato 1 è dispari, … Leggi tutto
Aggiunge, a destra, il bit di parità a una sequenza binaria Esempi NASTRO INIZIALE NASTRO FINALE 1 11 0 00 11111 111111 11011 110110 Algoritmo I bit 0 mantengono lo stato Pari oppure Dispari I bit 1 cambiano lo stato da Dispari in Pari, oppure da Pari in Dispari Se termina l’input in 0 (Pari) … Leggi tutto