Esercizi

Esercizi 1 Sistema Binario

Traccia 1. Convertire i seguenti numeri interi positivi dalla base decimale alla base binaria in parole di dimensione 8 bit

(7)₁₀
(66)₁₀
(79)₁₀
(122)₁₀
(255)₁₀

Domanda. E' possibile convertire il numero 300 dalla base decimale alla base due utilizzando 8bit? Giustificare o dimostrare la risposta.

Traccia 2. Convertire i seguenti numeri interi positivi dalla base binaria (con dimensione della parola di 8bit) in base decimale

(10101000)₂
(00101001)₂
(00000010)₂
(11101011)₂
(11000111)₂

Domanda. Analizzando i valori binari sopra riportati come è possibile discriminare un numero pari da uno dispari? Giustificare o dimostrare la risposta.

Traccia 3. Convertire i seguenti numeri interi positivi dalla base decimale alla base ottale ed esadecimale (con dimensione della parola di 8bit)

(66)₁₀
(122)₁₀

Traccia 4. Convertire i seguenti numeri interi positivi dalla base ottale o dalla base esadecimale in base decimale
(117)₈
(3B)₁₆
(1036)₈
(F7AC)₁₆

Traccia 5. Convertire i seguenti numeri interi dalla base decimale alla base binaria in parole di dimensione 8 bit

(-45)₁₀
(-72)₁₀
(103)₁₀
(-105)₁₀

Domanda. E' possibile convertire il numero -202 dalla base decimale alla base due utilizzando 8bit? Giustificare o dimostrare la risposta.

Traccia 6. Convertire i seguenti numeri interi dalla base binaria (con dimensione della parola di 8bit) in base decimale
(10010010)₂
(00010010)₂
(10000001)₂

Domanda. Analizzando i valori binari sopra riportati come è possibile discriminare un numero negativo da uno positivo? Giustificare o dimostrare la risposta.

Traccia 7. Effettuare le seguenti operazioni dopo aver convertito i numeri in base binaria. Tutti i numeri e i risultati sono rappresentati con parole di 8bit

77-45
50-60
-45-20
-20+67

Domanda. Cosa accade se si svolge il calcolo -203-122 dopo aver convertito i numeri in base binaria (parola 8bit)?

Traccia 8. Convertire in IEE754 Singola Precisione i seguenti valori reali

-345.59375
+500.40625

Traccia 9. Convertire in IEE754 Singola Precisione i seguenti valori reali

+5.75
+128.5

Effettuare somma e prodotto dei numeri.

Esercizi 2 Architettura Elaboratori

Traccia 1. Definire i campi di una istruzione a livello macchina di dimensione 16bit che possano consentire:

14 funzioni aritmetiche diverse che lavorano su registri ad uso generale
una operazione di trasferimento che copia un dato sito in una locazione di memoria all'interno di un registro ad uso generale
una operazione di trasferimento che copia un dato sito in un registro ad uso generale all'interno di una locazione di memoria

Il numero di registri ad uso generale è otto.

Domanda 1. Prefissata la dimensione a 16bit, quante locazioni di memoria sono accessibili dalle istruzioni?

Domanda 2. Provare ad usare dei codici mnemonici (load, store, addition,...) per rappresentare le istruzioni di trasferimento e i relativi campi dati (un esempio per ogni istruzione) e (almeno) due istruzioni aritmetiche.

Traccia 2. Considerare il seguente codice assemblativo simil- MIPS

Domanda 1. Che valore ha $t3 se il valore contenuto in x è 5 e quello contenuto in y è 5?

Domanda 2. Che valore ha $t3 se il valore contenuto in x è 8 e quello contenuto in y è 5?

Domanda 3. Che valore ha $t3 se il valore contenuto in x è 7 e quello contenuto in y è 10?

Traccia 3. Suddividere la parola a 16bit di un indirizzo per individuare

2 banchi
8 blocchi

