Esercizi sulle Macchine Astratte



Esercizio 1


Ho un sistema di calcolo in cui il livello superiore implementa una macchina astratta il cui linguaggio e' il linguaggio JAVA. Voglio implementare sopra questo livello la macchina astratta corrispondente al linguaggio di microprogrammazione Mic-1. Posso farlo? Se si, perche' cio' e' possibile ed in che modo posso realizzarlo? Se no, perche' non e' possibile e quali sono le caratteristiche del Mic-1 che impediscono tale implementazione?

  • Soluzione.


    Esercizio 2

    La componente "memoria" di una Macchina Astratta deve necessariamente essere realizzata in hardware? Perche'?

  • Soluzione.


    Esercizio 3
    (Anni Precedenti)
    HASKELL e' un linguaggio di programmazione funzionale, basato cioe' su un modello computazionale differente da quello che e' alla base dei linguaggi di programmazione imperativi.
    La nozione di Macchina Astratta per linguaggi di programmazione come HASKELL (MAF, Macchina Astratta Funzionale) e' simile a quella descritta nel corso?
    Una MAF ha le stesse componenti di una MA ?
    se si, le componenti di una MAF hanno funzioni differenti dalle relative componenti di una MA?
    oppure una MAF e' essenzialmente diversa da una MA?
    se si, descriverla.

    Esercizio 4

    Si consideri il linguaggio di programmazione che abbia programmi definiti dalla seguente grammatica: 
    Programma ::=  Istr | Istr;Programma
Istr ::=  m[x]<-0 | m[x]<-1 | m[x]<-m[y] | if B then Istr 
B ::= m[x]=0 | m[x]=1 | m[x]=m[y]
    dove il significato delle istruzioni e' il seguente: 
    m[x] <- 0     (nella cella di memoria di indirizzo x poni 0)
m[x] <- 1     (nella cella di memoria di indirizzo x poni 1)
m[x] <- m[y]  (nella cella di memoria di indirizzo x poni il contenuto della
               cella di indirizzo y)
