Lista Lista

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 L

L L

L = {insieme di tutte le liste}

A = {insieme degli atomi}

costante = λ : lista vuota

funzioni = {isEmpty, head, rest, build}

Lista

• Nel linguaggio LISP queste funzioni si chiamano:

isEmpty null

head car

rest cdr

build 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-lista costruisce la lista

llll

llll_'

a

llll

llll_'

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 ≠ λ

Lista

addToEnd(λ, 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.

Lista

public interface List{

boolean isEmpty();

Object getFirst(); //head Object removeFirst(); //rest void addFirst(Object x); //build ListIterator listIterator();

//metodo che restituisce un //iteratore su Lista }

Lista

public 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.util realizza 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.

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 Stack utilizzando 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);}

}

Stack con LinkedList

public Object top(){

return lista.getFirst();}

public void pop(){

Object ogg = lista.removeFirst();

}

public void makeEmpty(){

lista.makeEmpty();}

}//fine LinkedListStack

Stack con LinkedList

• 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.

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.

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 due

riferimenti: 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 LinkedList

public 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

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.

Lista di interi su lista concatenata

• In questa realizzazione, invece dell’iteratore e della classe che lo realizza, si definiscono due riferimenti, pos e prec di tipo ElemIntero analoghi 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).

Lista di interi su lista concatenata

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;

}

Lista di interi su lista concatenata

//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();

}

Lista di interi su lista concatenata

• 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 ordinecrescente 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 <= elem)){

prec = tmp;

tmp = tmp.next;

}

Lista ordinata di interi

//inserimento dell'elemento

ElemIntero nuovo = new ElemIntero();

nuovo.info = elem;

if(tmp==inizio){ // il primo nuovo.next = inizio;

inizio = nuovo;

}

else { //centrale o ultimo nuovo.next = prec.next;

prec.next = nuovo;

}//fine if }//fine insordine

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(n²) perché, eseguendo ad esempio l’unione, per ogni elemento di uno dei due si deve verificare che già non sia nell’altro.

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(log₂n).

• 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.

Riepilogo TDA 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 dichiara quali 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).

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 sequenziale

successivo i+1 a.next

dimensione massima sì* no

spazio info info e next

spostamento 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'ultimoelemento 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();

}

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 remove

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

(non ordinato) (in media)

array O(n) O(log₂n) O(n) (ordinato)

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

concatenata

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

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).

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 dati costruendo 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(log₂n) 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(n²) con array non ordinato

Java

Java

• Un algoritmo rappresenta l’astrazione della realtà.

• Un

linguaggio di programmazione

rappresenta 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

compilatore

che

traduce

il codice sorgente in un codice binario, detto

bytecode,

e di un

interprete, Java Virtual Machine, che elabora

ed esegue il bytecode.

• Il compilatore, durante la traduzione in codice

macchina, esegue una

analisi lessicale, sintattica

e semantica.

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 sola classe

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).

Deglinbit a disposizione, il primoè il bit del segno 0 positivi

1 negativi

I rimanenti n-1sono per il numero.

Tipo Intero

Si possono rappresentare 2^{n -1} valori diversi.

Costanti del tipo di dato: - 2^{n -1} e 2^{n -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 basee si prendono i resti.

• La rappresentazione dell'opposto è definita in complementoa 2

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

• 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 positivi 1 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.c₁c₂c₃.... ××××2^e

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 dato

minimo reale ≠ 0 float ~ 10 ^-38 massimo reale float ~ 10 ³⁸ 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 classeci permette di descrivere il nuovo concetto, con la definizione di campi e metodi.

• Per poter utilizzare il concetto si deve creare un oggettodel tipodella classe.

Classi e oggetti

• Un oggetto è una entità che può essere usata attraverso i metodidella classe.

• L'oggetto creato si chiama anche esemplare della classe oistanzadella 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 esemplareo 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 pubblica costituita dall'insieme dei metodi pubblici che permettono diutilizzarel'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 inizializzazione delle 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:

• appartieneall'oggetto

• è visibile ai metodidella sua classe

• viene inizializzata da un costruttore(default, esplicitamente)

• viene creata, "nasce", quando l'oggettoviene creato

• viene eliminata, "muore", quando l'oggetto viene eliminato, ossia nonè più referenziato(garbage collector)

Variabile locale

Una variabile locale:

• appartienea un metodo

• è visibile all'interno del metodo

• deveessere inizializzata esplicitamente

• viene creata, "nasce", quando viene eseguito l'enunciato in cui è definita

• viene eliminata, "muore", quando l'esecuzione del programma escedal blocco nel quale è stata definita(che può anche essere

il metodo che l'ha definita)

Variabile parametro

Una variabile parametro (formale):

• appartienea un metodo

• è visibile all'interno del metodo

• viene inizializzata all'atto della invocazionedel 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 eliminata quando 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’unicacopia).

• 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)vartiposup l’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)tiposuperclasse l’assegnazione inversa è automatica.

