Laboratorio di Introduzione alla
Programmazione
 II MODULO
 3 crediti
 Esame e voto unico (6 crediti totali)
1
Modalita’ d’Esame
 esame = progetto finale + orale
 prove di verifica intermedia
 non *necessarie*, verranno comunque considerate
come parte fondamentale per il voto finale
 analogamente alla valutazione del rendimento
dimostrato durante le esercizitazioni in Laboratorio
2
Chi puo’ presentare il progetto
 Gli studenti degli anni precedenti (devono
rivolgersi alla Prof. Occhiuto)
 Gli studenti che hanno frequentato nel
2007-2008 possono svolgere il progetto che
verra’ presentato oggi
3
Modalita’ per lo svolgimento del
progetto
 Come deve essere svolto? Dipende dalla
valutazione ottenuta durante l’anno
 Gli studenti che hanno ottenuto una valutazione
sufficiente (vedi pagina WEB) possono svolgere il
progetto in gruppo (di due, tre persone al
massimo)
 Tutti gli altri devono svolgere il progetto
individualmente
4
Modalita’ per i gruppi
 Il progetto deve essere consegnato una sola volta
 Al momento della consegna deve essere comunicato al
docente chi sono gli appartenenti al gruppo
 La prova orale deve essere sostenuta individualmente da
ogni partecipante al gruppo
 Puo’ essere svolta in momenti diversi
5
Quando si puo’ consegnare il
progetto?





Ad ogni sessione d’esame
Sessione estiva: entro 13 luglio 2008
Sessione autunnale: da fissare (settembre)
Orali: da concordare volta per volta
Tutte le informazioni sono disponibili sulla
pagina web del corso
6
Validita’ del progetto
 Fino a settembre
 Sessione invernale: nuovo progetto da
concordare volta per volta (richiedendolo al
docente)
7
Inoltre
 Devono essere spediti per e-mail (levifran
@di.unipi.it) tutti i files
classe.java
• in un archivio .zip o .gz
• indicando il nome (i nomi) dei partecipanti
8
Cosa deve contenere?
 Programma “Funzionante”
 Una relazione che spieghi le principali
scelte di progetto
9
Obiettivo del Progetto
 Progettare un semplice tipo di dato astratto
 Partiamo dal problema
10
Problema
 Vogliamo progettare un tipo di dato astratto
Biblio
• Un Biblio rappresenta
-un insieme di Scaffali numerati
1,........,n
n fisso (parametro)
-ogni Scaffale puo’ contenere al massimo
k items
k fisso(parametro)
11
Che cosa e’ un item?
 Un Libro
oppure
 Una Rivista
12
Libro
 Vogliamo che memorizzi
•
titolo, autore,editore
•
numero di copie disponibili (>0)
(“Le affinita’ elettive”, “Goethe”, “Einaudi”, 20)
(“Do the androids dream of electric sheeps?”,
“Dick”, “Feltrinelli”, 2)
13
Rivista
 Vogliamo che memorizzi