Domanda. A quante celle di memoria si può accedere per ciascun blocco? E in totale?

Traccia 4.Una Memoria Cache ha 1000 parole. Supponendo che l'elaborazione di una istruzione prelevata dalla memoria cache richieda 0.5 millesimi di secondo mentre il trasferimento di 1000 parole dalla Memoria Centrale alla Memoria Cache richieda 1 secondo; quanto guadagno temporale si ottiene utilizzando la memoria cache rispetto ad un accesso alla memoria centrale che richiede 6 secondi per elaborare un programma di 3000 parole?

Traccia 5. Supponendo che ogni istruzione abbia tre fasi (Fetch, Decode, Exceute) descrivere l'andamento temporale del programma sottostante in una macchina canalizzata con i valori x=11 e y=5 e con i valori x=4294967295 e y=1.

000: lw $t0,x #Copia il valore contenuto nella locazione all'indirizzo x nel registro ad uso generale $t0
001: lw $t1,y #Copia il valore contenuto nella locazione all'indirizzo y nel registro ad uso generale $t1
002: add $t4,$t0,$t1 #Addiziona il valore dei registri $t0 e $t1 e pone il risultato in $t4
003: btz #005 #Salta alla locazione di memoria 8 se il flag Z è attivo
004: li $t9,0 #Mette il valore 4 in $t2
005: btw #007 #Salta alla locazione di memoria 12 se il flag W è attivo
006: li $t9,1 #Mette il valore 1 in $t9
007: .END #Fine del programma

Domanda. Con quale coppia di valori (x,y) tra (500674685,1) e (10087,60989) è più veloce il programma? Perchè?

Esercizi 3 MIPS: set istruzioni

Traccia 1. Dato il seguente programma, determinare il valore di risb, rish, risw.

.text
.globl main

main:

lb $t0,Valore1
lb $t1,Valore2
add $t2,$t0,$t1
sb $t2,risb
sh $t2,rish
sw $t2,risw

li $vo,10
syscall

.data
Valore1: .byte 100
Valore2: .byte 250
risb: .byte 0
rish: .half 0
risw: .word 0
Implementare il codice e verificare la risposta

Traccia 2. Scrivere un programma in linguaggio assemblativo MARS che definiti cinque interi positivi definiti in memoria ne calcoli la media aritmetica (per valori interi). Riportare il risultato in $t0 o stamparlo su videoterminale.
Esempio
INPUT: a=0,b=11;c=7;d=1982;e=10051980
OUTPUT:2010796

Traccia 3. Scrivere un programma in linguaggio assemblativo MARS che, definiti due numeri (word) in memoria spazio e tempo, che fanno riferimento ad un punto mobile nello spazio, determina : La velocità del punto che si muove in modo rettilineo uniforme (risultato in $t0)

Traccia 4. Scrivere un programma che converta un valore da scala Celsius a scala Fahrenheit
Definire in memoria una variabile intera (word) riportante il valore in scala Celsius
Riportare il risultato in scala Fahrenheit in $t0 e in una cella in memoria
ES: gradoC=38 quindi $t0=100
OSS: Utilizzare le operazione tra interi (il valore risultante può essere approssimato)