Polimorfismo

• E' la proprietà in base alla quale il comportamentodi un metodo può variare in relazione al tipo dell'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 sovraccaricoquando è il compilatoreche decidequale metodo dovrà essere invocato: selezione anticipata.

Interfaccia

• Rappresenta una proprietà astratta.

• Possiedesolole firmedei metodi.

• I suoi metodi sono automaticamente pubblici.

• Una classe che realizza un’interfaccia deve implementare tuttii 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 catturatee 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 garbage collector 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: esiste una

prima

operazione, dopo ogni operazione è individuata la

successiva, esiste un'ultima

operazione.

• La risoluzione avviene in due passi:

• analisi, definizione del problema e progettazione

• codifica, trasformazione in un linguaggio di programmazione

Strutture di controllo

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

•

sequenza

•

alternativa

•

ciclo

• Queste strutture sono caratterizzate dall'avere un 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 il

problema della

terminazione.

Divide et impera

• E' una strategia generale per impostare algoritmi:

• 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) si ottengono

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 funzione

crescente

della dimensione dei dati del problema. Se la dimensione varia, può essere

stimato

in maniera

indipendente

dal linguaggio, dal calcolatore e dalla scelta di dati, considerando il

numero di operazioni eseguite

dall'algoritmo.

Complessità computazionale

• Indicata con n (numero naturale) la dimensione dei dati di ingresso, la funzione F(n) che calcola il numero di operazioni viene chiamata

complessità computazionale

e utilizzata come stima della complessità di

tempo.

• Si fanno delle

semplificazioni

individuando quali operazioni dipendono da n.

Andamento asintotico della complessità

• Se F(n) è crescente con n e se si ha che:

F(n) → +∞ per n → +∞

• date le semplificazioni per la valutazione di F(n), si stimailcomportamentodella funzione per n→+∞

utilizzando le seguenti notazioni:

• O(o-grande) limitazione superiore

• Ω(omega) limitazione inferiore

• Θ(theta) ugualeandamento

Calcolo della complessità

• Nel calcolo della complessità si valuta il comportamento dell'algoritmo su particolari

scelte di dati

e si distinguono:

• un caso

peggiore

in cui l'algoritmo effettua il

massimo

numero di operazioni,

• un caso

favorevole

in cui l'algoritmo effettua il

minimo

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

sempre dare una

stima

del caso

peggiore

e di quello favorevole.

• Se la

dimensione n

dei dati non varia, la funzione di complessità è costante.

• Se n si mantiene limitato le considerazioni asintotiche non valgono.

Classi di complessità

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

O(1) costanti

O(log (log n))

O(log n) logarimto

O(n) lineari

O(n*log n)

O(n^k) polinomi k = 2, 3, ...

O(n!), O(nⁿ), O(aⁿ) esponenziali (a ≠ 0,1)

• Gli algoritmi con complessità esponenziale sono impraticabili

Limiti inferiori e superiori

• Ogni algoritmo determina una

limitazione superiore

della

complessità

del

problema.

• Cercare le

limitazioni inferiori

alla

complessità

del

problema

vuol dire cercare algoritmi più efficienti.

• Un algoritmo la cui complessità coincide con

la limitazione inferiore è detto

ottimo.

Complessità di algoritmi fondamentali

• Calcolo dell‘n-esimo numero di Fibonacci

f₀= 1 f₁= 1 f_n= f_n-1+ f_n-2 n>1

tempo spazio definizione ricorsiva O(2ⁿ) 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(log₂ n) O(1) approssimazione numerica O(1) O(1)

Complessità di algoritmi fondamentali

•

Ricerca

caso peggiore caso favorevole

lineare O(n) Ω(1)

binaria O(log₂ n) Ω(1)

(vettore ordinato)

hash O(1)* Ω(1)

(array di interi) (in media)

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

Complessità di algoritmi fondamentali

•

Ordinamento lineare Θ(n²/2)

bubblesort O(n²/2) Ω(n) (con varianti) inserimento O(n²/2) Ω(n)

quicksort O(n²/2) O(n log₂ n) anche medio mergesort Θ(n log₂ n) sempre

