Diploma Universitario di Ingegneria Informatica
Esame di Fondamenti di Informatica II - secondo modulo
A.A. 1999/2000 - Appello del 17 aprile 2000
Si consideri un guardaroba di un teatro, quando uno spettatore deposita un
oggetto (ad esempio un cappotto, una borsa) all'oggetto viene associato un
token. La specifica del tipo astratto è la seguente Guardaroba:
- TipoAstratto
Guardaroba
Sorte GR (sorta per il dominio di interesse)
Funzioni
Crea : () -> GR
precondizioni e postcondizioni per Crea() = d
pre: nessuna
post: d è un guardaroba con 0 oggetti.
AggiungiOggetto: (GR,Oggetto) -> (GR, Token)
precondizioni e postcondizioni per AggiungiOggetto(g,o) = (e,t)
pre: nessuna
post: e è il guardaroba ottenuto da g aggiungendo l'oggetto o ed un nuovo token t, che viene associato all'oggetto o nel guardaroba g .
EstInGuardaroba : (GR, Token) -> Boolean
precondizioni e postcondizioni per EstInGuardaroba(g,t) = b
pre: nessuna
post: b=true se l'oggetto associato a t è nel guardaroba g, b=false altrimenti.
RestituisciOggetto : (GR, Token) -> (GR,Oggetto)
precondizioni e postcondizioni per RestituisciOggetto(g,t) = (e,a)
pre: l'oggetto al quale è associato il token t è nel guardaroba g
post: e è il guardaroba ottenuto da g eliminando l'oggetto o e a è l'oggetto al quale è associato il token t.
OggettiPresenti: (GR) -> Array(Token,Oggetto)
Precondizioni e postcondizioni per OggettiPresenti(g) = e
pre: nessuna
post: e è un array delle coppie <token, oggetto associato> contenute nel guardaroba g.
FineTipoAstratto
Domanda 1 Si scriva la classi C++
Guardaroba
(file .h e file .cpp) che realizza il tipo astratto
Guardaroba in modo che le funzioni del tipo astratto siano il più
efficiente possibile. Si assuma che siano state definita una classe
Oggetto
che realizza il tipo astratto
Oggetto ed una classe Token
che
realizzi il tipo astratto Token delle quali non sono note le funzioni
pubbliche e private. Si rappresenti Array(Token,Oggetto) con un array
C++.
Domanda 2 Si discuta la complessità di tutte le funzioni di Guardaroba
.
Domanda 3 Si illustri la visita in ampiezza di un grafo, mettendo in
evidenza come questa possa essere modificata per ottenere un algoritmo che
calcola le distanze minime da un dato nodo.
Note: Token e Oggetto sono astrazioni d’entità. Token ha il costruttore a zero argomenti.