Traccia 5. Scrivere un programma che, definiti due numeri appartenenti all'intervallo [-32768,32767] in memoria, X e Y, determina le seguenti informazioni:
$t0=0 se X è un numero positivo o $t0=1 se X è un numero negativo (non usare l'istruzione di salto)
$t1=0 se Y è pari $t1=1 se Y è dispari (non usare operazioni logiche-aritmetiche e istruzioni di salto)
$t2 riporta X+Y
$t3 riporta il valore massimo in valore assoluto tra
(±X) + (±Y)

Esercizi 4 MIPS: set istruzioni (salti)

Traccia 1. Scrivere un programma in linguaggio assemblativo MARS che pone in $t0 il valore 1 se l'operando definito in memoria Batman è maggiore dell'operando definito in memoria Robin.

Traccia 2. Scrivere un programma in linguaggio assemblativo MARS che, preso un intero n in memoria, calcola la somma dei primi n interi.
ES:
INPUT: n=5
OUTPUT: 15 cioè (5+4+3+2+1)

Traccia 3. Scrivere un programma in linguaggio assemblativo MARS che legge un valore intero da tastiera e scrive su videoterminale se il bit alla terza posizione meno significativa del numero acquisito ha un 1.

Traccia 4. Scrivere un programma in linguaggio assemblativo MARS che legge un valore intero da tastiera e scrive su videoterminale il valore del bit alla posizione specificata da un altro numero acquisito da tastiera successivamente (si può assumere che il secondo valore immesso sia un numero compreso tra 0 e 31).

Traccia 5. Scrivere un programma in linguaggio assemblativo MARS che legge un valore intero da tastiera e scrive su videoterminale il numero di 1 che compongono il numero acquisito.
Esempio
INPUT: 521 (in binario 1000001001)
OUTPUT:3

Esercizi 5 MIPS: programmi generici 1

Traccia 1. Confrontare due interi positivi a e b, definiti in memoria, e mettere in $t0 il valore 0 se a e' maggiore di b, 1 altrimenti. Non e' possibile utilizzare l'istruzione di comparazione tra valori: operare sui singoli bit dei valori.

Traccia 2. Scrivere un programma in linguaggio assemblativo MARS che legge da input un intero positivo a>2 (word) ed un intero positivo (word) b>1 e ne restituisca in output il prodotto (axb) senza utilizzare l'istruzione mul.

Esempio INPUT (a): 10 INPUT (b): 5 OUTPUT: 50

Traccia 3. Descrivere l'algoritmo che dato un numero intero maggiore di 2 (definito in memoria) stabilisca se il numero è primo (valore 1 in $t2) o no (valore 2 in $t2). Provare ad implementare il programma in linguaggio assemblativo MARS.
Esempio numeri primi 1,3,5,7,11,13,...
PS: un numero è primo solo se è divisibile per se stesso e per 1.

Traccia 4. Scrivere un programma in linguaggio assemblativo MARS che acquisito un intero positivo (da 0 a 255) inserito da tastiera, scrivere il valore binario al contrario
Esempio
INPUT : 5 (cioè 00000101)
OUTPUT: 160 (10100000)

INPUT : 105 (cioè 01101001)
OUTPUT: 150 (10010110)

Esercizi 6 MIPS: programmi generici 2

Traccia 1. Si scriva un programma in linguaggio assemblativo MIPS/MARS che letto un numero intero positivo dallo standard input (tastiera), visualizza su videoterminale il cubo del numero stesso facendo uso soltanto di operazioni di somma.

Traccia 2. Si scriva un programma in linguaggio assemblativo MIPS/MARS che legge una sequenza di interi positivi da tastiera (la sequenza termina quando viene inserito il valore -1), conta il numero complessivo dei numeri che sono multipli di 3, di 5 oppure di 7 compresi nella sequenza e stampa questo valore. Per esempio, nel caso la sequenza in ingresso è "4 8 12 15 14 8", il programma stampa il valore 3.

Traccia 3. Scrivere un programma in linguaggio assemblativo MIPS/MARS che, letti tre numeri interi da tastiera stampa su videoterminale la sequenza dei tre numeri in ordine monotono non decrescente.
Esempio: a = 10, b = 7, c = 9 deve dare in uscita 7 9 10.

Traccia 4. Si scriva un programma in linguaggio assemblativo MIPS/MARS per calcolare il massimo comun divisore (MCD) di due numeri interi positivi. Il MCD è definito come il massimo tra i divisori comuni ai due numeri.
Suggerimento. Si considerino due numeri interi N1 e N2. Il MCD di N1 e N2 è il massimo tra i numeri che sono divisori (con resto uguale a zero) sia di N2 che di N1. In particolare, si supponga che sia N1 minore di N2. Il MCD è il massimo tra i numeri compresi tra 1 e N1 che sono divisori (con resto uguale a zero) sia di N1 che di N2.

Esercizi 7 MIPS: programmi numeri reali

Traccia 1. Scrivere un programma in linguaggio assembaltivo MIPS/MARS che legga da tastiera cinque numeri interi e stampi su videoterminale il risultato della media tra i cinque numeri

Traccia 2. Sullo stipendio dei lavoratori lo stato applica una trattenuta fiscale in base alla seguente tabella: 10000-28000 euro 23%
28001-50000 euro 28%
50001 ed oltre 43%
Scrivere un programma in linguaggio assemblativo MIPS/MARS che, dato in input da tastiera lo stipendio di un dipendente, calcola la trattenuta da versare.
NB: Lo stipendio è immesso da tastiera com enumero intero.

Traccia 3. Scrivere un programma in linguaggio assembaltivo MIPS/MARS che Calcola la distanza tra due punti (x1,y1) (x2,y2).
NB:i punti x1,y1,x2,y2 sono interi definiti in memoria; la distanza si ottine con la radice quadrata di (x1-x2)^2+(y1-y2)^2
ES: (1,1) (2,2) d=1.41421

Traccia 4. Scrivere un programma in linguaggio assembaltivo MIPS/MARS che legga da tastiera tre numeri interi indicanti il raggio di altrettanti cerchi, calcola l'area di ciascun cerchio e riporta in $f0 l'area più grande, $f1 la mediana e $f2 la più piccola Traccia 5. La ridotta n-esima della serie armonica è definita come: Hn =1+ 1/2 + 1/3 +...+ 1/n Si scriva un programma in linguaggio assemblativo MIPS/MARS che ripeta i passi seguenti:

legga da tastiera un numero intero n
se il numero è minore o uguale a 0 termina l’esecuzione
se il numero è maggiore di 0 stampa Hn (cioè la somma dei primi n termini della serie)

Esercizi 8 MIPS: Funzioni

Traccia 1. Scrivere in linguaggio assemblativo MIPS/MARS una funzione che riceve in ingresso due numeri interi a e b, scrivere una funzione che restituisca il risultato di a elevato alla b; proporre quindi un adeguato main di prova (i numeri possono essere definiti in memoria o - meglio - inseriti da tastiera). Il risultto deve essere mostrato su videoterminale.

Traccia 2. Scrivere in linguaggio assemblativo MIPS/MARS una funzione che riceve in ingresso tre numeri interi h, m e s che rappresentano ore minuti e secondi e restituisce il numero di secondi trascorsi dalla mezzanotte.

Traccia 3. Scrivere in linguaggio assemblativo MIPS/MARS un programma che usa la funzione della Traccia 2 per calcolare i secondi trascorsi tra due orari entrambi contenuti entro il ciclo di una giornata.
Ad esempio, se i due orari inseriti fossero 12:30:00 e 13:40:30 il programma dovrebbe stampare: I secondi trascorsi tra i due orari sono: 4230

Traccia 4. Scrivere in linguaggio assemblativo MIPS/MARS un programma che dato in input base altezza di un triangolo rettangolo passi tali valori ad una funzione attraverso la quale si possano stabilire ipotenusa, area e perimetro del triangolo.

Traccia 5. Considerate la regola di Collatz: dato un numero intero positivo n, se n è pari lo si divide per 2, se è dispari lo si moltiplica per 3 e si aggiunge 1 al risultato. Quando n è 1 ci si ferma.
Ad esempio, la sequenza di Collatz di 7 è: 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
E' un noto problema aperto stabilire se ogni sequenza di Collatz termina (cioè, se arriva a 1). Scrivere in linguaggio assemblativo MIPS/MARS una funzione che, dato un numero, dia il successivo in una sequenza di Collatz. Quindi, usare la funzione in un programma che chiede all’utente un numero e mostra la sequenza di Collatz del numero e la lunghezza.
Esempi di funzionamento
Numero: 7
7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
Lunghezza: 17
Numero: 9 9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
Lunghezza: 20

Esercizi 9 MIPS: Syscall

Traccia 1. Dati due dadi con facce numerate da 0 a 5. Lanciare due dadi e scrivere su videoterminare se è uscita una coppia.

Traccia 2. Supponeno che testa sia 0 e croce sia 1. Lanciare una moneta cento volte e stampare su videoterminale quante teste sono uscite e quante croci.

Traccia 3. Dati due dadi con facce numerate da 0 a 5. Lanciare tre dadi e scrivere su videoterminale se è uscito un tris, una coppia o tutti valori diversi.

Traccia 4. Da un bussolotto estarre 3 palline numerate e stampare su videoterminale il loro valore. Le palline sono numerate da 0 a 90 e non sono ammesse ripetizioni.

Traccia 5. Gerry Scotti vuole realizzare un simulatore del gioco THE WALL. THE WALL prevede il lancio di una biglia in un tabellone con 10 colonne (enumerate da 0 a 9) e 8 righe. La palla arbitrariamente/casualmente si sposta ad ogni passo di una riga in basso verso destra o verso sinistra con pari probabilità. Realizzare un programma che legga in ingresso un valore tra 0 e 9 indicante la posizione della biglia. Descriva ogni passo/riga se la palla si sposta verso destra o verso sinistra (generare un testa o croce per determinare gli spostamenti) Dire in quale colonna atterra. NB: se la palla arriva alla colonna zero o rimane a zero (nel caso di decremento) o va ad uno (nel caso di incremento). Se la palla arriva alla colonna nove alla riga successiva o rimane a nove (nel caso di incremento) o va a otto (nel caso di decremento).

Traccia 6. I redattori di The Wall vogliono capire se la pallina, per un numero finito di lanci, ha più probabilità di cadere in alcune colonne piuttosto che altro. Per questo rubano il simulatore a Gerry Scotti e provano 100 tiri con posizione iniziale casuale. Descrivere la distribuzione delle cadute (fissando un seme di casualità).

Esercizi 10 MIPS: Vettori 1

Traccia 1. Scrivere un programma in assembly che definisca un vettore di word di lunghezza 10. Legga i numeri immessi da tastiera dall’utente. Stampa i valori immessi nel vettore.

Traccia 2. Scrivere un programma in assembly che definisca un vettore di word di lunghezza 6. Il programma deve ricavare il vettore inverso, cioè un vettore che ha le componenti invertite e, infine, stampi il vettore ricavato.
Esempio 156 432 5332 -23 0 688
invertito 688 0 -23 5332 432 156

Traccia 3. Scrivere un programma in assembly che definisca un vettore di word di lunghezza 6. Determinare con una stringa in output se le componenti inserite sono strettamente crescenti (v[i+1] > v[i] per ogni i

Traccia 4. Scrivere un programma in assembly che crei un vettore di 100 interi contenente numeri casuali compresi tra 0-50. Successivamente il programma chiede all’utente di inserire un numero compreso tra 0-50 e ricerca tale numero nel vettore. Per ogni occorrenza stampa la posizione in cui è stato trovato e alla fine della ricerca riporta anche il numero di elementi trovati.

Traccia 5. Scrivere un programma in assembly che definsice un vettore di 10 elementi con numeri casuali compresi tra 0 e 999 e calcoli alcuni dati statistici:
1) somma
2) media
3) min
4) max
PS: si consgilia di usare uan funzione per ogni analisi statistica

