DIPARTIMENTO   DI   INFORMATICA
Università di Torino

Laboratorio di Informatica: programmazione - Corso di Diploma in Informatica - a.a. 00/01

Esame a.a. 2000/2001 - Parte Seconda

Il progetto dovra' essere svolto in gruppi di 1 o 2 componenti. ATTENZIONE: i gruppi di 2 componenti dovranno provvvedere a comunicare la loro formazione, presentandosi ai docenti (preferibilmente durante le lezioni in laboratorio o in aula) ENTRO IL 30 Marzo 2001. Richieste di formazione di gruppo presentate successivamente a tale data non saranno, di norma, prese in considerazione.

Il progetto e' costituito da QUATTRO fasi distinte. Tutto il codice prodotto dovra' essere memorizzato in una directory PROGETTO, contenente quattro sottodirectory FASE1, FASE2, FASE3, e FASE4, come illustrato dal seguente "disegno":

                                  PROGETTO
                                     |
                                     |
            ____________________________________________________
            |                |                |                |
            |                |                |                |
          FASE1            FASE2            FASE3            FASE4

Descrizione del progetto

FASE 1

Si implementi il tipo di dato astratto "elemento".

Si devono realizzare ALMENO DUE implementazioni, utilizzando rappresentazioni sostanzialmente differenti: CONTATTARE I DOCENTI per l'ammissibilita' delle rappresentazioni scelte.

Tutte le implementazioni realizzate devono essere ottenute completando il seguente "schema di unit" ADTelem:

unit ADTelem

interface

type elem = ...

