LIST UN PROGRAMMA ASSEMBLY PER ESEGUIRE SEMPLICI

LIST
UN PROGRAMMA ASSEMBLY PER ESEGUIRE SEMPLICI
OPERAZIONI SU LISTE
VINCENZO MARRA
Sommario. Questo documento espone il tema d’esame valido dal 1.I.2005 al
30.IV.2005 per il laboratorio del corso di Architetture degli Elaboratori e delle
Reti (turno 3, Prof. D’Antona).
1. Modalità d’esame
•
•
•
•
•
Titolo del progetto: List
Validità: 1.I.2005 – 30.IV.2004
Votazione: in trentesimi
Peso relativo nel voto finale: 13
Appelli durante il periodo di validità: si veda il sito del Dipartimento di
Informatica e Comunicazione
• Date di consegna per portare il progetto all’orale: una settimana prima
delgli appelli.
Nota. Per una descrizione dettagliata delle modalità d’esame si consulti la pagina
web del corso all’indirizzo http://homes.dico.unimi.it/∼dantona/.
2. Tema d’esame: List
Una lista è una sequenza finita di elementi di un tipo dato. In questo progetto
si tratterà esclusivamente di liste di interi. Si denoti con L = [e1 , e2 , . . . , en ] una
lista di n elementi (numeri interi). La lista vuota, denotata da Λ, è l’unica lista che
non contiene elementi, ed ha dunque n = 0 nella notazione appena introdotta. La
lunghezza della lista L è il numero intero positivo n. La lista vuota è quindi anche
definibile come (l’unica) lista di lunghezza 0. Sia data una lista L. L’operatore
Length restituisce la lunghezza di una lista, ed è definito ricorsivamente da:
• Length([e1 , . . . , en ]) = 0 se n = 0.
• Length([e1 , . . . , en ]) = 1 + Length([f1 , . . . , fn−1 ]), dove fi = ei+1 per i ∈
{1, . . . , n − 1}, se n > 0.
L’operatore binario ∗ di concatenazione costruisce una lista L3 a partire da due
liste date L1 = [a1 , . . . , ar ] e L2 = [b1 , . . . , bs ] come segue:
L1 ∗ L2 = [a1 , . . . , ar , b1 , . . . , bs ] .
Dato un intero e e una lista [e1 , . . . , en ], si definisca l’operatore Append ricorsivamente come segue:
• Append([e1 , . . . , en ], e) = [e] se n = 0.
Date: 1 febbraio 2005.
1
2
VINCENZO MARRA
• Append([e1 , . . . , en ], e) = [e1 ] ∗ Append([f1 , . . . , fn−1 ], e), dove fi = ei+1 per
i ∈ {1, . . . , n − 1}, se n > 0.
Esempio. Un esempio di concatenazione:
[1, 23, −2, 5] ∗ [32, 4, 0] = [1, 23, −2, 5, 32, 4, 0] .
Un esempio di applicazione di Length:
Length([1, 23, −2]) = 1 + Length([23, −2]) =
= 1 + 1 + Length([−2]) = 1 + 1 + 1 + Length(Λ) =
=1+1+1+0 = 3
Un esempio di applicazione di Append:
Append([1, 23], −2) =
= [1] ∗ [23] ∗ Append(Λ, −2) =
[1] ∗ Append([23], −2) =
[1] ∗ [23] ∗ [−2] = [1, 23, −2] .
¤
Si implementi un programma assembly MIPS secondo le seguenti specifiche.
(1) Il programma chiede inizialmente all’utente di inserire una arbitraria 1 lista
L di interi.
(2) Il programma chiede poi all’utente di scegliere fra una delle seguenti opzioni.
(a) Calcolare la lunghezza della lista.
(b) Aggiungere un elemento alla lista.
Nel primo caso, il programma esegue una opportuna implementazione di
Length sulla lista L. L’implementazione in questione deve rispecchiare la
struttura ricorsiva della definizione data sopra. Inoltre, l’esecuzione del
calcolo deve essere illustrata il più chiaramente possibile tramite la visualizzazione di informazioni appropriate che evidenzino l’andamento della
ricorsione.
Nel secondo caso, il programma chiede all’utente di inserire un elemento
e, ed esegue una opportuna implementazione di Append sulla lista L e
l’elemento e. L’implementazione in questione deve rispecchiare la struttura
ricorsiva della definizione data sopra. L’esecuzione deve essere illustrata il
più chiaramente possibile tramite messaggi, come nel caso precedente.
(3) (Facoltativo.) Il programma permette all’utente di ripetere a piacimento
le operazioni (a) e (b) sulla lista corrente (cioè, la lista risultante dalla
sequenza di operazioni eseguite dall’inizio del programma).
Note.
• Si documenti adeguatamente il progetto. A tal scopo, può essere più che
sufficiente commentare opportunamente il codice. A discrezione del candidato, è possibile allegare una relazione che documenti aspetti del progetto non adeguatamente illustrati dai commenti. Si noti che, in ogni caso,
la documentazione deve essere proporzionata alla dimensione del progetto
(ossia, molto succinta).
• La documentazione deve includere le informazioni relative alla piattaforma
sulla quale si è sviluppato il progetto — sistema operativo, editor impiegato,
simulatore impiegato (spim, mips, altro) e sua versione, etc.
1Ma si assuma per semplicità che gli elementi della lista siano interi con segno rappresentabili,
per esempio, con 32 bit.
LIST
3
2.1. Approfondimenti. Un qualunque testo su algoritmi e strutture dati tratta
l’argomento di questo tema d’esame. Ad esempio, si veda A. Bertossi, Algoritmi
e Strutture Dati, Utet, Torino, 2000.
(V. Marra) D.I.Co., Università degli Studi di Milano, via Comelico 39-41, 20135 Milano
E-mail address: [email protected]