Esercizi 10 MIPS: Vettori 2

Traccia 1. Risiko. Scrivere un programma in assembly che permette di simulare un attacco del Risiko. L'utente imposta il numero di armate del colore giallo e il numero di armate del colore blu. Il programma genere 3 numeri casuali per l'attacco e 3 numeri casuali per la difesa. Il programma poi con una funzione ordina i 3 numeri dell'attacco e con la stessa funzione ordina i 3 numeri della difesa. Poi con una ulteriore funzione valuta i carri armarti persi dalla difesa e quelli persi dall'attacco li sottrae alle truppe correnti e si prosegue. Il gioco termina quando la difesa arriva a 0 (Vittoria Attacco) o quando l'attacco ha solo 3 carri armati (Vittoria Difesa)*.
* Nel Risiko si può lanciare 3 dadi o n-1 dati quando n è uguale a 3. In difesa ci si può difendere con 3 dati o n dati con n minore di 3 ... non considerare questi casi. ** Si consiglia di implementare la funzione ORDMAX che ordina tre numeri e riutilizzarla più volte.

Esercizi 11 MIPS: Stringhe

Traccia 1. Realizzare un programma in assembly MARS che, definite due stringhe in memoria di ugual lunghezza, calcola la similitudine tra due stringhe. La similitudine è data dal numero dei ceratteri uguali alla stessa posizione diviso la lughezza della stringa.

