Fondamenti di Informatica: Appello del 14/10/1999

Università di Roma ``La Sapienza''
Facoltà di Ingegneria
Corso di Fondamenti di Informatica
Corsi di Laurea: Aerospaziale, Chimica, Elettrica, Materiali, Nucleare, Ambiente e Territorio (v.p.)
Appello del 14/10/1999 -- 1^a prova scritta
tempo a disposizione: 2 ore

Problema 1 (18 punti) Un sistema grafico è in grado di gestire uno schermo quadrato di 10X10 punti, ognuno dei quali può essere acceso o spento. Il sistema riceve l'immagine da visualizzare sotto forma di un file composto da una sequenza di linee, dove ogni linea ha il formato:

n₁ n₂ n₃

dove n₁, n₂ e n₃ sono interi compresi fra 1 e 10. Il significato di tale linea è che nella riga n₁ dello schermo si accendono, a partire dalla posizione n₂ compresa, n₃ punti. Ad esempio, se il contenuto del file è il seguente:

5 8 1

2 3 1

2 4 6

8 1 10

10 1 1

3 10 1

allora lo schermo corrispondente è il seguente (distinguendo con il carattere '*' il punto acceso)

1 2 3 4 5 6 7 8 9 10

1

2 * * * * * * *

3 *

4

5 *

6

7

8 * * * * * * * * * *

9

10 *

Chiamiamo punto isolato qualsiasi punto che non sia in contatto (in nessuna delle posizioni adiacenti) con altri punti. Ad esempio, nello schermo di cui sopra, vi sono due punti isolati, rispettivamente di coordinate (10,1) e (5,8). Si noti che il punto di coordinate (3,10) non è isolato.

Un aspetto che deve essere preso in considerazione è che una o più linee del file di input potrebbero dare specifiche scorrette. Ad esempio, la linea

6 8 4

è scorretta, poiché il numero di punti per riga dello schermo (cioè 10) è insufficiente a contenere i 4 punti richiesti.

Si richiede di risolvere i seguenti punti:

1.: Scrivere le dichiarazioni dei tipi di dato Pascal da utilizzarsi per risolvere i punti successivi.
2.: Scrivere una (o più) unità di programma Pascal che, dato un file contenente una specifica, lo visualizzi su schermo (utilizzando solamente il carattere '*' e il carattere spazio; in particolare non devono essere visualizzati i numeri di riga o di colonna). Nel caso in cui la specifica sia scorretta, occorre stampare un messaggio di errore. (Suggerimento: progettare l'unità in maniera sufficientemente generale, al fine di renderla utile anche per il punto successivo).
3.: Scrivere una (o più) unità di programma Pascal che, dato un file contenente una specifica, verifichi se è corretta, e in tal caso costruisca una lista contenente le coordinate di tutti i punti isolati. La lista deve essere composta da record contenenti due interi. Il verso della lista è a scelta dello studente.

Problema 2 (4 punti)

Descrivere in generale le funzioni principali di un sistema operativo.

Descrivere inoltre in dettaglio la gestione dei processi.

Problema 3 (4 punti)

Scrivere un'unità di programma Pascal che effettui la copia di una lista.

Dire quale sia la complessità dell'unità scritta.

Problema 4 (4 punti)

Data una matrice di booleani, si dice ``sequenza omogenea'' una sequenza di valori:

tutti uguali,
presenti tutti sulla stessa riga oppure tutti sulla stessa colonna,
se presenti tutti sulla stessa riga, allora presenti in colonne adiacenti,
se presenti tutti sulla stessa colonna, allora presenti in righe adiacenti.

Scrivere un sottoprogramma Fortran che, ricevendo come parametro una matrice rettangolare di booleani di dimensione n X m, calcoli e restituisca in modo opportuno al programma chiamante la lunghezza della più lunga sequenza omogenea di valori .TRUE..