Listalaurap/didattica/Fondamenti-2... · 2007. 11. 29. · 1 Lista Lista • La Lista è un TDA che...

1

Lista

Lista• La Lista è un TDA che generalizza il concetto di

sequenza: gli elementi hanno un ordine posizionale. Nella Lista tutti gli elementi sono accessibili.

• C’è un linguaggio di programmazione LISP(LISt Processor, 1958) basato sul concetto di lista. È un linguaggio funzionale: il programma è inteso come funzione, la lista viene definita attraverso i suoi assiomi (funzioni) e le funzioni possono essere composte per costruire altre funzionalità della lista.

Lista• Le informazioni elementari che si vogliono

rappresentare in una Lista si chiamano atomi.• Dominio del TDA:

Dominio = {atomi, lista}= A ∪ LLLL

LLLL = {insieme di tutte le liste}A = {insieme degli atomi}

costante = λ : lista vuotafunzioni = {isEmpty, head, rest, build}

Lista• Nel linguaggio LISP queste funzioni si

chiamano:isEmpty nullhead carrest cdrbuild cons

• Vediamo il comportamento del TDA, assiomi, indipendentemente dalla sua realizzazione.

Lista• Funzioni (assiomi) che definiscono la Lista:• 1) isEmpty : L L L L →→→→ B B B B

true se llll = λ

isEmpty(llll) =

false se llll ≠ λ

• 2) head : L L L L →→→→ A

se llll ≠ λ head(llll ) = a

altrimenti “eccezione”

head: testa

llll

a

Lista• 1) rest : L L L L →→→→ L L L L

se llll ≠ λ rest(llll ) = llll '

altrimenti “eccezione”rest: toglie la testa

• 2) build : A ×××× L L L L →→→→ L L L L

build(a, llll ) = llll '

concatenazione atomo-listacostruisce la lista

llll

llll '

lllla

llll '

2

Lista• La Lista viene definita in generale tramite una

funzione ricorsiva:• una lista è:

• la lista vuota• oppure, dato un atomo e una lista (che può

essere λ) è la concatenazione dell’atomo alla lista.

• Con questa definizione ricorsiva vediamo come si può costruire la lista.

Lista• llll = λ = () si parte da lista vuota

• a è un atomo; si può costruire la lista (a):(a) = build(a, λ)

• aggiungiamo altri elementi: siano b e c atomi(b, a) = build(b,(a))(c, b, a) = build(c, (b,a))

• Le funzioni si possono comporre e si possono costruire altre funzioni, con le quali si rappresenta l’accesso a tutti gli elementi della lista.

Lista• Esempio. • Sia L = (c, b, a)

head(L) = c rest(L) = (b, a)

componiamo le funzioni:head(rest(build(c, (b, a)))) = b

head(build(c,(b, a))) = c

Lista• L’insieme degli assiomi è completo: ogni altra

funzione della Lista può essere espressa tramite gli assiomi. Si usano definizioni ricorsive.

• Esempio. Definiamo la lunghezza della Lista:ln: L L L L →→→→ ��

0 se L = λlen(L) =

1+ len(rest(L)) se L ≠ λlen((c, b, a)) = 1 + len((b, a)) = 1 + 1 + len((a)) =

= 1+ 1+ 1+ len(λ ) = 3

Lista• Definiamo la fine della Lista (l’ultimo

elemento)end: L L L L →→→→ A solo se L ≠ λ

head(L) se rest(L) = λend(L) =

end(rest(L)) se rest(L) ≠ λ

end((c, b, a)) = end((b, a)) = end((a)) = = head((a)) = a

Lista• Definiamo una funzione per aggiungere alla fine

un elemento:addToEnd: L L L L ×××× A→→→→ L L L L

build(a, L) se L = λ

addToEnd(L,a) =

build(head(L), addToEnd(rest(L), a)) se L ≠ λ

3

ListaaddToEnd(λ, a) = build(a, λ) = (a)

addToEnd((a), b) = = build(a, addToEnd(λ , b)) == build(a, (b)) = (a, b)