Traccia 2. Realizzare un programma in assembly MARS che, definita una stringa in memoria e letto un carattere da tastiera, calcola il numero di occorrenze del carattere nella stringa.

Traccia 3. Realizzare un programma in assembly MARS che, definita una stringa in memoria e letto un carattere alfabetico da tastiera, che trova la prima occorrenza in una stringa senza distinzione tra maiuscole e minuscole. Gestire eventuali errori/incoerenze di input

Traccia 3. Realizzare un programma in assembly MARS che, definita una stringa in memoria e letti due caratteri da tastiera search e replace, sostituisce il carattere seach con replace.

Traccia 4. Realizzare un programma in assembly MARS che rimuove il carattere spazio, " ", da una stringa definita in memoria.

Traccia 5. Realizzare un programma in assembly MARS che rimuove il carattere spazio, " ", da una stringa definita in memoria senza utilizzare una nuova stringa di supporto.

Traccia 6. Realizzare un programma in assembly MARS che concatena due stringhe definite in memoria. La concatenazione è l'unione di due stringhe. Es.: stringa1: "Gatto" stringa2: "matto" concatenazione="Gattomatto"

Esercizi 12 MIPS: Matrici

Traccia 1. Definire una matrice 5x5 di halfword. Realizzare un programma in linguaggio assemblativo che consente ad un utente di inserire da tastiera il numero di riga ed il numero di colonna e visualizzare su schermo l'elemento.