• Si può dimostrare che la limitazione inferiore della complessità nel problema dell'ordinamento è Ω(nlog₂n): mergesort è ottimo nel caso medio e peggiore, quicksort èottimonel caso medio.

Un problema divertente:

il problema del torneo

• Questo problema interessò vari matematici tra i quali Lewis Carrol, più noto per aver scritto Alice nel paese delle meraviglie; egli lo propose nella stagione tennistica inglese del 1883.

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

Il problema del torneo

• Supposto n = 2^k, i giocatori si affrontano a coppie in una serie di n/2 incontri; successivamente si affrontano 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 2^k foglie e di profondità k.

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

m è il vincitore

Il problema del torneo

• Un albero binario B_kcompleto possiede 2^k+1-1nodi dei quali 2^k sono foglie (dimostrazione per induzione), pertanto i nodi interni sono 2^k-1, vale a dire n-1.

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

• Questoproblemaè quello di determinare ilmassimo in un insieme di n elementi, di cui sappiamo occorrono n-1 confronti nei quali gli elementi non-massimi risultano perdenti nel confronto con il massimo.

Il problema del torneo

• Il vincitore della finale è il vincitore del torneo.

Ma chi è ilsecondo?

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

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

• Questi giocatori sono k = log₂n, perché k sono gli incontri disputati dal vincitore (k profondità dell'albero).

Girone di consolazione per il torneo

p è il secondo dopo m

Algoritmo del doppio torneo

• Eseguendo lo stesso algoritmo in k-1 (log₂n -1) incontri si determinerà il secondo.

• L'algoritmo del doppio torneodetermina il valore del primo e del secondo eseguendo un numero di confrontiuguale a

C(n) = n-1 + log₂(n) -1 = n + log₂(n) -2 per 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]

//finese peri da 3 a n

seprimo < a[i]

allorasecondo ← primo primo ← a[i]

altrimenti se secondo < a[i]

allorasecondo ← a[i]

//finese // finese

Algoritmo: primo e secondo

• L'algoritmo, che determina il valore del primo e del secondo, esegue invece nel caso peggiore (il massimo è in uno dei primi due posti, per cui si deve sempre 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

della determinazione del primo e del secondo, il

limite inferiore

dei confronti nel caso

peggiore

è

Ω(n + log₂(n) -2)

• Pertanto l'algoritmo del doppio torneo è

ottimo

nel

caso peggiore.

e per finire … come fa Google a scegliere le pagine più

importanti?

Google: il problema del page ranking

• Due studenti dell’Università di Stanford, Sergey Brin e Larry Page, hanno inventato Google 1998. 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.

Google: il problema del page ranking

• 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).

Google: il problema del page ranking

• Vediamo il modello matematico.

• Supponiamo che siano n le pagine del web, e definiamo la matrice seguente:

h₁₁ h₁₂ h_1n h₂₁ h₂₂ h_2n H = . . . . . .

h_n1 h_n2 h_nn

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

0 altrimenti

Google: il problema del page ranking

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

0 1 1 1 1 0 0 1 0 0 0 1 0 1 1 0

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

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

Google: il problema del page ranking

• Indichiamo ora con x_j l’importanza della pagina j;

risulta:

x_j= h_1jx₁/r₁ + h_2jx₂/r₂+ … + h_njx_n/r_n per j = 1, 2, 3, …, n

• Questo è un sistema lineare in n equazioni ed n incognite. Le soluzioni x₁, x₂, …, x_n 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.

Google: il problema del page ranking

• Le pagine attive odierne sono circa n = 8.5 ××××10⁹

• 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 2n³/3 operazioni.

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

2/3 ××××(8.5 10⁹)³ ~4.1 ××××10²⁹

(miliardi di miliardi di miliardi) di operazioni aritmetiche.

Google: il problema del page ranking

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

• Ha una velocità di circa 360 teraflops:

3.6× × × × 10

¹⁴

operazioni al secondo (1tera=1000giga)

• Per eseguire 4.1× × × × 10

²⁹

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.

Google: il problema del page ranking

• Esistono metodi numerici (metodi che costruiscono soluzioni approssimate che possono essere implementate 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:

x_j⁽¹⁾, x_j⁽²⁾ , x_j⁽³⁾, …. x_j

con un errore di approssimazione che risulta essere:

e^(k) ≤ λ^k dove λ (0 < λ < 1) è il modulo del secondo autovalore più grande di una certa matrice.

Google: il problema del page ranking

• 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.