testo esame 11 gennaio 2001

Università di Roma ``La Sapienza''
Facoltà di Ingegneria
Corso di Fondamenti di Informatica - A.A.å
Corsi di Laurea: Aerospaziale, Chimica, Elettrica, Materiali, Meccanica, Nucleare
Appello del 11 gennaio 2001 -- 1^a prova scritta
tempo a disposizione: 2 ore

Problema 1 (18 punti)

La catena commerciale POPPY riunisce N negozi, numerati da 1 a N, che vendono i prodotti di un medesimo catalogo.

Ogni negozio ha un gestore che può decidere il prezzo di vendita dei vari prodotti. Quindi un medesimo prodotto può essere trovato a prezzi diversi in diversi negozi.

Le informazioni sui prodotti sono gestite mediante un array di N puntatori:

la componente i-esima dell'array punta ad una lista dei prodotti venduti dal negozio i-esimo (rappresentata mediante record e puntatori);
tale i-esima lista contiene, per ogni prodotto, nome (una stringa di al max. 15 caratteri) e prezzo di vendita (numero reale) di quel prodotto in quel negozio. Dato che i negozi vendono i medesimi prodotti, le lunghezze delle N liste sono uguali.)

La figura successiva mostra un esempio di array, con le liste associate. In questo particolare esempio N=3 e le liste sono visualizzate solo per i primi 5 elementi.

  #####
  #   #    +-------+   +-------+   +-------+   +-------+   +-------+    
  #   #    |  PR1  |   |  PR2  |   |  PR3  |   |  PR4  |   |  PR5  |    
1 #  ----> |      -+-->|      -+-->|      -+-->|      -+-->|      -+--> . . .
  #   #    | 23.67 |   | 3.67  |   | 10.00 |   | 30.70 |   | 2.33  |    
  #   #    +-------+   +-------+   +-------+   +-------+   +-------+    
  #####
  #   #    +-------+   +-------+   +-------+   +-------+   +-------+    
2 #  ----> |  PR1  |   |  PR2  |   |  PR3  |   |  PR4  |   |  PR5  | 
  #   #    |      -+-->|      -+-->|      -+-->|      -+-->|      -+--> . . .   
  #   #    | 20.00 |   | 4.00  |   | 11.00 |   | 29.99 |   | 5.00  |
  #   #    +-------+   +-------+   +-------+   +-------+   +-------+    
  #####
  #   #    +-------+   +-------+   +-------+   +-------+   +-------+    
3 #  ----> |  PR1  |   |  PR2  |   |  PR3  |   |  PR4  |   |  PR5  | 
  #   #    |      -+-->|      -+-->|      -+-->|      -+-->|      -+--> . . .   
  #   #    | 25.00 |   | 5.00  |   | 8.00  |   | 29.99 |   | 4.99  |
  #   #    +-------+   +-------+   +-------+   +-------+   +-------+ 
  #####

1.

Scrivere le dichiarazioni dei tipi di dato Pascal da utilizzarsi per risolvere i punti successivi. In particolare, denominare TIPOARCHIVIO il tipo per l'array sopra descritto e TIPOLISTA il tipo per le liste di prodotti.

2.

Scrivere una function Pascal che, ricevendo un array di tipo TIPOARCHIVIO e il nome di un prodotto, controlli i prezzi praticati per quel prodotto nei vari negozi della catena e restituisca la variazione percentuale tra il minimo ed il massimo prezzo.

Ad esempio, considerando l'archivio in figura e il prodotto PR3, il massimo prezzo riscontrabile è più grande del minimo di un 37.5%. Quindi il risultato della funzione sarebbe 37.5. Analogamente, per il prodotto PR4 il risultato della funzione sarebbe 2.37.

3.

Scrivere una procedure Pascal che, ricevendo un array di tipo TIPOARCHIVIO restituisca, usando un opportuno parametro di output, il puntatore iniziale ad una lista composta dai prodotti venduti dalla catena POPPY, per ciascuno dei quali sia indicato:

il nome;
la variazione percentuale tra il minimo e il massimo prezzo praticato, per quel prodotto, nei negozi della catena.

Ad esempio, per l'array della figura precedente, la procedura costruirebbe una lista come la seguente.

     +-------+   +-------+   +-------+   +-------+   +-------+    
---> |  PR1  |   |  PR2  |   |  PR3  |   |  PR4  |   |  PR5  | 
     |      -+-->|      -+-->|      -+-->|      -+-->|      -+--> . . .   
     |  25   |   | 36.24 |   | 37.5  |   | 2.37  |   | 114.59|
     +-------+   +-------+   +-------+   +-------+   +-------+

Problema 2 (4 punti)

Illustrare uno dei principali algoritmi di visita di grafi, mostrandone gli effetti su un grafo di esempio non banale (almeno 5 nodi e 7 archi).

Problema 3 (4 punti)

Descrivere tutte le modalità che si conoscono con le quali diverse unità di programma Pascal possono scambiarsi informazioni. Fornire almeno un esempio di uso di ciascuna modalità descritta.

Problema 4 (4 punti)

Scrivere una unità di programma Fortran che, data una matrice di interi , produca una seconda matrice in cui gli elementi della prima hanno subito uno scorrimento di un posto verso destra. (L'ultimo elemento di una riga diventa il primo della riga successiva. L'elemento di coordinate (N,M) nella prima, diventa quello di coordinate (1,1) nella seconda.)

Ad esempio, (con N=3 e M=4), ricevendo la matrice l'unità richiesta produce la matrice

Scrivere inoltre un esempio di programma principale contenente un'invocazione dell'unità progettata.