addToEnd((a, b), c) = = build(head(a,b), addToEnd(rest(a,b), c) == build(a, addToEnd((b), c) = build(a, (b,c)) == (a, b, c)

Lista• Possiamo definire la funzione per togliere

l’ultimo elemento (se L ≠ λ):deleteFromEnd: L L L L →→→→ L L L L

rest(L) se rest(L) = λ

deleteFromEnd(L) =se rest(L) ≠ λ

build(head(L), deleteFromEnd(rest(L))

• Si può anche definire la funzione per la concatenazione di due liste.

Lista• La realizzazione della Lista si può fare su array o su

lista concatenata; ne vediamo la realizzazione su lista concatenata.

• Nella realizzazione in Java definiamo la Lista nell’interfaccia List.

• Nell’interfaccia List sono definite le operazioni di costruzione, rimozione e accesso al primo elemento e un metodo di tipo interfaccia ListIterator, che descrive i metodi per attraversare la Lista.

• L’iteratore su Lista, ListIterator, rappresenta il concetto di posizione all’interno della Lista.

Listapublic interface List{

boolean isEmpty();

Object getFirst(); //head

Object removeFirst(); //rest

void addFirst(Object x); //build

ListIterator listIterator();

//metodo che restituisce un

//iteratore su Lista

}

Listapublic interface ListIterator{

Object next();

boolean hasNext();

void add(Object ogg);

void remove();

void set(Object ogg);

//questa interfaccia contiene un

//sottoinsieme dei metodi

//dell’interfaccia standard

// java.util.ListIterator

}

LinkedList

• La classe LinkedList del pacchetto java.utilrealizza la struttura di dati: lista concatenata (par. 14.1).

• La classe LinkedList possiede tutti i metodi per accedere direttamente sia al primo che all’ultimo elemento: addFirst, getFirst, removeFirst, addLast, getLast, removeLast.

• Per accedere agli altri elementi utilizza un metodo che costruisce un iteratore su lista e quindi i metodi dell’iteratore.

4

LinkedList

• La classe LinkedList è una classe generica come ArrayList; si possono definire i vari tipi di dato scrivendoli entro parentesi angolari .

• Avremmo potuto realizzare lo Stackutilizzando i metodi di LinkedList.

Stack con LinkedList

public class LinkedListStack

implements Stack{

private LinkedList lista =

new LinkedList();

public boolean isEmpty(){

return lista.isEmpty();}

public void push(Object ogg){

lista.addFirst(ogg);}

}


public Object top(){

return lista.getFirst();}

public void pop(){

Object ogg = lista.removeFirst();

}

public void makeEmpty(){

lista.makeEmpty();}

}//fine LinkedListStack


• In tale modo avremmo utilizzato le classi della libreria senza però capire come si realizza una lista concatenata.

• Come si fa negli altri linguaggi che non hanno a disposizione classi (o pacchetti di software) che gestiscono liste concatenate?

• Si impara a scrivere il codice per eseguire la costruzione dei nodi e tutte le operazioni di inserimento e cancellazione.

• È ciò che noi abbiamo fatto.

List con LinkedList

List con LinkedList

• Potevamo costruire un’interfaccia List con i metodi head, rest, build e poi, analogamente a quanto fatto con lo Stack, costruire il codice di tali metodi tramite l’invocazione dei metodi di LinkedList.

• Invece abbiamo costruito un’interfaccia List con il nome dei metodi presenti in LinkedList e costruiremo una nostra classe LinkedListList che realizza List, nella quale andiamo a scrivere il codice di alcuni metodi di LinkedList: gestione del primo elemento e l’iteratore che avanza.

5

List con LinkedList

• Nel libro è presentata una versione piùsemplice della classe LinkedList, con il codice relativo ad alcuni dei metodi che gestiscono una lista concatenata (par. 14.2).

• La classe LinkedList definisce una classe interna privata LinkedListIterator che realizza l’interfaccia ListIterator.

• Questa versione semplificata non contiene i metodi per eseguire la scansione all’indietro.

List con LinkedList

public class LinkedListList

implements List{

private Node first;

public LinkedListList(){

first = null;

} //oppure first = null;

. . .

private class Node{

Object data;

Nodo next; }

List con LinkedList

• Nella classe ci sono i metodi dell’interfaccia List per gestire il primo elemento

//visione della testa

public Object getFirst(){//head

if(first == null)

throw

new NoSuchElementException();

else return first.data;

}

// NoSuchElementException di java.util

List con LinkedList

• Metodo per aggiungere un nuovo elemento in testa:

public void addFirst(Object element){

Node newNode = new Node();

newNode.data = element;

newNode.next = first;

first = newNode;

}

List con LinkedList

• Metodo per togliere la testa; restituisce la testa: è come topAndPop:

public Object removeFirst(){

if (first == null)

throw

new NoSuchElementException();

Object element = first.data;

first = first.next;

return element;

}

List con LinkedList

public boolean isEmpty() {. . .}

• Questo metodo che restituisce un riferimento di una classe che realizza ListIterator

public ListIterator listIterator(){

return new LinkedListIterator();

}

• Bisogna costruire la classe LinkedListIterator.

6

List con LinkedList

• La classe è privata perché deve essere nota solo all’interno di LinkedList:

private class LinkedListIterator

implements ListIterator{

//realizza i metodi:

// next, hasNext, add,

// remove, set

. . .

}//fine LinkedListIterator

}// LinkedListList

List con LinkedList

• Nella classe LinkedListIterator per poter accedere agli elementi della lista per eseguire le varie operazioni abbiamo bisogno di dueriferimenti: position che vede il prossimo, previous che vede il precedente:

private Node position;

private Nodo previous;

public LinkedListIterator(){

position = null;

previous = null;

}

List con LinkedList

• Vediamo solo hasNext e add//public boolean hasNext(){

if(position == null)

return first != null;

else

return position.next != null;

}

• Non c’è elemento successivo (restituzione di falso) se la lista è vuota, e cioè se first è uguale a null, oppure se position.next è null. Negli altri casi viene restituito vero.

List con LinkedListpublic void add(Object element){

if(position == null){

addFirst(element);

position = first;}

else{

Node newNode = new Node();

newNode.data = element;

newNode.next = position.next;

position.next = newNode;

position = newNode;

}

previous = position;

}

Lista di interi su lista concatenata


• Abbiamo visto nel laboratorio la classe ListaListC che realizza una Lista di interi (accesso ad ogni elemento) con una lista concatenata e una classe di prova con inserimenti e cancellazioni in testa, in coda, in posizioni intermedie, per verificare la possibilità di eseguire le operazioni su un qualunque elemento.

• Nella classe ListaListC ci sono tutti i metodi per accedere, aggiungere e togliere sia il primo che l’ultimo elemento della Lista.

7


• In questa realizzazione, invece dell’iteratore e della classe che lo realizza, si definiscono due riferimenti, pos e prec di tipo ElemInteroanaloghi a position e previous, e si effettua ogni volta la ricerca della posizione eseguendo la scansione della Lista.

• Si applicano quindi i metodi specifici che eseguono le varie operazioni di inserimento e cancellazione (prima o dopo un elemento dato per individuare la posizione, se è presente).


private ElemIntero pos, prec;

. . .

public boolean ricerca(int elem){//O(n)

boolean trovato;

pos = primo;

trovato = false;

while((pos!=null) && (!trovato))

if(pos.info == elem)

trovato = true;

else { prec = pos;

pos = pos.next; }

return trovato;

}


//inserimento di un elemento dopo un

//elemento elem se presente

public void insdopo(int elem, int dato){

if(this.ricerca(elem)){

ElemIntero nuovo = new ElemIntero();

nuovo.info = dato;

nuovo.next = pos.next; //aggancio a pos

pos.next = nuovo;

}

else throw new NoSuchElementException();

}


• La stampa della Lista viene fatta senza vuotare la Lista: ogni elemento è accessibile.

public void stampaLista() {

ElemIntero tmp = primo;

while (tmp != null) {

System.out.println(tmp.info);

tmp = tmp.next;

}

}//fine stampaLista

Lista ordinata di interi

• Vediamo come si può realizzare l’inserimento in ordine crescente di un elemento in modo da costruire una Lista ordinata di interi: inizio è il riferimento al primo elemento della Lista.

public void insordine(int elem){

//ricerca della posizione in cui inserire

ElemIntero tmp = inizio;

while((tmp != null) && (tmp.info

8

Insieme

Insieme

• Il TDA Insieme, Set, è un contenitore, eventualmente vuoto, di oggetti distinti:• senza alcun particolare ordinamento• senza memoria dell’ordine temporale in cui

gli oggetti vengono inseriti od estratti• si comporta come un insieme matematico

• Le operazioni che si possono su un Insieme sono• inserimento di un oggetto• verifica se un oggetto è presente• ispezione di tutti gli oggetti

Insieme

• Per poter inserire un elemento nell’insieme si deve prima verificare che non sia giàcontenuto. Se l’elemento è presente non si segnala alcun errore, semplicemente non lo si inserisce.

• Un insieme si può realizzare su array non ordinato, array ordinato e su lista concatenata.

• Vediamo un realizzazione del metodo che verifica se un elemento è oppure no presente nell’insieme, considerando un array non ordinato e ridimensionabile.

Insieme//verifica se un elemento e’ presente o no

// in un Insieme di interi

public boolean contains(int x){

boolean presente = false;

int i = 0;

while(i< dim && !presente){

if(v[i] == x)

presente = true;

i++;

}

return presente;

}

//con Object if(v[i].equals(x))

Operazioni sugli insiemi

• Per due insiemi A e B, si definiscono le operazioni di unione, intersezione, differenza.

• Unione A∪B: appartengono all’unione di due insiemi tutti e soli gli oggetti che appartengono ad almeno uno dei due insiemi.

• Intersezione A∩B: appartengono alla intersezione di due insiemi tutti e soli gli oggetti che appartengono ad entrambi gli insiemi.

• Differenza A\B: appartengono alla differenza tutti e soli gli oggetti che appartengono all’insieme A e non appartengono all’insieme B.

Insieme con array non ordinato

• La realizzazione di un Insieme con un array non ordinato non è buona:

• il metodo di verifica ha un costo O(n) e anche l’operazione per inserire un elemento è O(n);

• tutte le operazioni che agiscono su due insiemi sono O(n2) perché, eseguendo ad esempio l’unione, per ogni elemento di uno dei due si deve verificare che già non sia nell’altro.

9

Insieme con lista concatenata e array ordinato

• Si può verificare che si ottengono le stesse prestazioni realizzando l’Insieme con una lista concatenata.

• La realizzazione di un Insieme con un array ordinato non fa variare la complessità della operazioni se non si tiene conto dell’ordine.

• Sfruttando l’ordine dei due array, l’unione si ottiene eseguendo il merge tra array che è O(n), inserendo però un solo elemento nel caso di uguaglianza.

Insieme array ordinato

• Sfruttando l’ordine dell’array, il metodo di verifica può utilizzare la ricerca binaria che è O(log2n).

• Per inserire un elemento si può utilizzare l’inserimento in ordine, che in media è O(n).

• Non è detto, ovviamente, che abbia senso l’ordine degli elementi dato che il concetto matematico di insieme è privo di ordinamento.

RiepilogoTDA e strutture di

dati

TDA

• Un Tipo di Dato Astratto è:• un insieme di elementi chiamato dominio del

tipo di dato• caratterizzato da un nome• possiede delle funzioni che operano sul

dominio• operatori, predicati, operatori di creazione

• possiede delle costanti che lo caratterizzano

TDA

• Nel linguaggio Java i TDA :

• si definiscono in una interfaccia che dichiaraquali sono le funzioni che operano sul dominio (cosa fa il TDA)

• si realizzano in una classe che definisce la struttura di dati e le funzioni che operano su di essa (come agisce il TDA).

10

TDA

• I seguenti TDA sono contenitori caratterizzati dalle loro diverse operazioni :• Pila (Stack)• Coda (Queue)• Lista (con iteratore)• Dizionario e Tavola• Insieme

• Questi TDA estendono l'interfaccia GenericContainer, avendo la proprietà di verifica del contenitore vuoto e della sua inizializzazione.

Strutture di dati

• Una struttura di dati è un modo di organizzare i dati in un contenitore di dati ed ha una sua propria modalità di accesso. Sono state viste le seguenti strutture:

• array riempito in parte e ridimensionabile• ordinato• non ordinato

• lista concatenata.

Strutture di dati

Array Lista concatenata

accesso diretto sequenzialesuccessivo i+1 a.nextdimensione massima sì* nospazio info info e nextspostamento dati sì no(inserire e cancellare)

(* senza raddoppio)

Pila Stack (Last In First Out)

• Le operazioni coinvolgono solo il primo elemento della Pila. Il TDA viene descritto nella seguente interfaccia:

public interface Stack {

boolean isEmpty();

void push(Object x);

void pop(); //oppure Object pop();

Object top();

}

Pila Stack (Last In First Out)

• Complessità delle funzioni

push pop top

array O(1) O(1) O(1)

(ultimo) (in media*)

lista O(1) O(1) O(1)

concatenata

(* raddoppio)

Coda o Queue (First In First Out)

• Le operazioni coinvolgono il primo elemento e l'ultimo elemento della Coda. Il TDA viene descritto nella seguente interfaccia:

public interface Queue{

boolean isEmpty();

void enqueue(Object x);

void dequeue(); //oppure Object dequeue();

Object front();

}

11

Coda Queue (First In First Out)

• Complessità delle funzioni

enqueue dequeue front

array O(1) O(1) O(1)(circolare) (in media*)

lista O(1) O(1) O(1)

concatenata

(* raddoppio)

Lista (iteratore)

• Generalizza il concetto di sequenza: è un contenitore di informazioni che hanno un ordine posizionale. Il TDA viene descritto nella seguente interfaccia:

public interface List{ boolean isEmpty();void addFirst(Object x);Object removeFirst();Object getFirst();ListIterator listIterator(); //posizione nella lista

}

Lista (iteratore)

public interface ListIterator{ boolean hasNext();Object next();void add(Object x);void remove();void set(Object x);

}

• La complessità delle operazioni della Lista su lista concatenata che riguardano il primo e ultimo elemento, usando un riferimento all’ultimo nodo, sono O(1) tranne removeLast che è O(n).

Dizionario o Dictionary

• E' costituito da coppie (chiave, attributo); la chiave èunica e deve permettere il confronto. Il TDA viene descritto nella seguente interfaccia:

public interface Dictionary{boolean isEmpty();void insert(Comparable chiave, Object x);Object find(Comparable chiave);void remove(Comparable chiave);

}

Dizionario o Dictionary

• Complessità delle funzioni:

insert * find removearray O(1) O(n) O(n)

(non ordinato) (in media)

array O(n) O(log2n) O(n)

(ordinato)

lista O(1) O(n) O(n)

concatenata

(*senza la ricerca per l'unicità della chiave che è O(n) o O(log2n))

Tavola o Table

• E' un dizionario a chiave intera. Il TDA viene descritto nella seguente interfaccia:

public interface Tavola{boolean isEmpty();void insert(int chiave, Object x);Object find(int chiave);void remove(int chiave);

}

• Se la chiave coincide con l'indice dell'array, le operazioni sono O(1).

12

Tavola Hash

• Si esegue una trasformazione della chiave per ottimizzarne la memorizzazione:

posizione = h(chiave)• h : resto della divisione intera chiave/dim• dim : dimensione della tavola

• Si utilizzano assieme le due strutture daticostruendo un array di liste concatenate (bucket).

• Se le chiavi sono n e le liste hanno la stessa lunghezza, le prestazioni sono O(n/dim).

Insieme o Set

• Rappresenta un insieme matematico: gli elementi sono unici. Le funzioni sono gli operatori unione, intersezione, differenza e la funzione appartiene-a. Il TDA viene descritto nella seguente interfaccia:

public interface Set{boolean isEmpty();void add(Object x);boolean contains(Object x);

}• Le funzioni hanno come argomento un elemento per

l'insieme.

Insieme o Set

• La complessità delle operazioni dipende dalla complessità della ricerca per verificare se l’elemento èoppure no presente.

• La complessità del metodo contains è:• O(n) per array non ordinato e lista concatenata• O(log2n) con array ordinato.

• Complessità delle operazioni di unione, intersezione e differenza su due insiemi di dimensione n ed m:• O(n+m) = O(n) con array ordinato • O(n*m) = O(n2) con array non ordinato

Java

Java

• Un algoritmo rappresenta l’astrazione della realtà.

• Un linguaggio di programmazionerappresenta l’astrazione del processore.

• La variabile e il tipo della variabile rappresentano l’astrazione della locazione di memoria e delle operazioni sulla variabile.

• Il linguaggio Java è un linguaggio di programmazione ad alto livello.

Java : compilatore e interprete

• Il linguaggio Java è dotato di un compilatoreche traduce il codice sorgente in un codice binario, detto bytecode, e di un interprete,Java Virtual Machine, che elabora ed esegueil bytecode.

• Il compilatore, durante la traduzione in codice macchina, esegue una analisi lessicale, sintattica e semantica.

13

Java Virtual Machine

• La macchina virtuale Java (JVM) è un interprete che carica in memoria il bytecode, esegue gli agganci con le classi delle librerie standard, interpreta ed esegue il bytecode.

• Si hanno così efficienza (compilatore) e portabilità, non solo a livello di codice sorgente, ma anche a livello di bytecode.

Programma Java

• Un programma Java è composto da una o piùunità compilabili: classi contenute in file di estensione .java .

• Ogni file sorgente può contenere una solaclasse con accesso pubblico il cui nome deve coincidere con quello del file che la contiene.

• Il file in uscita dal compilatore ha estensione .class

Alfabeto

• L'alfabeto del linguaggio è UNICODE, a 16 bit. • I primi 128 caratteri costituiscono il codice

ASCII.• Si distinguono le lettere minuscole dalle

maiuscole.• Lo spazio è un separatore.• Le parole chiave (parole che hanno un

particolare significato per il linguaggio) sono riservate, ossia non si possono usare come nomi di identificatori.

Token

• Le unità lessicali (token) con cui si costruiscono le frasi del linguaggio sono:

identificatori parole chiave costanti separatori operatori

• Parole chiave, costanti, separatori e operatori sono costruiti con i simboli del codice ASCII.

Tipi di dato in Java

• tipi base (primitivi, predefiniti): • numeri, caratteri, valori logici

• riferimenti a oggetti

• Le variabili associate a questi tipi sono memorizzate nello Stack.

Tipo Intero

A seconda dell'occupazione in byte si hanno i seguenti tipi:

byte (1), short (2), int (4), long (8).

Degli n bit a disposizione, il primo è il bit del segno0 positivi1 negativi

I rimanenti n-1 sono per il numero.

14

Tipo Intero

Si possono rappresentare 2n -1 valori diversi.

Costanti del tipo di dato: - 2n -1 e 2n -1 -1 che delimitano l'intervallo di rappresentazione.

In Java:

• Byte.MIN_VALUE Byte.MAX_VALUE

• Short.MIN_VALUE Short.MAX_VALUE

• Integer.MIN_VALUE Integer.MAX_VALUE

• Long.MIN_VALUE Long.MAX_VALUE

Tipo Intero

• Dato x, per trovare la sua rappresentazione r(x) in base b (b=2) si divide per la base e si prendono i resti.

• La rappresentazione dell'opposto è definita in complemento a 2

r(x) + r(-x) = 2n

• Per trovare la rappresentazione dell'opposto r(-x) si invertono tutti i bit di r(x) fatta eccezione degli 0 a destra e del primo 1 a destra (oppure si invertono tutti i bit e si aggiunge 1).

Tipo Reale

• A seconda dell'occupazione in byte si hanno i seguenti tipi: float (4), double (8).

• Dati n bit a disposizione il primo è il bit del segno

0 positivi1 negativi

• Dei rimanenti n-1 bit si ha una ripartizione tra esponente e mantissa.

Mantissa

• I numeri reali sono rappresentati in modulo e segno, riferiti alla base 2, con mantissa normalizzata e bit nascosto.

• Dato x per costruire la rappresentazione r(x) si deve trasformare in binario il numero reale:

parte intera: si divide per la base e si prendono i resti

parte frazionaria: si moltiplica per la base e si prendono e parti intere

• Si deve poi portare il numero binario in forma normalizzata 1.c1c2c3.... ×××× 2e

Esponente

• L'esponente e viene rappresentato con l'eccesso (in traslazione) vale a dire che e deve essere aumentato, di 127 per i float (eccesso). Il nuovo esponente (intero) viene trasformato in binario.

Costanti del tipo di datominimo reale ≠ 0 float ~ 10 -38

massimo reale float ~ 10 38

In Java• Float.MIN_VALUE Float.MAX_VALUE • Double.MIN_VALUE Double.MAX_VALUE

Classi e oggetti

• Java è un linguaggio orientato agli oggetti, basato su classi.

• Per costruire un nuovo concetto dobbiamo definire la sua forma (campi) e le sue proprietà (metodi).

• La classe ci permette di descrivere il nuovo concetto, con la definizione di campi e metodi.

• Per poter utilizzare il concetto si deve creare un oggetto del tipo della classe.

15

Classi e oggetti

• Un oggetto è una entità che può essere usataattraverso i metodi della classe.

• L'oggetto creato si chiama anche esemplare della classe o istanza della classe.

• Per creare un oggetto si usa l'operatore new.

• La variabile oggetto (il suo tipo è nomeclasse) dopo l'attivazione dell'operazione new, contiene il riferimento all'oggetto creato (informazioni sulla posizione di memoria dell'oggetto creato).

• Gli oggetti stanno nello Heap.

Campi

• All'interno di una classe sono definiti campi e metodi.

• I campi di una classe, chiamati anche campi di esemplare o variabili di istanza; solitamente sono dichiarati con accesso privato: incapsulamento o protezione dei dati.

• Con l’incapsulamento, solo i metodi della classe possono accedere ai campi.

Interfaccia pubblica

• Nella classe viene definita una interfaccia pubblicacostituita dall'insieme dei metodi pubblici che permettono di utilizzare l'oggetto dall'esterno.

• All'interfaccia pubblica appartiene anche il costruttore, che inizializza l'oggetto al momento della sua creazione.

• Astrazione: all'utente esterno è noto solo il nome del metodo e il suo comportamento; si usa l'oggetto senza conoscere la realizzazione dei suoi metodi.

Tempo di vita e inizializzazionedelle variabili in una classe

All'interno di una classe ci sono:

- variabili di istanza (campi)- variabili locali- variabili parametro

• Queste variabili hanno un diverso tempo di vita e diverse modalità di inizializzazione

Variabile di istanza

• Una variabile di istanza:• appartiene all'oggetto• è visibile ai metodi della sua classe• viene inizializzata da un costruttore (default,

esplicitamente)• viene creata, "nasce", quando l'oggetto viene

creato

• viene eliminata, "muore", quando l'oggetto viene eliminato, ossia non è più

referenziato (garbage collector)

Variabile locale

Una variabile locale:• appartiene a un metodo• è visibile all'interno del metodo• deve essere inizializzata esplicitamente• viene creata, "nasce", quando viene eseguito

l'enunciato in cui è definita • viene eliminata, "muore", quando l'esecuzione

del programma esce dal blocco nel qualeè stata definita (che può anche essere

il metodo che l'ha definita)

16

Variabile parametro

Una variabile parametro (formale):• appartiene a un metodo• è visibile all'interno del metodo• viene inizializzata all'atto della invocazione del

metodo (con il valore fornito dall'invocazione)• viene creata, "nasce", quando viene invocato

il metodo• viene eliminata, "muore", quando l'esecuzione

del metodo termina

Variabile statica

• Una variabile statica viene creata quando la JVM carica la classe per la prima volta ed eliminataquando la classe viene scaricata (si dice che ''esiste sempre'').

• Si chiama anche variabile di classe perché non appartiene ad un oggetto ma è di tutta la classe (ce n’èun’unica copia).

• Viene inizializzata esplicitamente o con il default(non nel costruttore).

Specificatore di accesso

Campi, metodi e classi hanno uno specificatore di accesso che può essere:

• private: visibile solo all'interno della classe• public: visibile al di fuori della classe • protected: visibile ai metodi della classe, delle

sue sottoclassi e delle classi dello stesso pacchetto

• nessuna specifica: visibilità di pacchetto

Ereditarietà

• E' un meccanismo che consente di costruire una nuova classe che estende le funzionalitàdi un'altra classe: si possono utilizzare metodi e variabili di istanza della classe superiore, senza accedere al codice dell'altra classe (riusabilità del codice).

• Ogni classe deriva direttamente o non direttamente dalla superclasse universale Object.

Metodi nella sottoclasse

Un metodo della sottoclasse può:

• essere un nuovo metodo non presente nella superclasse

• essere un metodo ereditato dalla superclasse• essere un metodo della superclasse

sovrascritto

nella sottoclasse

Cast: conversione forzata

• Tipi base:si può eseguire l’assegnazione di una variabile di tipo superiore ad una di tipo inferiore:

vartipoinf = (tipo inferiore)vartiposupl’assegnazione inversa è automatica.

• Riferimenti:si può eseguire l’assegnazione di un riferimento di un oggetto di tipo superclasse ad un riferimento di tipo sottoclasse:

tiposottoclasse = (sottoclasse)tiposuperclassel’assegnazione inversa è automatica.

17

Polimorfismo

• E' la proprietà in base alla quale il comportamento di un metodo può variare in relazione al tipodell'oggetto che viene effettivamente usato come parametro implicito del metodo.

• E' la JVM che decide durante l'esecuzione quale metodo deve essere scelto: selezione posticipata.

• Si parla di sovraccarico quando è il compilatore che decide quale metodo dovrà essere invocato: selezione anticipata.

Interfaccia

• Rappresenta una proprietà astratta.

• Possiede solo le firme dei metodi.

• I suoi metodi sono automaticamente pubblici.

• Una classe che realizza un’interfaccia deve implementare tutti i suoi metodi.

• Quando più classi realizzano l’interfaccia si ha polimorfismo, come nei TDA realizzati su array e lista concatenata.

Eccezioni

• Sono situazioni di possibili errori che possono essere esterne al problema o dipendere da un cattivo utilizzo dell'algoritmo.

• Le situazioni di errore devono essere previste e gestite.

• Le eccezioni sono oggetti: la classe dell’eccezione può estendere Exception (a controllo obbligatorio) o RuntimeException.

• Le eccezioni possono essere catturate e si eseguono istruzioni alternative, oppure lanciate ed interrompono l'esecuzione del programma.

Stack e Heap

• Rappresentano parti diverse della memoria: Stack(tipi base e riferimenti), Heap (oggetti, il garbagecollector mette in coda le aree liberate).

• Schema della disposizione degli indirizzi di memoria:indirizzi di memoria crescenti

lunghezza cresce verso → ← cresce verso

fissa la memoria alta la memoria bassa

Codice di

programma

Java RuntimeStack

Memoria libera

Heap

Algoritmi

Algoritmi

• Un algoritmo (deterministico) è un procedimento di soluzione costituito da un insieme di operazioni eseguibili tale che: esisteuna prima operazione, dopo ogni operazione èindividuata la successiva, esiste un'ultimaoperazione.

• La risoluzione avviene in due passi:• analisi, definizione del problema e progettazione• codifica, trasformazione in un linguaggio di

programmazione

18

Strutture di controllo

• Con le seguenti strutture di controllo si puòscrivere qualsiasi algoritmo:• sequenza• alternativa• ciclo

• Queste strutture sono caratterizzate dall'avereun unico punto di ingresso e un unico punto di uscita.

Iterazione e Ricorsione

• La scomposizione in sottoproblemi può essere:

• iterativa: • i sottoproblemi sono simili tra loro

• ricorsiva:• almeno uno dei sottoproblemi è simile a quello

iniziale, ma di dimensione inferiore

• In entrambe le scomposizioni si pone ilproblema della terminazione.

Divide et impera

• E' una strategia generale per impostarealgoritmi:• suddividere l'insieme dei dati in un numero

finito di sottoinsiemi sui quali si puòoperare ricorsivamente.

• Se la suddivisione in sottoinsiemi è bilanciata(sottoinsiemi di uguale dimensione) siottengono algoritmi efficienti.

Complessità

• L'efficienza di un algoritmo si valuta in base all'utilizzo che esso fa delle risorse di calcolo: memoria (spazio), CPU (tempo).

• Il tempo che un algoritmo impiega per risolvere un problema è una funzionecrescente della dimensione dei dati del problema. Se la dimensione varia, può esserestimato in maniera indipendente dallinguaggio, dal calcolatore e dalla scelta di dati, considerando il numero di operazionieseguite dall'algoritmo.

Complessità computazionale

• Indicata con n (numero naturale) la dimensione dei dati di ingresso, la funzioneF(n) che calcola il numero di operazioni vienechiamata complessità computazionale e utilizzata come stima della complessità ditempo.

• Si fanno delle semplificazioni individuandoquali operazioni dipendono da n.

Andamento asintotico dellacomplessità

• Se F(n) è crescente con n e se si ha che: F(n) → +∞ per n → +∞

• date le semplificazioni per la valutazione di F(n), sistima il comportamento della funzione per n→+∞utilizzando le seguenti notazioni:

• O (o-grande) limitazione superiore

• Ω (omega) limitazione inferiore

• Θ (theta) uguale andamento

19

Calcolo della complessità

• Nel calcolo della complessità si valuta ilcomportamento dell'algoritmo su particolariscelte di dati e si distinguono:

• un caso peggiore in cui l'algoritmo effettua ilmassimo numero di operazioni,

• un caso favorevole in cui l'algoritmo effettua ilminimo numero di operazioni,

• un caso medio in cui l'algoritmo effettua un numero medio di operazioni.

Calcolo della complessità

• Quando si scrive un algoritmo si deve sempredare una stima del caso peggiore e di quellofavorevole.

• Se la dimensione n dei dati non varia, la funzione di complessità è costante.

• Se n si mantiene limitato le considerazioniasintotiche non valgono.

Classi di complessità

• Le funzioni di complessità sono distinte in classi cherappresentano i diversi ordini di infinito

O(1) costantiO(log (log n))O(log n) logarimtoO(n) lineariO(n*log n)O(nk) polinomi k = 2, 3, ...

O(n!), O(nn), O(an) esponenziali (a ≠ 0,1)• Gli algoritmi con complessità esponenziale sono

impraticabili

Limiti inferiori e superiori

• Ogni algoritmo determina una limitazionesuperiore della complessità del problema.

• Cercare le limitazioni inferiori allacomplessità del problema vuol dire cercarealgoritmi più efficienti.

• Un algoritmo la cui complessità coincide con la limitazione inferiore è detto ottimo.

Complessità di algoritmifondamentali

• Calcolo dell‘n-esimo numero di Fibonacci

f0 = 1 f1 = 1 fn = fn-1 + fn-2 n>1

tempo spazio

definizione ricorsiva O(2n) O(n)iterazione con vettore O(n) O(n)iterazione con scalari O(n) O(1)moltiplicazione di matrici O(n) O(1)matrice quadrati (ricorsione) O(log2 n) O(1)approssimazione numerica O(1) O(1)


• Ricerca

caso peggiore caso favorevolelineare O(n) Ω(1)

binaria O(log2

n) Ω(1)(vettore ordinato)

hash O(1)* Ω(1)(array di interi) (in media)

(*dipende dalla dimensione dell’array e dalla funzione hash)

20


• Ordinamento

lineare Θ(n2 /2)

bubblesort O(n2 /2) Ω(n) (con varianti)

inserimento O(n2 /2) Ω(n)

quicksort O(n2 /2) O(n log2

n) anche medio

mergesort Θ(n log2

n) sempre

• Si può dimostrare che la limitazione inferiore dellacomplessità nel problema dell'ordinamento èΩ(nlog

2n): mergesort è ottimo nel caso medio e

peggiore, quicksort è ottimo nel caso medio.

Un problema divertente:il problema del torneo

• Questo problema interessò vari matematici tra i qualiLewis Carrol, più noto per aver scritto Alice nelpaese delle meraviglie; egli lo propose nella stagionetennistica inglese del 1883.

• In un torneo ad eliminazione diretta si affrontano n giocatori: chi perde viene subito eliminato. Si postulala transitività della bravura: se a perde con b e b perde con c si conclude che a perderebbecomunque con c.

Il problema del torneo

• Supposto n = 2k, i giocatori si affrontano a coppie in una serie di n/2 incontri; successivamente siaffrontano i vincitori in una nuova serie di n/4 incontri e così via fino ai quarti di finale (8 giocatori), alle semifinali (4 giocatori) e alla finale (2 giocatori) che deciderà il vincitore del torneo.

• Si può rappresentare il tabellone del torneo con un albero binario, completo, con 2k foglie e di profondità k.

Tabellone di un torneo rappresentato su un albero binario tra 24 = 16 giocatori

m è il vincitore


• Un albero binario Bkcompleto possiede 2k+1-1 nodi dei

quali 2k sono foglie (dimostrazione per induzione), pertanto i nodi interni sono 2k-1, vale a dire n-1.

• Gli incontri che vengono effettuati sono tanti quanti i nodi interni.

• Questo problema è quello di determinare il massimoin un insieme di n elementi, di cui sappiamo occorronon-1 confronti nei quali gli elementi non-massimirisultano perdenti nel confronto con il massimo.


• Il vincitore della finale è il vincitore del torneo.

Ma chi è il secondo?

• Se il “secondo in bravura” capita nella stessa metà del tabellone del primo, verrà eliminato prima di arrivarealla finale.

• Per non commettere ingiustizie bisogna far eseguire unsecondo torneo tra tutti coloro che hanno perdutoin un incontro diretto con il primo.

• Questi giocatori sono k = log2n, perché k sono gli

incontri disputati dal vincitore (k profonditàdell'albero).

21

Girone di consolazione per il torneop è il secondo dopo m Algoritmo del doppio torneo

• Eseguendo lo stesso algoritmo in k-1 (log2n -1)

incontri si determinerà il secondo.

• L'algoritmo del doppio torneo determina il valore del primo e del secondo eseguendo un numero di confronti uguale a

C(n) = n-1 + log2(n) -1 = n + log2(n) -2per n = 16 C(n) = 18

Algoritmo: primo e secondo

se a[1] > a[2]allora primo ← a[1]

secondo ← a[2]altrimenti primo ← a[2]

secondo ← a[1]//fineseper i da 3 a n

se primo < a[i]allora secondo ← primo

primo ← a[i]altrimenti se secondo < a[i]

allora secondo ← a[i]//finese

// finese//fineper

Algoritmo: primo e secondo

• L'algoritmo, che determina il valore del primo e del secondo, esegue invece nel caso peggiore (ilmassimo è in uno dei primi due posti, per cui si devesempre eseguire anche il secondo confronto) un numero di confronti uguale a

C(n) = n-1 + n-2 = 2n -3

per n = 16 C(n) = 46

• Nel caso favorevole (ordine crescente in un array) C(n) = n-1.

Algoritmo del doppio torneo

• Si può dimostrare che, nel problema delladeterminazione del primo e del secondo, illimite inferiore dei confronti nel casopeggiore è

Ω(n + log2(n) -2)

• Pertanto l'algoritmo del doppio torneo è ottimonel caso peggiore.

e per finire …

come fa Google a scegliere le pagine più

importanti?

22

Google: il problema del page ranking

• Due studenti dell’Università di Stanford, SergeyBrin e Larry Page, hanno inventato Google1998. Uno dei problemi era:

• Come ordinare le pagine presenti sul web in base alla loro importanza. Come definire l’importanza?

• Si possono scegliere varie possibilità: il numero di volte che una parola viene cercata, il numero di link che partono o arrivano a quella parola, il numero delle pagine importanti che partono o arrivano alla pagina.


• L’idea di Page e Brin era che una pagina ha una sua importanza che deriva dalle sue connessioni (e non dal suo contenuto).

• L’importanza di una pagina si trasferisce in parti uguali alle pagine che essa punta (una persona importante dà importanza alle persone che frequenta).

• L’importanza di una pagina è data dalla somma dell’importanza che viene dalle pagine che puntano ad essa (una persona è importante se frequenta molte persone importanti).


• Vediamo il modello matematico.• Supponiamo che siano n le pagine del web, e

definiamo la matrice seguente:h11 h12 h1nh21 h22 h2n

H = . . . . . .hn1 hn2 hnn

1 se c’è un link dalla pagina i alla pagina jcon hij =

0 altrimenti


• Esempio. Sia n = 4 e sia H la seguente matrice:

0 1 1 11 0 0 10 0 0 10 1 1 0

• Sommando i valori sulla riga i-esima si trova il numero di link che partono dalla pagina i: ri

• Sommando i valori sulla colonna j si trova il numero di pagine che puntano alla pagina i: cj.


• Indichiamo ora con xj l’importanza della pagina j; risulta:

xj = h1j x1/r1 + h2j x2/r2 + … + hnj xn/rn

per j = 1, 2, 3, …, n• Questo è un sistema lineare in n equazioni ed n

incognite. Le soluzioni x1, x2, …, xn forniscono il livello di importanza delle n pagine: page rank.

• L’equazione usata in Google è un po’ diversa, perché“pesata” con un parametro e le soluzioni che derivano sono tutti valori compresi tra 0 e 1.


• Le pagine attive odierne sono circa n = 8.5 ××××109

• Un sistema lineare con la regola di Cramer si risolve con un numero di operazioni dell’ordine di n!.

• Il metodo di eliminazione di Gauss risolve il sistema con circa 2n3/3 operazioni.

• Se usassimo quest’ultimo avremmo un numero di operazioni dell’ordine di:

2/3 ×××× (8.5 109)3 ~4.1 ×××× 1029

(miliardi di miliardi di miliardi) di operazioni aritmetiche.

23


• Il calcolatore più veloce al mondo èattualmente il Blue Gene dell’IBM.

• Ha una velocità di circa 360 teraflops:3.6××××1014 operazioni al secondo

(1tera=1000giga)• Per eseguire 4.1××××1029 operazioni

impiegherebbe più di 36 milioni di anni.• Come può essere se Page e Brin calcolano il

page rank ogni mese?• Anche un calcolatore mille volte più veloce

non risolverebbe il problema.


• Esistono metodi numerici (metodi che costruiscono soluzioni approssimate che possono essereimplementate sul calcolatore) con i quali si riesce a risolvere il sistema lineare, in tempi più brevi.

• Si parte da una ipotetica soluzione, si stima un errore e in maniera iterativa la si migliora; si costruisce cosìuna successione che converge indipendentemente dalla approssimazione iniziale:

xj (1) , xj (2) , xj (3) , …. xjcon un errore di approssimazione che risulta essere:e(k) ≤ λk dove λ (0 < λ < 1) è il modulo del

secondo autovalore più grande di una certa matrice.


• L’algoritmo è molto più efficiente: il numero di prodotti e di somme dipende dal numero di 0 della matrice H, che solitamente sono pochi (la matrice è sparsa); se ci fossero circa 50 elementi non nulli su una riga, l’algoritmo implementato sul calcolatore impiegherebbe pochi secondi per trovare la soluzione.

• Questo è il metodo adottato in Google.

Listalaurap/didattica/Fondamenti-2... · 2007. 11. 29. · 1 Lista Lista • La Lista è un TDA che...

Documents

Transcript of Listalaurap/didattica/Fondamenti-2... · 2007. 11. 29. · 1 Lista Lista • La Lista è un TDA che...