Abstract Data Type

(1)

Abstract Data Type

Paolo Bison

Fondamenti di Informatica 1 A.A. 2004/05

Universit`a di Padova

Abstract Data Type, Paolo Bison, A.A. 2004-05, 2004-12-04 – p.1/33

(2)

Tipo di dato astratto

definizione di un dato indipendente dalla sua rappresentazione interna e dalla effettiva

implementazione delle operazioni su tale dato

viene definito specificando:

un insieme di valori, detto dominio del tipo di dato

un nome con cui si indica il dominio

un insieme di funzioni che opera sul dominio

• costruttori

• operatori

• predicati

un insieme di costanti appartenenti al dominio

(3)

Esempio di ADT

Tipo Boolean

Dominio B = {true, false}

Funzioni

Costruttori operatori di uguaglianza e confronto

Operatori

∧ : B × B → B

∨ : B × B → B

¬ : B → B

Predicati = : B × B → B 6= : B × B → B Costanti true,false

(4)

Altro di ADT

Tipo Integer Dominio Z ⊂ Z

Funzioni

Costruttori trunc : R → Z read

Operatori + : Z × Z → Z − : Z × Z → Z

∗ : Z × Z → Z / : Z × Z → Z

Predicati

= : Z × Z → B 6= : Z × Z → B

> : Z × Z → B < : Z × Z → B

≤ : Z × Z → B ≥ : Z × Z → B

(5)

ADT in OOP

la classe rappresenta un ADT Tipo nome della classe

Dominio insieme delle istanze

Funzioni metodi dell’interfaccia pubblica Costanti notazione per le istanze

(6)

Esempio di ADT in OOP

Tipo Complex

Dominio C = R × R

Funzioni

Costruttori new : R × R → C Operatori add: C × C → C

mul: C × C → C

Predicati equals: C × C → B

Costanti -

(7)

ADT in Java

¿ classe o interfaccia ?

equivalente come rappresentazione di ADT

differente uso pratico

interfaccia

non si può istanziare

possibilità di scelta tra più implementazioni

classe

si può istanziare

implementazione trasparente all’utilizzatore

Esempio:

il tipo Complex realizzato in tre modalità differenti

(8)

Collezioni

una collezione rappresenta un insieme di oggetti, detti elementi

differenti tipi di collezioni a seconda della

strutturazione e dei metodi di accesso agli elementi

Stack

Queue

Dictionary

(9)

Elementi comuni alle collezioni

Dominio dato l’insieme V degli elementi, D = V ^∗ Funzioni size: D → N

isEmpty: D → B

dato D ∈ D

size(D) = |D|

isEmpty(D) = ( true se D = λ false se D 6= λ

(10)

Stack

una collezione in cui la rimozione di elementi può avvenire solamente in ordine inverso di come sono stati inseriti

Funzioni push: D × V → D pop: D → D × V

dati v ∈ V e D ∈ D

push(< D, v >) = vD pop(vD) =< D, v >

Last In First Out (LIFO)

(11)

Realizzazione di uno Stack

array che vengono ridimensionati

pop: 0(1)

push: O(1) o O(n) a seconda della modalità di ridimensionamento

liste dinamiche

sia pop che push: O(1)

(12)

Analisi prestazioni push con array

push è O(1) eccetto “alcune volte” in cui è O(n)

quante volte?

n → n+k con k>0 (costante additiva)

su n si hanno n/k operazioni “lente” ⇒ O(n)

n → kn con k>1 (costante moltiplicativa)

su n si hanno 1/(k-1) operazioni “lente” ⇒ O(1)

analisi ammortizzata

(13)

Controllo di parentesi

verificare se in un’espressione algebrica ad ogni parentesi aperta corrisponde una parentesi chiusa dello stesso tipo:

tonda

quadra

grafa

(14)

Controllo di parentesi

effettuando una scansione dell’espressione

inseriamo sulla pila le parentesi aperte

quando troviamo una parentesi chiusa, estraiamo una parentesi dalla pila e controlliamo che i tipi

corrispondano, segnalando un errore in caso contrario

se ci troviamo a dover estrarre da una pila vuota, vi è errore:parentesi chiusa senza aperta

se al termine della stringa la pila non è vuota, vi è

errore: parentesi aperta senza chiusa

(15)

Reverse Polish Notation

notazione postfissa per le espressioni

l’operatore segue gli operandi a cui si applica

non ci sono le parentesi

7 1 2 + 4 * 5 4 + - /

7/((1+2)*4 - (5+4))

(16)

RPN algoritmo

Finché l’espressione non è terminata

leggi da sinistra il primo simbolo o valore non letto

• se è un valore, inseriscilo sulla pila

• altrimenti (è un operatore)

- estrai dalla pila il primo operando

- estrai dalla pila il secondo operando - esegui l’operazione

- inserisci il risultato sulla pila

se alla fine la pila contiene più di un valore,

l’espressione è errata

(17)

Classe StringTokenizer

classe del package java.util

permette di suddividere un stringa in singoli elementi (token)

separatori di default: " \t\n\r\f"

metodi

boolean hasMoreTokens()

String nextToken()

(18)

Queue

una collezione in cui la rimozione di elementi può

avvenire solamente nello stesso ordine di come sono stati inseriti

Tipo Queue

Funzioni add: D × V → D delete: D → D × V

dati v ∈ V e D ∈ D

add(< D, v >) = Dv

delete(vD) =< D, v >

(19)

Simulazione di una banca

simulazione delle code di attesa alle casse di una banca

dati

numero di casse

efficienza di ogni cassa = numero di operazioni per unità di tempo

generata casualmente tra un valore max e uno min

probabiltà che entri un cliente ad ogni unità di tempo

numero di operazioni per cliente

generata casualmente tra un valore max e uno min

(20)

Algoritmo di simulazione

ad ogni unità di tempo simulato

genera un cliente,avente un numero casuale di

operazioni, con la probabilità data ed inseriscilo in coda nella cassa con meno clienti

per ogni cassa

• esegui un ciclo di lavoro se ci sono clienti in coda

(21)

Numeri casuali

metodo double random() della classe Math

restituisce un numero nell’intervallo [0, 1[ generato in maniera pseudo-casuale con distribuzione uniforme

numero intero tra [a, b] con distribuzione uniforme (int)(a +(1+b-a)*Math.random()

(22)

Dictionary

un dizionario è un contenitore che contiene coppie di dati del tipo

chiave/valore

funzionalità

inserimento

ricerca per chiave

cancellazione data la chiave

vincolo

la chiave deve essere unica

altri termini

(23)

Property list in Java

classe Properties del package java.util java.util.Dictionary

java.util.Hashtable

java.util.Properties

ciascuna chiave e il suo corrispondente valore sono stringhe

metodi

String getProperty(String)

Object setProperty(String,String)

Object remove(Object)

properties di sistema

System.getProperties()

(24)

Dictionary

dato l’insieme K delle chiavi e l’insieme M dei valori, si ha V = K × M

Tipo Dictionary Funzioni

insert: D × K × M → D remove: D × K → D

find: D × K → M

(25)

Realizzazione di un Dictionary

liste dinamiche

non ordinate

ordinate

array che vengono ridimensionati

non ordinati

ordinati

lista array non ordinato array ordinato

insert n n n

find n n log n

remove n n n

(26)

Aumento delle prestazioni

se K = {k ∈ Z : k ⁰ ≤ k ≤ k ¹ }

⇓

si può usare un array che contiene i riferimenti ai valori, usando le chiavi come indici nell’array

valore null indica che la chiave non è presente

⇓

tutte le operazioni hanno complessità O(1)

(27)

Tabella

un dizionario con chiavi numeriche intere viene detto tabella (table)

dato dato

dato null

null null chiave = 2

chiave = 3 chiave = 0

(28)

Pro e cons di una tabella

pro

dizionario con prestazioni ottime

cons

chiavi numeri interi

per chiavi qualunque deve esistere un funzione iniettiva f : K → Z

l’intervallo [k ⁰ , k ¹ ] deve essere conosciuto a priori

inefficiente uso della memoria

dimensione della tabella: k

¹

− k

⁰

+ 1

fattore di riempimento (load factor) : numero dati contenuti dimensione tabella

(29)

Funzione di hash

per ridurre lo spreco di memoria si fissa la dimensione N della tabella e si usa una funzione di trasformazione delle chiavi:

h : K → {i : 0 ≤ i < N }

h funzione di hash

generalmente non è invertibile:

h(k j ) = h(k l ) con k j , k l ∈ K e k j 6= k l

esempio di funzione di hash

se k ∈ Z h(k) = k mod N

chiave ridotta

tabella hash (hash table)

(30)

Collisione

dato che due chiavi possono avere la stessa chiave ridotta può succedere che una locazione della tabella sia già occupata da un valore

le due coppie chiave/valore collidono

risoluzione

uso della prima locazione libera

liste di coppie chiave/valore con la medesima chiave

ridotta

(31)

Tabella hash con bucket

ogni cella della tabella è una lista di elementi con la medesima chiave ridotta

Abstract Data Type

Abstract Data Type

Tipo di dato astratto

definizione di un dato indipendente dalla sua rappresentazione interna e dalla effettiva

implementazione delle operazioni su tale dato

viene definito specificando:

 un insieme di valori, detto dominio del tipo di dato

 un nome con cui si indica il dominio

 un insieme di funzioni che opera sul dominio

• costruttori

• operatori

• predicati

 un insieme di costanti appartenenti al dominio

Esempio di ADT

Tipo Boolean

Dominio B = {true, false}

Funzioni

Costruttori operatori di uguaglianza e confronto

Operatori

∧ : B × B → B

∨ : B × B → B

¬ : B → B

Predicati = : B × B → B 6= : B × B → B Costanti true,false

Altro di ADT

Tipo Integer Dominio Z ⊂ Z

Funzioni

Costruttori trunc : R → Z read

Operatori + : Z × Z → Z − : Z × Z → Z

∗ : Z × Z → Z / : Z × Z → Z

Predicati

= : Z × Z → B 6= : Z × Z → B

> : Z × Z → B < : Z × Z → B

≤ : Z × Z → B ≥ : Z × Z → B

ADT in OOP

la classe rappresenta un ADT Tipo nome della classe

Dominio insieme delle istanze

Funzioni metodi dell’interfaccia pubblica Costanti notazione per le istanze

Esempio di ADT in OOP

Tipo Complex

Dominio C = R × R

Funzioni

Costruttori new : R × R → C Operatori add: C × C → C

mul: C × C → C

Predicati equals: C × C → B

Costanti -

ADT in Java

¿ classe o interfaccia ?

equivalente come rappresentazione di ADT

differente uso pratico

interfaccia

 non si può istanziare

 possibilità di scelta tra più implementazioni

classe

 si può istanziare

 implementazione trasparente all’utilizzatore

Esempio:

il tipo Complex realizzato in tre modalità differenti

Collezioni

una collezione rappresenta un insieme di oggetti, detti elementi

differenti tipi di collezioni a seconda della

strutturazione e dei metodi di accesso agli elementi

 Stack

 Queue

 Dictionary

Elementi comuni alle collezioni

Dominio dato l’insieme V degli elementi, D = V ∗ Funzioni size: D → N

isEmpty: D → B

dato D ∈ D

size(D) = |D|

isEmpty(D) = ( true se D = λ false se D 6= λ

Stack

una collezione in cui la rimozione di elementi può avvenire solamente in ordine inverso di come sono stati inseriti

Funzioni push: D × V → D pop: D → D × V

dati v ∈ V e D ∈ D

push(< D, v >) = vD pop(vD) =< D, v >

Last In First Out (LIFO)

Realizzazione di uno Stack

array che vengono ridimensionati

 pop: 0(1)

 push: O(1) o O(n) a seconda della modalità di ridimensionamento

un insieme di valori, detto dominio del tipo di dato

un nome con cui si indica il dominio

un insieme di funzioni che opera sul dominio

un insieme di costanti appartenenti al dominio

non si può istanziare

possibilità di scelta tra più implementazioni

si può istanziare

implementazione trasparente all’utilizzatore

Stack

Queue

Dictionary

Dominio dato l’insieme V degli elementi, D = V ^∗ Funzioni size: D → N

pop: 0(1)

push: O(1) o O(n) a seconda della modalità di ridimensionamento

sia pop che push: O(1)

n → n+k con k>0 (costante additiva)

n → kn con k>1 (costante moltiplicativa)

tonda

quadra

grafa

inseriamo sulla pila le parentesi aperte

quando troviamo una parentesi chiusa, estraiamo una parentesi dalla pila e controlliamo che i tipi

se ci troviamo a dover estrarre da una pila vuota, vi è errore:parentesi chiusa senza aperta

se al termine della stringa la pila non è vuota, vi è

l’operatore segue gli operandi a cui si applica

7/((1+2)*4 - (5+4))

leggi da sinistra il primo simbolo o valore non letto

boolean hasMoreTokens()

String nextToken()

numero di casse

efficienza di ogni cassa = numero di operazioni per unità di tempo

probabiltà che entri un cliente ad ogni unità di tempo

numero di operazioni per cliente

genera un cliente,avente un numero casuale di

per ogni cassa