Traccia 2. Definire una matrice 5x4 di word. Realizzare un programma in linguaggio assemblativo che consente di sommare il valore degli elementi di una colonna il cui valore è inserito da tastiera da un utente.

Traccia 3. Definire una matrice 3x4 di byte. Realizzare un programma in linguaggio assemblativo che inizializza la matrice con un valore casuale tra 0 e 10.

Traccia 4. Definire una matrice 10x10 di byte. Realizzare un programma in linguaggio assemblativo che inizializza la matrice con valori casuali 0 e 1. Permettere ad un utente di scegliere riga e colonna e decidere dopo cinque tentativi quanti elementi con valore 1 ha individuato. Ogni volta che individua un 1 l'elemento è settato a 0.

Esercizi 13 MIPS: Funzioni ricorsive

Si scriva la routine assembler MIPS che implementa la funzione ricorsiva definita come segue:

Si assuma che x, y siano immessi da input sempre maggiori o uguali a 0

Si scriva la routine assembler MIPS che implementa la funzione ricorsiva definita come segue:

Si assuma che x, y, z siano sempre maggiori o uguali a 0

Si scriva la routine assembler MIPS che implementa la funzione ricorsiva definita come segue:

Si assuma che a,b,c,d siano immessi da input sempre maggiori o uguali a 0