if B then I   (se B e' vera allora esegui I)
    Inoltre x e y possono avere come valori solo 0, 1, 2, 3. Questo significa che la memoria per i dati associata al nostro linguaggio ha solo quattro celle. Inoltre queste celle della parte di memoria riservata ai dati sono formate da un unico bit (possiamo memorizzarci solo 0 oppure 1).
    Ovviamente questo linguaggio non e' universale (non ha la potenza computazionale per descrivere qualsiasi algoritmo).

    Dire, motivando dettagliatamente la risposta, perche' la Macchina Astratta associata al linguaggio descritto puo' essere realizzata SOLAMENTE in Hardware.

  • Soluzione.

    Esercizio 5

    E' possibile vedere un circuito combinatorio come una Macchina Astratta?

  • Soluzione. (By C. Bosco)

    Esercizio 6

    (a) Descrivere la componente Interprete delle Macchine Astratte.

    (b) Potrebbe accadere che nell'implementazione della MA del livello 5 di un sistema di calcolo la componente memoria sia esattamente la componente memoria del livello 3 ?


  • Soluzione.


    Esercizio 7

    (a) E' possibile avere delle macchine astratte senza la componente Interprete?
    Motivare brevemente la risposta.
    (b) Dire perche' e' indispensabile che in un sistema di calcolo organizzato a livelli esista un livello microprogrammato.

  • Soluzione.


    Esercizio 8


    (a) E' possibile avere un sistema di calcolo organizzato a livelli in cui esistano tre livelli corrispondenti alla macchina astratta del linguaggio Java?
    Motivare brevemente la risposta.
    (b) Dire perche' e' indispensabile che in un sistema di calcolo organizzato a livelli esista il livello 6.

  • Soluzione.



    Esercizio 9

    Nel testo sono descritte due possibili tipi di implementazione per IJVM: realizzazione (parziale) in HW con PicojavaII e realizzazione per interpretazione com Mic-1.
    Sarebbe possibile pensare ad una realizzazione compilativa per IJVM?
    Perche' si o perche' no?


    Esercizio 10

    Indicate quali livelli sono in esecuzione quando fate girare sulla vostra macchina il simulatore per IJVM.
  • Soluzione (by E. Papotto & M. Morgano)


    Esercizio 11

    Sul testo, piu' o meno esplicitamente, si assume che il livello del linguaggio Assembly venga realizzato per traduzione. E' possibile pensare, in teoria, di realizzarlo per interpretazione?

    Esercizio 12

    (a) Avete cinque righe a disposizione (scritte normali e non una di piu') per dirmi perche' e' conveniente organizzare a livelli i sistemi di calcolo.
    (b) Dire perche' in un sistema di calcolo organizzato a livelli almeno un livello deve essere necessariamente realizzato per compilazione (traduzione).
  • Soluzione.


    Esercizio 13

    (a) Qual'e' il numero teorico massimo di livelli in un sistema di calcolo? Perche'?
    (b) Se come parametro di valutazione abbiamo la velocita' di esecuzione dei programmi, e' meglio una realizzazione interpretativa o compilativa di un linguaggio ad alto livello? Perche'?
  • Soluzione.


    Esercizio 14

    Con riferimento ai livelli di macchina virtuale, barrare quelle giuste tra le seguenti asserzioni. Una macchina virtuale e' caratterizzata: (a) dalla velocita' di esecuzione tipica del livello; (b) dal linguaggio di programmazione che accetta; (c) dal metodo usato per simularla a partire da una macchina piu' semplice; (d) dal fatto che il suo linguaggio e' necessariamente piu' complesso di quella su cui viene simulata; (e) dal fatto che il suo linguaggio e' necessariamente piu' semplice di quella su cui viene simulata.
  • Soluzione.

    Esercizio 15

    (a) Supponendo che ormai chiunque sappia piu' o meno quali sono le funzionalita' medie di un telefono cellulare: e' possibile vedere un cellulare come una macchina astratta? In caso negativo motivare la risposta. In caso positivo descrivere brevemente le componenti di tale macchina astratta.

    (b) Se la risposta al punto (a) e' affermativa, sarebbe possibile utilizzare il linguaggio della macchina astratta telefonino per implementare per interpretazione un altro linguaggio? Fate un esempio (anche fantasioso, ma concretamente realizzabile) di una possibile istruzione di tale linguaggio.

  • Soluzione.

    Esercizio 16

    Identificare nella macchina Mic-1 quali sono le parti che corrispondono alla componente Controllo di Sequenza.
    Soluzione
    Esercizio 17

    Fornire un esempio di Macchina Astratta tratto dalla vita comune (del tipo della MA Ristorante descritto nella pagina http://www.dipmat.unict.it/~barba/Architetture.html/MATERIALE-IN-RETE/MA/4.htm.
    Esercizio 18

    Perche' in un sistema di calcolo strutturato a livelli non puo' esserci piu' di un livello realizzato per traduzione?
  • Soluzione.


    Esercizio 19


    (a) Volendo fornire una definizione di Macchina Astratta parallela, questa deve avere una o piu' componenti "Interprete", una o piu' componenti "Memoria"? Discutere.

    (b) Considerate il livello ISA corrispondente al linguaggio IJVM realizzato nel testo del Tananbaum sopra il livello microprogrammato Mic-1. Ci sono componenti della macchina astratta IJVM realizzate per interpretazione? ce ne sono di realizzate direttamente Hardware? ce ne sono altre che sono parte del livello sottostante?
  • Soluzione.


    Esercizio 20

    Spiegare perche' in una macchina astratta realizzata al livello 1 di un sistema di calcolo, la componente "gestione della memoria" e' praticamente inesistente.
  • Soluzione.

    Esercizio 21

    (a) In quali casi e' possibile avere un sistema di calcolo organizzato a livelli in cui tutti i livelli sono realizzati in hardware?

    (b) In un sistema di calcolo organizzato a livelli, cosa si intende quando si dice che "un livello non e' completamente coperto da quello superiore"? Fornire un possibile esempio.
  • Soluzione.

    Esercizio 22

    (a) Identificare nella macchina Mic-1 quali sono le parti che corrispondono alla componente Controllo di Sequenza.

    (b) Discutere brevemente come un impianto Hi-Fi puo' venire visto come una macchina astratta, identificando le varie componenti (che in qualche caso possono essere praticamente inesistenti).
  • Soluzione.

    Esercizio 23

    (a) Riguardo molti microprocessori si parla di backward compatibility (compatibilita'). Visto che un microprocessore puo' esser visto come la realizzazione hardware (di parte) di una macchina astratta, qual e', secondo voi, il significato di backward compatibility in termini di macchine astratte? in altre parole, cosa significa che una macchina astratta e' backward compatible?

    (b) La Macchina di Turing e' alla base della nostra definizione di Macchina Astratta. Quindi una Macchina di Turing potrebbe esser vista anche come una semplicissima macchina astratta. Dire brevemente cosa fa l'interprete di una macchina di Turing.
    In una macchina di Turing universale ci sono sempre due interpreti, uno, per modo di dire, "hardware", e l'altro "software". E' vero? Perche'?

  • Soluzione.

    Esercizio 24

    (a) E' possibile realizzare la macchina astratta IJVM per traduzione su quella Mic-1? Motivare la risposta.
    (b) Cos'e' una Macchina di Turing? Perche' il modello della Macchina di Turing e' alla base delle architetture di tipo Von Neumann?
  • Soluzione.

    Esercizio 25

    (a) Prendete in considerazione l'implementazione descritta nel testo (Tanenbaum) della macchina astratta IJVM. Quali componenti della macchina astratta vengono realizzate (totalmente o parzialmente) dallo Stack?
    (b) Una cucina dotata di tutto, compresa una persona che sta cucinando, puo' esser vista come la realizzazione hardware di una macchina astratta? Se si, identificarne la varie componenti. Se no, spiegarne il motivo.
  • Soluzione.

    Esercizio 26
    (a) Prendete in considerazione la macchina astratta Mic-1. Quali parti della sua realizzazione hardware descritta nel testo (Tanenbaum) corrispondono alla componente Controllo di Sequenza?

    (b) E' possibile che una macchina astratta che tipicamente sarebbe realizzata in hardware venga realizzata per traduzione o compilazione su una macchina astratta corrispondente ad un linguaggio ad alto livello come Java o C?
    Ne abbiamo esempi nella pagina web del corso?
  • Soluzione.

    Esercizio 27
    (a) Si consideri la struttura a livelli di un calcolatore.
  • Si motivi l'introduzione di tale struttura.
  • Si spieghi cos'e' il semantic gap.
  • Possibile soluzione. (by Camillo Bosco)

    (b) Si veda un'impresa di costruzioni come un sistema di calcolo che realizza edifici abitabili. Si descrivano almeno 2 dei suoi livelli di macchina astratta (uno puo' essere il livello "muratore").
  • Possibile soluzione. (by Camillo Bosco)

    Esercizio 28
    E' possibile realizzare IJVM per compilazione (traduzione) su Mic-1? Discutere brevemente.
  • Possibile soluzione.
    Esercizio 29

    Cosa si intende per "realizzazione" di una Macchina Astratta per interpretazione? e per compilazione (traduzione)?
    Esercizio 30

    * Delle varie fasi del ciclo di un interprete in una macchina astratta, qual e' quella piu' lenta a venire eseguita? Perche'?

  • Possibile soluzione.
    Esercizio 31

    Si descriva (brevemente!) il Modello Computazionale di Turing e si discuta la definizione di Computazione in tale modello attraverso un esempio plausibile.
    Esercizio 32
    Qual e' la relazione tra macchina di Turing, macchina (architettura) di von Neumann e definizione di macchina astratta imperativa? Perche' non e' possibile definire macchine astratte che non siano imperative?
  • Possibile soluzione.
    Esercizio 33
    E' possibile avere un sistema di calcolo organizzato a livelli in cui esistano tre livelli corrispondenti alla macchina astratta del linguaggio Java? Motivare brevemente la risposta.
    Dire poi perche' in un sistema di calcolo organizzato a livelli almeno un livello deve essere necessariamente realizzato per compilazione (traduzione).
  • Soluzione.
    Esercizio 34
    Cosa significa, in un sistema di calcolo a livelli, che "un livello che realizza una macchina astratta non copre del tutto il livello sottostante"?
    E' possibile realizzare la macchina astratta Mic-3 sopra il livello della macchina astratta Mic-2 supponendo che quest'ultima sia realizzata in hardware?
    Esercizio 35
    Descrivere le componenti Interprete e Controllo Sequenza di una generica macchina astratta.
    Esercizio 36
    Cos'e' l'Interprete in una macchina astratta?
    Identificare nella macchina Mic-1 quali sono le parti che corrispondono alla componente Memoria.
    Esercizio 37
    Si consideri la seguente frase presa dalle note del corso:
    "La gerarchia di macchine astratte di un sistema di calcolo
    non termina necessariamente con l'implementazione di un linguaggio di programmazione HLL L."
    Commentarla, spiegandone il significato.
    Esercizio 38
    Si descriva la componente Gestione Trasferimento Dati nella macchine astratte Mic-1 e IJVM.
    Esercizio 39
    Commentare e chiarire il senso della seguente frase: "È da notare che nella pratica non è raro che un livello realizzi una macchina astratta che non copre del tutto il livello sottostante ma ne potenzia alcune delle caratteristiche, lasciandone trasparire del tutto altre."
    Esercizio 40
    Si consideri un sistema a livelli contenente i livelli L1, L2 ed L3.
    L1 e' realizzato in hardware e tale che il tempo di esecuzione di un'istruzione di L1 e' di K secondi.
    I livelli L2 ed L3 sono invece interpretati. Ogni istruzione di L2 viene realizzata con n istruzioni di L1. Ogni istruzione di L3 viene realizzata con n istruzioni di L2.
    Il linguaggio L3 e' m volte piu' potente del linguaggio L2 (per ogni cosa che fa un'istruzione di L3, ce ne vogliono m di L2 per fare la stessa cosa. In breve, lo stesso algoritmo si realizza in L2 con un programma m volte piu' lungo di uno equivalente in L3).
    Siano P3 e P2 due programmi semanticamente equivalenti scritti, rispettivamente, in L3 e L2 (semanticamente equivalenti significa che calcolano la stessa cosa).
    Fornire delle espressioni che esprimano il tempo di esecuzione di P3 e di P2 in modo da poter confrontare tali tempi tra loro e poter decidere (fissati n ed m) se, dal punto di vista della velocita' di esecuzione, convenga eseguire P3 sul livello 3 oppure P2 sul livello 2.
    Giustificare brevemente la soluzione proposta.
  • Soluzione.
    Esercizio 41
    Descrivere brevemente cosa si intende per "struttura a livelli dei sistemi di calcolo".
    Esercizio 42
    Si consideri la seguente frase presa dalle note del corso:
    Una programmazione consapevole ed adeguata per una particolare realizzazione di una macchina astratta e' possibile solo se l'utente conosce non solo la struttura della macchina astratta, ma anche quali componenti sono stati realizzati direttamente in hardware, quali emulati, quali interpretati. Infatti, scegliere un modo piuttosto che un altro di realizzare un algoritmo puo' risolversi in un guadagno di prestazioni, dovuto alla maggiore efficienza della realizzazione di alcune componenti della macchina astratta rispetto ad altri.
    E' un'affermazione condivisibile? Giustificare brevemente la risposta.
    Esercizio 43

    Si consideri il linguaggio di programmazione, che chiameremo VSL (Veeery Simple Language), che ha i programmi definiti dalla seguente grammatica: 
    Programma ::=  Istr; | Istr;Programma
Istr ::=  m[x]<-0 | m[x]<-1 | m[x]<-m[y] | m[x]<-m[y]ANDm[z] | m[x]<-m[y]ORm[z] |  if B then Istr
B ::= m[x]=0 | m[x]=1 | m[x]=m[y]
    dove il significato delle istruzioni e' il seguente: 
    m[x] <- 0     (nella cella di memoria di indirizzo x poni 0)
m[x] <- 1     (nella cella di memoria di indirizzo x poni 1)
m[x] <- m[y]  (nella cella di memoria di indirizzo x poni il contenuto della
               cella di indirizzo y)
m[x] <- m[y]ANDm[z]  (nella cella di memoria di indirizzo x poni l'OR del contenuto della
               cella di indirizzo y con quello della cella z)
m[x] <- m[y]ORm[z]  (nella cella di memoria di indirizzo x poni l'OR del contenuto della
               cella di indirizzo y con quello della cella z)
    Inoltre x, y e z possono avere come valori solo 0, 1, 2, 3. Questo significa che la memoria per i dati associata al nostro linguaggio ha solo quattro celle. Inoltre queste celle della parte di memoria riservata ai dati sono formate da un unico bit (possiamo memorizza rci solo 0 oppure 1).
    Ovviamente questo linguaggio non e' universale (non ha la potenza computazionale per descrivere qualsiasi algoritmo).

    Realizzare via software (in modo interpretativo cioe'), la macchina astratta VSL sopra la macchina astratta JAVA.

  • Realizzazione compilativa, by Danilo Vaccalluzzo.
    Esercizio 44

    Che relazione esiste tra le Macchine di Turing ed il concetto di Macchina Astratta Imperativa? Ogni macchina astratta e' comunque imperativa, o possono esserci altre nozioni di macchina astratta? Giustificare.
    Esercizio 45

    Identificare nella macchina Mic-2 quali sono le parti che corrispondono alla componente Controllo di Sequenza. Fornire breve giustificazione.
  • Soluzione.
    Esercizio 46
    In un sistema di calcolo organizzato a livelli cosa si intende per livello di microprog rammazione?
    Esercizio 47
    Cos'e' una Macchina Astratta? Quali sono le componenti di una Macchina Astratta? Identificare nell'Hardware Mic-1 le varie componenti della macchina astratta che tale Hardwarre realizza.
    Esercizio 48
    Fornire la definizione di "livello di Microprogrammazione" all'interno di un sistema di calcolo organizzato a livelli.
    Esiste sempre tale livello? perche'?
    Esercizio 49
    Fornire la definizione di Realizzazione Interpretativa di una macchina astratta.
    Descrivere la differenza tra realizzazione interpretativa via firmware o via software. Dire perche', nello stesso sistema organizzato a livelli, non ci possono essere due macchine astratte entrambe realizzate in modo interpretativo.
    Esercizio 50
    Descrivere le componenenti della macchina astratta IJVM e la loro implementazione all'interno del sistema a livelli studiato nel corso.