Diploma Universitario in Ingegneria Informatica

                    Esame di Fondamenti di Informatica II Secondo Modulo
                    A.A. 1999/00 - Esempio compito d'esame - prima parte


Problema 1
Un museo e' costituito da varie sale, identificate da numeri
interi positivi e collegate da corridoi percorribili in entrambi i
sensi.   La specifica del tipo astratto "Museo" e':

TipoAstratto  Museo

Commento ogni valore del tipo rappresenta un museo

Sorte Mus (sorta per il dominio di interesse)

Funzioni
       Crea    : (Intero) --> Mus
              precondizioni e postcondizioni per Crea(n) = m
              pre_: n > 0
              post_:  m e' un museo con n sale e nessun corridoio; le sale
                      sono rappresentate dai numeri 0...n-1; l'entrata e'
                      rappresentata dalla sala 0
       NumeroSale      : (Mus) --> Intero
              precondizioni e postcondizioni per NumeroSale(m) = i
              pre_: nessuna
              post_: i e' il numero di sale di m
       AggiungiCorridoio       : (Mus, Intero, Intero) --> Mus
              precondizioni e postcondizioni per AggiungiCorridoio(m, i, j) = s
              pre_: i <= j, 1 <= i <= NumeroSale(m), 1 <= j <=  NumeroSale(m)
              post_: s e' il museo ottenuto da m aggiungendo il corridoio che
                     congiunge le due sale i e j; se tale corridoio e'
                     in m, s e' uguale a m
       SaleAdiacenti      : (Mus, Intero) --> Insieme(Intero)
              precondizioni e postcondizioni per SaleAdiacenti(m, i) = ins
              pre_: i <= j, 1<=  i <= NumeroSale(m)
              post_: ins e' l'insieme delle sale collegate da un corridoio
                     alla sala i
FineTipoAstratto



Domanda 1 Progettare una classe C++ Museo che realizzi il tipo astratto Museo,
in modo da rendere la funzione SaleAdiacenti il piu' efficente
possibile. Scrivere la definizione della classe (file .h), descrivendo
brevemente le funzioni della classe e discutendo la loro complessita'.


Domanda 2 Scrivere una funzione esterna (non friend) alla classe Museo che
riceva in ingresso:
   1.  un oggetto m della classe Museo,
   2.  una lista p di elementi interi che denota una sequenza di stanze da
       visitare, dove la lista e' rappresentata mediante un puntatore di tipo
       rec, la cui definizione e':

       struct rec {
         int  info;
         rec*  next;
       };

e restituisca una lista, anch'essa rappresentata mediante un puntatore di tipo
rec, che denota il cammino minimo all'interno del museo che a partire
dall'entrata (nodo 0) passa per le stanze indicate in p rispettando l'ordine
indicato da p. Calcolare la complessita' della funzione.