•
titolo, autore,editore
•
numero
•
numero di copie disponibili (>0)
(“Science of Computer Programming”, “Milner”,
“Elsevier Science”, 3, 20)
(“Science of Computer Programming”, “Milner”, “Elsevier
Science”, 4, 10)
14
Proprieta’ degli scaffali
• Vogliamo per costruzione delle proprieta’ degli
scaffali
• Ogni scaffale contiene SOLO LIBRI o SOLO
RIVISTE
• Per semplicita’ assumiamo che
1) scaffali tra L1 e Ln contengono libri
2) scaffali tra R1e Rn e n contengono riviste
n (parametro)
15
Proprieta’ degli scaffali I
• Vogliamo sia nel caso di Libri che di Riviste che
gli item siano memorizzati in modo ordinato
16
Libri: ordinamento
• in base al titolo
• se titolo uguale in base all’autore
• se titolo e autore uguali in base all’editore
17
Esempio
(“Le affinita’ elettive”, “Goethe”, “Einaudi”, 20)
>
(“Do the androids dream of electric sheeps?”, “Dick”, “Feltrinelli”, 2)
(“Do the androids dream of electric sheeps?”, “Dick”, “Feltrinelli”, 2)
>
(“Do the androids dream of electric sheeps?”, “Dick”, “Einaudi”, 10)
18
Riviste: ordinamento
•
•
•
•
in base al titolo
se titolo uguale in base all’autore
se titolo e autore uguali in base all’editore
se titolo, autore, editore uguali in base al
numero
19
Esempio
(“Science of Computer Programming”, “Milner”, “Elsevier Science”,
3, 20)
<
(“Science of Computer Programming”, “Milner”, “Elsevier Science”, 4, 10)
(“Science of Computer Programming”, “Milner”, “Elsevier Science”,
3, 20)
<
(“Theoretical Computer Science”, “harel”, “Elsevier Science”, 4, 100)
20
Proprieta’ degli scaffali II
• Vogliamo che il numero di pezzi totali degli item
presenti in ogni scaffale sia minore o uguale della
dimensione (k parametro fisso)
21
Esempio: dimensione 20
[ (“Do the androids dream of electric sheeps?”, “Dick”, “Feltrinelli”, 2),
(“Le affinita’ elettive”, “Goethe”, “Einaudi”, 10)]
[ (“Do the androids dream of electric sheeps?”, “Dick”, “Feltrinelli”, 11),
(“Le affinita’ elettive”, “Goethe”, “Einaudi”, 10)]
OUT OF BOUNDS !
22
Proprieta’ degli scaffali III
• Per motivi di efficienza vogliamo che non
compaiano ripetizioni di items (Libri o Riviste)
23
Esempio: ripetizioni
[ (“Do the androids dream of electric sheeps?”, “Dick”,
“Feltrinelli”, 2),
(“Do the androids dream of electric sheeps?”, “Dick”,
“Feltrinelli”, 10)]
Non e’ una rappresentazione efficiente.
Meglio usare
[ (“Do the androids dream of electric sheeps?”, “Dick”,
“Feltrinelli”, 12)]
24
Proprieta’ della Biblio
• collezione di scaffali di Libri
• collezione di scaffali di Riviste
• Ogni scaffale deve avere le proprieta’ viste in
precedenza
25
Proprieta’ della Biblio
• Inoltre per entrambe le collezioni vogliamo
--l’ultimo item dello scaffale i precede o e’
uguale al primo item dello scaffale i+1
--lo scaffale i puo’ contenere items solo se tutti
gli scaffali j con j<i sono pieni
26
Esempio
1=[L1,L2,L3,L4]
2=[L5,L6]
deve essere L5 <L6
e la dimensione 4 (assumendo i libri con
occorrenze 1)
Se la dimensione e’ 5==>
1=[L1,L2,L3,L4,L5]
2=[L6]
27
Operazioni
 Abbiamo visto le proprieta’ dei dati astratti
Biblio
 Vediamo le operazioni
28
Inializzazione: parametri
 la dimensione degli scaffali (k)
 il numero di scaffali dei due tipi (n)
 la dimensione e’ >0
29
Operazioni
 capacity-libro
• restituisce il numero di occorrenze per Libri
ancora liberi
 capacity-rivista
• restituisce il numero di occorrenze per Riviste
ancora liberi
30
Operazioni
 number-l
 prende come parametro l’autore, il titolo e
l’editore
• restituisce il numero di occorrenze del Libro
corrispondente presente in this
31
Operazioni
 number-r
 prende come parametro l’autore, il titolo, l’editore
ed il numero
• restituisce il numero di occorrenze della Rivista
corrispondente presente in this
32
Operazioni
 alllibri
• restituisce il numero di Libri
presenti in this (come numero di occorrenze)
33
Operazioni
 allriviste
• restituisce il numero di Riviste
presenti in this (come numero di occorrenze)
34
Operazioni
 scaffale-l
 prende come parametro un titolo, un autore, un
editore ed un numero di occorrenze x
• restituisce il numero di uno scaffale in cui si
trovano almeno x occorrenze del libro
corrispondente
• se non ci sono restituisce 0
35
Operazioni
 scaffale-r
 prende come parametro un titolo, un autore, un
editore, un numero ed un numero di occorrenze x
• restituisce il numero di uno scaffale in cui si
trovano x occorrenze della rivista corrispondente
• altrimenti restituisce 0
36
Operazioni
 libro-titoli
 prende come parametro un autore
• restituisce il numero di titoli differenti di Libri di
tale autore
• se non ce ne sono restituisce 0
37
Operazioni
 rivista-titolo
 prende come parametro un autore ed un titolo
• restituisce il numero di numeri differenti di Riviste
tale autore e titolo
• se non ce ne sono restituisce 0
38
Modificatori
 insert-l
 prende come parametro un titolo, un autore, un
editore, un numero di occorrenze x
• se il numero di pezzi di x supera il limite sulla
dimensione della Biblio solleva
SizeException (controllata)
• altrimenti, inserisce il Libro (come abbiamo
descritto in precedenza)
39
Modificatori
 insert-r
 prende come parametro un titolo, un autore, un