procedure set_elem (var e1:elem; e2:elem);
          {AI: e2 e' inizializzato, contiene il valore E}
          {AF: e1 contiene il valore E}

procedure read_elem (var e:elem);
          {AI: }
          {AF: e contiene un valore E letto da INPUT}

procedure write_elem (e:elem);
          {AI: e e' inizializzato, contiene il valore E}
          {AF: il valore E e' stato scritto su OUTPUT}

function eq_elem (e1, e2:elem): boolean;
          {AI: e1, e2 sono inizializzati}
          {AF: restituisce TRUE se e1, e2 sono "uguali", 
                           FALSE altrimenti}
    

function le_elem (e1, e2:elem): boolean;
          {AI: e1, e2 sono inizializzati}
          {AF: restituisce TRUE se e1 e' "minore o uguale" di e2, 
                           FALSE altrimenti}

implementation

...

end.


Ciascuna unit (UNA PER OGNI RAPPRESENTAZIONE CONSIDERATA) dovra' avere nome ADTelem, pertanto le unit dovranno essere memorizzate in sottodirectory distinte di FASE1 (scegliere un nome opportuno per tali directory).

Realizzare (nella sottodirectory TEST di FASE1) un programma che permetta di testare interattivamente le operazioni del tipo di dato astratto ADTelem. Si consiglia di usare un'interfaccia a menu'.

Il programma di test deve essere INDIPENDENTE DALLA RAPPRESENTAZIONE USATA per il tipo di dato astratto ADTelem, quindi ci deve essere UNA SOLA versione del programma di test che funziona per TUTTE le implementazioni di ADTelem.

FASE 2

Si implementi il tipo di dato astratto "insieme di ADTelem" (dove ADTelem e' il tipo di dato astratto definito, e implementato in almeno due modi, nella FASE1).

Si devono realizzare ALMENO DUE implementazioni, utilizzando rappresentazioni sostanzialmente differenti: anche in questo caso CONTATTARE I DOCENTI per l'ammissibilita' delle rappresentazioni scelte.

Ciascuna implementazione deve essere INDIPENDENTE DALLA RAPPRESENTAZIONE USATA per il tipo di dato astratto ADTelem.

Tutte le implementazioni realizzate devono essere ottenute completando il seguente "schema di unit" ADTset.

unit ADTset
uses ADTelem ...

interface ...

implementation ...

end.

Ciascuna unit (UNA PER OGNI RAPPRESENTAZIONE CONSIDERATA per il tipo di dato astratto insieme) dovra' avere nome ADTset, pertanto le unit dovranno essere memorizzate in sottodirectory distinte di FASE2 (scegliere un nome opportuno per tali directory).

Realizzare (nella sottodirectory TEST di FASE2) un programma che permetta di testare interattivamente le operazioni del tipo di dato astratto ADTset. Si consiglia di usare un'interfaccia a menu'.

Il programma di test deve essere:

  • INDIPENDENTE DALLA RAPPRESENTAZIONE USATA per il tipo di dato astratto ADTelem, e
  • INDIPENDENTE DALLA RAPPRESENTAZIONE USATA per il tipo di dato astratto ADTset.
Quindi ci deve essere UNA SOLA versione del programma di test che funziona per TUTTE le implementazioni di ADTelem e di ADTset.

Le operazioni definite sul tipo di dato astratto ADTset sono le seguenti (si noti che la specifica e' VOLUTAMENTE informale e lacunosa: parte integrante dell'esercizio consiste proprio nel formalizzare e completare tale specifica):

  1. MAKENULL(Set): restituisce in Set l'insieme vuoto.
  2. INSERT(Element,Set): modifica Set in Set unione {Elem}
  3. DELETE(Element,Set): modifica Set in Set - {Elem}
  4. MEMBER(Element,Set): restituisce TRUE se ELEM appartiene a SET, FALSE altrimenti
  5. SCAN(Element,Set): modifica Set rimuovendone un elemento qualsiasi e ritorna tale elemento in Element
  6. ISEMPTY(Set): restituisce TRUE se Set e' l'insieme vuoto, FALSE altrimenti

FASE 3

Usando il tipo di dato astratto ADTset definito nella FASE 2 realizzare una unit "operazioni complesse" contenente le seguenti operazioni (si noti che tale unit NON realizza un tipo di dato astratto):
  • UNION(Set1,Set2,Set3): dati Set1 e Set2 restituisce Set3 = Set1 unione Set2
  • INTERSECTION(Set1,Set2,Set3): dati Set1 e Set2 restituisce Set3 = Set1 intersezione Set2
  • DIFFERENCE(Set1,Set2,Set3): dati Set1 e Set2 restituisce Set3 = Set1 - Set2
  • EQUAL(Set1,Set2): restituisce TRUE se Set1 e' uguale a Set2, FALSE altrimenti

La unit "operazioni complesse" dovra' essere realizzata completando il seguente "schema di unit":

unit OperComp
uses ADTset, ADTelem ...

interface ...

implementation ...

end.

La unit OperCom deve essere:

  • INDIPENDENTE DALLA RAPPRESENTAZIONE USATA per il tipo di dato astratto ADTelem, e
  • INDIPENDENTE DALLA RAPPRESENTAZIONE USATA per il tipo di dato astratto ADTset.
Quindi ci deve essere UNA SOLA versione della unit OperComp che funziona per TUTTE le implementazioni di ADTelem e di ADTset.

Realizzare (nella sottodirectory TEST di FASE3) un programma che permetta di testare interattivamente le operazioni del tipo di dato astratto ADTset e le operazioni della unit OperComp. Si consiglia di usare un'interfaccia a menu'.

Anche il programma di test deve essere

  • INDIPENDENTE DALLA RAPPRESENTAZIONE USATA per il tipo di dato astratto ADTelem, e
  • INDIPENDENTE DALLA RAPPRESENTAZIONE USATA per il tipo di dato astratto ADTset.
Quindi ci deve essere UNA SOLA versione del programma di test che funziona per TUTTE le implementazioni di ADTelem e di ADTset.

FASE 4

Estendere la definizione di ADTset aggiungendo l'operazione
  • SORT(Set): stampa gli elementi di Set in ordine crescente.
La realizzazione di tale operazione deve essere INDIPENDENTE DALLA RAPPRESENTAZIONE USATA per il tipo di dato astratto ADTelem (dipendera' invece dalla rappresentazione usata per ADTset: si dovra' quindi scrivere una opportuna versione di SORT per ciascuna implementazione). Estendete anche il programma di test realizzato nella FASE2.

ATTENZIONE: non modificate direttamente il codice delle implementazioni del tipo di dato astratto memorizzate nelle sottodirectory di FASE2 e il programma di test memorizzato nella directory TEST di FASE2, ma fatene una copia di tali directory nella directory FASE4 e lavorate su queste copie!!!

Estendete anche il programma di test memorizzato nella directory TEST di FASE3, in modo da testare anche l'opezione SORT. Anche in questo caso copiate il codice da modificare nella directory FASE4, e lavorate sulla copia. NOTA: non si deve modificare la unit OperComp, basta copiarla.

Risultati del progetto e modalita' di esame

Ricapitolando: il codice prodotto dovra' essere organizzato in sottodirectory, come illustrato dal seguente "disegno":
                                  PROGETTO
                                     |
                                     |
            ______________________________________________________________
            |                |                |                |         |
            |                |                |                |         |
          FASE1            FASE2            FASE3            FASE4     PROVE
            |                |                |                |
            |                |                |                |
        _________        _________        _________        _________________
        |    |  |        |    |  |        |       |        |       |    |  |
        |    |  |        |    |  |        |       |        |       |    |  |
    ADTelem1 |  |    ADTset2  |  |    OperComp  TEST    ADTsetEst1 |    |  |
             |  |             |  |                                 |    |  |
             |  |             |  |                                 |    |  |
       ADTelem2 |        ADTset2 |                          ADTsetEst2  |  |
                |                |                                      |  |
                |                |                                      |  |
              TEST             TEST                                  TEST2 |
                                                                           |
                                                                           |
                                                                        TEST3   

Copiando i file opportuni nella directory PROVE dovra' essere possibile compilare ed eseguire diverse combinazioni delle differenti realizzazioni dei tipo di dati astratti ADTelem, ADTset, ADTsetEst, con i programmi di test memorizzati in FASE1/TEST/, FASE2/TEST/, FASE3/TEST/, FASE4/TEST2/, e FASE4/TEST3/.

Ogni gruppo dovra' consegnare ALMENO 8 GIORNI prima della discussione

  1. La stampa dei sorgenti Pascal contenenti:
    1. Almeno due realizzazioni di ADTelem e un programma di test.
    2. Almeno due realizzazioni di ADTset e un programma di test.
    3. La unit OperComp e il programma di test.
    4. Almeno due realizzazioni di ADTset esteso con l'operazione SORT e l'estensione dei programmi di test realizzati nella FASE 2 e nella FASE 3 per testare anche l'operazione SORT.
  2. Una breve relazione contenente:
    1. Per ciascuna implementazione di ADTset: discussione della complessita' computazionale (in tempo e spazio) delle operazioni MAKENULL ,...,ISEMPTY.
    2. Discussione della complessita' computazionale (in tempo e spazio) delle operazioni UNION,...,EQUAL.
    3. Per ciacuna implementazione di ADTset: giustificazione dell'algoritmo usato per realizzare l'operazione SORT e discussione della sua complessita' computazionale (in tempo e spazio).

La correttezza del codice realizzato e' condizione necessaria, ma NON sufficiente per superare l'esame. A tal fine si richiede infatti che il codice:

  1. Contenga commenti di aiuto alla lettura (in particolare: ASSERZIONI iniziali e finali per ogni funzione e procedura, e INVARIANTI di ciclo).
  2. Sia scritto usando una regola di indentazione opportuna.
  3. I nomi della variabile e delle procedure siano, per quanto possibile, significativi.


[Ferruccio Damiani - DIDATTICA] [Corsi di Studi in Informatica]

Last update: Mar 13, 2001