editore, un numero, un numero di occorrenze x
• se il numero di pezzi di x supera il limite sulla
dimensione della Biblio solleva
SizeException (controllata)
• altrimenti, inserisce la rivista (come abbiamo
descritto in precedenza)
40
Esempio: inserimento
1=[L1,L2,L3,L4]
2=[L5,L6]
(assumendo i libri con
occorrenze 1 e la dimensione 4)
Se devo inserire L tale che L3<L<L4 =====>
1=[L1,L2,L3,L]
2=[L4,L5,L6]
devono essere shiftati!
attenzione alle ripetizioni!!!
41
Modificatori
 remove-l
 prende come parametro un titolo, un autore, un
editore ed un numero di pezzi x
• se gli scaffali di Libri non contengono almeno x
occorrenze del libro corrispondente solleva
l’eccezione NotFoundException
(controllata)
• altrimenti rimuove dagli scaffali x occorrenze del
Libro corrispondente
42
Modificatori
 remove-r
 prende come parametro un titolo, un autore, un
editore, un numero ed un numero di pezzi x
• se gli scaffali di Riviste non contengono almeno x
occorrenze della rivista corrispondente solleva
l’eccezione NotFoundException
(controllata)
• altrimenti rimuove dagli scaffali x occorrenze
della Rivista corrispondente
43
Modificatori
 svuota-scaffale
 prende come parametro il numero i di uno scaffale
di Libri o Riviste
• elimina tutto il contenuto dello scaffale
• se non esiste lo scaffale i-esimo solleva una
opportuna eccezione
44
Modificatori
 aggiungi-scaffale
 prende come parametro un intero i >0
• aggiunge i Scaffali sia di Libri che di Riviste
45
Modificatori
 union
 prende come parametro una Biblio b
 modifica this facendo l’unione con b
46
Subset
 subset
 prende come parametro una Biblio b
 restituisce -1 se this e’ un sottoinsieme di b,
resituisce 0 se sono uguali, 1 se b e’ sottoinsieme
di this
 solleva un’ eccezione se non sono confontabili
ATTENZIONE (L1,x) appartiene
{(L1,y)} se x <=y
47
Proprieta’ della Biblio
 Devono essere garantite per costruzione
 Costruttori
 Metodi d’istanza modificatori
 Per esempio se si svuota lo scaffale 3, gli
items degli scaffali successivi devono essere
spostati
48
Esempio: rimuoviamo lo scaffale
1
1=[L1,L2,L3,L4]
2=[L5,L6,L7,L8]
3=[L9,L10,L11,L12]
(assumendo i libri con
occorrenze 1 e la dimensione 4)
1=[L5,L6,L7,L8]
2=[L9,L10,L11,L12]
49
Come procedere?
• Partire dalla specifica del tipo di dato principale Biblio
• Specifica: costruttori, metodi e descrizione informale
(pre e post condizioni)
• Devono realizzare le richieste descritte in precedenza
• I commenti alle classi sono parte integrante del progetto
50
Tipi di dato ausilari
• La specifica del magazzino si basa su alcuni tipi di dato ausiliari: Libro
e Rivista
• E’ necessario darne specifica ed implementazione
• Lo stato degli oggetti deve memorizzare le informazioni richieste
• Quali Operazioni? A scelta:
---pensare ad un insieme di operazioni significativo
---semplifichino e supportino la realizzazione del tipo di
dato principale
• Scelte di progetto spiegate e motivate nella relazione
51
Implementazione
• Scegliere la rappresentazione piu’ adeguata per ogni tipo di
dato
• Non ci sono vincoli sul modo in cui realizzarlo (purche’
funzioni)
52
Verranno apprezzate
• Uso delle liste concatenate (per esempio per memorizzare
la collezione degli scaffali sia di Libri che di Riviste)
• Se ci sono h scaffali uno potrebbe usare un array di
dimensione h
• In posizione i-esima una lista ordinata di Libri potrebbe
rappresentare lo scaffale i-esimo
• Un po’ complesso spostare le cose da uno scaffale
all’altro!!
• Piu’ semplice usare una lista concatenata in cui i nodi
riportano l’info sul numero di scaffale in cui siamo
53
Verranno apprezzate
• L’uso dell’ereditarieta’: e’ evidente che i tipi di dato Libro
e Rivista hanno qualcosa in comune (si possono usare tipi
e sottotipi?)
• Analogamente : le due collezioni di scaffali hanno
qualcosa in comune (si possono realizzare nello stesso
modo?)
54
Testing
 Deve essere realizzato tramite un opportuno
metodo main (in modo standard)
 Deve essere inviato insieme ai files del
progetto
 NOTA: il progetto deve essere inviato una
ed una sola volta nella versione finale
(funzionante)
55