Algoritmi e strutture dati/Appunti/2003-2004

Tratto dal Dsy

Appunti Videolezioni Prof.Mauro Torelli (#42 lezioni)

Le indicazioni dei paragrafi sono dal testo: Cormen [1] Altre indicazioni disponibili alla pagine:

• [2] e [3] (integra Cormen)
• oppure alle dispense di Bertoni/Goldwurm alla pagina [4].

LEZIONE 01di42 del 30/Settembre/2003

Introduzione al corso, modalita’ esame, iscrizione SIFA. DADS: Dictionary of Algorithms and Data Structures (on-line) http://www.nist.gov/dads/ Herb Wilf: book on line http://www.cis.upenn.edu/~wilf/ Esempi introduttivi (potenze di 2, logaritmi e “somma di Gauss” sono indispensabili nella valutazione della complessità degli algoritmi). La compressione di testi e l'algoritmo di Huffman (§17.3). La legge di Zipf (http://linkage.rockefeller.edu/wli/zipf/) Codici e in particolare codici prefissi (appunti: "Codici e linguaggi"). http://homes.dsi.unimi.it/~torelli/Codici e linguaggi.pdf

Primi 40:00 Min: Introduzione al corso, modalita’ esame, iscrizione SIFA.

Esiste un algoritmo per vincere al lotto? Ovvio che si. Basta giocare tutte le combinazioni possibili (combinazioni sono finite) visto che nessuno ce lo vieta ma è necessario che il costo non sia elevato. Infatti di un algoritmo si deve guardare efficienza e costo (per portare a termine algoritmo) e quindi è inutile giocare tutte le possibili combinazioni poiché avrei una perdita rilevante. Questa cosa è valida non solo per l’algoritmo per vincere al lotto ma si applica a tutti gli algoritmi. Un’altra caratteristica di un algoritmo e quella di risolvere tutti i problemi di una determinata classe (anche ampia) e tipicamente di terminare con output. Ad esempio un algoritmo di ordinamento che ordina numeri (chiavi, record) deve funzionare per tutti i numeri di un determinato intervallo (esempio con numeri interi o reali). Per esempio: riesco a piegare un foglio di carta A4 10 volte? No perché dopo 210 piegamenti ho 1024 strati. Se il foglio avesse una superficie di 1024 cm2 alla fine dei dieci piegamenti avrei un foglio di un cm (lo riduco di 1024 volte).

Ho un problema di dimensione n (foglio di carta di dimensione n o 1024 cm). Dopo quanti passi lo riduco alla dimensione 1 (cioè un cm2)? Dopo log2(n).

Esempio (i.e.contare le pecore): ho un problema di dimensione n e ammettiamo che per ridurlo di una dimensione (quindi per portarlo alla dimensione n-1) devo fare n operazioni. Se poi voglio ridurlo ancora di una dimensione farò n-1 operazioni e lo porto a dimensione n-2. Per portarlo alla dimensione 1 farò circa n*n=n2 operazioni. Quando è a dimensione 1 si risolve da sé visto che non c'è nulla da ridurre.

Se n>1 farò più o meno operazioni di n*n? Ne faccio circa n*n e ciò si dimostra con la “somma di Gauss”. "Somma di Gauss" (nome dato da prof.) Somma dei numeri da 1 a n (Somma di Progressione aritmetica di ragione 1). Vedi esempio dei 100 numeri sommati su due righe. La somma fa sempre 100 ed è stata scritta 101 volte. Quindi (101 x 100) / 2 . L'ordine di grandezza è Θ(n2). (§3.1 e 3.2). Che corrisponde al coefficiente binomiale = [n+1/2]. (§6.1 c’e’ anche Fattoriale). Dimostrazione grafica: costruisco un rettangolo di dimensione n(n+1) cominciando a disegnare il primo quadretto e sopra gli altri e infine ci aggiungo di fianco una figura uguale rovesciata di modo tale da ottenere un rettangolo di dimensione n(n+1). La somma dei primi n numeri è uguale alla metà di questo rettangolo ovvero n(n+1) / 2 .

Per risolvere i problemi posso quindi avere algoritmi banali (anche costosi), algoritmi (anche) efficienti ed anche non ci sono soluzioni algoritmiche (vedi Indecidibilita’, problema “Collatz” 3x+1, macchina di Turing?)

Codici e Linguaggi. Introduzione al Codice&Algoritmo di Huffman (§17.3)

Allegato: 1_Codici e linguaggi.pdf

Abbiamo un file da 2.0 MB e vogliamo trasferirlo su un dischetto che contiene al massimo 1.44 MB: cosa facciamo? Usiamo un programma di compressione dei dati e vogliamo sapere come funziona questo programma, le idee su cui è basato l’algoritmo di compressione ed i costi, tempi associati. Innanzitutto dobbiamo sapere cos’è un codice. Ad esempio tutti conosciamo il codice ASCII con cui rappresento 28=256 caratteri oppure il codice UNICODE con cui rappresento 216=1024*26=65536 caratteri. \ Entrambi i codici hanno lunghezza fissa. Uno 8 l'altro 16. Ad esempio con la codifica a lunghezza fissa se devo rappresentare 6 caratteri quanti bit uso? 22= 4 < 6 quindi 2 non va bene. 23 = 8 > 6 va bene. Normalmente in un testo italiano ci sono molte più A che Z e quindi il trucco è usare codifiche brevi per caratteri frequenti e codifiche più lunghe per caratteri poco frequenti.

Ecco dunque che l'algoritmo di Huffman realizza uno tra i codici ottimi per la compressione. Attenzione a codificare i caratteri: se ad esempio dovessi codificarli in questo modo a=0, b=00, c=01, d=1, e=10, f=11 la cosa non funzionerebbe. Infatti per una stringa come 0001 la decodifica non sarebbe unica quindi ci sarebbero ambiguità e di conseguenza il codice non andrebbe bene!

In generale se possiamo scrivere per un insieme che una parola ad=c allora non abbiamo un codice. Al contrario si può chiamare codice un qualunque insieme di parole per il quale non valga alcuna equazione. Tranne ovviamente identità banali come ad=ad che sono ammesse.

Cominciamo con il dire che il codice dell'algoritmo di Huffman è un codice prefisso. Ma cos'è un prefisso? Informalmente il prefisso di una parola è l'inizio della parola ovvero una parola è prefisso di un'altra se l'altra parola comincia con la parola più corta. Esempio: La parola X è un prefisso della parola Y se Y si può scrivere come X seguito da Z cioe’ Y=X+Z.

Un codice prefisso è un codice libero da prefissi cioè un codice in cui nessuna parola è prefisso di un'altra. Questa condizione assicura che l'insieme è un codice.

Dimostrazione per assurdo. Se prendo due parole dello stesso insieme xy...z=uv...w l'uguaglianza vale se x=u e y=v e z=w. Ma questo è il caso banale in cui le due parole sono uguali. Se invece fosse x più corta di u allora x è prefisso di u per verificare l'uguaglianza, ovvero non è un codice perché una parola è prefisso dell'altra!

La condizione di codice libero da prefissi è sufficiente ma non necessaria per garantire di avere un codice. E' sufficiente ma non necessaria infatti se ho suffissi basta che non abbia prefissi. Posso prendere codici liberi da suffissi e che hanno prefissi. Ad esempio {0, 01, 11}. Se un codice è libero da suffissi allora è un codice.

Codice che ha sia suffissi che prefissi. C = {00, 001, 011, 01, 11} da "Algebraic Combinatorics on Words".

LEZIONE 02di42 del 02/Ottobre/2003

Alberi binari e codici di Huffman (§5.5.3 e 17.3). Il programma per il codice di Huffman (§17.3).Introduzione Algoritmi Greedy. Code con priorità (§7.5).

Primi 7:00 MINUTI - Generalità sul corso e raccolta informazioni.

I codici di Huffman costituiscono una tecnica diffusa ed efficiente per la compressione dei dati. Nei casi in cui ha senso usare i codici di Huffman le riduzioni saranno da circa il 20% al 90%. Ci sono casi in cui i codici di Huffman non riducono niente? Certo, quando tutti i caratteri hanno la stessa frequenza! Quindi li dobbiamo usare quanto le differenze fra i caratteri sono effettivamente rilevanti. Il codice ottimo è quello che ci garantisce la massima compressione possibile e che ci permette di rappresentare il testo con il minor numero possibile di bit. A questo punto si esamina la figura a pagina 321 del libro e si fanno alcune osservazioni: una di queste è che gli alberi con codifica ottima hanno nodi con 2 figli o con 0 figli, infatti è vero che se un nodo avesse solo una foglia allora potremmo spostare in su la foglia risparmiando 1 bit. Ottimo significa che ottengo la MAX compressione possibile, ovvero minimo utilizzo di bit <> da “abbastanza buono”

Gli alberi che si chiamano binari hanno al più due figli per ogni nodo ( ‘0’ oppure ‘1’ oppure ‘2’).(Vedi Albero Genealogico). I codici di Huffman vengo creati a partire da questi alberi binari. Un albero che ha un solo figlio in corrispondenza di un nodo non può essere ottimo. Basta infatti spostare in su di un nodo i figli per ottenere una codifica più breve. Se è OTTIMO deve avere due figli per ogni nodo. Gli alberi con codifica ottima hanno sempre DUE figli per ogni nodo.

Albero pieno (alberi completi): un albero che ha tutte le foglie su un determinato livello. Albero full-binary (pienamente binario): è un albero che ha due figli per ogni nodo oppure 0 ovvero sono foglie. I codici di Huffman servono solo quando le differenze di frequenza (distribuzione) tra caratteri sono rilevanti. Nella pratica quando succede? Ad esempio in un testo le differenze di caratteri saranno rilevanti? Se prendiamo in considerazione un’immagine, come sorgente, ci saranno differenze significative per esempio di raggruppamenti di 8 bit? Pensiamo a chiaro vs. scuro, non sono distribuiti uniformemente.

Nei linguaggi naturali la distribuzione di parole e caratteri come e’? Se pensiamo alla Legge di Zipf: riguarda la distribuzione delle parole nei linguaggi naturali: se la prima parola + frequente ha frequenza pari a F allora la seconda parola + frequente ha frequenza F/2, la terza parola + frequente ha frequenza F/3 e la parola n-esima + frequente ha frequenza F/n. Qui intesa come Frequenza Assoluta ovvero numero di occorrenza, numero di volte che la parola occorre. Anche se non e’ chiarito il perche’. (Citazione del Libro di Knuth) Quindi con differenze di frequenze molto alte e’ giustifcato l’utilizzo di algoritmi di compressione come Huffman.

L’algoritmo di Huffman è un algoritmo Greedy. Cos’è Greedy(Ingordo/Miope)? E’ un algoritmo che cerca di risolvere i problemi in cui si cerca una soluzione ottima, soluzioni di ottimizzazione che non sono generalmente uniche. Come chiameremo la classe dei problemi in cui si cerca la soluzione ottima? Ovvero, per quale classe di problemi su usano gli algoritmi Greedy? Non per ordinamento e ricerca, ma per i problemi dove a senso parlare di soluzioni ottime e quindi problemi di ottimizzazione. Es: Codifica di un testo. Nei problemi di ordinamento la soluzione è unica cioè quella ‘ordinata’ mentre nei problemi in cui si cerca la soluzione migliore ci possono essere più soluzioni ‘ottime’. Vedi esempio sul libro ed esempio ‘studente frettoloso’ sugli allegati I codici prefissi (ovvero dovremmo dire codici liberi da prefissi) sono dei codici che semplificano la codifica e la decodifica. Si può dimostrare (ma noi non lo faremo) che la compressione ottima ottenibile con un codice per i caratteri può essere sempre ottenuta con un codice prefisso. Il libro cita la decodifica ‘furba’ ovvero quella che percorre l’albero a sx=bit 0 e dx=bit1 percorrendo al max n=profondita’ albero per decodificare carattere vs. uso di una tabella che nel caso peggiore i.e.unicode a 16bit e’ 64k!

Alberi binari di ricerca: alberi in cui le ‘chiavi’ piccole si mettono a sinistra di ogni nodo(sottoalbero) rispetto a tutti i nodi e le ‘chiavi’ grandi a destra di ogni sottoalbero rispetto a tutti i nodi. Le chiavi sono i valori che noi cerchiamo.

Gli alberi della figura 17.4 del codice di Huffman non sono alberi binari di ricerca in quanto confrontano sempre 0 vs.1. Sono dei particolari alberi binari di ricerca si chiamano TRIES (alberi digitali di ricerca) (che non sono proprio di ricerca nel senso vero e proprio poiché gli elementi sono solo due e quindi con 0 va sempre a sinistra e con 1 a destra ed è ovvio che tutti gli elementi a sinistra di un nodo considerato non sono mai tutti minori di esso). La foglia e’ riconosciuta quando non ci sono figli, implementata con puntatori NIL, ovvero non ci sono puntatori.

Continuiamo a vedere la costruzione del codice di Huffman tramite alberi pienamente-binari (ogni nodo ha 0 or 2 figli). Un codice ottimo è sempre rappresentato con un albero pienamente-binario (Condizione necessaria ma non sufficiente). Infatti il primo albero della figura 17.4 pur essendo pienamente binario non rappresenta un codice ottimo. Basta spostare il nodo figlio al nodo padre per ottenere un codice migliore di quello precedente in cui si risparmia un bit, dimostrando così che non era ottimo.

Poiche’ restringiamo l’attenzione agli alberi pienamenti binari quindi alberi per codice prefisso ottimo, se C è l'insieme delle nostre parole ci saranno C foglie e C-1 nodi interni.(Cap.5 Insiemi). Se X sono le foglie perché ci sono X-1 nodi interni? Dimostrare x esercizio. Corrispondenza tra un albero e un codice prefisso ovvero l‘albero che costruisco da un codice prefisso. Si dimostra ‘visivamente’ che il codice è prefisso guardando l’albero e visto che le parole si associano alle foglie e non c’è nessuna parola che si ferma ai nodi interni allora il codice è libero da prefissi. Il fatto di associare le parole alle foglie di un albero garantisce che il codice sia prefisso.

Perché il codice di Huffman è un codice prefisso? Basta guardare l’albero dato che le parole finiscono con le foglie e non c’è nessuna parola associata ai nodi interni e quindi per forza è prefisso. Poiche’ usiamo un codice binario, ma potremmo usare un codice ternario oppure n-ario.

Come si fa a calcolare il numero di bit richiesti alla fine per codificare il file? pag. 321 (§17.3) E’ una sommatoria in cui vengono sommati i bit che codificano una parola (quindi la profondità dell’albero, distanza della foglia dalla radice) moltiplicati per la loro occorrenza/frequenza: ScÎC (frequenza di c)*(distanza di c da radice) = # bit.

Finito il paragrafo vediamo finalmente come costruire un Codice di Huffman; ci sono almeno 2 due approcci: 1.leggersi il codice/programma sul testo oppure 2.guardarsi la fig.17.5 con i passaggi seguenti: 2.0 Idea associare codici lunghi a caratteri ‘-‘ frequenti, e codici corti a caratteri ‘+’ frequenti 2.1 Partiamo da albero con due caratteri con frequenza minore e proseguiamo con approccio bottom-up 2.2 Per creare un albero pienamente binario ottimo ordiniamo i caratteri in ordine di frequenza crescente. 2.3 Abbiniamo i caratteri con frequenza minore. E sommiamo frequenze. 2.4 Riordiniamo in ordine crescente e raggruppiamo i due con frequenza più bassa. 2.5 Così via fino a quando non finiamo di costruire l'albero.

Prima di partire con l'algoritmo di Huffman è ovvio che dobbiamo avere caratteri di input, la rappresentazione caratteri e loro frequenza. Dopo di che dobbiamo usare struttura adeguata con minimo tempo per eseguire le funzioni di cui sopra. Procedura Huffman, lavora su struttura dati dei caratteri C inseriti in una ‘coda’ (che contiene le frequenze dei caratteri) da cui sia facile estrarre l’elemento con il valore minimo di frequenza. L'algoritmo è ‘Greedy/ingordo/avido’ di frequenze basse cioe’ va sempre a prendere i due elementi con le frequenze più basse, procede ‘localmente’ poiche’ ‘miope’ poi itera. Esecuzione codice di Huffman: partiamo dai caratteri poco frequenti che sono più lontani dalla radice visto che quelli poco frequenti li voglio rappresentare con una codifica più lunga. Estraggo le due frequenze minime e le metto come figlie. Il nodo padre è la somma delle due frequenze e lo inserisco nella coda. Iteriamo questo procedimento n-1 volte e restituiamo un puntatore a tutta la struttura (ultima istruzione return nel codice dell’algoritmo che restituisce un puntatore alla radice). Non c’è il bisogno di tenere ordinata la coda rispetto alle frequenze dei caratteri visto che vado a prendere sempre le frequenze più basse, ovvero devo solo prendere i due valori minimi senza tenerla continuamente ordinata. Qual è il costo dell'algoritmo di Huffman se tengo ordinata la coda? Rispondere per esercizio L'alternativa è come facciamo a mettere in piedi una struttura di dati che ogni volta fornisce il minimo con poca spesa e costa meno che tenere ordinata una coda? RISPOSTA: E’ UN ALBERO BINARIO DI RICERCA? Come sopra?

LEZIONE 03di42 del 3/Ottobre/2003

Formalizzazione: Complessità e correttezza dell’algoritmo di Huffman (§17.3). Introduzione teoria dei linguaggi, linguaggi formali e operazioni su linguaggi (appunti: "Codici e linguaggi" §1.3).

Riassunto lezioni precedenti: - Codice Huffman come esempio di Algoritmo Greedy - Porta a compressioni e risparmi del 20-90% dipendendo dalla frequenza dei caratteri - Eseguo algoritmo ‘unendo’ char con freq+bassa, salendo nell’albero costruito con approccio bottom-up - Il codice costruito e’ codice-prefisso perche’ associato alle foglie dell’albero - Algoritmo di Huffman risale al 1952 [Teoria dei Codici e’ molto antica (i.e. codice di Cesare)]

Introduciamo Teoria dei Linguaggi per utilizzarla di seguito: - S e’ l’insieme dei simboli ovvero alfabeto - Operazione e’ Il prodotto di concatenazione (o giustapposizione), indicato con ‘·’, è un’operazione che concatena due o più simboli dell’alfabeto S a formare quella che chiameremo parola sull’alfabeto S. Operazione associativa ma NON commutativa.

Indichiamo con |P| la lunghezza della parola cioe’ il numero di simboli che la compongono (simbolo di cardinalita’ degli insiemi), dove i simboli sono ripetuti e l’ordine e’ importante. Lg(P) = lunghezza parola. Nei testi anglosassoni, attenzione a non confonderla con il logaritmo.

L’analogia dice che log[a*b]=loga + logb, inoltre il log e’ la lunghezza del numero vedi log binario e log decimale. La rappresentazione binaria di un numero intero ovvero la sua lunghezza è uguale a (base) ëlog2(n)û+1 oppure (tetto) élog2(n+1)ù .

Un linguaggio e’ un insieme di parole e posso estendere l’operazione di concatenzione dalle parole ai linguaggi. Il prodotto di due linguaggi è l'insieme delle parole del primo linguaggio moltiplicate per le parole del secondo linguaggio. Infatti se prendo L1={0,01} e L2={0,10} il linguaggio che ottengo con il prodotto dei due è: L1·L2={00,010,0110}. Ovvero concatenazione delle stringhe di parole con eliminazione delle ridondanze ed in ordine. Non vale commutativa. Non e’ prodotto cartesiano.

Dove ε (epsilon) e’ il simbolo della parola vuota che non appartiene all’alfabeto S altrimenti sarebbe un simbolo con cardinalita’ |1|.

Formalizzando la definizione di codice prefisso (cioe’ libero da prefissi): e’ un linguaggio ovvero un insieme C (codice) tale che se X e Y appartengono al linguaggio allora X ≠ YZ in cui Z ≠ ε (niente).

Cos’è S2(Alfabeto per alfabeto)? S · S è l'insieme delle parole ottenute concatenando un simbolo Î S con un simbolo Î S quindi è l’insieme delle parole di 2 simboli di lunghezza due. Sn=insieme parole lunghezza n; dove S0 = ε e l’insieme di tutte le parole e’ S* = S+ U S0 è la chiusura di Kleene, chiusura dell’Alfabeto. S* e S+ sono linguaggi infiniti appunto perché non poniamo limiti sulla lunghezza delle parole. Mentre Sn=insieme parole lunghezza n e’ finito se l’alfabeto dei simboli e’ finito.

Ai teorici piace chiamare S* il Monoide libero generato da S. Il monoide è una struttura algebrica in cui vi è un insieme di elementi, un'operazione associativa e una identità. L'operazione è il prodotto di concatenazione e l'identità è il prodotto con la parola vuota. (S*,·,ε) è il monoide non commutativo. E' anche libero perché non ci sono vincoli (i vincoli sono le equazioni che non vogliamo che ci siano), quindi consideriamo tutte le parole senza ‘uguaglianze’ tra parole ‘diverse’.

Con un algoritmo (Greedy) quanto costa vedere in un linguaggio di ‘n’ parole se una parola è prefisso di un'altra? Devo confrontare coppie di parole (in tempo costante) e quindi occorre un numero di confronti dell’ordine di n2. Posso risparmiare guardando se una parola è più corta/lunga dell'altra e vedere se quella corta e’ prefisso e quindi controllo solo quelle, anche se il lavoro che faccio di comporta sempre come ½ n2.

Dal minuto 52 al 55 – Pausa nella lezione

Dimostrazione di Correttezza dell'algoritmo di Huffman (Huffman e’ Codice Ottimo) (pag. 323) (Poco convincente x Torelli). La dimostrazione della correttezza dell’algoritmo di Huffman NON viene chiesta quindi chi vuole può saltare a 1:19:00.

La dimostrazione si articola in due lemmi. Lemma/Passo 1 Huffman comincia con l’abbinare i caratteri con le frequenze più piccole e queste due foglie poi saranno figlie di un unico nodo padre. Esiste sempre una soluzione ottima di un problema di codifica in cui due caratteri con le frequenze minori sono figlie dello stesso padre in un albero; prima assunzione. Passo 1 - Devo spostare le parole con le frequenze più basse alla profondità massima e farle diventare figlie dello stesso padre. Con questo procedimento ottengo un albero di costo minore poiché gli altri caratteri hanno una codifica con meno bit e hanno una frequenza più alta.

Lemma/Passo 2 Passo 2 – Prendo un albero che rappresenta codice prefisso ottimo. Se io tolgo le due foglie e metto un supercarattere (tolgo due caratteri es: A+B=C all'albero togliendo A e B). Quindi i nodi diventano n - 1 e ho un nuovo carattere; l'albero risultante rimane ottimo continuando a iterare il procedimento dell'albero di Huffman.

Finale (specie di dimostrazione per induzione a rovescio, poco soddisfacente x Torelli) Siccome vale la prima proprietà e siccome iterando il procedimento l'albero rimane ottimo allora alla fine ho l'albero ottimo. Per induzione le proprietà valgono sempre e quindi se parto da un albero ottimo otterrò sempre un albero ottimo. Dimostrazione ‘grafica’: Costo del codice (anche dell’albero) di Huffman e’ quindi uguale alla somma dei nodi interni; che in un albero di Huffman rappresenta il numero di bit che servono per la codifica. Vedi fig.17.4 perche’ il 100K nella root e’ il numero di primi bit che ci sono nella nostra codifica, a cui aggiungere 45K secondi bit+55K secondi bit+25K terzi bit etc etc

Ora, cosa vuol dire complessità di un algoritmo? Vuol dire quante risorse richiede l'algoritmo sia in tempo o in spazio ed eventualmente in altre caratteristiche (per esempio risorse hw).

Quanto costa costruire albero di Huffman? 1. Prima dobbiamo ordinare l’input per frequenza. Ordino gli elementi che uso per costruire l'albero di Huffman in tempo nlog2(n) (Per esempio usando QuickSort). 2. Poi unisco due elementi e mi trovo un nuovo elemento da inserire. Il costo di inserimento nel caso peggiore=n visto che dovrò fare n confronti per inserire l'elemento (nel caso fosse in fondo) e nel caso medio comunque ne faccio la metà n/2. 3. Osservando bene il nostro array (posso posizionarmi nel punto desiderato) (o lista che devo scorrere) ogni volta che fondo insieme due elementi si accorcia di uno quindi a parte il passo iniziale che dovrò ordinare n elementi al passo successivo me ne rimangono n-1, a quello dopo n-2 e così via. Questa cosa ci riporta alla somma di Gauss, tuttavia la complessità rimane nell'ordine di n2 per quanto riguarda i confronti. 4. Quindi complessita’ e’ quadratica se facessi cosi.

Possiamo vedere anche il caso in cui non si tengono ordinati gli elementi. Dobbiamo avere una struttura dati che ci fornisce in tempo minore i due elementi con la frequenza minima (approccio tipicamente Greedy che non si cura degli altri elementi). Vedremo che si fa con una struttura heap. Con l'heap si tira fuori l'elemento minimo e rimetto le cose ‘ok’ (ovvero ripristino le condizione di heap) per l’elemento successivo in tempo log2(n).

Se con Huffman faccio ‘n’ operazioni avrò un costo di nlog2(n). che e’ assolutamente migliore di n2.

Vedremo algoritmi che non tengono conto dell'ordinamento degli elementi (Heap).

LEZIONE 04di42 del 7/Ottobre/2003

Nuova dimostrazione della correttezza dell’algoritmo di Huffman, introduzione heapsort. Grafi e alberi come linguaggi: http://homes.dsi.unimi.it/~torelli/2grafi.zip. Un albero libero è un grafo connesso aciclico (appunti: "Grafi e alberi.pdf" §2.1).

Dimostrazione alternativa dell'algoritmo di Huffman. Interessante x introdurre nuovi concetti.

Dunque, data una lista L di interi positivi (lista perche’ posso avere possibili ripetizioni) chiameremo catena di addizioni generata da L una lista o sequenza, per esempio non decrescente, di interi positivi comprendente la lista L e tale che ogni elemento non in L sia la somma di due elementi precedenti nella sequenza. Con la condizione non decrescente mi garantisce quanto sopra. Gli esempi dell’insieme generatore L gli elementi sottolineati.Ad esempio: {5, 9, 12, 13, 16, 45}. [Frequenze degli esempi di Huffman precedente]

Proseguendo dall’insieme iniziale poi ottengo: {5, 9, 12, 13, 14, 16, 45} dove 14 è ottenuto da 9+5. Ogni numero delle ‘foglie’ viene sommato una volta sola con un altro. Alla fine ottengo la sequenza di numeri più piccoli visto che ho sempre sommato i due numeri con valore minore tra tutti; posizionati nei nodi interni dell’albero.

Non vi è solo una ‘liana’ (catene dei valori) minima! Sebbene siano tutte ottime non ve ne è solo una. Quella di Huffman è indubbiamente una ottima. Gli alberi pienamente-binari corrispondono a delle catene di concatenazione particolari in cui ogni elemento (tranne radice) viene usato in una e una sola somma. Se vedessi il processo come una sorta di eleminazione dopo quanti passi mi rimane un solo elemento? Dopo n-1 visto che ogni volta tolgo un elemento [cioe’ elimino 2 e aggiungo 1]. Il che dimostra che con ‘n’ foglie ho ‘n-1’ nodi interni. [vale anche per alberi binari non necessariamente pienamente binari].

Gli alberi pienamente binari che hanno gli elementi di L nelle foglie e le somme dei nodi figli in ciascun nodo interno corrispondono a particolari catene tali che ogni elemento della catena (tranne l’ultimo) viene usato come addendo in una e una sola somma. In altre parole, possiamo pensare di eliminare due elementi di L sostituendoli con la loro somma, poi sostituire altri due elementi (inclusi i nuovi) con la loro somma, e così via.

Dopo quanti passi resta un solo elemento (di valore pari, ovviamente, alla somma degli elementi di L)? Si tratta in sostanza di un torneo a eliminazione un po’ insolito, poiché il numero di partite necessarie per vincere può variare da giocatore a giocatore: ogni partita elimina un giocatore e se i giocatori sono n, il vincitore si avrà dopo n – 1 partite. Sappiamo dunque quanto sono lunghe queste catene e anche quanti sono i nodi interni in un albero pienamente binario: se vi sono n foglie, vi sono n – 1 nodi interni!

La ‘liana’ di Huffman (somma delle due frequenze piu’ piccole, iterativamente applicato) è quella in cui la somma dei primi k elementi è minima, per ogni k. Dove, se ci sono n foglie in un albero pienamente binario ci sono n-1 nodi interni visto che elimino due elementi ogni volta facendole corrispondere al padre. Non e’ pero’ detto che sia l’unica ‘liana minima’, potrebbero essercene altre anche se non ‘migliori’ della liana di Huffman, che e’ certamente minima e ‘percorre’ gli elementi + piccoli in ordine.

Completiamo le premesse, comprendenti definizione di albero binario e sue proprieta’, ma anche vediamo come si possono generare i codici di Huffman; operazioni interessanti sono estrazione minino ed inserimento nuovo valore dato dalla somma dei minimi. Ora dipende dal livello di astrazione da cui partiamo, potremmo solo usare una procedura ‘black box’ che ci ritorna i valori desiderati; se invece vogliamo sapere come fare allora possiamo definire una struttura di dati astratta che ci permette di estrarre il minimo che definiamo come coda con priorita’ (§7.5).

Coda che viene implementata con l’algoritmo heapSort, heapsort (ottime prestazioni, anche se nella pratica ci mette il doppio di quicksort) e’ l’unico algoritmo che con mergeSort ordina n elementi in tempo di nlog(n) anche nei casi peggiori. Quindi complessita’ e’ (nlogn). Migliore è quickSort che nella pratica impiega (nlogn) ma nel caso peggiore richiede un tempo nell'ordine di n2.

Una coda con priorità è una struttura di dati per gestire un insieme di S elementi a cui è associato un valore chiamato chiave/indice (campo priorità). Nell'algoritmo di Huffman le priorità sono le frequenze basse. Se fossero processi con priorita’, allora sarebbe ‘privilegiato’ il processo con priorita’ massima. Ha senso parlare di coda con priorità per dati di cui abbia senso parlare di criterio di priorità e su cui siano definite le operazioni. Quindi una struttura di dati astratta e’ definita dai dati e dalle operazioni che possiamo fare su questi dati. Astraendo, le operazioni si definiscono dicendo cosa devono fare e non come lo devono fare. (diciamo la semantica ma non la sintassi).

Esempio di coda con priorita’ allora le operazioni definite saranno: - Insert(S, x) inserisce l’elemento x nell’insieme S. - Maximum(S) restituisce l’elemento con chiave più grande. - Extract-Max(S) rimuove e restituisce l’elemento di S con chiave più grande. Heap definiamo le operazioni: Extract-Min, Extract-Max, Minimum, Maximum.

Grafi & Alberi (§5.x).

Prima di vedere queste operazioni occupiamoci (colmiamo alcune lacune) di strutture di dati come grafi ed alberi, poi torneremo ad occuparci di heap. [Torelli utilizza teoria dei linguaggi per spiegare i Grafi, sul libro cap.5 e cap.23]. Cominciamo con il definire alcune nozioni aggiuntive, 3 nuovi concetti: 1. La parola x è un fattore (prefisso/suffisso/sottoparola) di y se la parola y è scritta come y=uxv. Un fattore di y è quindi una sottoparola contigua (di y). 2. Un’altra nozione è quella di trasposizione (o rovesciamento di una parola). Si può usare la ricorsione per definire la trasposizione. Dare una definizione ricorsiva significa usare il concetto stesso da definire per definire il concetto. Precisamente la parola vuota: εT=ε invece (xa)T=axT dove x e’ la parola ed a e’ simbolo. 3. La terza nozione è quella di parola semplice: se non contiene ripetizioni quindi tutti i suoi simboli sono distinti/unici.

Concetti utili per definire un grafo orientato: è una coppia (V,E) dove V è un insieme di vertici (S alfabeto usato fin’ora) ed E (archi) è una parola di lunghezza 2 su V. Ovvero E e’ contenuto in V2. Un arco orientato è semplice se non contiene cappi/loop: infatti una parola in quel caso avrebbe simboli uguali e non sarebbe semplice. Cos'è un cammino (quanti passi) di lunghezza K in un grafo orientato? E' una parola di lunghezza K+1 in cui ogni fattore di lunghezza 2 è un arco. Un cammino di lunghezza 0 viene detto cammino improprio mentre un cammino è semplice se la parola corrispondente è semplice [Un cammino proprio/’vero’ è un cammino di lunghezza almeno 1]. Un ciclo in un grafo orientato è un cammino proprio chiuso ossia un cammino di lunghezza positiva che inizia e termina con lo stesso vertice che chiameremo vertice di chiusura: il ciclo è semplice se tolto il primo vertice o l'ultimo il cammino restante è semplice (i.e cammino 454, se tolgo inizio o fine, oppure 22).

Lemma dell'eliminazione dei cicli (inventato da Torelli): se esiste un cammino tra due vertici a e b ne esiste anche uno semplice. Basta eliminare i cicli presenti nel cammino lasciando soltanto il vertice di chiusura del ciclo rimosso. L’osservazione che se a è un vertice e xa e ay sono cammini, allora anche xay è un cammino (mentre in generale xy o xaay non lo sono!) ci garantisce che la rimozione dei cicli fornisce ancora un cammino.

Nei grafi NON orientati se c'e' un arco ci deve essere anche il suo trasposto (nessun senso unico). In un grafo non orientato fare attenzione alla definizione di ciclo. Dobbiamo coinvolgere almeno 3 vertici/nodi/lati per avere un ciclo (senza "avanti e indietro"). In un grafo non orientato axa è un ciclo sse xa è un cammino semplice di lunghezza almeno 2. Per esempio, 1251 è un ciclo (a = 1, x = 25). Il grado per grafi NON orientati di un vertice A è il numero di lati incidenti su A (sia uscenti sia entranti). Se il grado è 0 (non compare nell’elenco dei lati) il vertice è isolato. Se in un grafo tutti i vertici hanno grado 2 allora è necessariamente un ciclo. Un sottografo è un grafo che come vertici ha un sottoinsieme di V e un sottoinsieme di E. Se per ogni coppia di vertici a e b esiste un cammino allora il grafo è connesso. Un albero libero (senza radice ovvero non orientato) è un grafo non orientato aciclico e connesso e quindi non vi è nemmeno l’ordinamento dei rami. Quando scegliamo una radice (albero radicato) il grado è dato dal numero dei figli. Teorema: In un albero c'è sempre uno e un solo cammino semplice tra due nodi distinti qualsiasi. Si dimostra per assurdo supponendo che ci siano due cammini distinti tra due nodi. (La dimostrazione è a pag. 86 del libro oppure sulla documentazione di Torelli).

LEZIONE 05di42 del 09/Ottobre/2003

Alberi radicati e linguaggi ereditari (appunti: “Grafi e alberi” §2.2). Alberi binari, k-ari e ordinati (appunti: "Grafi e alberi" §2.3).Grado e profondita’.

Primi 24:00 minuti. Riassunto lezione precedente (per poi collegare grafi&alberi ad heap): - Nozione di fattore (prefisso/suffisso) y=uxv tramite prodotto di concatenazione - Nozione di trasposizione/rovesciamente, εT=ε e (xa)T = axT - Nozione di parola semplice ovvero senza ripetizioni (vedi inoltre nozione parola vuota) - Quanto sopra per definire un Grafo Orientato come coppia (V,E), cappio, grafi semplici - Cammini di lunghezza k=parola di lunghezza k+1 composto da successione di archi di lunghezza 2 - Un ciclo e’ un cammino proprio chiuso (cammino contiene almeno un arco) - Lemma eliminazione dei cicli (da Torelli) - Grafo non orientato, grado, grafo connesso se si puo’ andare da ogni punto a ogni punto - Albero libero, albero radicato

Dimostrazione teorema 5.2 del testo: in un albero c’è sempre uno e un solo cammino semplice tra due nodi distinti qualsiasi (naturalmente ignorando il cammino trasposto). (tratto da “Grafi e alberi come linguaggi”, dimostrare che prima o poi viene fuori un ciclo). “In un albero, poiché è un grafo connesso, esiste un cammino tra ogni coppia di nodi. Tuttavia, a priori potrebbero esistere più cammini semplici tra due nodi. Il teorema 5.2 del testo, invece, ci dice che di fatto in un albero c’è sempre uno e un solo cammino semplice tra due nodi distinti qualsiasi (naturalmente ignorando il cammino trasposto). Dimostriamo questo teorema “a modo nostro” (ossia senza figure), ma la dimostrazione è simile a quella del libro a pagina 86, solo che ci siamo attenuti alla nostra convenzione su come indicare parole e simboli singoli. Supponiamo, per assurdo, che tra due nodi a e b ci siano due cammini semplici distinti: axb e ayb. Ma allora anche (ayb)T=byTa è un cammino e quindi axbyTa è un cammino chiuso su a. Se xbyTa è semplice, allora ha anche lunghezza almeno 2, perché x e y non possono essere entrambi vuoti (devono essere distinti!) e quindi il cammino chiuso è un ciclo, contro l’ipotesi che il grafo sia un albero, e dunque aciclico. Se, viceversa, x e y hanno vertici in comune, possiamo usare il lemma dell’eliminazione dei cicli, e l’unico caso in cui restiamo con un cammino semplice di lunghezza 1 (che non va bene!) è quello in cui x e y iniziano con lo stesso nodo c: se x=cu e y=cv, allora xbyTa = cubvTca e l’eliminazione del ciclo cubvTc dà ca. Ma in questo caso possiamo considerare i cammini da c a b, escludendo a, ed è chiaro che questo caso non può ripresentarsi all’infinito, dato che i cammini si accorciano: alla fine, o otteniamo un ciclo o due cammini coincidenti, cioè, in entrambi i casi, una contraddizione. ”

Usiamo i concetti sovraesposti per passare agli alberi radicati. Basta scegliere un nodo come radice (in un grafo non orientato aciclico e connesso). Avendo scelto la radice adesso possiamo considerare tutti e soli i cammini che partono dalla radice e non considerare gli altri cammini. Possiamo determinare i nodi secondo una gerarchia ad esempio la distanza/profondita’ dalla radice. Gli alberi radicati vengono chiamati anche orientati poiché implicitamente vi è un ordinamento dei nodi dalla radici alle foglie o viceversa. (Le foglie in un albero libero sarebbero i vertici di grado 1 cioè quelle che hanno solo un lato incidente, anche se a quel punto anche una radice e’ foglia e viceversa).

Poiche’ vi e’ un solo cammino semplice da radice a nodo (per definizione), per identificare un nodo lo si può chiamare con il cammino che raggiunge il nodo partendo dalla radice. Quindi possiamo definire un albero radicato come il linguaggio dei cammini semplici partenti dalla radice. La radice di un albero è l'unico cammino con lunghezza zero. I cammini di lunghezza 1 sono i figli della radice. Piu’ in generale diremo figlio di x ogni nodo b cui corrisponda una parola xb. Simmetricamente chiameremo padre di b ogni nodo x se a b è associata la parola xb.

Il numero di figli di un nodo è il grado del nodo (e quindi il grado di un nodo di un albero radicato è sempre inferiore di uno rispetto al grado di un vertice in un grafo, tranne per la radice visto che ha due figli e grado due oppure un figlio e grado uno). Un nodo senza figli e’ esterno (vs. interno).

Che caratteristiche deve avere un linguaggio per rappresentare un albero radicato? Ogni prefisso deve appartenere al linguaggio perché rappresenta un nodo e ogni simbolo finale deve essere diverso da ogni altro simbolo finale.

Basta questo per avere un linguaggio che rappresenta un albero? No, ad esempio {1,2} anche se soddisfa entrambe le caratteristiche non è un albero radicato poiché non sappiamo di chi è figlio 2. I simboli sono tutti diversi e per i prefissi manca la parola vuota. La parola vuota è prefisso di ogni parola ma non appartiene al linguaggio che abbiamo preso ad esempio. Ma allora dobbiamo identificare la radice di un albero non con un nodo qualsiasi ma con la parola vuota e quindi non dobbiamo preoccuparci che ci siano due radici come in questo caso.

Un linguaggio L in cui se xy appartiene ad L allora anche x appartiene ad L si chiama linguaggio ereditario. La ragione di questa denominazione è evidente: l’appartenenza al linguaggio è ereditata da ogni prefisso. Notiamo che, se L è un linguaggio ereditario, o L= ∅, oppure εÎL, parola vuota e’ quindi prefisso di tutte le parole in tutti i linguaggi.

Un albero radicato è un linguaggio ereditario L in cui se xa e xb sono due parole distinte appartenenti a L allora a ≠ b. Ad esempio {ε,1,2,12} è un linguaggio ereditario ma non è un albero visto che 2 e 12 terminano con lo stesso simbolo.

Due alberi sono isomorfi se hanno la iso=stessa morf=forma anche se le etichette dei vertici sono differenti. Completiamo la terminologia osservando che un nodo con cammino x è un antenato di un nodo y sse x è un prefisso di y: in questo caso y è un discendente di x. La profondità di un nodo x è la lunghezza della parola x e l'altezza dell'albero è la lunghezza della parola più lunga. La radice ha profondità 0. L’altezza dell’albero è la lunghezza della parola più lunga.Dove l’altezza dell’albero e’ la massima profondita’.

I lati in un albero sono uno in meno dei nodi e ogni lato richiede 2 simboli e ogni vertice un simbolo. Perché anche se l'albero è libero posso pensarlo come radicato e parlo di padri e figli. Ogni nodo dell'albero ha un padre tranne la radice quindi tutti i figli sono collegati al padre da un lato tranne la radice. In pratica, possiamo talvolta usare un unico array che in posizione i riporta il padre di i (come ci si può muovere, in questo caso, nell’albero? Come si distingue la radice?). Si veda anche il § 11.4 nel testo, ora prematuro.

Un albero binario è un linguaggio ereditario sull'alfabeto binario {0,1}. La radice è la parola vuota ε e denotiamo il figlio sinistro della parola x con la parola x0 e il figlio destro della parola x con x1. Ovvero a sinistra ci metto gli 0 e a destra 1. Il linguaggio associato all'albero è la codifica del linguaggio.

Alberi lessicografici o TRIES. Sono strutture dati utilizzati per la ricerca di informazioni in quanto l'etichetta del nodo può essere la chiave di ricerca e il percorso nell'albero è determinato dalla chiave stessa.

LEZIONE 06di42 del 10/Ottobre/2003

Code a priorità (§7.5) e loro realizzazione con heap (§7.1). Alberi binari completi a sinistra e heap ("Gli heap Ita.pdf" §3.1 testo §7.1)http://homes.dsi.unimi.it/~torelli/3heap.zip Rappresentazione con array: dove sono padri e figli? La procedura Heapify (testo §7.2).

Primi 26:00 minuti. Riassunto lezione precedente: - Albero e’ grafo connesso senza cicli quindi se e’ un albero esiste uno ed un solo cammino tra due lati - Percorrere albero da radice a figli vs. da figli a radice - Albero radicato, grado, figli e padri, genealogia, nodo esterno vs. nodo interno - Linguaggi ereditari - Isomorfismo, esiste algoritmo per capire se due alberi sono isomorfi? Si perche’ sono strutture finite anche se non ci sono algoritmi con complessita’ polinomiale (sono ‘ancora’ nn oppure n!). - Alberi binari, alberi tries (retreival) di cui una versione sofisticata sono gli alberi Patricia

Che cosa succede se l’alfabeto è composto non da 2 ma da k > 2 simboli? Ogni nodo potrà avere fino a k figli, e il linguaggio ereditario rappresenterà allora un albero k-ario. Anche se ci saranno 3 alberi ternari con 2 nodi: {ε,0}radice+zero, {ε,1}radice+uno e {ε,2}radice+due, quindi la posizione fa differenza.

Albero ordinato ristretto a due figli cioè un albero in cui ogni nodo ha al più due figli e vi è la distinzione tra il primo e il secondo figlio. Se c'è un solo figlio non è ne destro ne sinistro. Gli alberi della figura 5.6 non sono isomorfi.

Alberi ordinati generici senza limitazione nel # di figli: il numero di figli di ciascun nodo non è noto a priori. Per far si che un albero di questo tipo sia ordinato dobbiamo avere un alfabeto infinito ad esempio l’insieme dei numeri naturali N.

Cos’è un albero binario completo? Un albero binario in cui tutti i nodi hanno due figli e tutte le foglie sono alla stessa profondità e ha 2h-1 nodi interni se ci sono h livelli. Quindi non posso avere un albero completo con 10 nodi. Perché? Perché o ne ha 7 o 15 e quindi per averne 10 tolgo gli ultimi 5. Questo albero si chiama albero binario completo a sinistra: abcs. Per passare dalla rappresentazione decimale in binaria nell’esempio dell’albero {1,2,3,4,5,6,10}, metto un 1 davanti alla rappresentazione binaria che abbiamo. Aggiungere uno 0 in fondo invece equivale a raddoppiare la cifra binaria.

Gli Heap:

Usiamo l’approccio ai linguaggi per definire heap. L' Heap binario è una struttura di dati in cui un albero binario completo viene rappresentato in un'array. Attenzione alla relazione tra Heap e Alberi. L'Heap puo’ essere rappresentato con un array che è una struttura unidimensionale oppure con l'albero che e’ bidimensionale.

L'albero ha padri e figli e quindi devo sapere dove metto padri e figli nell'array. Quando sposto da albero ad arrary se ho un nodo ‘padre’ in posizione ‘i’ dove stanno i suoi figli? Nell'array in posizione ‘2i’ il figlio sx e ‘2i+1’ il figlio dx. Il padre sta in posizione (parte intera di posizione figlio/2) = ëfiglio/2û .Inoltre L'albero binario deve essere completo a sinistra.

In un heap ordinato in ordine decrescente il valore del nodo è al più il valore del padre (valore figlio £ valore padre). Chiavi uguali non creano nessun problema. Sse ci interessa avere l'elemento massimo nella radice -> abbiamo implementato l'heap per poter estrarre il massimo (oppure minimo) da una coda con priorità. Con Huffman realizziamo l'heap al contrario (ovvero nella radice c’e’ il valore minimo, infatti estraiamo gli elementi con le frequenze minime). In questo caso il valore di un nodo deve essere almeno il valore del genitore.

Quanto mi costa estrarre l'elemento minimo dall'array (ove il primo elemento è quello minimo)? Tempo costante perché lo trovo nella prima posizione dell'array. Costante se lo devo solo leggere, perche’ se lo estraggo devo ripristinare le condizioni di heap. In questo caso non faccio scorrere l’array (perderei le proprieta’ di heap) ma ‘riempio’ il buco con il campo di valore piu’ piccolo, che nel caso di array ordinato decrescentemente, e’ l’ultimo campo dell’array.

Procedura per estrarre il massimo: toglie il massimo e ripristina le proprietà dell'heap. Quando ho tolto il primo elemento che è il massimo al suo posto ci inserisco l'ultimo elemento dell'heap e poi diminuisco di 1 la lunghezza dell'heap e richiamo heapify.

Quali sono le precondizioni che consentono di utilizzare la procedura heapify? Figlio destro e sinistro di (i) devono essere radici di sottoalberi che rappresentano heap e quindi mantengono le proprieta’, l'unico elemento fuori posto può essere l'elemento (i) a cui si applica heapify. Si scambia ovviamente con il valore più grande tra i figli visto che se dopo tiro su il più piccolo dovrò rifare la procedura.

LEZIONE 07di42 del 14/Ottobre/2003

Proprieta’ heap e costruzione heap. Alberi binari completi a sx.

Primi 13:00 minuti. Riassunto lezione precedente: - Alberi binari=numerati dalla radice con 1 e poi procedendo a sx=0 e dx=1 - Albero binario completo ‘almeno’ da/a sx (con ‘buchi’ a dx) - Insieme interi positivi rappresenta albero binario se: Possiamo ottenere una nuova definizione di albero binario, in termini di interi positivi: un albero binario è un insieme B di numeri interi positivi tali che, se yÎB e y > 1, allora anche ëy/2û ÎB. - Heap: proprieta’ ordinamento parziale

Quanti alberi diversi con ‘n’ nodi? Quanti ‘abcs’ (alberi binari completi sinistra) con ‘n’ nodi ci sono? Ovviamente uno, ovvero c’e’ un solo modo di rapprensentare ‘n’ nodi in un albero completo da 1 a ‘n’. Inoltre gli ‘abcs’ stanno in un’array senza creare ‘buchi’, ritrovando padri e figli.

Quindi, un heap è un abcs il cui contenuto deve soddisfare la proprietà di ordinamento parziale: la chiave contenuta in un nodo non deve superare quella del padre (si veda a pagina 134 del testo). In altre parole, in un heap le chiavi sono ordinate (in ordine debolmente decrescente: ci possono essere chiavi uguali) lungo ciascun ramo, andando dalla radice alle foglie. L'ordine è solo parziale: non vale, in generale, alcuna relazione d'ordine tra chiavi in rami diversi.

In un heap le chiavi sono ordinate lungo ogni percorso quindi avremo un ordine debolmente decrescente andando dalla radice alla foglia. Il minimo in un heap è in una foglia ma non si sa in quale. Le foglie sono almeno metà del totale dei nodi. In un heap sta nella seconda metà dell'array in un punto qualsiasi.

Quante sono le foglie in un albero binario completo a sinistra con n nodi? O in un heap con n nodi? Le foglie sono almeno metà del totale dei nodi.

Quando si chiede di costruire i codici di Huffman si usano gli heap facendo una coda con priorità in cui la priorità sono le frequenza più basse. Il massimo numero di passi che deve fare Heapify è log(n).

Quanto è alto un (heap) abcs (albero binario completo sx) con n nodi? L’altezza è data dalla lunghezza della parola più lunga, che rappresenta la parola ‘n’. Ovvero quanti bit occorrono per rappresentare la parola ‘n’ in binario, in generale richiede base di ëlog nû+1. Quindi l’altezza e’ base di ëlog nû. Vedi esercizio 7.1.2.

Quante foglie ha un abcs con n nodi? In un abcs, un nodo è una foglia se non ha figlio sinistro (e quindi neanche destro, dato che dev'essere completo a sinistra). Perciò, se un nodo corrisponde al numero y mentre 2y (che dovrebbe corrispondere al figlio sinistro) è maggiore di n, allora y è una foglia; ma 2y>n implica y>n/2, perciò i nodi numerati da 1 fino a ën/2û hanno figli quindi sono interni, i restanti én/2ù nodi sono invece foglie, quindi foglie sono ≥ numero di nodi interni (uguali oppure 1 in +)

Altezza di un nodo: L’altezza di un nodo in un albero [nozione complementare a quella di profondità (distanza da radice) già vista al §2.3] è definita a pagina 134 del testo: l’altezza a(x) di un nodo x è semplicemente la lunghezza del più lungo cammino fino a un suo discendente: a(x):=max{|y|:xyÎaL}. Negli abcs, se x ha altezza h, x0h deve appartenere a L ed essere una foglia, perché altrimenti l’altezza di x sarebbe maggiore di h. La parola x0h rappresenta, in binario, un multiplo di 2h, qualunque sia x, ma naturalmente, cambiando x, cambia anche il multiplo. Ora, quanti multipli di 2h ci possono essere, al più, tra le én/2ù foglie dell’abcs considerato? Al più é(n/2)/2hù, ossia én/2h+1ù, come specificato nell’esercizio 7.3-3.

L’heap si costruisce in tempo lineare. Ma come si costruisce un Heap: la heapify ci consente di ripristinare la proprietà degli heap (il padre deve essere maggiore o uguale ai figli, facendo scendere elemento + piccolo; i sottoalberi devono gia’ essere heap).

Per inserire (aggiungere) un elemento uso la procedura heapinsert che inserisce la chiave n+1 nell’heap di n elementi (heap contenuto in un array). Devo incrementare la lunghezza dell'heap e assegnare al nuovo elemento la posizione ultima dell'heap, posizione ‘nuova’. Poi controllo via via coi padri e se sono minori scambio la chiave con il suo padre (padre deve essere + grande). Facendo salire la chiave (heapfy fa scendere partendo da root poi sottoroot,etc), al massimo mi arriva alla radice.

E' più facile far salire o far scendere la chiave? Salire visto che faccio un solo confronto ogni volta con il padre, per scendere devo decidere se scendere sx o dx.

Il modo più ovvio per costruire un heap sarebbe quello di posizionare l'elemento inserito nell'ultima posizione. Funziona ma quanto costa? Al massimo percorre tutta altezza albero e quindi log(n) operazioni per ogni elemento; se inseriamo n elementi quindi il costo è nlog(n). Non e’ sempre cosi perche’ all’inizio l’heap non contiene n elementi, quindi posso non considerare ‘n’ costante ma cresce durante gli inserimenti. Posso riconsiderare la somma di Gauss in cui il risultato non è effettivamente nxn ma è di quello stesso ordine di grandezza. Se considerassimo solo gli inserimenti da n/2 in poi (le cose ‘piccole’ non sarebbero considerate), anche in questo caso la crescita sarebbe nlog(n). Quindi costruire heap in modalita’ inserimento incrementale costa sempre nlog(n).

Heapfy puo’ essere usata per costruire heap da array (convertendolo) con approccio bottom-up, l’idea e’ che da n/2 in poi siano foglie (ovvero heap di 1 solo elemento) presupponendo che da n/2 a sx siano ‘nodi’ ed applicando heapfy (ipotizzo che da n/2 in poi – a dx - siano gia’ heap di 1 solo elemento).

(BUILDHEAP) In questo modo Possiamo quindi costruire un heap (da array non ordinato) in tempo lineare (minore di nlog(n)) ovvero proporzionale a n. Costruire un heap con buildheap costa O(n) che e’ minore di heapinset con nlog(n).

Dimostrazione non semplice, vedi note. Per costruire un heap con n chiavi bastano in ogni caso meno di n spostamenti di chiavi e precisamente al più n meno il numero di 1 che compaiono nella rappresentazione binaria.

La massima potenza di 2 che divide n! è n meno il numero di 1 che compaiono nella rappresentazione binaria di n (da Adrien-Marie Legendre). i.e. 10! e’ divisibile per 28 ma non per 29. Vedi §3.3 negli allegati di Torelli. La conclusione generale è dunque che la costruzione di un heap può avvenire in tempo lineare.

LEZIONE 08di42 del 16/Ottobre/2003

Riepilogo sugli heap. Introduzione Heapsort (§ 7.4). Algoritmo di Fibonacci. Origine termine “algoritmo” (nel testo la prefazione italiana ed eventualmente il riferimento Knuth [121]) e caratteristiche fondamentali degli algoritmi (testo §1.1, dispense Goldwurm §1.1). Il problema della terminazione. Esempio: frazioni egizie http://www.ics.uci.edu/~eppstein/numth/egypt/ e problema di Collatz (3x + 1) http://www.cecm.sfu.ca/organics/papers/lagarias/.

Primi 15:00 minuti. Riassunto lezione precedente: - Cap.7 libro. Heapsort. Struttura di dati Heap per gestire code con priorita’ e riferimento a Huffman. - Heap binari. ABCS. Figlio sx in 2i, figlio dx in 2i+1 - Altezza di un nodo. Altezza albero/heap e’ base(parte intera) di log(n)

Operazioni fondamentali su heap: - Heapify procedura che mantiene la proprietà degli heap e impiega tempo di O(logn). - Build Heap è la procedura che serve per costruire l’heap da un’array non ordinato e impiega O(n). - Heap sort è la procedura che ordina l’array in loco e ci impiega O(nlogn). - Extract-max/min, insert sono le procedure che permettono all’heap di essere usato come una coda a priorità Ordinare in loco vuol dire che c’è bisogno di una quantità di memoria definita e costante per spostare gli elementi e non di una memoria che cresce al crescere degli elementi. In questa memoria pensiamo di trasferire parte dei dati. In loco non trasferisce più di una quantità costante di dati di input. Ma l’algoritmo potrebbe trasferire una quantità non costante di dati che gli servono non di input. In quel caso ordina il loco? Il libro dice Si ma il prof. non sembra molto d’accordo! Poiche’ per implementare devo sapere a priori se allocare una memoria ‘costante’ oppure ‘dinamica e crescente’ al crescere di ‘n’. Anche per quicksort prof. dice che non ordina in loco sebbene il libro dica il contrario, xche’ ha bisogno di uno stack dinamico per esecuzione. Se inseriamo un elemento alla volta nell’heap non ci vuole tempo lineare ma nlog(n). Serve tempo lineare se facciamo un inserimento bottom-up. Il tempo di esecuzione di heapfy e’ Θ(1) (vuol dire tempo costante ovvero proporzionale ad 1)+ tempo di esecuzione nel sottoalbero. Un sottoalbero di un abcs contiene al più (2/3)n nodi (ovviamente se sx ha (2/3)n l'altro sottoalbero dx ha (1/3)n nodi). BuildHeap: Per ordinare un heap usando heapify utilizzo una procedura che parte da n/2 che è la posizione del primo nodo che ha almeno un figlio e quindi la prima posizione in cui ci può essere una chiave fuori posto. Tempo di esecuzione di heapfy su un nodo su altezza h e’ O(h) e l’altezza massima e’ log(n) e quindi complessita’ e’ O(logn). Dopo heap vediamo ora heapsort: A heap-size(A) viene assegnato length(A), la prima operazione da fare è build-heap. Quando abbiamo costruito l’heap l’elemento più grande è immagazzinato nella radice cioè nella posizione 1 dell’array A (quello di partenza) e noi lo mettiamo nella posizione n dell’array finale. Se un algoritmo riesce a ordinare anche nel caso peggiore in nlog2(n) è asintoticamente ottimo perché fa il meglio possibile sugli algoritmi basati sui confronti. (nota: Quicksort non è facile da implementare!) Mostrare che il tempo di esecuzione di HeapSort è nlog(n). E’ sbagliato! Noi eseguiamo n volte la procedura heapify che nel caso peggiore richiede log (n). La heapify lavora in tempo costante quando trova ogni chiave a posto. L'heapsort richiede nlog(n) perché ripetiamo n volte la procedura heapify che richiede tempo log(n). Quando gli elementi sono uguali (ovvero le chiavi sono già ordinate o sono proprio uguali) richiede tempo n cioè costante! Terminiamo qui le code con priorita’.

Torniamo all’inizio del libro: Etimologia del termine algoritmo e frazioni egizie. Il termine algoritmo che significa procedimento di calcolo è una versione moderna del termine latino medioevale algorismus che deriva dal nome del matematico uzbeco Mohammed ibn-Musa al-Khowarismi vissuto nel IX d.C. secolo e famoso per aver scritto un trattato di algebra. Cominciamo con il dire che per un algoritmo deve esserci un input e un output (l'input può essere omesso, vedi Knuth). Per un algoritmo ci deve essere almeno un output. Un algoritmo è una procedura che produce almeno un output e deve essere finito (e terminare anche in tempo ragionevole) e come spiegato nella prima lezione deve avere costi accettabili (vedi esempio gioco lotto). Frazioni egizie. Papiro Ahmes. Gli egizi erano soliti scrivere le frazioni come somma di frazioni in cui i numeratori erano sempre 1 e i denominatori erano tutti diversi. Algoritmo di Fibonacci (Algoritmo Greedy) dalle/sulle frazioni egizie. Scegli il denominatore più piccolo rispetto alla frazione che devi rappresentare e vai avanti così fino a quando non rimane più nulla mettendo sempre 1 al numeratore. Ma questa cosa non si sa se termina. Sylvester nel 1880 ha dimostrato che questa è una procedura che termina sempre con n termini. Non ottimo anche se Greedy.

LEZIONE 09di42 del 17/Ottobre/2003

Cenni correttezza algoritmi. Classe P ed NP. Test di Primalita’ (testo §33.8). Ordinamento per inserimento, ordinamento in loco, pseudocodice (testo §1.1). Insertion Sort (§1.x). Random Access Machine and Random Access Store Program (§1.x).

Primi 21:00 minuti. Riassunto lezione precedente: - Etimologia e connotazioni termine algoritmo.Non necessariamente solo problemi computazionali. - Secondo Knuth caratteristiche di algoritmo: regole con sequenza operazioni finita (algoritmo termina) per risolvere problemi. Passi definiti con precisione, ed effettivamente eseguibili. - Esempio 10n+1 e’ primo? (non da risposta sempre) Abbiamo necessita’ di caratteristiche di generalita’ almeno entro un certo intervallo, deve dare soluzione.

Algoritmi ordinamento sono comuni e riconosciuti come utili (i.e. ordinamento # matricole, file, numeri). Teorizziamo il problema e prendiamo una successione finita di ‘n’ numeri interi in ingresso e in uscita vogliamo una permutazione di questi numeri in ordine diverso, ad esempio in ordine crescente. Nel caso in cui ci fossero numeri uguali non dovrebbero esserci problemi per quanto riguarda l’ordinamento ma il primo tra i due numeri uguali deve rispettare la posizione ‘iniziale’ poiché se così non facesse l’algoritmo verrebbe chiamato instabile vs stabile ovvero l’ordine di chiavi uguali in input viene mantenuto in ouput.

Algoritmo di decisione: decidere se una cosa è vera o falsa quindi dà in output 1=vero oppure 0=falso.

Un'istanza (esempio) di un problema è l'input che si dà al problema da risolvere.Quando un algoritmo è corretto? Quando risolve ogni istanza che gli viene data.

Quando un algoritmo fa meno fatica (meno tempo) ad ordinare un file già ordinato si dice che ha un comportamento naturale. Tutti gli algoritmi di ordinamento basati su confronti hanno un comportamento NON-naturale, tranne l’insertion sort che ha un comportamento naturale (e’ piu’ veloce se il file e’ gia’ ordinato).

Secondo il libro, un algoritmo si dice corretto se per ogni istanza di ingresso si ferma con l'output corretto. Un algoritmo scorretto potrebbe non fermarsi per qualche istanza di input o potrebbe fermarsi con una risposta diversa da quella attesa. Classifichiamo gli algoritmi secondo complessita’ strutturale vs complessita’ ‘senza aggettivo’.

La classe p è la classe dei problemi che si risolvono con una complessita’ in tempo e/o spazio che cresce come un polinomio (tempo polinomiale) rispetto all’input ‘n’. La classe p=np(non deterministici) detti algoritmi di verifica (ovvero posso verificare in tempo polinomiale dato sia input che output)?No.

Algoritmi scorretti possono essere talvolta utili se il loro ritmo di errore può essere controllato. Per dimostrarlo prendiamo Test di Primalità (di Miller e Rabin 33.8 del libro) e lo vediamo come ‘Black Box’ (lo usiamo senza ‘guardarci’ dentro).

Supponiamo di avere una procedura BB(n, x) che applicata a un intero n e a un intero x più piccolo di n (1<x<n) restituisce 1 se n è primo e 0 se n è composto (prodotto di 2 altri numeri diversi da uno e se stesso).

Quindi se n è composto ¾ dei numeri tra 1 ed n fanno si che la procedura BB dia come risultato 0 avvertendoci che il numero è composto ma ¼ dei valori di x tra 1 ed n ingannano BB e danno come risultato 1.

Quando è primo BB non fallisce mai e invece quando è composto sbaglia una volta su 4, quindi non e’ corretta...Vediamo quando e’ comunque utile: supponiamo che BB ci abbia restituito 1 cioè BB(n, x) per 10 valori di x scelti a caso allora qual è la probabilità che n non sia primo ovvero che la procedura abbia sbagliato?

La probabilità che si ripeta per 10 volte è (¼)10 cioè una probabilità su un milione e quindi la possibilità che ci sia stato un errore è parecchio bassa! Nel capitolo 33.8 viene fatta nel caso più semplice cioè 1 volta su 2. E anche in questo caso va bene lo stesso!

Insertion sort

l libro dice che l'insertion sort è un algoritmo utile per ordinare un piccolo numero di elementi. (NON dite questa frase all'esame xche’ TUTTI gli algoritmi vanno bene con insiemi piccoli di elementi). L’insertion sort non va bene solo quando abbiamo un piccolo numero di elementi in input infatti basta che siano un po’ ordinati che insertion sort lavora in tempo lineare. E' un algoritmo particolarmente semplice e se avete problemi piccoli si potrebbe usare questo.

Gli elementi sono ordinati in loco ovvero ordino i dati di input tenendoli dentro l'array che mi viene data in input. Si tiene conto della memoria ausiliaria che mi serve per spostare gli elementi. Nell'insertion sort mi serve solo una variabile ausiliaria visto che sposto un elemento alla volta e nella variabile ausiliaria ci sta l'elemento che confronto con tutti gli altri.

Confronto l'elemento di posto J con i precedenti a cominciare da quello più vicino a sinistra. Non da sinistra a destra però! Altrimenti nel caso avessi un’array ordinato farei molti confronti in più. La parte ordinata è quindi sempre quella in testa. Caso peggiore array ordinato al contrario

Come Analizzare algoritmi

RAM Random Access Machine: (modello tecnologia/risorse implementative con costi) questa macchina ha una memoria casuale nel senso che tutte le posizioni memorizzate sono accessibili con lo stesso impiego di tempo. Rigida separazione tra memoria dei dati e memoria in cui risiede il programma: ma questo è un modello poco realistico.

Gli elementi principali sono la memoria, una locazione privilegiata che è l’accumulatore e un’altra memoria che contiene il programma e c’è una sorta di puntatore in location counter che dice a che punto siamo all’esecuzione del programma (vedere le dispense di Goldwurm e Bertoni scaricabili in rete).

La rigida separazione tra la memoria per i dati e la parte in cui risiede il programma è la caratteristica della macchina ma non assomiglia molto alle macchine reali.

RASP Random Access Store Program. E' più realistica infatti il programma stesso è immagazzinato nella memoria e non ci sono più due memorie come nella macchina RAM. Il location counter punta all’istruzione prossima del programma.

=== LEZIONE 10di42 del 21/Ottobre/2003 === (Con qualche problema audio)

I modelli di macchine RAM e RASP (testo §1.2 e dispense Goldwurm cap. 3, senza il linguaggio di programmazione). Analisi degli algoritmi e analisi insertion sort: caso migliore, medio e peggiore (testo §1.2).

Primi 44:00 minuti. Modelli RAM e RASP.

Modelli di Calcolo

RAM: Caratterizzato da una memoria ad accesso casuale formata da celle che possono contenere un intero qualsiasi (anche se non è ragionevole assumere che possano contenere un intero qualsiasi visto che se è troppo grande non lo contengono; per questo si ricorre a un criterio di costo logaritmico). Le istruzioni sono quelle di un qualsiasi linguaggio macchina ragionevole:input, output, operazioni aritmetiche, modifiche etc.

Macchina RAM: Nastro di ingresso, nastro di uscita, un programma, un contatore (Location Counter che indica l'istruzione corrente da eseguire) e una memoria formata da un insieme infinito di registri. Il programma è fissato e non può essere modificato durante l'esecuzione della istruzione. Infatti il programma non sta nella memoria con i suoi infiniti registri ma sta in un’altra memoria. Ogni registro può contenere un numero arbitrario non negativo.

Macchina RASP: il programma è memorizzato in memoria ed è un modello più realistico. Nella RAM il programma non è nei registri mentre nella RASP si. La macchina RASP si comporta come macchina RAM a meno di una costante. Valutazione dell’esecuzione delle istruzioni avviene secondo: a. Criterio costo uniforme (tempo o spazio): costo ‘costante’ per singola unita’/operazione b. Criterio costo logaritmico (tempo o spazio): che dipende dalla dimensione dell’operando, che e’ rappresentata e dipende dal logaritmo del suo valore.

Calcolabilita’ e calcolabilita’ effettiva: in generale classi funzioni ricorsive parziali esaurisce funzioni calcolabili.(vedi Touring)

Analisi InsertionSort.

Nei problemi di ordinamento la dimensione tipica dell'input è il numero di chiavi da ordinare, quindi dimensione chiavi ‘ragionevole’. Microanalisi per vedere quante volte viene eseguita una istruzione: la prima istruzione del for dell'insertion sort viene eseguita n volte e non n-1 perché l'ultima volta esegue il test per vedere se deve fare il ciclo o no; supponiamo che il costo sia costante, cioe’ C1 eseguita ‘n’ volte. Il ciclo while dipende dalla chiave e quindi non sappiamo a priori il costo del ciclo.

Nel caso migliore (array gia’ ordinato) la funzione è lineare cioè in funzione di n mentre nel caso medio e peggiore (array ordinato al contrario/inverso) è quadratica n2. Il caso peggiore ci dà la garanzia che l'algoritmo non impiegherà + tempo di quello per qualsiasi input, e’ l’estremo superiore.

Quanto ci vuole per ordinare n numeri nel caso peggiore? Sebbene dipenda dall'algoritmo posso dire che la migliore risposta ‘possibile’ è nlog(n). Infatti i migliori algoritmi lo fanno in ordine di nlog(n) e sono asintoticamente ottimi cioe’ teoricamente e’ dimostrato che nessuno impiega -di nlogn e +di nlogn, Θ (nlogn). Non necessariamente gli algoritmi asintoticamente ottimi sono i migliori nella pratica, poiche’ nella pratica di ordinamento ci sono algoritmi con migliori performance; ovvero il caso peggiore e’ raro. Quicksort viene utilizzato più frequentemente nella pratica degli algoritmi asintoticamente ottimi perché nel caso medio e’ piu’ veloce ci mette nlog(n).

Nel caso medio bisogna ipotizzare che i numeri siano distribuiti a caso e con distribuzione uniforme, nella pratica non è ragionevole avere numeri in input con una certa distribuzione e sopratutto di solito non sono inseriti a caso o completamente a caso, spesso sono dati ‘significativi’. Un buon algoritmo non deve incappare nel caso peggiore quando i dati sono inseriti quasi ordinati. Esempio degli assegni emessi da una persona: gli assegni sono disposti in libretti ordinati e quindi quando vengono consegnati alla banca sono già sensibilmente ordinati anche se li dovremo ordinare rispetto alla data di emissione.

LEZIONE 11di42 del 23/Ottobre/2003

Tecniche di progettazione degli algoritmi: approccio incrementale, divide et impera (testo §1.3). Merge sort ed analisi in spazio e tempo, versione ricorsiva e non-ricorsiva (testo §1.3). Ricerca binaria (o dicotomica) (testo esercizio 1.3-5).

Riassunto lezione precedente: - Insertion sort ha complessità lineare nel caso migliore e quadratico nel caso peggiore e medio. E' da tener presente per input ordinati o quasi visto che la complessità lineare nel caso migliore e’ solo di insertion sort.

Nessuno lo fa, ma supponiamo di avere un algoritmo di ordinamento che funziona in modo eccellente quando il file è disordinato e funziona male quando il file è ordinato sia in modo crescente che decrescente. ‘Paradossalmente’ possiamo benissimo prendere il file e “disordinarlo” e così utilizziamo nel modo migliore il nostro algoritmo. Questo è un modo randomizzato. L’insertion sort è semplice ed e’ da tener presente per input ‘quasi’ ordinati.

Posso usare InsertionSort combinato con QuickSort. Uso all'inizio Quicksort per ordinare un po’ il file e quando è abbastanza ordinato uso insertion sort sui restanti elementi. Questo è un modo per guadagnare tempo in un problema di ordinamento (anche il 20%).

Tecniche per Progettare Algoritmi

Nel caso di insertion sort uso Approccio Incrementale. Per risolvere un problema di dimensione n prima risolvo un problema di dimensione 1 e successivamente incremento fino a raggiungere n. E' un tipico metodo iterativo. Vale anche da n a 1, anche se poi tornare ad n potrebbe essere un problema.

Vediamo tecnica particolarmente vantaggiosa chiamata "Divide & Conquer/Divide et Impera". Ha il vantaggio che si può scrivere la relazione di ricorrenza che individua la complessità dell'algoritmo fin dall’inizio. Gli algoritmi ricorsivi sono quelli che richiamano se stessi fino a quando si arriva a un sottoproblema di dimensione 1 che appunto è un termine naturale per la ricorrenza visto che non vi è più nulla da ordinare.

1. Quindi: Divide: spezza il problema in parecchi sottoproblemi simili all'originale. 2. Impera: Li risolve ricorsivamente (se non fosse ricorsiva allora forse sapevo risolvere il problema iniziale). 3. Combina(fondere) i sottoproblemi risolti per dare la soluzione del problema iniziale.

Spezzando circa a ‘meta’ e suddiviso circa della medesima ‘sottodimensione’, attenzione che se spezzo in due parti in cui una parte è n e l'altra è 0 il problema va avanti all'infinito. Perche’ ‘0’ non raggiunge mai la condizione di terminazione, affinché funzioni da una parte devo avere un problema di dimensione almeno 1.

Ad esempio il Merge sort è un esempio di problema risolto con "Divide et impera". Divide la sequenza dei numeri che deve essere ordinata (ad esempio in un array) in circa n/2 ciascuna (se n è dispari non cambia nulla e una delle due parti avrà un elemento in più solitamente la seconda; infatti prendiamo ën/2û e quindi la prima parte ha un elemento in meno). Si ordinano poi le due sottosequenza usando ancora merge sort. Poi Merge=Fondere le due finali sottosequenze ordinate per produrre un unica sequenza.

MERGE (A, p, q, r) con Array A e p, q, r sono degli indici. A[p..q] e A[q+1..r] supponiamo che sottoarray siano ordinati. La procedura li fonde insieme in un singolo array ordinato. La fusione si fa trasferendo i dati da un array A ad un array B e la fusione la facciamo nell’array B. Quando abbiamo l’array B ordinato i pezzi li fondiamo nell’array A che ricicliamo. Un volta che abbiamo usato l’array A come input possiamo riciclarlo ed usarlo come target per l’output e quindi merge sort NON ordina in loco.

Esempio dei due mazzi sul tavolo con la faccia rivolta verso l'alto. Si prende la carta più piccola dei due mazzi e la si mette in un nuovo mazzo partendo da zero. Merge sort non ordina in loco e ha bisogno di un' array supplementare. Si possono ordinare elementi in numero sia pari che dispari! La ricorsione procede andando avanti fino alle foglie che rappresentano un solo elemento e quindi sono ordinate e poi porta su il lavoro fatto.

Il lavoro viene fatto quando si fa la fusione: il fatto di spezzare il file in due parti uguali non è particolarmente pesante/utile. Vale la pena usare algoritmo ricorsivo per merge sort? Si visto che ho un programma di 4 righe.

Dato che usa già il doppio della memoria necessaria per contenere i dati avrà bisogno di altra memoria per fare la ricorsione? Si! Se facciamo le chiamate ricorsive il compilatore deve gestirsi la ricorsione e quindi deve salvare nello stack le informazioni necessarie. Quali sono le informazioni necessarie? I punti in cui si spezza il file. Bisogna ricordare i punti dove si è spezzato il file? Possiamo vedere dove sono i punti di divisione a priori visto che decidiamo di spezzarli sempre nella metà.

Il numero di livelli è log(n) (visto che divido sempre i numeri a metà avrò potenze di 2) e per ordinare gli elementi ci metto sempre n (su ogni livello si fanno n operazioni). Quindi ci metto nlog(n). In questo caso le prestazioni sono indipendenti dall’ordine degli elementi in input!

Come scrivere il tempo necessario alla equazione ricorrenza del "Divide et impera"? Paradigma base dei tre passi: 1. Dividi: D(n) Tempo per dividere il problema. Θ(1) esprime tempo costante se n=1. 2. Impera: se si divide il problema in ‘a’ sottoproblemi, ciascuno di dimensione n/b, il tempo per conquistare i sottoproblemi sarà di dimensione aT(n/b). Quando l'input è banale, una costante c, il tempo è Θ(1). 3. Combina: C(n) Tempo per comporre le soluzioni dei sottoproblemi.

Quindi T(n) = (Dividi)D(n)+(Impera)aT(n/b)+ (Combina)C(n) quando n ≥ c e se fosse <c allora tempo è Θ(1).

Equazione di ricorrenza per Merge sort

La fase di divisione nel caso di merge sort richiede tempo costante Θ(1) si tratta di calcolare dove cade la metà quindi il tempo di una divisione. La fase di conquista si esplicita nel risolvere due sottoproblemi ciascuno di dimensione n/2 quindi 2T(n/2). La fase di ricombinazione fatta dalla merge richiede tempo Θ(n) cioè nell'ordine di n. Il tempo d’ esecuzione di merge sort è sempre Θ(nlogn)

Ricerca lineare scorre completamente array (ordinato) alla ricerca dell’elemento w, mi=c me/pe=n

Ricerca binaria/dicotomica (Ex.1.3.5), confronto numero cercato w con elemento n/2 e dimezzo la porzione rimanente a secondo che w sia ><= di n/2. Tempo di ricerca dividendo a meta’ ricorsivamente la porzione, ed il numero max di divisione e’ logn. Attenzione che l’ordinamento puo’ costare nlogn e quindi la ricerca lineare potrebbe essere migliore, ora se faccio numerose ricerche conviene ordinare, per esempio.

Osserviamo che confronto con n/2 costa 1, ma accedervi quanto costa se non e’ array ed invece e’ lista? La devo passare 1.5 volte. Piu’ ‘furbo’ se in una lista uso due puntatori in cui uno si muove a velocità doppia (salta due posizioni) allora dovrò scorrerla solo mezza volta, il primo puntatore sara’ meta’ il secondo alla fine della lista. Quindi la Ricerca binaria non funziona sulle liste.

Se è minore di log(n) ad esempio è √( logn) [risposta migliore del log(logn)]. Con log(log(n)) con N = 1.000.000.000 N circa 230 quindi il primo logaritmo è 30 e poi rimane il log30 che è circa <5, quindi mi servirebbero meno di cinque confronti. Ma interpolazione puo’ non funzionare. Inoltre non faccio solo ricerche, ma anche inserimenti/cancellazione che in questo caso sono costosi, tanto quanto spostare gli elementi dell’array che e’ in tempo lineare ed e‘ eccessivo.

Quanto costa l'inserimento in un array ordinato? Se non c'e' posto devo spostare tutti gli elementi dopo l'elemento che inserisco e in media ho n/2 spostamenti. Se parto dall'inizio infatti ne faccio n e se parto dal fondo 0. Quindi l’inserimento ha un tempo lineare.

Vedremo che con gli alberi binari di ricerca bilanciati si riuscirà a fare inserimenti e ricerche in tempo logaritmico. Necessita’ di essere bilanciati e quindi tempo e’ logn.

=== LEZIONE 12di42 del 28/Ottobre/2003 === (da 1:22:50 no audio)

Notazioni asintotiche e loro utilizzo. (testo §§1.4 e 2.1). Le notazioni ‘O grande’ O( ), e ‘o piccolo’ o( ): le altre notazioni (’Tetha’ Θ e ‘Omega’ Ω) si possono esprimere in funzione di queste prime (testo § 2.1). Funzioni monotòne. Base e tetto (testo §2.2). Richiami sulle notazioni usate (testo § 2.2, si può saltare solo il logaritmo iterato lg*).

Notazioni asintotiche. Ovvero ordine di grandezza e rapidità di crescita delle funzioni. Il tempo di esecuzione dell'algoritmo dà un'idea dell'efficienza dell'algoritmo stesso.

Asintotico: fare un confronto asintotico vuol dire che stiamo usando valori di n molto grandi che tendono all’infinito, ovvero da un determinato punto ‘n0’ in poi. Le funzioni su cui lavoriamo sono asintoticamente non negative, cioe’ da n0 in poi. Svincolandoci dalle costante semplifichiamo l’analisi delle performance.

Si dice che la funzione f definita sui naturali cresce: - O grande: al più come g cioè f ≤ g quindi f=O(g) - Omega: almeno come g cioè f ≥ g quindi f=Ω(g) - Tetha: circa come g cioè f@g quindi f=Θ(g) + blanda di f asintotico a g dei matematici dove limite di f/g = 1. Limita asintoticamente da sopra e da sotto. - o piccolo: lim f(n)/g(n)->0 f cresce meno rapidamente di g - OmegaPiccolo: più di g cioè f>g quindi f=ω(g)

Si dice che F(n)ÎO(g(n)) e non f(n)=O(g(n)) visto che O(g(n)) è un insieme di funzioni.

Semplificando possiamo anche scrivere: - f=Ω(g) sse g=O(f) - f=Θ(g) sse f= Ω(g) e f=O(g) a meno di un ‘c’ e ‘d’ - Θ è un estremo sia superiore che inferiore ovviamente moltiplicato per costanti diverse - f=ω(g) sse g=o(f) Esempi su algoritmi di ordinamento: - Insertion Sort ha complessita’ nel caso peggiore O(n2). - Merge Sort O(nlogn) ed il tempo e’ anche Θ(nlogn) e tempo di esecuzione o(n2). - HeapSort nel caso migliore arriva anche a Θ(n) quindi lineare, mentre caso medio/peggiore e’ Θ(nlogn).

Tempo di esecuzione di qualsiasi algoritmo di sort è Ω(n) ovvero almeno nell'ordine di n (devo fare almeno n operazioni).

Esempi: - (2 + Sin(n))n2 + O(nlog2(n)) = Θ(n2 ) xche’ (2+sin(n)) e’ comunque una costante limitata 2-3 - 2 + Sin(n) = Θ(1) ovvero è una costante anche se oscilla al variare di n - Un heap si può costruire in tempo lineare. - Proprieta’ tricotomia, sorvolare - Ex.2.1.8

Notazioni standard

- Monotonia: non decrescente - Strettamente crescente - ‘Base’ e ‘tetto’: x-1<intero inferiore/base£x£intero superiore/tetto<x+1 - Polinomio: funzione p(n) della forma p(n)=ådi=0ai*ni - Esponenziali - Logaritmi - Fattoriali

=== LEZIONE 13di42 del 30/Ottobre/2003 === (audio fino 1:22:00 di 1:28:26)

Ancora su funzioni asintotiche e loro uso. Esempio del calcolo del numero delle parti in cui n rette dividono il piano (dispense Goldwurm §5.1). Fattoriali e binomiali (testo §6.1); formula approssimata di Stirling e calcolo di lg(n!) (testo §2.2). Osservazioni sul tempo di calcolo del fattoriale (criterio di costo logaritmico).

Ancora sulle funzioni asintotiche e come usarle esplicitamente nelle equazioni; possiamo eliminare dettagli che ‘ingombrano’ oppure non sono importanti ai fini della equazione.

Crescita polinomiale F(n)=O(nk)=nO(1). O(nk) richiede una costante k Crescita esponenziale F(n)=Ω (an) con a>1 Crescita (poli)logaritmica F(n)=O(log(n))k = log(n)O(1) Crescita sub-logaritmica log2(log2(n)) Crescita super-esponenziale 22^n=2^2^n

Ripasso sui logaritmi (che sono da sapere). Notazioni: lgn=log2n cioe’ Logaritmo binario; ln=logen cioe’ Logaritmo Naturale

Formula (Approssimazione) di Stirling.

log2(n!) = log2(n) + log2(n – 1) + log2(n –2) + . . . + log2(2) + log2(1) ≥ n/2 log2(n/2)=(n/2)log2(n – 1)=Θ(nlog2(n))

Funzione Logaritmica cresce meno di Funzione Polinomiale che cresce meno di Funzione Esponenziale.

Funzione Fattoriale. Con definzione ricorsiva.

Relazioni di ricorrenza.

Numeri di Fibonacci.

Problema dei conigli: Se una coppia di conigli giovani matura in un mese e genera una nuova coppia di conigli ogni mese successivo quante coppie si avranno in un anno partendo da una coppia giovane?

tempo t0 t1 t2 t3 t4 t5 coppie 1 1 2 3

Come trovare una soluzione ricorsiva per il problema dei conigli? (vedi esempio Matrioske)

LEZIONE 14di42 del 31/Ottobre/2003

Definizione di ricorrenza e relazioni di ricorrenza. Teorema principale e Risoluzione di ricorrenze con il metodo di sostituzione (testo §4.1 e Cap.4.x). Cenni alla parte II del testo: ordinamento e selezione, statistiche d’ordine (testo pagine129-131).

Riassunto: modalita’ di crescita di una funzione

Considerazioni su:

- Iterazione (i.e. 2n dove se mi fermo prima del termine ho un risultato intermedio Iterazione: pot=1 poi con i da1aN -> pot=pot*2) e - Ricorsione (che non da risultati intermedi).

Relazioni di ricorrenza (ricorsione).

Esempio di relazione di ricorrenza che calcola le potenze di 2 in maniera generico ed efficiente: f(n)=1 se n ≤ 0 con f(n)=2f(n-1) altrimenti con n>0

Definizione di ricorrenza sul libro: la ricorrenza è un'equazione o una disuguaglianza che descrive una funzione in termini del suo valore su input più piccoli. Avevamo visto un esempio che non era solo su input necessariamente più piccoli ma addirittura su infiniti input?

Un’ultima osservazione: è facile scrivere le relazioni di ricorrenza che definiscono la funzione z(j), il numero di 0 finali nella rappresentazione binaria dell’intero j, (ovvero la massima potenza di 2 che divide j) e la funzione v(j), il numero di 1 nella rappresentazione binaria di j. Si provi a farlo per esercizio. Le relazioni di ricorrenza per la funzione z(j) hanno un’interessante peculiarità. Infatti, nelle relazioni di ricorrenza più comuni i casi definiti esplicitamente sono dati per valori piccoli dell’argomento, e sono in numero finito. Per z(j), al contrario, abbiamo infiniti casi espliciti: z(j)=0 se j è dispari, ossia se j=2k+1, e invece z(j) = z(j/2) + 1 se j è pari, ossia se j = 2k. La funzione z(j) è talvolta chiamata la funzione righello, perché fornisce l’altezza dei trattini di un righello, se le divisioni sono fatte seguendo le potenze di 2 invece di quelle di 10 (come si usa in America, almeno per le misure in pollici: i sedicesimi di pollice hanno un trattino piccolo, gli ottavi un po’ più grande, e così via).

Il Teorema Principale fornisce esplicitamente le ricorrenze di questa forma:

T(n) = aT(n/b) + f(n)

con a ≥1, b>1 (dim problema diminuisce) ed f(n) è la funzione data. Quindi sfrutto questo teorema per arrivare alla soluzione. Ma il teorema non copre tutti i casi possibili! Altrimenti il prob delle ricorrenze sarebbe banale. Nella pratica quando si descrivono e risolvono le ricorrenze si trascurano certi dettagli tecnici ad esempio che le funzioni devono avere argomenti interi.

Metodo di sostituzione (per risolvere equazioni di ricorrenza) Il metodo di sostituzione per risolvere le ricorrenze richiede di tentare uno schema di soluzione e quindi di usare l’induzione matematica per trovare le costanti e mostrare che la soluzione funziona.

Esempio: determiniamo un limite superiore per questa equazione 4.4 (simile ricorrenze mergesort, solo simile) T(n) = 2T( ën/2û ) + n Proviamo con T(n) = O(nlog2(n)). Il metodo consiste nel provare che T(n)≥cnlog2(n) dove c è una costante positiva scelta in modo appropriato. Quindi sostituendo nella formula si ha

T(n) ≤ 2( c ën/2û logën/2û ) + n

≤  cnlog (n/2) + n
=  cnlog (n) - cnlog2(2) + n
=  cnlog (n) - cn + n
≤  cnlog (n) Dove l’ultimo passo vale per c ≥ 1

Adesso dobbiamo dimostrare che la soluzione vale anche per le condizioni iniziali. In questo caso T(1) ci crea dei problemi poiché T(1) > c 1 log21 e quindi si considera n = 2 e n = 3. In questi casi succede che T(2) ≤ c 2 log22 e T(3) ≤ c 3 log23. Qualunque scelta per c ≥ 2 è sufficiente.

Non esistono regole generali per trovare la soluzione corretta per ogni ricorrenza ma vi sono alcune euristiche che aiutano a risolverle. Ad esempio quando le ricorrenze sono simili anche le soluzioni che tenteremo saranno simili. Un altro modo per azzeccare la soluzione è quello di provare limiti vicini tra di loro delle ricorrenze: se cominciamo con un limite inferiore T(n) = Ω(n) e uno superiore T(n) = O(n2) per la ricorrenza T(n)=2T(ën/2û)+n.

Gradualmente abbasseremo il limite superiore e alzeremo quello inferiore fino a giungere alla soluzione esatta.

=== LEZIONE 15di42 del 4/Novembre/2003 === (qualche problema visualizzazione con i lucidi)

Il metodo iterativo per risolvere le ricorrenze e l’albero di ricorsione (testo §4.2). Richiami sulla serie geometrica (testo §3.1). Il teorema Principale (testo §4.3)Dispense Goldwurm (§5.1)

Metodi per risolvere ricorsione

Partendo dall’esempio: Determinare il numero massimo di parti in cui n rette dividono il piano.(i.e 4 tagli su torta ottenendo anche 15 parti?tagli verticali(fette)+orizzontali(strati)+diagonali). (vedi Enciclopedia sequenze di interi, link sul sito di Torelli)

Detto P(n) il numero di parti in cui n rette dividono il piano

1) Una retta divide il piano in due parti 2) Sia P(n) il numero di parti in cui n rette dividono il piano e aggiungendo una nuova retta è facile verificare che è intersecata al più in n parti dalle precedenti creando al più n+1 nuove parti.

Vale quindi P(n+1)=P(n)+n+1 (è poi la relazione di ricorrenza del quick sort nel caso peggiore !!)

Procedura ricorsiva che calcola P(n)

if n == 1 then return 2 else x = P(n – 1) return (x + n)

Coefficienti binomiali: se prendo un binomio (x + y)2 mi chiedo quali siano i coefficienti dei termini del binomio.

Metodo di iterazione

Il metodo di iterazione ha il vantaggio che non si deve ‘indovinare’ la risposta come nel metodo di sostituzione.

L’idea è di espandere la relazione di ricorrenza e di esprimerla in sommatoria dei termini dipendenti solo da n e dalle condizioni iniziali. Le tecniche per valutare le somme possono essere usate per limitare la soluzione o per trovare la soluzione esatta (vedi cap.3).

Per esempio consideriamo la seguente relazione di ricorrenza: T(n) = 3T( ën/4û ) + n

Spezziamo un problema di dimensione n e ne risolviamo 3 di dimensione n/4 visto che “pensiamo” che la soluzione non si trovi nel sottoproblema che scartiamo.

Ora si itera come segue: (§4.2)

T(n) = n + 3T( ën/4û ) = n + 3( ën/4û + 3T( ën/16û )) = n + 3( ën/4û + 3( ën/16û+3T( ën/64û ))) = n + 3( ën/4û + 9( ën/16û+ 27T( ën/64û )

Studio della serie geometrica pag. 41 del libro

Si passa dalla serie finita a quella infinita poiché è più semplice calcolarne il limite. Per fare questo moltiplico la sommatoria iniziale per (x–1) e successivamente quando passo a quella infinita devo dividerla per lo stesso termine. In definitiva trovo come risultato 1/(1–x).

Metodo di Iterazione con Albero di ricorsione

Un albero di ricorsione è un modo comodo di visualizzare ciò che accade quando si itera una ricorrenza e che può aiutare a organizzare la gestione algebrica necessaria a risolvere la ricorrenza.

Ad esempio associo l’albero di figura 4.1 del libro alla seguente relazione di ricorrenza

T(n) = 2T( n/2 ) + n2

Assumiamo per comodità che n sia una potenza esatta di 2.

Per costruire l’albero di ricorrenza in pratica parto da n2 e nei figli ci metto 2T(n/2). Successivamente risolvo 2T(n/2) e quindi aggiungo dei nuovi nodi e così via. L’altezza dell’albero sarà log2(n). All’ultimo livello il tempo di calcolo sarà n. Infatti abbiamo livelli di costo via via decrescenti. Non dobbiamo curarci del numero dei livelli infatti i costi sono dominati dalla radice tanto è vero che possiamo mandarlo all’infinito. La serie è convergente ed è la serie geometrica di ragione ½ elevato a k. Quindi il risultato della serie è 2 poiché 1/(1–x) con x = ½ fa appunto 2 e la soluzione della ricorsione tralasciando il 2 è Θ(n2).

Teorema principale (1980)

Questo metodo fornisce un approccio “ricettario” (ovvero se le cose stanno in un modo fai una certa operazione e se stanno diversamente il risultato sarà un altro) per risolvere le ricorrenze della forma

T(n)=aT(n/b)+f(n)

Funziona per le relazioni di ricorrenza tipiche dei metodi “Divide et Impera” in particolare con a≥1, b>1 costanti qualsiasi non necessariamente interi e f(n) è una funzione asintoticamente positiva. (esempio semplice e semplificato: ricerca dicotomica).

Qual è l’idea? Supponiamo che a sia intero, noi dobbiamo sostituire a T(n) con f(n) e tanti sottoproblemi che richiedono tempo T(n/b) e i sottoproblemi sono a e quindi figli di f(n).

I tre casi corrispondo a tre eventualità cioè: - quello in cui prevalgono le foglie - quello in cui i costi sono nella radice o nei primi livelli - il terzo caso è quello in cui i costi sono distribuiti su tutti i livelli.

Per sapere in che caso siamo dobbiamo confrontare sempre il costo nelle foglie=n^(log(baseb)a) con il costo nella radice=f(n).

LEZIONE 16di42 del 6/Novembre/2003

Cenno alla dimostrazione del teorema principale tramite l'albero di ricorsione (testo fig. 4.3). Introduzione a quick sort (testo cap.8).Counting sort, radix sort, bucket sort. Statistiche d’ordine.

Finire di giustificare Teorema Principale e vedere qualche esempio. Ipotesi del teorema principale.

1 - La relazione di ricorrenza (ottenuta tipicamente da tecniche divide et impera) deve avere una forma del genere: T(n) = aT(n/b)+f(n) con a ≥ 1 e b > 1, quindi richiede memorizzazione di 3 casi. Si divide il problema di dimensione n in problemi di dimensione n/b e f(n) ci dà il costo sia della divisione in a sottoproblemi che dell'eventuale ricombinazione in un unico problema. La dimostrazione del teorema principale non viene chiesta all'esame.

Ritornado agli algoritmi di ordinamento Solitamente si usano le chiavi per ordinare ma quello che interessa poi sono i "dati satellite" che interessano ovvero i dati in cui ci sono informazioni addizionali alle chiavi. Insertion sort non va solo bene quando abbiamo un piccolo numero di elementi in input, infatti basta che siano un po’ ordinati che insertion sort lavora in tempo lineare. Quick sort ordina n numeri in loco e non ha bisogno di spostare elementi di input se non in quantità costante in un memoria ausiliaria. Il prof dice che non ordina in loco perché ha bisogno di una quantità non costante di memoria ausiliaria per gestire i dati. Non mi importa se ci metta dati di input o no. Quindi forse è meglio dire che NON ordina in loco! !QuickSort batte MergeSort ed HeapSort (inloco) perché ha un codice compatto ed efficiente e i cicli interni sono semplici e veloci e in media è più veloce. Non è più veloce in senso asintotico, la complessità è sempre nlog(n) nel caso medio solo che la costante è più bassa. Insertionsort, mergesort, heapsort, quicksort sono algoritmi di ordinamento (per confronti) che confrontano le chiavi per metterle in ordine. E' possibile dare un modello relativamente astratto di questo modo di procedere per vedere quali sono le limitazioni agli algoritmi di ordinamento per confronti? Si usa un albero di decisione. La decisione di spostare un elemento prima di un altro oppure no viene presa tramite un confronto. L'albero di decisione serve per dimostrare un estremo inferiore per il tempo di esecuzione di qualsiasi algoritmo di ordinamento per confronti su n input nel caso peggiore. Se non è possibile nel caso peggiore di ordinare n elementi in tempo (migliore di) nlog(n) gli algoritmi che lo fanno sono detti algoritmi asintoticamente ottimi. Dunque heapsort e mergesort sono teoricamente importanti perché sono asintoticamente ottimi anche se non li usa nessuno visto che quicksort è più veloce ma servono per dimostrare che ci sono algoritmi asintoticamente ottimi.

Counting sort assume come ipotesi che i numeri (le chiavi) siano entro un ben preciso insieme cioè da 1 fino a k. Usando l’indicizzazione dell’array come uno strumento per determinare l’ordine relativo degli elementi il counting sort può ordinare n elementi nell’ordine di O(k+n) . E’ lineare o no? Qui ci sono due parametri quindi voglio sapere se è lineare rispetto ad n. Quando k è O(n) allora il counting sort è lineare rispetto alle dimensioni dell’input anche nel caso peggiore. Quindi esistono algoritmi di ordinamento lineare.

Un altro algoritmo di ordinamento lineare si chiama radix sort. Se ci sono n interi da ordinare e ogni intero ha d cifre e ogni cifra è nell’insieme da 1 a k il radix sort può ordinare nell’ordine di O( d (n+k)). Quando d è una costante e k è O(n) allora il radix sort ordina in tempo lineare. BucketSort, si mettono le chiavi nei “secchi” e poi si ordinano. Bisogna sapere qual è la destinazione della chiave nel secchio. Quanti secchi ci vogliono per ordinare n chiavi? Usiamo n secchi per ordinare n chiavi. Quindi mediamente ci va una chiave per ogni secchio. Se lo ‘sparpagliamento’ viene fatto in tempo costante per ciascuna chiave, tempo costante per ordinare le chiavi nei secchi quindi faccio tutto in tempo lineare. Occhio a non far finire tutte le chiavi in un secchio altrimenti la suddivisione e’ unutile.

Statistiche d’ordine (Order Statistic): l’i-esima statistica d’ordine di un insieme di n numeri è l’i-esimo numero più piccolo in quell’insieme. Si ordina tutto il file e si va a prendere l’elemento più piccolo così si trova l’i-esima statistica d’ordine. Trovarlo così costa circa nlog(n) nel caso peggiore poiché devo ordinare tutti gli elementi. Noi vogliamo l’i-esimo elemento non tutti gli altri. Per trovare l’i-esimo elemento devo fare almeno n operazioni. (vedi argomento dell’antagonista/avversario)

LEZIONE 17di42 del 7/Novembre/2003

Quick sort: la procedura di partizionamento (testo §8.1). Prestazioni di quick sort: caso migliore e peggiore (testo §8.2). Considerazioni sul caso medio Θ(nlgn) (testo §8.2).

Riprendiamo il Teorema Principale: e dimostriamo che la condizionare di regolarita’ implica condizione normale nel terzo caso dove prevale la radice (libro esercizio 4.4.2). Esempi: Quanto costa stimare il fattoriale: n!(pag.32 libro)

Quick sort. Nel caso peggiore è Θ(n2). Ciònonostante è spesso la scelta pratica migliore per ordinare xche’ efficiente, in media il tempo di esecuzione atteso è nlog(n) come per altri algoritmi ma i fattori costanti nascosti nella notazione Θ che ci libera dalle costanti sono piccoli ed è difficile battere quicksort. Ha il vantaggio di ordinare in loco? Non è vero. Ha bisogno di un piccolo stack che ha dimensione logaritmica (c’è in uno dei problemi/esercizi alla fine del capitolo).

Il codice di quick sort e’ semplicemente composto da sole 4 righe. La complessità del quick sort è sposata nella procedura partition. Viene diviso l’array e viene applicato ricorsivamente il quicksort su entrambi i sottoarray. La ricorsione finisce quando p è ≥ r. E' basato sulla tecnica divide et impera.

La parte che riguarda la divisione dell'array A[p..r] lavora nel seguente modo:

1.Divide l'array in due sottoarray (non vuoti! Se uno dei due fosse vuoto le dimensioni del sottoproblema con tutti gli elementi non diminuirebbero mai quindi vado avanti all’infinito) A[p..q] e A[q+1..r] in cui tutti gli elementi del primo sottoarray sono minori del secondo. 2.Impera: viene applicato l'algoritmo Quick sort ricorsivamente su entrambi i sottoarray. I due sottoarray sono ordinati in loco e quindi il lavoro viene fatto nella fase di divisione e non di fusione. La partizione viene fatta nel seguente modo: si prende un valore arbitrario dall'array da scegliere come perno per tutti gli elementi. La scelta più ovvia è prendere il primo elemento dell'array ma ovviamente non è la migliore. E’ meglio cambiare gli elementi con l’elemento perno anche se sono uguali. E’ una delle sottigliezze del quick sort provare per credere… Per fare la partizione impiego tempo dell’ordine di n visto che confronto un elemento con tutti gli altri.

Se si usa l'ultimo elemento (e se è l’elemento maggiore) come perno il Quick sort sul libro va in loop. Si può scegliere l’ultimo elemento come perno ma si deve cambiare la procedura visto che con quella segnata sul libro va in loop. E in ogni caso non è obbligatorio prendere il primo elemento come pivot. Se invece scelgo il primo elemento come perno e l’array è ordinato in modo decrescente ho la parte fatta di un solo elemento e l’altra di n–1 elementi quindi non è una buona scelta nemmeno prendere il primo elemento.

La scelta ragionevole è quella di prendere l'elemento nel mezzo.

Il tempo di esecuzione dipende dal fatto se il quick sort è bilanciato o no. Quindi dipende da quali elementi sono usati nel partizionamento.

Il caso peggiore si ha quando c'è una regione con n-1 elementi e l'altra regione ha 1 elemento. L’equazione di ricorrenza nel caso peggiore diventa T(n)=T(n-1)+Θ(n) che è l’equazione di ricorrenza con cui n rette dividono il piano. Oppure ricorda la somma di Gauss visto che faccio prima n poi n-1 poi n-2 e così via confronti e quindi è nell’ordine di Θ(n2).

Nel caso migliore produciamo due regioni di ampiezza n/2 e cadiamo nel 2° caso del teorema principale. T(n)=2T(n/2)+Θ(n) Che si trasforma in: T(n) = Θ(nlogn)

In questo caso basta disegnare l’albero di ricorsione che ha n livelli e la somma su ogni livello è n. Anche se il partizionamento è sbilanciato sebbene l’altezza dell’albero non sia sempre uguale la somma su ogni livello è sempre n e alla fine ottengo lo stesso risultato.

LEZIONE 18di42 del 11/Novembre/2003

Quick sort randomizzato (testo § 8.3). Generazione di numeri e permutazioni pseudo-casuali (generatore lineare congruente: vedere Knuth, riferimento [122] nel testo, oppure, per esempio, http://www.math.utah.edu/~alfeld/Random/Random.html).

Riepilogo QuickSort: Procedura di partizionamento, poi vengono scanditi i due array confrontando l'elemento perno e gli elementi più piccoli vengono messi a sinistra e quelli più grandi a destra, se uguale viene scambiato comunque.

QuickSort non mantiene l'ordine degli elementi uguali. A priori li sposto e quindi non mi interessa del loro ordinamento, basta che siano ordinati rispetto all'elemento perno. Si dice che Quick Sort non è stabile. Non mantiene l’ordine ‘iniziale’ degli elementi uguali. L’analisi nel caso medio del quicksort non è stata fatta (abbastanza complicata), per chi interessato è meglio guardala sul libro di Sedgewick [caso medio=1.38*(caso migliore)=38% peggioramento]. Il caso peggiore si ha quando ogni volta partition crea sottoarray con 1 solo elemento e sottoarray con n-1 elementi, in questo caso partition e’ dell’ordine Θ(n) e relazione di ricorrenza e’ quella del numero di parti di n rette sul piano che e’ nell’ordine di Θ(n2).

E' meglio tenere la ricorsione o toglierla? (vedi §.prob 8.4) La seconda chiamata ricorsiva può essere evitata usando una procedura iterativa che si chiama "Tail Recursion". Questa tecnica è fornita da buoni compilatori. Sul libro negli esercizi c’è una versione che simula la versione iterativa al posto della seconda chiamata ricorsiva (sulla seconda parte dell’array). La prima ricorsione non può essere rimossa poiché dopo di essa deve essere fatta quell’altra chiamata. Per eliminare anche questa chiamata ricorsiva dovremmo simulare la gestione dello stack. Per vedere quale delle due versioni del quicksort sia meglio basta fare qualche prova sulla macchina e vedere quale versione viene eseguita in tempo minore.

Meglio eseguire quick sort sulla partizione +piccola e lasciare in sospeso nello stack la/e parte/i +grande/i.

Dal 37:00 al 51:00 Commento alla gestione amministrativa delle videolezioni.

Versione randomizzata del quick sort. La prima idea è quella di rendere casuale l’input, pre-tratto l’input ‘sparpagliando’ gli elementi (come si fa a generare dei valori casuali? per esempio per definire posizioni casuali in cui mettere i dati). Il modo più semplice è ad esempio quello di andare a vedere il clock e campionare/prendere i millesimi di clock in quel determinato istante ed ottengo un numero che posso considerare ‘genuinamente casuale’ 0-999.

Generatori di numeri pseudo-casuali. (vs veramente casuale che e’ non deterministico e non replicabile).

Metodo Lineare Congruente. Congruente perché c'è un’operazione di modulo (resto della divisione per m), lineare perché c'è un’espressione lineare nella variabile x (che viene poi iterata)

Xn+1 = (a xn + c) mod m Per esempio tra i piu’ studiati a=75, c=0, m=(231)-1 [per rappresentazione 32bit]. Altro esempio: a mod 1 e’ la parte frazionaria di a, verra’ usata nelle tabelle hash. Ad esempio per generare una sequenza di input casuali posso usare questa procedura di permutazione: For i = 1 To n Do Scambia A[i] con A[Random(i, n)] Ogni permutazione ha quindi la stessa possibilità di essere scelta.

LEZIONE 19di42 del 13/Novembre/2003

Generatore pseudocasuale con metodo lineare congruente. Esercizi 8.4.4, 8.4.6, prob 8.4 ed 8.5. CountingSort (testo §9.2).

Riassunto della versione randomizzata di quicksort. Con ipotesi di input equidistribuiti per misurare le performance, l’equidistribuzione e’ garantita con ‘rimescolamento’ dell’input tramite il generatore pseudocasuale.

Tra i metodi abbiamo visto: - Metodo lineare congruente - Metodo centro del quandrato (non si riesce a dominare il comportamento) - Metodo parte frazionaria di un numero

Oltre che per generare numeri, interi e frazionari puo’ essere usato per ottenere la permutazione casuale degli input. Iterando gli scambi di elementi dell’array in posizione A[i] e l’elemento in posizione casuale A[random].

Anche se nessuno in realta’ rimescola gli elementi, il generatore viene usato per identificare l’elemento perno della procedura partition, scegliendo quindi un elemento casuale nell’array. Attenzione che in questo modo l’algoritmo si comporta diversamente anche mantenendo lo stesso input. (vedi differenza tra Algoritmi Probabilistici ed Algoritmi Randomizzati, anche se spesso i termini sono usati intercambiabilmente)

Per esempio abbiamo visto il Test di primalità "Black Box" di Miller e Rabin (cap.33) e’ un algoritmo probabilistico per determinare se l’intero n e’ primo. Utile anche se non-corretto perche’ con probabilita’ ¾ che sia corretto dopo n tentativi...

Ricordiamo anche che per permutare casualmente e’ richiesto tempo ordine di n, inoltre per scegliere casualmente elemento perno dovrei anche aspettarmi tempo ordine di n.

Esercizio 8.4.4.Utilizzare insertionsort combinato/associato a quicksort quando l’array e’ al di sotto di una determinata soglia k, ovvero cessiamo la ricorsione e ci ritroviamo un numero di sottoarray di dimensione max k dove gli array sono ordinati tra loro e abbstanza ordinati internamente, quindi non ci saranno scambi tra sottoarray/sottopartizioni. Il tutto eseguito in O(n k + n log(n/k)) per un opportuno k da definire. Sedgwick dice che praticamente/empiricamente quicksort+insertionsort migliora di 15/20% con questo metodo.

Esercizio 8.4.6. Suggerisce di cambiare la procedura di partizionamento prendendo 3 elementi casuali nell’array e prendendo la mediana dei tre elementi.

Problema 8.4 Ridurre profondita stack per quicksort. Ricordando la Tecnica di ricorsione in coda (tail recursion), dobbiamo scegliere se lasciare in sospeso, nello stack, la parte + piccola o + grande dell’array; possiamo decidere analizzando il caso peggiore e migliore. Caso peggiore due sottoarray con 1 ed n-1 elementi, in questo caso lo stack cresce 1 alla volta fino ad n-1. Se viceversa ci metto parti + grandi la prima sara’ n-1 mentre elaboro 1 e cosi via, e quindi nello stack ho un solo elemento se ci metto quello + grande ovvero il pountatore alla porzione di array di interesse.

Problema 8.5. Mediano di 3 partizioni/elementi con considerazioni probabilistiche. Idea utile dove il problema e’ la scelta dei tre elementi, che potrebbero essere scelti a caso oppure in maniera deterministiaca per esempio il primo, quello centrale e l’ultimo.

Ordinamento in tempo lineare.

Un algoritmo basato sui confronti deve fare almeno Ω(nlogn) operazioni nel caso peggiore, mergesort e quicksort che impiegano questi tempi possono essere definiti come asintoticamente ottimi, ma non vuol dire che siano i migliori da usare. Ad esempio il QuickSort non è asintoticamente ottimo ma nel caso medio si comporta in modo migliore degli altri. Per ordinare in tempo lineare n ci sono algoritmi che lo fanno senza confronti, vedremo CountingSort, RadixSort e BucketSort.

Come definire limiti inferiori per algoritmi di ordinamento per confronti in qualsiasi caso presente/passato/futuro? Capitolo.9 Con albero di decisione, utilizzando albero binario con due direzioni ‘<=’ e ‘>’. L’albero di decisione non e’ unico a parita’ di elementi da ordinare, la forma/albero cambia al cambiare dell’algoritmo, ma a noi interessa vedere quanto e’ alto nell’ipotesi che sia il + basso possibile.

Ora, un albero binario di altezza h (cammino piu’ lungo[caso peggiore]=numero confronti) non può avere più di 2h foglie, dove numero di foglie e’ uguale ad n!(fattoriale) con (n!-1) nodi interni.

Il teo.9.1 dice che h= Ω(nlogn) con n! foglie.

CountingSort. Algoritmo ordinamento non basato su confronti.

Abbiamo in input un’array A e nell’array C mettiamo il numero di volte che un numero compare nell’array A. Ad esempio se nell’array A il numero 1 compare 4 volte allora nell’array C in posizione 1 metto il numero 4. Quindi l’array C rappresenta le occorrenze di ciascuna chiave, quindi C e’ lungo quanto la max lunghezza della chiave max. Successivamente scrivo un’array B in cui metto i numeri ordinati secondo l’array C e le frequenze/occorrenze. Si potrebbe riutilizzare l’array A per riscrivere i numeri ordinati senza creare l’array B. Anche se non possiamo poiche’ esisteranno campi/dati satelliti delle chiavi.

Vedi somma cumulata dei valori di C...ottenuto sommando i precedenti....mi dice il numero di elementi che precedono la chiave desiderata, considerando anche le chiavi uguali. Non possiamo usarla...

Usa tanta memoria poiche’ necessita di = array input A + array ausiliario + array output. Con poche chiavi ripetute molte volte allora le cose funzionano bene, ovvio.

LEZIONE 20di42 del 14/Novembre/2003

Albero di decisione.Algoritmi di selezione o statistica d’ordine. Counting sort. Radix sort (testo §9.3). Bucket sort (testo §9.4).

Riepilogo: Albero di decisione usato negli algoritmi di ordinamento per confronti, quando non conosciamo input. Potrebbe essere ambigua l’etichettatura foglie, intendiamolo anche come albero confronti oppure albero degli scambi. Vediamo come interpretare una permutazione, come ordinare un n-permutazione in loco. (Per stabilire il minimo tra n elementi faccio n-1 confronti.)

Il CountingSort ha bisogno di tre array: di input, di output ed uno ausiliario contenente il numero di occorrenze dei dati. Si deve sapere quanto fare grande l'array transitorio C che deve essere di dimensione k pari al numero delle chiavi diverse che dobbiamo ordinare; questa informazione ci deve essere data prima o la deduciamo noi contando gli elementi da ordinare. Procedura: prima calcoliamo somma cumulata in C con valori debolmente crescenti, rappresentanti le posizioni delle chiavi e le frequenze, poi scansione dell’array input/A da dx a sx e collochiamo i valori su array output/B decrementando i valori delle frequenze dell’array C. Sviluppata in circa 10 righe di pseudo-codice. Complessita’: spazioS(n)=Θ(n+k) implica almeno-> TempoT(n)=Ω(n+k) effettivamente Θ(n+k); quindi se T(n)= Θ(n) sse k=O(n) cioe’ k cresca al piu’ come n.

Radix Sort. Ordinamento per radice ovvero prendo le cifre dei numeri, ordinando cifra per cifra. Facendo un po’ di storia: era un algoritmo usato per ordinare le schede che si usavano con i vecchi elaboratori. Procedura: Ordino partendo dalla cifra meno significativa (i.e. 653412 parto dal 2), passo alla cifra successiva (i.e.1) e l’algoritmo deve essere stabile per non perdere il lavoro fatto. Per ordinare le singole cifre devo quindi usare un algoritmo stabile, banale nel caso binario (0 vs.1); ordino quindi per esempio con countingsort (con k=numero chiavi distinte).Quindi tutto bene se ci sono tante ripetizioni, che mantengono d=# cifre basso. Complessita’:Il tempo di esecuzione di radix sort è d=# di cifre, Θ(kd + dn) che è lineare nel caso in cui k = O(n) e d è una costante ovvero il numero delle cifre deve essere costante. Quindi radixsort esegue in tempo lineare O(n), se la lunghezza delle chiavi (ovvero numero di cifre) rimane costante. Sotto queste condizioni e’ un buon algoritmo di ordinamento per esempio rispetto quicksort.

Bucket Sort. (Ordinamento a secchi). Eseguito in tempo lineare in media, caso peggiore e’ almeno nlogn od addirittura n2. Funziona bene con alcune premesse sull’input. Ovvero la premessa e’ che l‘input sia distribuito uniformemente per esempio sull’intervallo [0-1) semiaperto a dx, ovvero dovremo ricondurre le chiavi iniziali all’intervallo richiesto, inoltre preoccupandoci che siano distribuite uniformemente e non concentrate/affollate. Procedura: Suddividiamo intervallo input in secchi, usiamo insertionsort per ordinare internamente ai secchi. Se dobbiamo fare Bucket Sort su n elementi quanti secchi dobbiamo preparare? n ed al massimo n. (se mi aspetto k chiavi per secchio allora k secchi). Anche se sono tanti fa niente visto che ci finisce solo una chiave in ogni secchio e alla fine ho solo n elementi da ordinare e quindi sarà facilissimo. Nel caso volessi scegliere meno secchi allora faccio puntare ogni secchio a una lista e collego/link l’ultimo elemento di ogni lista al secchio successivo. Per ricondurre k all’intervallo [0,1) posso usare la formula:

Complessita: lineare in media (numero chiavi costante in ogni secchio), quadratico caso peggiore (tutte le chiavi in un unico secchio, nel caso usassi insertionsort; complessita’ migliore se usassi per esempio quicksort ma a questo punto tanto valeva non usare bucketsort)

Prossimo argomento: Algoritmi di Selezione o di Statistica d’Ordine, trovare k-simo elemento senza ordinare ed in particolare trovare il mediano. Quanto costa trovare elemento minino o massimo in un file? Costa n - 1 visto che confronto un elemento con tutti gli altri e quindi faccio n - 1 confronti per estrarre il minimo. Per estrarre anche il massimo farò gli stessi confronti e quindi mi costa il doppio. Invece vedremo che ci sono metodi per impiegarci meno del doppio per estrarre sia massimo che minimo. Per moltiplicare due matrici 2x2 quante moltiplicazioni dovro’ fare? Istintivamente 8 ma ci sono approcci che permettono di farlo con 7 moltiplicazioni.

LEZIONE 21di42 del 18/Novembre/2003

Statistiche d'ordine. Determinazione del minimo, del massimo e minimo simultaneamente (testo §10.1). Prodotto di matrici e algoritmo di Strassen (testo §31.2, solo la presentazione e le conclusioni; si confrontino anche le dispense Bertoni-Goldwurm §10.5). Selezione con tempo medio lineare (§10.2).Selezione in tempo lineare nel caso peggiore (§10.3, solo risultato).

Mediana e statistiche d’ordine (Cap.10). Terminologia: L’ i-esima statistica d’ordine di un insieme di elementi è l’i-esimo elemento più piccolo dell’insieme. Il minimo è la prima statistica d’ordine quindi con i=1 e il massimo è l’n-esima statistica d’ordine quindi i=n. Terminologia anglosassone dove ‘i-esima statistica d’ordine’ corrisponde ad ‘i-esimo elemento’.

Tra le piu’ importanti statistiche d’ordine c’e’ Il mediano: è in posizione i=(n+1)/2 quando n è dispari, con array ordinato. Quando n è pari ci sono due mediani: uno in posizione n/2 e l’altro in posizione (n/2)+1; oppure scegliamo uno dei due cioe’ quello che occupa la posizione tetto di n/2. Se vogliamo usare base e tetto prendiamo ë(n+1)/2û quando n è pari oppure é(n+1)/2ù quando è dispari.

Quello che vediamo e’ il problema della selezione dell’i-esima statistica d’ordine da un insieme di n numeri non necessariamente tutti distinti. Avrà in input un insieme A di n numeri ed un numero i con 1 ≤ i ≤ n. In output avremo l’elemento x che sarà più grande di ‘i–1’ altri elementi di A, ovvero in posizione i-esima. Il problema della selezione è risolto in tempo O(nlogn) per esempio ordinando gli elementi con uno degli algoritmi visti. L’obiettivo e’ di trovare l’elemento senza ordinare e risparmiando tempo, magari in tempo lineare.

Prima di vedere il problema della selezione vediamo il problema di identificare min, max od entrambi di un insieme di elementi. Abbiamo gia’ visto che abbiamo un lower bound di n-1 confronti per trovare min o max. Per trovare entrambi abbiamo un totale di 2(n-1), ora se confronto due elementi tra loro e succesivamente con il min or max faccio meno confronti 3én/2ù passando quindi da una costante 2 a 3/2.

Ci sono approcci che migliorano significativamente. Partendo dal problema: un problema numerico fondamentale è la moltiplicazione di due matrici. E’ facile vedere che l’algoritmo richiede tempo dell’ordine di O(n3). Fino alla fine degli anni ’60 il tempo richiesto era Ω(n3) ma poi Strassen (Algoritmo di Strassen Cap.31) mostrò che si poteva usare un tempo inferiore con la tecnica divide et impera cioè divideva le matrici in 4 quadranti/sottomatrici più piccole, ed ottenendo 7 moltiplicazioni invece di 8, con relazione di ricorrenza T(n)=7T(n/2)+O(n2) con soluzione O(n2.81) quindi non e’ necessario tempo cubico per moltiplicare due matrici. Ad oggi si e’ visto un limite di O(n2.376), con estremo inferione Ω(n2); anche se dal punto di vista pratico e’ decisamente/eccessivamente complessso.

Passiamo alla ricerca dell’i-esima statistica d’ordine. Dove e’ possibile selezionare in tempo attesa lineare. Usando algoritmo di partizionamento (randomizzato) con scelta elemento perno pseudo-casuale. Procedura: ... Complessita’: O(n)

(Cap.23) Per rappresentare grafi in memoria posso utilizzare liste, allora avro’: Metodo delle liste di adiacenza vengono usate per rappresentare i grafi. A ogni elemento vengono aggiunti i vertici adiacenti al nodo. I grafi possono essere rappresentati anche con le matrici di adiacenza: quest’ultima sarà nell’ordine/dimensione di n2 poiché devo rappresentare i nodi sia sulle righe che sulle colonne. Quindi se la complessità in spazio è Θ(n2) in generale il costo in tempo sarà almeno Ω(n2) ma ci sono delle eccezioni anche se rare. Ad esempio nell’esercizio 23.1-6 viene trattato questo caso.

Riassumendo. Per trovare min/max la complessita’ in tempo e’ lineare. Per trovare il massimo e il minimo in modo veloce posso usare un heap. Infatti in prima posizione ho il massimo mentre in ultima posizione ho il minimo.

Θ(n+klogn) quando è lineare in n? Quando k = n/logn quindi k=O(log n)

Qualche considerazione sull’utilizzo della struttura heap anche se non efficiente: costruire heap in tempo lineare+ricerca in tempo logaritmico.

LEZIONE 22di42 del 20/Novembre/2003

Introduzione parte III del corso: strutture di dati (testo pagg. 185-187). Pile, code e loro operazioni (testo §11.1 ed esercizio 11.1-5).

Esercizio 10.1-1: Per trovare il secondo elemento minimo usiamo per esempio l'albero del torneo e vediamo che il tempo per trovarlo è n+élognù-2. Esercizio 10.1-2 Dimostrare che servono é3n/2ù -2 confronti per trovare sia min che max insieme. Termina qui cap.10 e parte seconda del corso/libro.

Parte 3 Corso - Strutture di dati

Gli insieme che mutano nel tempo vengono chiamati insiemi dinamici (finiti). La principale struttura di dati che gestisce insiemi dinamici si chiama convenzionalmente dizionario (l'origine è data da ragioni storiche, anche se non ricorda un dizionario materiale) e le operazioni che si possono fare su un dizionario sono quelle di cancellazione, inserimento e verifica di appartenenza a un insieme. Ricordiamo che un tipo di ‘dato astratto’ è un insieme di dati e di operazioni sui dati stessi.

Un campo dell’oggetto/dato su cui facciamo le operazioni si chiama chiave/puntatore. I dati presenti oltre la chiave si chiamano dati satellite.

In alcuni insiemi le chiavi sono già ordinate, es. i numeri Reali. L’insieme totalmente ordinato soddisfa le proprietà di tricotomia ovvero presi due elementi A e B ci sono soltanto tre possibili casi: A<B, A=B, A>B. Un ordinamento totale ci consente di definire l’elemento minimo dell’insieme. In ambito matematico con insiemi infiniti non avrebbe senso (potrebbe essere non definito) definire il massimo e il minimo mentre in un ambito informatico (pragmatico/implementato) ha senso.

Le operazioni su insiemi dinamici possono essere divise in due categorie di operazioni di lettura/query e di scrittura/modify:

Search(S,k) Dato un insieme S e la chiave k restituisce un puntatore x in cui key[x]=k oppure NIL. Insert(S,x) Dato un insieme S inserisce l'elemento puntato da x. Delete(S,x) Dato un insieme S e un puntatore x toglie l'elemento puntato. Minimum(S) Restituisce la chiave più piccola di S. Maximum(S) Restituisce la chiave più grande di S. Successor(S,x) Restituisce il successore dell'elemento x, dove l’insieme e’ totalmente ordinato. Predecessor(S,x) Restituisce il predecessore dell'elemento x, dove l’insieme e’ totalmente ordinato.

Il tempo per eseguire un'operazione su insiemi è di solito misurato in funzione della dimensione/cardinalità dell'insieme che viene fornita come argomento.

Strutture di dati elementari: Pile e Code

Il punto di accesso alla pila/stack è unico, mentre alla coda/queue ho un accesso all’inizio ed uno alla fine. La gestione nella pila è LIFO Last In First Out, mentre nella coda è FIFO First In First Out. Nella pila l'operazione di inserimento è chiamata push e quella di estrazione/cancellazione è chiamata pop.

Come si realizzano queste strutture in un ambiente dove non siano gia’ previste/proposte?

Come si realizza pila con array? Visto che c'è un unico punto di accesso ci basta definire un'unica variabile Top(S)=puntatore, per lo stack S, la quale punti all'ultima posizione in cui abbiamo inserito un elemento nella nostra pila. L’ultimo elemento e’ anche il totale degli elementi presenti nello stack.

Se si fa un’operazione di pop su una pila vuota si va in underflow mentre se si fa un' operazione di push su una pila che è al massimo della dimensione si va in overflow.

Tutte le operazioni sullo stack/pila richiedono tempo costante O(1).

Nella coda l'operazione di inserimento su una coda è chiamata enqueue/put e quella di cancellazione si chiama dequeue/get. La coda e’ implementata/realizzata sempre un con array e due puntatori alla testa/inizio=primo elemento della coda ed alla fine=prossimo elemento libero, sempre entro i limiti dell’array.

L'elemento che viene estratto è sempre quello in testa alla coda. Si procede in modo circolare quindi quando finisco la lunghezza dell'array torno al primo elemento.

Esercizio 11.1.-5 come riassunto: punti di accesso per lista, coda, doppia coda(coda a due vie).

[Quali strutture conbinatorie (permutazioni) e’ possibile creare partendo da pila, coda o doppia coda? Con pile posso ottenere permutazioni diverse da quelle iniziali.]

Per cambiare argomento vediamo il problema delle celebrita’: modo per rifrasare problema cap.23.1-6

Ora che sappiamo cosa sono stack, code vediamo come possiamo rappresentare/implementare grafi in una struttura dati. Ricordiamo che grafo e’ un insieme (V=Vertici, E=Lati). Ci sono due modi canonici per rappresentare i grafi: uno con le matrici (nxn) di adiacenza e l'altro con collezione di liste di adiacenza (tante liste quanti sono i vertici).

La rappresentazione con le liste di adiacenza si preferisce quando |E| è molto minore (i.e. lineare) di |V2| cioè quando il grafo è sparso (pochi lati). La matrice di adiacenza si usa quando |E| è molto vicino a |V2| cioè quando il grafo è denso (i.e. grafo completo).

Prendendo esempio figura 23.1. Un vertice non e’ adiacente a se stesso (altrimente sarebbe un cappio).

Nella lista ci sono tanti elementi quanti sono i nodi mentre nella matrice se ci sono n nodi la matrice sarà n x n

LEZIONE 23di42 del 21/Novembre/2003

Liste concatenate, con e senza sentinelle (testo §11.2). Puntatori, oggetti ed array (testo §11.3).

Strutture di dati elementari: Liste concatenate (collegate, puntate)

La lista concatenata è una struttura dati in cui gli elementi sono collegati tra loro in qualche modo, per esempio sono organizzati in un ordine lineare. L'ordine di accesso è determinato dai puntatori a ogni oggetto, per esempio il successivo in una determinata direzione, dove non necessariamente le chiavi siano ordinate.

Per esempio abbiamo una chiave che ‘punta’ ad un predecessore e successivo elemento: prev<-chiave->next

Una lista può essere semplice/monodirezionale oppure bidirezionale. Se è semplice si omette il puntatore 'prev' di ogni elemento. Se una lista è ordinata l'ordine lineare della lista corrisponde all'ordine lineare delle chiavi memorizzate negli elementi della lista. In una lista circolare il puntatore 'prev' del primo elemento punta alla coda della lista e il puntatore 'next' dell'ultimo elemento punta alla testa della lista. Fare attenzione nel caso di liste circolari per il rischio di perdere inizio e/o fine.

In una lista posso fare le operazioni: - di ricerca con caso medio e peggiore Θ(n) mentre nel caso migliore e’ tempo costante O(1) - di inserimento (tipicamente in testa) con tempo di esecuzione O(1) - di cancellazione con tempo di esecuzione O(1) con Θ(n) per ricercare elemento specifico

Nelle liste concatenate per semplificare la procedura di cancellazione ed evitare i controlli nei casi limite sulla testa e sulla coda uso delle sentinelle. Quindi la lista circolare non e’ chiusa su se stessa ma su oggetto fittizio=sentinella, ovvero non ho puntatori NIL ma punto in quel caso alla sentinella. In questo modo rimuovo i casi particolari, nelle posizioni agli estremi della lista, il puntatore NIL e’ tra la coda e la testa. L'uso delle sentinelle non velocizza necessariamente l'esecuzione del codice tuttavia lo rende molto più leggibile/chiaro/semplice. Il valore della chiave nella sentinella potrebbe essere -1.

Esercizio 11.2-5 Come si fa un'unione di due insiemi disgiunti usando una lista e facendolo in tempo costante?

Come implementare liste concatenate quando non ho puntatori a disposizione nell’ambiente di programmazione? Usando una rappresentazione di oggetti tramite array multipli, ovvero usando un array per ogni campo. Per esempio gli array prev, key, next. Oppure usando una rappresentazione degli oggetti con un unico array, ovvero prendiamo per esempio tre posizioni in un unico array. Dove ogni elemento di una lista occupa una porzione contigua di tre elementi nell'array quindi è un sottoarray di tre elementi con il primo elemento che punta al predecessore, il secondo è la chiave e il terzo è il puntatore a 'next'.

Allocare e liberare oggetti/memoria: in alcuni sistemi con ‘garbage collector’, oppure liberando la memoria quando ho terminato di utilizzarla (ovvero tenendo una lista ‘libera/ombra’ di elementi che sono stati utilizzati e poi rilasciati/liberati).

§11.4 Rappresentazione di alberi con radice con numero di figli non noto a priori. Rappresentazione di alberi binari avra’ puntatore nodo sx e puntatore nodo dx. Se i figli sono di numero indeterminato, comunque pensiamo ad un albero ordinato.

LEZIONE 24di42 del 25/Novembre/2003

Strutture ad albero. Rappresentazione di alberi ordinati, alberi binari (appunti: "Grafi e alberi" §2.3, §2.4). Rappresentazione di alberi mediante un'unica parola binaria (appunti: "Grafi e alberi" §2.5). Alberi radicati (testo §11.4).

Ripasso su cancellazione elementi in una lista. Ultimiamo Cap.11 con Strutture di dati elementari: Strutture ad Albero

Ricordando un albero ordinato ristretto a k figli ovvero un alfabeto con k simboli [0,1,..., k-1]. Possiamo dunque rappresentare con un linguaggio L un albero ordinato ristretto a k figli? Dovremo usare un alfabeto con k simboli, per esempio {0,1, ...,k – 1}, e poi dovremo imporre che se xjÎL, allora anche xiÎL per 0 ≤i<j, perché non vogliamo lasciare “buchi” tra i figli: se c’è j-esimo figlio, ci devono essere anche tutti i fratelli che lo precedono. Naturalmente dobbiamo mantenere anche l’ereditarietà. Anzi, possiamo vedere le proprietà necessarie come un’estensione dell’ereditarietà, e formulare la regola come segue: se xjÎL e j>0, allora anche xiÎL con i=j-1; se invece j=0, allora dev’essere xÎL. Un esempio chiarirà eventuali dubbi. Il linguaggio {ε, 0, 1, 2, 00, 01, 20, 21, 000, 001, 010, 0010} rappresenta l’albero ordinato (ristretto a 3 figli) della figura 5.6(a). Un utile esercizio può essere quello di rappresentare come linguaggio l’albero della figura 5.6(b). Non ci resta da compiere che un ultimo passo, per definire alberi ordinati generici, ossia in cui il numero di figli di ciascun nodo è arbitrario (o meglio non è noto a priori): in questo caso, non possiamo prestabilire la cardinalità dell’alfabeto e siamo costretti ad assumere un alfabeto infinito, costituito dall’insieme N dei numeri naturali {0,1,2,...}. Un qualsiasi albero ordinato finito userà comunque, di fatto, un alfabeto finito, e quindi in pratica l’unico eventuale problema è dato dalla necessità di usare interi con più cifre. Un intero costituito da più cifre nella rappresentazione scelta (decimale o no) va pensato come un unico simbolo e l’intero i rappresenta sempre l’(i +1)-esimo figlio di un dato nodo. Il grado di un nodo x in un albero ordinato è sempre il numero dei figli e, se non è 0, è il massimo i tale che xi Î L, aumentato di 1, dato che il primo figlio è etichettato con 0. Un qualsiasi albero libero può spesso essere pensato come un albero radicato, scegliendo arbitrariamente un nodo come radice. Allo stesso modo, un albero radicato può essere pensato come un albero ordinato, fissando un ordine arbitrario per i figli. In entrambi i casi abbiamo il problema di alfabeti potenzialmente grandi e comunque non fissati a priori. Abbiamo già detto che non ci interessa, in questo ambito teorico, risparmiare memoria, possiamo quindi cercare di rappresentare i simboli che ci occorrono con un alfabeto più piccolo, senza preoccuparci dell’efficienza. Qual è l’alfabeto più piccolo che possiamo usare? Sorprendentemente, la soluzione più estrema e inefficiente, quella di usare un alfabeto con un solo simbolo, ossia una rappresentazione unaria, fornisce risultati interessanti, che, adeguatamente reinterpretati, si rivelano utili anche dal punto di vista pratico, come ora mostriamo.[… vedi appunti Torelli: "Grafi e alberi §2.4"] Dunque ogni albero (ordinato) può essere rappresentato come un albero binario! §2.5 Quanti bit stiamo usando per rappresentare un albero con n nodi? Esattamente 2n–2=2bit *[n-1]lati (due bit per nodo, esclusa la radice): una rappresentazione decisamente compatta! Inoltre l’idea di associare gli 1 ai nodi fa sorgere spontanea la domanda di cosa associare agli 0. C’è qualche struttura in cui vi siano nodi di due tipi, uno a cui associare gli 1 e un altro a cui associare gli 0? Ci sono in sostanza gli alberi pienamente binari (si veda a pagina 89 del testo), che vanno intesi come alberi con nodi "veri" (interni), quelli con 2 figli, a cui associamo il bit 1, e nodi "falsi" (esterni), senza figli, cui associamo il bit 0. Da un punto di vista astratto sono banali alberi binari in cui non ci sono nodi con un solo figlio, mentre dal punto di vista informatico sono gli alberi binari che si costruiscono effettivamente in memoria, in cui i nodi "veri" sono quelli puntati da puntatori, mentre quelli "finti" corrispondono ai puntatori NIL. In qualsiasi albero binario, il numero di nodi senza figli supera di uno il numero di nodi con due figli, ovvero negli alberi pienamente binari, i nodi esterni sono sempre uno in più dei nodi interni., con n foglie ho n-1 nodi interni. Il risultato interessante è che anche in questo modo ritroviamo la corrispondenza biunivoca tra alberi ordinati con n + 1 nodi e alberi binari con n nodi, già vista nel §2.4 di queste note: l'albero binario con n nodi si ottiene da quello pienamente binario… ignorando i "falsi" nodi esterni.

LEZIONE 25di42 del 27/Novembre/2003

Un esempio di rappresentazione "esotica" degli alberi: i numeri di Matula (si veda, per esempio, l'articolo accessibile dall'indirizzo http://www.math.ethz.ch/EMIS/journals/PIMB/067/3.html) Tabelle e funzioni hash. Indirizzamento diretto vs. in-diretto (§12.1).Hash per concatenazione (testo §12.2).

Fino al Min.25:00 Riassunto lezione 24 del 25 Nov 2003 - Rappresentazioni binarie di alberi - Alberi binari=linguaggi ereditari - Alberi ordinati con notazione unaria + ’0’

Prossimo argomento: Funzioni Hash.

Molte applicazioni necessitano di insiemi dinamici in cui le operazioni richieste sono inserimento, cancellazione e ricerca (non successore, predecessore etc); le tabelle hash vanno bene per dizionari in cui ci sono questi tipi di operazioni. La cattiva notizia è che un’operazione di ricerca può durare come la ricerca in una lista collegata e quindi dell’ordine di n, Θ(n), nel caso peggiore. La buona notizia è che nella tabella hash viene fatta quasi sempre in tempo costante O(1), sotto assunzioni ragionevoli. La tabella hash è una generalizzazione della semplice nozione di array, usando la chiave come indice.

Le tabelle si chiamano hash perché c'è una funzione hash che trasforma le chiavi in indirizzi. Se c'è l'indirizzamento diretto non c'è bisogno di nessuna funzione hash. Quindi si da’ per scontato che non facciamo l'indirizzamento diretto se vogliamo parlare di hash. Infatti un vecchio nome delle tabelle hash era: tabelle con indirizzamento calcolato oppure tecniche di memorizzazione dispersa. Perche’ l'indice è calcolato a partire dalla chiave, ma non e’ il valore della chiave.Viene da ‘to hash’=sminuzzare/tritare.

§12.1 Tabelle indirizzamento diretto.

§12.2 Tabelle Hash. Come gestire problemi nel caso di collisione di piu’ chiavi nello stesso indirizzo. Se ho un grande universo di chiavi che devono essere messe in una piccola tabella che problemi ho? I problemi nel realizzare una tabella hash sono che chiavi diverse possono andare a finire nello stesso indirizzo. Se dovesse succedere, si attacca una lista all'inizio dell'indirizzo così posso avere più chiavi memorizzate. Se non volessi usare le liste calcolo l’indirizzo a partire dalla chiave e lo inserisco nella posizione giusta se trovo un buco e se la trovo occupata lo inserisco nella successiva. Questo rende la ricerca inefficiente.

§12.3 Funzione Hash. Cos’è una funzione hash? Una funzione hash è una funzione h(k) che trasforma le chiavi k, in indirizzi. La funzione hash deve mappare l’universo U delle chiavi nelle posizioni della tabella hash che tipicamente vanno dalla posizione 0 alla posizione m-1, quindi la tabella e’ un array fino m-1 posizioni. Ha come dominio l’insieme delle chiavi e come condominio le posizioni da 0 a m-1. Quello che rovina l’idea è che due chiavi possono andare a collidere nella stessa posizione. Visto che cardinalita’=|U|>m=dimensione tabella, prima o poi avremo una collisione.

Chiaramente se in una tabella devo mettere m/2 indirizzi le collisioni non per forza devo esserci ma devo calcolare lo stesso una funzione hash ‘perfetta’ che eviti, ovvero gestisca, le collisioni.[esempio del paradosso dei compleanni, bastano 23 persone perche’ probabilita’ di collisione di due persone con lo stesso compleanno sia maggiore nella non-collisione, ovvero supera ½ nella ipotesi di distribuzione omogenea/uniforme dei compleanni].

Le collisioni si gestiscono facilmente con le liste concatenate (Metodo Concatenazione) presenti ad ogni posizione. Nelle posizioni vuote metto un puntatore a NIL mentre nelle altre un puntatore a una lista anche nel caso ci fosse un solo elemento. La cancellazione viene fatta in tempo costante O(1) se abbiamo accesso direttamente all’elemento se invece abbiamo accesso solo alla chiave dobbiamo cercare l’elemento. Poi dopo la cancellazione dobbiamo attaccare successore a predecessore per riunire la lista. Nell’assunzione che le liste non siano troppo lunghe possiamo lasciarle non-ordinate ed inserire sempre in testa, inserendo in tempo costante O(1).

Passiamo ora all’analisi di hashing con concatenazione ovvero quanto saranno lunghe le liste e la ricerca. Le prestazioni di carico dipendono unicamente dal fattore di carico Alpha. Ovvero il numero medio di elementi immagazzinati in una posizione della tabella. Non importa la dimensione della tabella poiché basta guardare il fattore di carico. Inoltre tabelle con dimensioni molto diverse possono avere lo stesso fattore di carico e quindi le stesse prestazioni, paradossale?!

Nel caso peggiore le prestazione della tabella hash con concatenamento sono ‘terribili’: perche’ tutte le chiavi vanno a finire nello stesso slot creando una lista lunga n e quindi l’ordine di ricerca è Θ(n). Nel caso migliore la chiave si trova al primo colpo quindi banale. Nel caso medio entra in gioco il fattore di carico, asintotico alla lunghezza della catena. Le prestazioni della funzione hash nel caso medio dipendono da come la funzione dispone le chiavi bene negli m slot, indipendentemente da dove sono messi gli altri elementi. Questa ipotesi viene chiamata ipotesi dell’uniformità semplice dell’hash. Ovvero in una tabella di m posizioni una chiave ha probabilità 1/m di andare a finire in ogni posizione.

Theorem 12.1&12.2 In una tabella hash in cui le collisioni sono risolte per concatenazione una ricerca senza successo richiede tempo dell’ordine di Θ(1+α) nel caso medio (dobbiamo passare tutta la lista), assumendo l’ipotesi dell’uniformità semplice della funzione hash. Cosa vuol dire Θ(1 + α)? E’ costante o no? Se α è costante allora il tempo è costante ma se α cresce anche il tempo medio di ricerca cresce. Il ‘+1’ si comporta come ‘or logico’ vuol dire che il tempo è costante oppure cresce come α. Esempio il caso in cui α è < 1 il tempo è costante. In una tabella hash in cui le collisioni sono risolte con il concatenamento una ricerca con successo richiede tempo dell’ordine di Θ(1+α) nel caso medio (mediamente non passiamo tutta la tabella, mediamente meta’ della lista) , assumendo l’ipotesi dell’uniformità semplice.

Quindi le ricerche in tabelle con liste (concatenate e non) e’ sempre Θ(1+α).

Sara’ come nel caso medio anche per l’alternativa alle liste concatenate definita ad indirizzamento aperto (Open addressing). Le tabelle hash sono sempre pensate come circolari, quindi le posizioni in fondo non sono svantaggiate rispetto alle prime.

LEZIONE 26di42 del 28/Novembre/2003

Riepilogo dell'hash con concatenazione: la complessità media è sempre Θ(1+α) (testo §12.2). Nota: si può saltare la dimostrazione del teorema 12.2 (basta pensare che mediamente si percorre mezza lista, dunque di lunghezza α/2). Contrariamente a quel che dice il libro, conviene pensare α come una variabile che può crescere all'infinito (se continuo a inserire dati in una tabella di dimensione fissa...), e interpretare Θ(1+α) come: il tempo o è costante Θ(1) o cresce come α. Le collisioni cominciano presto: si veda il paradosso del compleanno (testo §6.6.1). Funzioni hash (testo §12.3: non è richiesta la procedura descritta nella figura 2.4, si rifletta piuttosto su quante cifre decimali deve avere la costante A. Solo un cenno all'hash universale: pagina 216). Hash per divisione.Indirizzamento aperto.

Riassunto sulle tabelle Hash. L'idea delle tabelle hash è di avere un universo di chiavi molto grande, un insieme di ‘chiavi effettivo’ piccolo e di costruirsi una tabella che ‘mappa’ le chiavi, la quale tipicamente indicizzeremo con posizioni da 0 a m-1 ed è , in qulche modo, proporzionale al numero degli elementi che intendiamo inserirci. Può essere più grande o più piccola, poiche’ useremo un calcolo dell’indirizzo partendo dalle chiavi iniziali. Funzioni per ricerca, inserimento o cancellazioni sono semplici. Si possono riorganizzare/ristrutturare le liste in modo tale da ridurre il tempo di ricerca nelle ricerche successive anche senza ordinarla? Se accediamo a un determinato elemento può darsi che lo abbiamo ricercato poiché è particolarmente importante ed è quindi possibile che ci si debba accedere più volte successivamente. Lo porto così sulla testa della lista cancellandolo dalla vecchia posizione, con la speranza che il record in questo modo sia immediatamente accessibile. Sostanzialmente è il principio della cache.

Vediamo ora come costruire concretamente una funzione Hash e Gestione collisioni.

Per fare una buona funzione hash ogni chiave deve corrispondere a ciascuna delle m posizioni in modo equamente probabile. Una buona funzione hash dovrebbe quanto meno soddisfare l’assunzione dell’uniformità semplice. Sebbene ci si debba convincere che le collisioni non siano un fenomeno patologico ci si deve anche convincere che bastano poche chiavi per far verificare le collisioni. A questo proposito possiamo utilizzare il paradosso del compleanno (§6.6.1), dove con k≥23 persone la probabilita’ di collisioni sullo stesso giorno e’>½

Problema. Che cosa facciamo se la chiave che dobbiamo trasformare in un indirizzo è troppo lunga? 1. Se la chiave non è numerica cosa succede? Non ci interessa molto anche perché la rappresentazione dei caratteri, dati non numerici, è binaria e quindi non ci sono particolari problemi. 2. Se la chiave è troppo lunga per ridurre il numero delle cifre basta non prenderle tutte! Si scelgono le parti della chiave che variano maggiormente e che quindi individuano la chiave. Di sicuro su tantissime cifre ci saranno dati ridondanti. Per esempio nel codice fiscale (16 caratteri) la parte numerica che individua la città è uguale per tutti quindi posso escluderla. 3. Se non so quali sono le parti che cambiano maggiormente posso prendere tutti i bit e li "ripiego" su se stessi più volte con funzioni che abbiano senso su singoli bit ad esempio con funzioni AND ed OR anche se non vanno bene perche’ così vengono fuori o tutti 0 o tutti 1. Quindi ci vuole una funzione booleana che privilegi sia 0 che 1; ad esempio ‘or esculsivo’ XOR.Tecnica del folding.

Metodo della Divisione (per realizzare la funzione Hash).

Metodo piu’ semplice per ottenere indirizzo nell’intervallo 0-1 e’ prendere la chiave, calcolarla/convertirla modulo m dove m e’ la dimensione della tabella. E dove m e’ il resto della divisione. Per definire la funzione hash si fa corrispondere una chiave k a una delle m posizioni, prendendo il resto della divisione di k per m. Dovrei/devo scegliere la dimensione di m in anticipito sulla funzione hash. Buoni valori per m sono numeri primi non troppo vicini alle potenze di 2. Perché? Più avanti c’è un esempio in cui si vede perché è meglio scegliere dei valori primi. In generale però non è detto che vada bene così, meglio prendere cifre meno significative che cambiano piu’ spesso, esempio numeri matricola. Il difetto del metodo di divisione mappa chiavi vicine in posizioni vicine, quindi non le disperde molto. Se usiamo il metodo di indirizzamento aperto allora questo è un problema. Infatti ci saranno pezzi di tabella vuoti altri molto occupati. Come faccio a risolverlo/migliorarlo? Moltiplico le chiavi ‘iniziale’ per una costante opportuna che poi sarà la distanza tra gli indirizzi (per esempio 11*#matricola).

Metodo della Moltiplicazione (per realizzare la funzione Hash).

Il metodo della moltiplicazione funziona in due parti: 1.Moltiplico la chiave k per una costante 0<A<1, quindi costante frazionaria. 2.Tolgo la parte frazionaria di kA e moltiplico il valore per m e prendiamo la base del risultato. La funzione hash si esprime così: h(k) = ëm(kA mod 1)û dove ( kA mod 1 ) è la parte frazionaria di kA. A questo punto posso usare anche m potenza di 2, m=2*integer. La costante A come deve essere scelta? Deve essere scelta in modo adeguato perche’ se viene scelta male il numero di collisioni sarà elevato. Si deve scegliere A in modo tale che abbia un numero ragionevole/limitato di cifre decimali (almeno una decina, magari non regolari,…).

Hash Universale ( Solo cenni senza entrare in dettaglio. Non chiesta all’esame) Se un avversario malintenzionato, che vuol far andar male le cose, dovesse scegliere le chiavi da essere messe in una tabella hash potrebbe scegliere le chiavi che vanno tutte a finire in uno stesso slot. Per esempio basta sapere qual è il modulo della funzione hash e prendere le chiavi di modo tale che escano multipli della posizione. Come si fa a far andar bene il benchmark/test anche se l’avversario conosce la funzione hash ed il modulo ? Si deve usare la funzione hash in modo casuale (come con quicksort), con un generatore pseudo casuale. Questo approccio detto dell’Hash Universale da risultati in media buoni.

§12.4 Indirizzamento Aperto.

Nell'indirizzamento aperto tutti gli elementi della tabella sono memorizzati nella tabella stessa e non in liste concatenate esterne. Aperto perche’ a fronte dell’indirizzo della funzione hash dobbiamo calcolare l’indirizzo effettivo in cui cercare la chiave. Cioè ogni elemento della tabella contiene un elemento dell'insieme dinamico (chiave) oppure NIL, ovvero non ci sono puntatori. Può esserci anche una terza cosa: se una posizione è stata prima occupata e poi cancellata ci devo mettere dentro NIL oppure qualcosa di differente? Contrassegno diverso da NIL. Supponiamo una scansione linerare, pensiamo di avere una chiave che va messa alla posizione 30. Nella posizione 30 c’è però memorizzata un’altra chiave e quindi passo alla posizione 31. La posizione 31 è occupata e quindi passo alla 32 che essendo libera mi permette di memorizzare la chiave. Poniamo il caso che poi la chiave alla posizione 31 venga cancellata e che ci venga inserito NIL. Quando cerco la chiave in posizione 32 arrivo alla posizione 30 non trovo la chiave e passo alla posizione 31. Ma lì ci trovo NIL e quindi interrompo la ricerca poiché altrimenti ci avrei messo la chiave che invece è ancora in posizione 32. E quindi al posto di NIL ci dovrò mettere un’altra cosa, un contrassegno diverso per la cancellazione, poiche’ queste posizioni cancellate possono essere usate per inserire e saltate nella ricerca. Abbiamo una Gestione Ibrida quando mettiamo le concatenzioni all’interno della tabella stessa, ma e’ un approccio confuso. Inoltre l’ordine di scansione non avviene necessariamente con modalita’ lineare, il punto di partenza dipende dalla chiave calcolata dalla funzione hash. Con il metodo dell’indirizzamento aperto richiediamo che per ogni chiavi k la sequenza di scansione sia una permutazione delle posizioni, comunque visitando tutte le posizioni senza saltarne alcuna. La permutazione/scansione dipende dalla funzione hash e da un ulteriore parametro che rappresenta il numero di tentativi per cercare la chiave oppure la posizione libera, ecco il parametro i=indice di tentativo della ricerca.

LEZIONE 27di42 del 2/Dicembre/2003

Indirizzamento aperto (testo §12.4). Scansione lineare, quadratica ed hashing doppio (testo §12.4 e problema 12-4). Analisi dell'hash ad indirizzamento aperto (teorema 12.5 del testo).

§12.4 Indirizzamento Aperto. (continua)

Nell'indirizzamento aperto tutti gli elementi sono memorizzati nella stessa tabella hash [quindi senza liste concatenate]. In pratica ogni elemento della tabella contiene una chiave oppure NIL oppure un contrassegno che dice se quella posizione è stata cancellata/liberata. Nell'indirizzamento aperto non si usano i puntatori [alle liste esterne], risparmiando spazio ma dobbiamo includere tutti gli elementi nella tabella e non nelle liste concatenate. [La ricerca senza successo termina quando si arriva a una posizione vuota. La memoria extra liberata dai puntatori permette di utilizzare più posizioni nella tabella consentendo poche collisioni e un recupero più veloce. Per inserire un elemento nella tabella si fa una scansione e si inserisce l'elemento in una posizione libera.] Quindi per gestire/risolvere le collisioni invece di seguire i puntatori alle liste si deve calcolare la sequenza di posizioni da esaminare. E calcolare l’indirizzo desiderato a partire da quello della funzione hash, partiamo da questo indirizzo e poi seguendo una sequenza di scansione andremo ad esaminare le posizioni ‘successive’. Quindi senza avere un ordine fisso, l’ordine dipendera’ dal metodo di scansione e dalla chiave di partenza. La funzione hash dipendera’ quindi anche dal parametro ‘i’ che indica il numero di tentativi fatti fino al determinato momento. La funzione hash si puo’ quindi dire in ‘k’ ed ‘i’: h(k,i). Ed abbiamo: Algoritmo/codice per Inserimento fino a NIL quindi posizione libera oppure fine tabella con overflow. Algoritmo/codice per Ricerca fino a elemento ricercato nel caso positivo oppure posizione vuota/fine tabella per ricerca negativa. Algoritmo/codice per Cancellazione corrisponde a ricerca con inserimento del contrassegno di cancellazione.

I tempi per la ricerca non dipendono solo dal fattore di carico (per esempio le posizioni cancellate vanno comunque scandite/computate)...

L’Ipotesi dell’uniformita’ nell’hashing nel caso di indirizzamento aperto significa che le possibili scansioni della tabella hanno tutte probabilita’ 1/m! (dove m! sono tutte le possibili permutazioni della tabella stessa). In realta’ questo non succede, i tre metodi presentati hanno due m possibili sequenze ed il migliore m2; comunque le prestazioni non sono molto lontane.

Le tre tecniche utilizzate per calcolare la scansione sono: scansione lineare, quadratica ed hashing doppio. Tecniche che dovrebbero garantire che la sequenza ottenuta sia una permutazione delle posizioni della tabella, la migliore dal punto di vista dell’uniformita’ e’ il doppio hashing con m2 sequenze.

Hash ad indirizzamento aperto. Dopo ‘i’ tentativi la funzione e’ rapprensentabile come:

h(k,i) = [h’(k) + f(i) h’’(k)]mod m, con h’ h’’ due funzioni hash, e con i casi:

caso 1. scansione lineare: f(i)=i and h’’=1 [cioe’ h’’ non esiste, e’ costante] -> h(k,i)=[h’(k)+i] mod m Quindi visitiamo tutta la tabella ed occupiamo/addensiamo la tabella ‘contiguamente’, vedi agglomerazione. Avro’ m possibili sequenze/scansioni partendo dalla posizione iniziale. Facile da implementare ma soffre di clustering/agglomerazione che incrementa il tempo di ricerca.

caso 2 scansione quadratica: dove f(i) e’ quadratica per esempio i2, tipo ‘canguro’ con il rischio di ripetere salti oppure saltare posizioni. Prob12.4 esempio che permette di passare tutta le posizioni una ed una sola volta. Funziona meglio della scansione lineare, ma per coprire tutta la tabella siamo vincolati sui parametri c1, c2 dove m e’ potenza di 2 [m=2*integer] e prendiamo c1 e c2 entrambi uguali ad ½. Dove le sequenze di scansione sono soltanto m [dipende solo dal punto di inizio] e non m!, con agglomerazione chiamata secondaria.

caso 3. hashing doppio: con f(i)=i and h’’=h2(k) con una reale seconda funzione hash, molto probabilmente torneremo al punto di partenza senza visitare tutta la tabella. Il problema nasce quando mi sposto di una quantita’ che e‘ un divisore della dimensione della tabella, o piu’ in generale quando la dimensione della tabella e quella dello spostamento hanno divisori in comune. Per risolverlo possiamo cambiare la dimensione della tabella, per esempio con numero primo. Ho due funzioni che definiscono punto di inizio/partenza e spostamento/scostamento ed entrambi dipendono da chiave iniziale. Esempio Fig.12.5. E’ un miglioramento su hash quadratico perche’ ci sono circa n2 possibili permutazioni.

Analisi dei metodi di hash con indirizzamento aperto. Cosi come nei metodi di concatenazione tutto dipende dal fattore di carico alpha α, in particolare nel caso medio. Nel caso peggiore siamo nell’ordine di n, per ricerche con successo ed anche per non-successo. Nell’indirizzamento aperto abbiamo un elemento per posizione quindi n<m, e α= <1; dove ci sara’ sempre una posizione vuota, per non avere ricerche che vadano all’infinito. Theo.12.5 Il numero atteso di accessi alla tabella nel caso di ricerca senza-successo e’

LEZIONE 28di42 del 4/Dicembre/2003

Alberi binari di ricerca (ABR) e ricerche in un albero binario di ricerca. Algoritmi di visita degli alberi (inclusa la visita per livelli: § 13.1). Alberi binari di ricerca:se figlio sx è < del padre e ogni figlio dx è > non è necessariamente di ricerca! (§ 13.1).

Fino al 42:00 Riassunto lezione precedente. Teo.12.5 Numero medio di accesso per ricerca nei metodi hash ad indirizzamento aperto [con ipotesi uniformita’]: - caso successo:  ; [logaritmo naturale] con α<1;se α=1 allora numero accessi=(m+1)/2 - caso senza-successo: α=n/m<1, allora numero atteso confronti=1/1-α; questo anche nel caso dell’inserimento Terminiamo qui le tabelle hash.

Cap13. Alberi binari di ricerca. Cosa da NON DIRE all'esame: nel caso peggiore un albero binario di ricerca richiede per una ricerca logn confronti (sciocchezza) dato che le operazioni base su un albero binario di ricerca richiedono tempo proporzionale alla lunghezza dell'albero (che potrebbe essere n). Mentre e’ vero che se un albero ha tutti i nodi ovvero è completo ed è bilanciato allora le operazioni vengono fatte in tempi dell’ordine di Θ(logn). Il caso peggiore è quello in cui ogni nodo ha solo un figlio tranne l’ultimo cioè quando è una foglia. Questo albero è rappresentato con un ramo (catena lineare di n nodi, albero con una sola foglia) e i tempi sono nell’ordine di Θ(n) mentre la costruzione di un ramo richiede tempo quadratico sempre per la somma di Gauss. Per evitare il caso peggiore vedremo successivamente le tecniche di bilanciamento. L’altezza di un albero binario di ricerca costruito “a caso” è nell’ordine di O(logn).

Alberi binari di ricerca (ABR): sono strutture di dati che consentono tutte le operazioni su insiemi dinamici. Si hanno sia le prestazioni di un dizionario sia quelle di una coda con priorita’. Un albero in cui ogni figlio sinistro è minore del padre e ogni figlio destro è maggiore NON è necessariamente di ricerca! Si deve usare la parola sottoalbero. Un albero binario di ricerca è un albero binario in cui le chiavi sono sempre memorizzate di modo tale da soddisfare la proprietà dell'albero binario di ricerca. Ovvero, se x è un nodo in un ABR e y è un nodo del sottoalbero sinistro allora y deve essere minore o uguale a x. Se y è un nodo del sottoalbero destro allora è maggiore o uguale di x. Quindi questo vale per ogni sottoalbero sx e dx e non solo per i singoli nodi, vedi esempio 10-20. Modalita’ di visita degli alberi, di ricerca e non, binari e non: - in pre-ordine (ordine anticipato; Radice Sx Dx) ovvero si elencano/elaborano i nodi appena si incontrano andando dall’alto al basso da sx a dx (verso sinistra), ricorda esempio labirinto. - in post-ordine (ordine differito; SDR) elenco i nodi quando li lascio, prima i nodi di sinistra poi quelli di destra e poi la radice.Quindi dal basso verso l’alto, da sx a dx, dalle foglie alla radice. - in-ordine (ordine simmetrico, per alberi binari, SRD) prima nodo di sinistra poi radice poi nodo di destra.Facciamo la proiezione dell’albero, e viene fuori una lista ordinata dei nodi. - per livelli: la radice poi il primo livello da sx a dx, seguito dal secondo livello da sx a dx, etc Le procedure ricorsive sono particolarmente adatte in queste viste, soprattutto per in-ordine ma anche per pre/post ordine. Le chiavi uguali sul libro vengono messe a destra ma questa cosa va bene? Se cominciamo a mettere le chiavi uguali solo da una parte si rischierebbe di avere un albero bilanciato sulla destra e così è meglio metterle da entrambe le parti. Un albero bilanciato è un albero in cui il numero dei nodi a sinistra è uguale a quello dei nodi a destra. Decidiamo se mettere le chiavi uguali a sx oppure a dx?Dipende perche’ sbilancia l’albero ma e’ piu’ facile cercare le chiavi uguali.

§ 13.2 Ricerche in un albero binario di ricerca Prendiamo un ABR e consideriamo un nodo ad esempio prendiamo la radice. Dove trovo il predecessore e il successore (e’ il successore nella visita in ordine simmetrico)? Il successore è il minimo del sottoalbero destro. Se non ci fosse il sottoalbero destro allora devo risalire fino a quando si trova un nodo che è il massimo del sottoalbero in cui c’è il nodo di cui si vuole trovare il successore. In un albero di ricerca il minimo è la foglia + a sx ed il massimo quella a + a dx. La ricerca di un elemento è molto semplice dato che partendo dalla radice confronto le chiavi e decido se scendere a destra o sinistra.La complessita’ della ricerca e’ O(h) ovvero O(altezza dell’albero, logn).

LEZIONE 29di42 del 5/Dicembre/2003

Operazioni sugli alberi binari di ricerca (inserimento e cancellazione: § 13.2 e 13.3). Alberi lessicografici, alberi Tries. Per l'esercizio 13.4-2 e problema 13-4 (sui numeri di Catalan si può consultare per esempio http://www.geometer.org/mathcircles/catalan.pdf oppure http://www.maths.usyd.edu.au:8000/u/kooc/catalan.html)

Tornando agli alberi binari di ricerca vediamo come fare l’Inserimento:se la chiave da inserire è minore basta scendere a sx, oppure dx se maggiore; il caso e’ semplice poiche’ si inserisce sempre una foglia con puntatore a NIL. Il numero di confronti è O(h), rispetto all'altezza dell'albero.

La cancellazione è più difficile poiche’ devo ri-ottenere sempre la struttura e le proprieta’ dell’albero e quindi devo stare attento a quello che c’è sotto il nodo che cancello. Quando cancello un nodo che è la radice di un sottoalbero devo ripristinare le proprietà del sottoalbero e quindi dovrò mettere il successore rispetto a quel nodo. Ci sono tre casi Fig.13.4: a. il nodo e’ una foglia quindi si cancella inserendo il puntatore NIL nel padre del nodo da canc. b. il nodo ha un solo figlio [e’ come una lista] quindi si collega il padre ad il figlio del nodo da canc. c. il nodo ha due figli si sostiuisce il successore al nodo da canc.mantenendo la proprieta’. Il successore è il minimo del sottoalbero destro. Se non ci fosse il sottoalbero destro allora devo risalire fino a quando si trova un nodo che è il massimo del sottoalbero in cui c’è il nodo di cui si vuole trovare il successore.[Nel ns caso di alberi binari il sottoalbero dx c’e’ oppure siamo in una foglia] Anche la cancellazione, cosi come inserimento, viene fatta in tempo O(h) su un albero binario di ricerca di altezza h, dove h=O(logn). Quanti sono gli alberi con n nodi (binari e non)?Difficile da calcolarare.

Alberi lessicografici (Radix trees, Alberi stringa): rispettano l’ordine lessicografico, date due stringhe ‘a’, ‘b’ di caratteri di lunghezza p1, p2 dove i caratteri sono ordinati. Possiamo dire che ‘a’ lessicograficamente precede/minore di ‘b’ se i simboli in ‘a’ da un certo punto in poi sono < di b oppure ‘a’ e’ piu’ corta di ‘b’. Sono strutture alberi utili per fare ricerca, tipicamente ricerca digitale dove la ricerca non e’ per confronti ma per digit/bit. Buon metodo perche’ confronta bit, ovvero la lunghezza della chiave.

Alberi tries (pron:trais, da retrieval): sono strutture ad albero per la ricerca digitale seguendo i bit. Riferimento ad Alberi Patricia.

Riprendiamo il Problema dei conigli [Fibonacci],[inoltre c’e’ connessione tra il problema e gli alberi]: “Se una coppia di conigli matura in un mese e genera una nuova coppia ogni mese successivo, quante coppie ci saranno in un anno, partendo da una coppia giovane?” Mese: 1 2 3 4... Coppie: 1 1 2 3...

Ed allora valgono le relazioni di ricorrenza con g=giovani ed m=maturi dove:

- g(0) = 1; m(0) = 0 - g(k) = m(k-1); per k>0 le coppie di conigli giovani al tempo k sono tante quante le coppie di conigli maturi al tempo k-1;perche’ ogni coppia di conigli maturi genera una coppia di conigli giovani - m(k) = m(k-1) + g(k-1); per k>0

Concretamente si rappresenta con un albero delle coppie a 12 mesi, dove fare attenzione per non fare tante operazioni quanti sono i conigli. Per il problema dei conigli guardiamo la serie di Fibonacci dove ogni argomento e’ la somma dei due precedenti oltre le condizioni iniziali :con f(0)=0 f(1)=1 quindi f(k)=f(k-1) + f(k-2).

LEZIONE 30di42 del 9/Dicembre/2003

Cenni alberi AVL. Alberi lessicografici (prob 13-2). Calcolo n-esimo numero Fibonacci. Cenni Eulero-Binet. Gli RB-alberi, anche come estensioni di strutture dati (introduzione cap.15 + § 14.; appunti “A proposito degli Alberi rosso/neri”).http://homes.dsi.unimi.it/~torelli/note.html

Concludere discorso sui nomeri di Fibonacci collegandoli agli Alberi AVL (AVL dal nome dei creatori,1962). Questi alberi erano il primo esempio in letteratura di alberi di ricerca bilanciati. Dove bilanciati significa che per ogni nodo x la differenza del sottoalbero sx e dx e’ max 1, ... L’albero AVL th con il minimo numero di nodi ed altezza h puo’ essere espresso con una relazione di ricorrenza che richiama quella dei numeri di Fibonacci a meno di una costante 1[la radice]: th=th-1 + th-2 + 1, dove t-1=0 e t0=1. Nel caso contassimo le foglie sarebbe ancora piu’ evidente fh=fh-1 + fh-2 dove fo=f1=1 ... Un esempio e’ l’albero di ricorrenza dei conigli (api secondo Knuth).Figli sx sono m=maturi, figli dx sono g=giovani. Ed i figli dx hanno solo figli sx.In questo modo associamo all’albero stringhe binarie 0,1 dove non ci sono mai due 1 consecutivi (due volte un figlio dx che non abbiamo). I numeri di fibonacci contano anche le stringe binarie di lunghezza n che non contengono due 1 consecutivi, e quindi sono < di 2n. Quindi i numeri di Fibonacci crescono meno di 2n. Ora vediamo come ricavare l’n-esimo numero di Fibonacci con una formula ‘chiusa’, senza fare n passaggi. Prima di proseguire risolviamo il problema del Calcolo della potenza ennesima di una matrice/altro.

Per il calcolo efficiente [O(logn)] di Xn definisco di seguito con n>=1: f(1)=x, per esempio x e’ una matrice oppure una base od altro f(2n)=[f(n)]2 f(2n+1)=x f(2n)

Faccio cosi un numero di passi dell’ordine del logn, per esempio per calcolare x15 devo fare 6 passi con le catene binarie che non sono ottime, oppure in 5 passi con catena migliore. Calcolando il risultato come somma di valori precedenti. Numero di operazoni e’ comunque dell’ordine di logn. ... Quindi se potessimo calcolaci l’n-esimo numero di Fibonacci con il prodotto invece delle somme potremmo sperare di calcolarlo in tempo logaritmico invece di lineare, anche se questo metodo funziona solo se l’n rimane costante come per esempio in nn mentre non funziona quando n cambia come in n![fattoriale].

C’e’ quindi un metodo omogeneo di procedere per calcolare l’n-esimo numero di Fibonacci per prodotti? Si, usando il prodotto di matrici, e quindi con numero di operazioni dell’ordine di logn,Θ(logn). Questo metodo e’ utile per calcolare delle potenze anche grandi in maniera efficiente.

Prob.4.6.Ora vediamo come migliorare il risultato riscoprendo La formula di Eulero (1765)-Binet (1843) ricavata elementarmente.

Partiamo dalla definizione dei numeri di Fibonacci: f(0) = 0, f(1) = 1, f(n) = f(n – 1) + f(n – 2) per n > 1 (*)

1) f(n) = f(n – 1) + f(n – 2) ≤ 2 f(n – 1) per n abbastanza grande (di fatto, per n > 1): il metodo iterativo ci dà quindi: f(n) ≤ 2 f(n – 1) ≤ 2 · 2 · f(n – 2) ≤ … ≤ 2k f(n – k) ≤ … ≤ 2n-1 f(1), ovvero limtatata superioremente f(n) = O(2n).

2) Ma non può essere per esempio se fosse f(n) = c · 2n, perché per la ricorrenza dovrebbe essere c · 2n = c · 2n-1 + c · 2n-2 = 3 c · 2n-2 dà 4 c = 3 c, vero solo per c = 0; ed in questo caso non ottengo quello che voglio.Quindi la base non e’ due.

Esiste invece una base Φ≠ 2 per cui valga (*) ? La risposta e’ si, anzi esistono due basi Φ. Vediamo di ricavarli:

Dovrà valere c · Φn = c · Φn-1 + c · Φn-2, c posso semplificarlo,ossia Φ2 = Φ + 1 (**) che ha soluzioni Φ = (1 + √5)/2 ≈ 1.618 (Φ = chiamato rapporto aureo)e Φ' = (1 – √5)/2 ≈ – 0.618. Troppa grazie abbiamo due basi che cercheremo di combinare.

3) Infatti, se prendiamo f(n) = c · Φn + c' · Φ’n, abbiamo 2 costanti c e c' a disposizione per i due valori iniziali f(0) = c + c' = 0 e f(1) = c · Φ + c' · Φ' = 1. Dalla prima ricaviamo c' = – c, dalla seconda f(1) = c · (Φ – Φ') = 1 ricaviamo c = 1/√5, dato che Φ – Φ' = √5. Dunque l’n-esimo numero di Fibonacci: f(n) = 1/√5 (Φn – Φ’n) che è la formula cercata di Eulero-Binet.

4) In conclusione come cresce f(n), f(n) = Θ(Φn), e anche f(n) =ë 0.5 + Φn /√5 û, dato che |Φ’n| < 1, Φ’n → 0 e i segni si alternano.

5) Come mai 1/√5 (Φn – Φ’n) è sempre esattamente intero? A causa dell'equazione (**)Φ2 = Φ + 1, che conviene interpretare come riscrittura Φ2 → Φ + 1. Quindi posso ‘abbassare’ la potenza di Φ riportandola sempre a 1. Φ3 = Φ2 · Φ = (Φ + 1) · Φ = Φ2 + Φ = (Φ + 1) + Φ = 2 Φ + 1, Φ4 = Φ3 · Φ = (2 Φ + 1) · Φ = 2 Φ2 + Φ = 2 (Φ + 1) + Φ = 3 Φ + 2, … in generale Φn = x Φ + y con x e y interi positivi (che, per inciso, sono due numeri di Fibonacci consecutivi), e la stessa cosa vale per l'altra soluzione di (**),Φ’n = x Φ' + y, con gli stessi interi x e y. Ne consegue che Φn – Φ’n = x Φ + y – (x Φ' + y) = x (Φ – Φ') = x√5 e quindi che 1/√5 (Φn – Φ’n) = x è intero (e x = f(n)).

6) L'equazione (**) può essere interpretata come Φ → 1 + 1/Φ e iterando questa riscrittura abbiamo Φ = 1 + 1/Φ = 1 + 1/(1 + 1/Φ) = 1 + 1/(1 + 1/(1 + 1/Φ)) = … che esprime Φ come una frazione continua con infiniti quozienti tutti uguali a 1 (si veda, per esempio, la pagina web:

math.unifi.it/~mugelli/promat/diofanto/fracont.htm). 

7) Interpretando invece (**) come Φ → √(1 + Φ) otteniamo Φ = √(1 + Φ) = √(1 + √(1 + Φ)) = √(1 + √(1 + √(1 + Φ))) = …, un altro modo di ottenere il rapporto aureo

Questo era il modo elementare per ricavare la fomulare di Eulero-Binet cioe’ una formula chiusa per i numeri di Fibonacci. Sul libro viene svolta utilizzando una Funzione generatrice, ovvero un artificio potente per rappresentare una successione (in questo caso i numeri di Fibonacci). ...

Cap.14 Prossimo argomento ovvero, alberi binari di ricerca bilanciati piu’ semplici dei suddetti Alberi AVL. Alberi Red Black. E' un albero [pienamente] binario di ricerca con in più un bit che rappresenta il colore. Quindi nodi colorati rosso/neri con determinati vincoli che vengono ripristinati con regolarita’ per bilanciare l’albero in maniera soddisfaciente con un numero costante di operazioni, dopo singolo sbilanciamento. E’ una tecnica per tenere bilanciato l’albero mantenendo una altezza dell’ordine di O(logn). Si sono sviluppati dagli alberi ‘2-3-4’. La colorazione e’ un artificio per definire vincoli interni all’albero, legami rossi sono interni ai ‘maxi-nodi’ e i legami neri sono quelli esterni. Gli alberi RB assicurano che lo sbilanciamento (per bilanciamento intendiamo la lunghezza di ogni cammino) al massimo è di un fattore due. Quindi il rapporto tra il ramo più corto e quello più lungo non supera 2.

Per mantenere il bilanciamento, con il suddetto fattore doppio, ci sono dei vincoli legati a queste 4 proprietà: 1 - Ogni nodo è rosso o nero 2 - Ogni foglia è nera [quindi i nodi puntati da NIL sono una sentinella, con campo colore nero] 3 - Se un nodo è rosso allora entrambi i suoi figli sono neri. 4 - Ogni cammino semplice da un nodo a una foglia, che sia sua discendente, contiene lo stesso numero di nodi neri. Proprieta’ del bilanciamento. Quindi chi sbilancia l’albero sono/sarebbero i nodi rossi.

I figli di un nodo rosso sono sempre due per rispettare la proprietà quattro/4 e sono sempre neri poiché è un albero pienamente binario. La Black-Altezza è il numero dei nodi neri contenuti in un albero, e’ ben definita poiche’ e’ costante per un qualsiasi cammino.

LEZIONE 31di42 del 11/Dicembre/2003

Cenni Numeri di Catalan. Operazioni sugli RB-alberi (§§14.2 e 14.3: le cancellazioni (§14.4) si possono saltare; sapere quando basta una rotazione e quando ne occorrono due)Appunti “A proposito degli Alberi rosso/neri”).http://homes.dsi.unimi.it/~torelli/note.html

Cominciamo confrontando il numero di alberi binari con n nodi, con la formula dei conigli di Fibonacci. Il libro usa il concetto utile di funzione generatrice per ricavare l'ennesimo numero di Fibonacci. In particolare e’ l’idea di rappresentare mediante una serie di potenze l’intera sequenza di numeri che ci interessano, una funzione generatrice in questo caso dei numeri di Catalan. Dal punto di vista del tipo e forma si chiamano anche come serie di potenze formali, dove ci interessano solo i coefficienti.

Il bello e’ che spesso l’equazione funzionale si puo’ scrivere ‘al volo’ con un po’ di esperienza, nel caso di Fibonacci la funzione generetrice deve rispettare la seguente equazione funzionale:

relazione ricorrenza: Fi = Fi-1 + Fi-2 riscrivibile con potenze di z: Fi zi=z Fi-1 zi-1 + z2 Fi-2 zi-2 ... ...

Torniamo agli Alberi. Premessa: con l’approccio elementare alla formula di Eulero-Binet, ci eravamo chiesti quale era la base Φ che andava bene per esprimere la crescita dell’n-esimo numero di Fibonacci, non cresce come 2n. Se cerchiamo di fare la stessa cosa con gli alberi binari di n nodi non ci si riesce.

Invece il metodo della funzione generatrice funziona molto bene. Problema 13.4. ... ... I numeri di Catalan ci dicono quanti sono gli alberi binari con n nodi. Ed e’ ovviamente sempre intero anche se non evidente. Il numero di alberi con n nodi cresce quasi come 4n, crescita esponenziale. ... ... Riferimento a Teoria delle Specie: modo elegante di interpretare le strutture combinatorie che possono formalizzare le equazioni funzionali suddette. ... ... Tutto quanto suddetto per sostanziare come tutti gli alberi ricerca binari con n nodi fossero equiprobabili oppure equiprobabili le n! permutazione su cui costruire gli alberi.

Cap.14. Torniamo agli Alberi RB con colori per bilanciare albero. Dove la proprieta’ + importante e’ la quarta: “4 - Ogni cammino semplice da un nodo ad una foglia, che sia sua discendente, contiene lo stesso numero di nodi neri. Proprieta’ del bilanciamento. Quindi chi sbilancia l’albero sono/sarebbero i nodi rossi.” Allora per non rovinare il bilanciamento ci serve la terza/3 proprieta’.

Ricordando uno degli esercizi: La proprietà 4 basta farla solo per la radice oppure per ogni nodo? Ovvero se vale per la radice vale anche per gli altri nodi o no? Si, xche’ La proprietà seguente: “ogni cammino semplice dalla radice a una foglia contiene lo stesso numero di nodi neri” implica la proprietà quattro/4 (a pagina 247) del libro (che si riferisce invece a un nodo qualsiasi).

Dimostrazione. Indichiamo con n(xy) il numero di nodi neri che si incontrano lungo il cammino da x a y (senza contare x). Siano r la radice e y e z due foglie qualsiasi: la nostra ipotesi è dunque n(ry) = n(rz). Se x è un qualsiasi nodo interno che ha y e z tra le foglie del sottoalbero di cui è radice, allora vale n(ry) = n(rx) + n(xy), grazie al fatto di aver escluso il nodo x dal computo di n(xy) (altrimenti lo conteremmo due volte, se x è nero). Mostriamo ora che dall’ipotesi discende n(xy) = n(xz). Infatti, n(ry) = n(rz) implica n(rx) + n(xy) = n(rx) + n(xz), dunque, semplificando n(rx), n(xy) = n(xz).

Da queste semplici proprieta’ discende il seguente Teo/Lemma 14.1: un albero RB con n nodi interni ha al massimo altezza 2log(n+1). Il prof. dice che non supera 2log(n).

Da “ A proposito degli Alberi Rosso-Neri” AA 2005/06:

1. La proprietà seguente: “ogni cammino semplice dalla radice ad una foglia contiene lo stesso numero di nodi neri” implica la proprietà 4 (a pagina 247) del libro (che si riferisce invece a un nodo qualsiasi). Dimostrazione. Indichiamo con n(xy) il numero di nodi neri che si incontrano lungo il cammino da x a y (senza contare x). Siano r la radice e y e z due foglie qualsiasi: la nostra ipotesi è dunque n(ry) = n(rz). Se x è un qualsiasi nodo interno che ha y e z tra le foglie del sottoalbero di cui è radice, allora vale n(ry) = n(rx) + n(xy), grazie al fatto di aver escluso il nodo x dal computo di n(xy) (altrimenti lo conteremmo due volte, se x è nero). Mostriamo ora che dall’ipotesi discende n(xy) = n(xz). Infatti, n(ry) = n(rz) implica n(rx) + n(xy) = n(rx) + n(xz), dunque, semplificando n(rx), n(xy) = n(xz).

2. Vogliamo ora dimostrare che l’altezza di un albero rosso-nero con n nodi interni (n ≥ 2) non supera 2ëlog nû, migliorando così leggermente il risultato del lemma 14.1 del libro. Dimostreremo che il nostro limite è stretto (ossia non può essere ridotto, in generale) e anche qualcosa di più preciso, dopo aver caratterizzato gli alberi rosso-neri dal punto di vista combinatorio (ancora una volta tramite un linguaggio). Notiamo esplicitamente che intendiamo prescindere dalle proprietà degli alberi di ricerca: al solito, siamo interessati solo alla forma dell'albero, non al contenuto dei nodi.

Ciò premesso, gli alberi rosso-neri sono alberi pienamente binari (vedere la nota 2 su Grafi e alberi) con nodi interni neri, che rappresenteremo con n, nodi interni rossi, che rappresenteremo con r e nodi esterni (o foglie) neri, che rappresenteremo con f; i nodi esterni contribuiscono sia all’altezza sia alla altezza nera bh dell’albero. Ci sono quattro alberi rosso-neri di base che chiameremo 1-nodo, 2-nodo, 3-nodo e 4-nodo, secondo il numero di nodi esterni. La terminologia si ispira a quella degli alberi 2-3-4: si veda Sedgewick (edizione 1993) §15.1. L'1-nodo è l'albero rosso-nero costituito da un unico nodo esterno f e ha altezza 0.

Il 2-nodo è l'albero rosso-nero costituito da una radice nera e dai suoi due figli, nodi esterni: lo indicheremo con la parola nff che si ottiene visitando l'albero ed elencando i nodi in ordine anticipato (vedi testo a pagina 215 e appunti Grafi e alberi a pagina 12). Il 2-nodo ha altezza e altezza nera uguali a 1.

I 3-nodi sono due, costituiti da una radice nera e da un figlio rosso, che può essere destro o sinistro, più i rispettivi nodi esterni: le parole corrispondenti sono nfrff e nrfff. I 3-nodi hanno altezza 2 e altezza nera 1.

Il 4-nodo è l'albero rosso-nero costituito da una radice nera, due figli rossi e quattro nodi esterni: nrffrff. Anche il 4-nodo, come il 3-nodo, ha altezza 2 e altezza nera 1.

Gli alberi rosso-neri, infine, sono tutti e soli gli alberi che si ottengono da un albero rosso-nero sostituendo simultaneamente tutti i suoi 1-nodi (nodi esterni) con 2-nodi, 3-nodi o 4-nodi. Gli alberi rosso-neri così definiti coincidono con gli alberi rosso-neri del testo perché i 2, 3 o 4-nodi hanno altezza nera 1 e la sostituzione degli 1-nodi con essi aumenta dunque di 1 la altezza nera dell'intero albero, mantenendo costante il numero di nodi neri lungo ciascun ramo. Inoltre, non è possibile creare nodi rossi con figli rossi, come prescritto dalla proprietà 4.

Per esempio, l'albero rosso-nero della figura 13.4(d) del testo è codificato (prescindendo dalle chiavi contenute nei nodi) dalla parola nr nff nrfff r nff nfrff, che si può ottenere semplicemente dal 4-nodo nr f f r f f con le sostituzioni delle f evidenziate dai colori (gli spazi servono solo ad agevolare la percezione dei diversi sottoalberi).

In altre parole, il linguaggio degli alberi rosso-neri è generato da f mediante il sistema di Lindenmayer non deterministico (ricordate i conigli – deterministici – di Fibonacci g → m e m → mg?) che prevede la riscrittura in parallelo di f come nff oppure nfrff oppure nrfff oppure nrffrff (sui sistemi di Lindenmayer, solitamente abbreviati in L-sistemi, si possono vedere i siti http://www.biologie.uni-hamburg.de/b-online/e28_3/lsys.html e http://en.wikipedia.org/wiki/Lindenmayer_system, tra i tanti).

A questo punto non sarebbe difficile contare i possibili alberi rosso-neri con dato numero di nodi interni o foglie (si veda il sito http://www.theory.cs.uvic.ca/~cos/inf/tree/RedBlackTree.html). Ma qui ci interessa invece stabilire il minimo numero n(h) di nodi interni che un albero rosso-nero di altezza h può avere. Grazie alla notazione introdotta precedentemente, tutto risulta molto semplice: per aumentare di 2 l'altezza (non l'altezza nera, che aumenta solo di 1) di un albero rosso-nero inserendo il minimo numero di nodi, basta trasformare un solo 1-nodo in un 3-nodo e tutti gli altri in 2-nodi. Se l'albero rosso-nero aveva il minimo numero n(h) di nodi per l'altezza h, l'albero rosso-nero ottenuto avrà il minimo numero di nodi n(h + 2) per l'altezza h + 2.

La trasformazione f → nff degli 1-nodi in 2-nodi viene fatta per tutte le foglie tranne una: le foglie sono n(h) + 1 (ricordate?), quindi queste trasformazioni aggiungono altri n(h) nodi interni (neri), mentre l’unica trasformazione f → nfrff o f → nrfff di una foglia in un 3-nodo aggiunge altri 2 nodi interni (un n e un r). Dunque n(h + 2) = 2 n(h) + 2, con le ovvie condizioni iniziali n(0) = 0 (l’1-nodo, che non ha nodi interni!) e n(1) = 1 (il 2-nodo). La successione dei primi valori di n(h) è 0, 1, 2, 4, 6, 10, 14, 22, 30, 46, 62, 94, 126, 190, 254, 382, 510, 766, 1022, …, la successione A027383 dell'Encyclopedia of Integer Sequences.

È facile vedere che n(2k) = 2k+1 – 2 (è vero per k=1 e, se vale per k, la ricorrenza dà n(2(k +1)) = 2 n(2k) + 2 = 2(2k+1 – 2) + 2 = 2k+2 – 2, OK) e anche n(2k + 1) = 2k+1 + 2k – 2, oppure n(k + 1) = n(k) + 2ëk/2û, ma ci serve solo la prima relazione.

Se ora supponiamo che un albero rosso-nero abbia n=2k+1 – 2 oppure n = 2k+1 – 1 nodi interni, con k≥1, ëlog nû vale k ed esiste un albero rosso-nero con n nodi avente altezza 2k = 2ëlg nû. Per valori di n più grandi, da 2k+1 sino a 2k+2 – 3, l'altezza vale 2k o 2k + 1 ed è quindi minore di 2ëlg nû = 2k + 2.

In conclusione, l'altezza di un albero rosso-nero con n nodi interni (n≥2) è sempre minore o uguale a 2 ëlog nû e quest'altezza può essere di fatto raggiunta solo se n precede di 1 o 2 unità una potenza di 2. ... Operazioni sugli Alberi RB.

Problema nell’inserimento negli alberi RB ovvero come inserire mantenendo le proprieta’. L’inserimento e’ piu’ facile poiche’ inserisco alla fine del ramo, nella foglia. Quando inserisco un nuovo nodo lo coloro nero o rosso? Rosso, se lo metto nero allora in quel cammino ci sarà un nodo nero in più e quindi viene violata la proprietà quattro/4 e quindi lo dovrò mettere rosso per forza. Ma se il padre del nodo inserito è rosso allora ci saranno dei problemi e quindi devo fare rispettare tutte le proprietà degli RB-Alberi.

Caso 1. Con una visione miope/localmente; oppure albero ‘piccolo’. Cambiano colore (da R a B, da B a R) il padre lo zio e il nonno del nodo inserito. Posso ricorsivamente salire fino alla radice.

Caso 2. Se ritrovo il problema dei rossi consecutivi & nodi allo stesso livello di colore diverso non posso cambiare colore. Ed allora faccio le operazioni del caso due, ovvero faccio una rotazione sx. Il caso due e’ servito xche’ i due nodi rossi erano figlio sx e dx, a zig-zag, c’era un conflitto...la funzione era di allineare i due nodi rossi dalla stessa parte.

Caso 3. Mi ritrovo nel caso 3 ed applico una rotazione dx con ricolorazione.Quindi numero di rotazioni e’ max due, ed il numero di operazioni e’ costante. Questo e’ il grosso vantaggio degli alberi RB rispetto ad altri alberi con numero di operazioni variabile. Ricololazioni sono in numero non costante ma non richiedono lavoro sui puntatori.

[Quando poi ho inserito il nodo rosso devo far si che tutte le proprietà degli RB-Alberi vengano rispettate e quindi dovrò fare delle rotazioni. La prima rotazione allineiamo i due nodi rossi e quando li abbiamo allineati sistemiamo la colorazione dei nodi dell’albero. Le operazioni sono costanti se ci sono da fare solo rotazioni mentre sono proporzionali all’altezza dell’albero nel caso delle ricolorazioni.]

Si preferisce avere la radice nera, ricolorandola e ri-sistemando l’albero; anche se il colore della radice e’ irrilevante non contandola.

Concludendo il risultato fondamentale, e’ che con numero operazioni nel caso di inserimento di O(logn), ora il lemma ci garantiva che l’altezza dell’alberi e’ max 2(logn+1). Sia nel caso che vada da radice a foglie [logn operazioni] e poi debba risalire fino alla radice [altre logn ricolorazioni] con max 2 rotazioni. Il costo delle operazioni e’ max altezza di albero che e’ un logaritmo moltiplicato fattore 2.

LEZIONE 32di42 del 12/Dicembre/2003

I B-alberi e le operazioni su di essi (testo cap.19: introduzione, §§ 19.1 e19.2. Saltare §19.3. Perché nella figura 19.7(d) si spezza la radice?).

Riassunto. Proprieta’ alberi-RB: 1. nodi rossi oppure neri 2. nodi esterni sono foglie nere 3. se un nodo e’ rosso ha due figli neri 4. ogni cammino semplice ha lo stesso numeri di n nodi neri Il principale risultato degli alberi RB e’ che un albero con n nodi interni ha altezza < 2logn. Per mantenere le proprieta’ degli alberi dopo inserimento e cancellazione dobbiamo fare delle operazioni. Nel caso di inserimento potremmo trovarci in una situazione di nodi rossi consecutivi, che dobbiamo ricolorare e/o rotare. Vedi casi 1-2-3. Gli alberi-RB nascono sostanzialmente dagli alberi 2-3-4 puntatori (i.e. dove 2 nodi hanno 3 puntatori esterni al ‘maxi/super nodo’). Fig.14.2 Alberi-RB – Rotazioni. Vengono eseguite nella condizione che la visita in ordine simmetrico non cambia. Per questo i sottoalberti α e β vengono ri-arrangiati e β spostato da x a y, poiche’ era/e’ maggiore di α (quindi a dx di α ) e contemporaneamente minore di y (quindi alla sx di y). Fig.14.5-Fig.14.6 Dove infatti l’ordine simmetrico viene mantenuto. La cancellazione di nodi e’ + complessa dell’inserimento. [non richiesto all’esame].

Insiemi dinamici persistenti ovvero teniamo traccia dei cambiamenti, tenendo una copia di ogni configurazione dalla prima all’ultima. Qual’e’ la soluzione migliore, con minor occupazione di spazio? Registrando solo i cambiamenti.

Cap15. Estensione di strutture dati. L’idea ingegneristica e’: quando necessitiamo di una struttura dati differente da quelle “standard” non serve inventarne una nuova ma verosimilmente si dovrà estendere una struttura dati classica aggiungendo ulteriori informazioni e quindi definire nuove operazioni che permetteranno di ottenere il comportamento richiesto dall’applicazione. Fig.15.1 Per esempio ho un albero RB dove ogni nodo consiene il numero di nodi del relativo sottoalbero. Inoltre vedremo dei casi + avanti, per esempio strutture per la gestione di insiemi disgiunti.

Cap.19 I B-Alberi (pensabili come generalizzazione degli alberi 1-2-3-4, RB senza colore). Sono alberi di ricerca bilanciati (non sono binari, anzi fattore di diramazione molto maggiore di 2) progettati per operazioni su dischi magnetici. La differenza principale con gli alberi-RB è che i B-Alberi possono avere molti figli, e non hanno colori: da decine a migliaia e quindi non sono binari mentre i RB si. Il fattore di diramazione, “grado” di ramificazione di un B-Albero può quindi essere molto elevato. Tenendo presente le caratteristiche del disco l’obiettivo è minimizzare le operazioni di I/O sui dischi, per ridurre tempi di accesso tramite alberi ‘bassi’. Come negli alberi-RB l’altezza dei B-Alberi è dell’ordine di O(logn) e sono bilanciati. Anche se il log e’ in base pari al fattore di diramazione.

Caratterizzazione dei nodi dei B-alberi: Cosa dobbiamo mettere nei nodi dei B-Alberi? Se un nodo x di un B-Albero contiene un numero n[x] di chiavi, allora ha n[x] + 1 figli. Le chiavi di un nodo sono usati come punti di divisione: dividono l’intervallo di chiavi gestito dal nodo x in n[x]+1 (sotto)intervalli, dove ciascun sottointervallo è gestito da un figlio di x. ... I B-alberi sono perfettamente bilanciati poiche’ gli inserimenti si fanno sempre nelle foglie, se il nodo e’ pieno allora posso spezzare il nodo in due (di solito) parti il + possibile uguali, cioe’ contenere lo stesso numero di nodi. Meglio che il numero di chiavi sia dispari, xche’ allora avro’ una chiave mediana che porto sopra in modo tale che i nodi ottenuti siano pari e poi inseriro’ nei nodi ottenuti.

Perché è così importante minimizzare il numero degli accessi a disco? Fig.19.2 Se ad esempio fa 6000 rpm (revolutions per minute) in un secondo fa 100 r e quindi accede ai dati in 1 centesimo di secondo cioe’ 10 millisecondi (10^-3). Gli accessi alla memoria RAM sono dell’ordine dei nanosecondi (10^-9?) quindi un milione di volte più veloci. Ecco perché si devono minimizzare i numeri di accessi a disco. Questo anche se facciamo una ricerca sequenziale (poco sofisticata e complicata) delle chiavi nel nodo, che saranno in RAM e quindi ad accesso molto veloce.

LEZIONE 33di42 del 16/Dicembre/2003

I B-alberi ed operazioni su di essi. Ricerca, creazione, inserimento. Grado ed altezza.

Riassunto. Cap.19 B-Alberi x minimizzare accessi a dischi (memoria secondaria) Il fattore di diramazione dei B-alberi e’ tale che con fattore (# figli) min=T avro’ un fattore max≤2T.Ricordiamo che sono alberi bilanciati che crescono verso l’alto, le foglie/nodo salgono solo se sono la mediana che sale per ‘spezzare’ il nodo.

Riprendiamo un attimo la Fig.14.3 Vediamo il codice per la rotazione a sx (dove rotazione dx e’ analoga). Partiamo da un puntatore all’albero ed al nodo ‘x’ che dobbiamo far ruotare, da cui prendiamo il figlio dx di ‘x’. ...

Definiamo con precisione i diversi aspetti dei B-Alberi, albero con radice: 1. in ogni nodo c’e’ l’informazione che ci dice quante chiavi ci sono nel nodo e quali sono le n[x} chiavi, in ordine per esempio non decrescente 2. c’e’ un valore booleano che dice se il nodo e’ interno o foglia 3. se ‘x’ e’ interno ci sono gli n[x]+1 puntatori ai figli 4. le chiavi separano gli intervalli di chiavi presenti nei sottoalberi 5. ogni foglia ha la stessa profondita’ h, quindi tutte le foglie sono ben allineate sulle stesso livello 6. ci sono un estremo inferiore e superie a quante chiavi un nodo puo’ contenere, grazie al parametro T≥2 chiamato grado minimo del B-albero.Tutti i nodi hanno almeno T-1 chiavi (quindi T figli) ed al massimo 2T-1 chiavi con 2T figli. 7. Un nodo e’ pieno quando contiene 2T-1 chiavi (non necessitiamo di una variabile boolenana) 8. Il valore minimo di T e’ 2 (se fosse minore T-1 sarebbe O, senza significato) che produce gli alberi 2-3-4 (figli)

L’altezza dei B-alberi, valutando nel caso peggiore, quindi il fattore di diramazione e’ ‘t’ per ogni nodo. Teo.19.1 Per ogni n-chiavi≥1 B-alberi con t≥2 allora h<logt (n+1)/2. Attenzione alla base-t.

Dimostriamo il risultato: consideriamo il caso peggiore ovvero quale e’ la max altezza (ovvero il minimo numero di nodi) di un B-albero, lo otteniamo mettendo in radice il minor numero di chiavi cioe’ 1, poi in ogni nodo mettiamo t-1 chiavi al livello 3 avremo quindi 2(t-1) nodi e cosi a seguire dove alla profindita’ h avremo 2t(h-1) con n ≥ 2th-1 che implica il Teo.19.1 e prendendo i log otteniamo proprio il teo.

In un certo senso quindi i B-alberi si comportano con RB con altezza O(logn) dove la vera differenza e’ il fattore t.

§ 19.2 Operazioni base sui B-Alberi sono + interessanti soprattutto se vediamo il codice [Attenzione alle sottigliezze chieste anche all’esame]. Vedremo ricerca, creazione di un albero vuoto e inserimento, la cancellazione non si fa.

Ricordarsi che le procedure presentate sono algoritmi a “singola passata” ovvero che visitano l’albero dalla radice a scendere e non tornano mai sui propri passi. Perché? Abbiamo visto che in un nodo ci sono 1000 chiavi e 1001 puntatori che vanno solo verso il basso e quindi per risalire ci vorrebbero altrettanti puntatori e quindi diventa troppo costoso. Se usiamo questi puntatori di conseguenza non facciamo algoritmi a “singola passata” e non limitiamo gli accessi a disco. Attenzione che lo splitting di un nodo implica che sopra ci sia posto, ma non possiamo/vogliamo risalire e quindi spezziamo il nodo in discesa quando e’ piano.

Ricerca sui B-Alberi è come quella sugli alberi binari solo che le possibili alternative non sono binarie a due vie ma coincidono con i n+1 figli del nodo in esame che contiene n chiavi. Quindi e’ una generalizzazione della ricerca sugli alberi binari normali.Esempio Fig.19.1. Il numero di pagine su disco a cui si accede e’ Θ(h)=Θ(logtn).

Creazione di un B-Albero vuoto. Si deve creare con la procedura B-TREE-CREATE allocando un nodo radice vuoto adatto al ns B-albero; successivamente per inserire le nuove chiavi si richiama la procedura B-TREE-INSERT. L’operazione di creazione richiede quindi quantita’ costanti: O(1) in accesso a disco e O(1) CPU time.

Inserire la chiave in una B-Albero è decisamente più complicata dell’inserimento di una chiave in un albero di ricerca binario; in entrambi i casi si inserisce nelle foglie. Si segue il percorso di ricerca fino alla foglia adeguata e poi si inserisce, il problema e’ quando non c’e’ spazio e dobbiamo ‘splittare/dividere’ il nodo in due nodi ‘ semivuoti’. Mandando su la ‘chiave centrale/mediana’ e si attaccano due puntatori alle minori chiavi a sx e le maggiori chiavi a dx; dopo lo spezzamento avro’ lo spazio per inserire la nuova chiave. Lo spezzamento viene generalmente fatto in fase preventiva.

Vedi Fig.19.7 dove all’inserimento di L viene spezzata la radice con intervento preventivo. Spezziamo i nodi pieni che attraversiamo siano essi nodi interni o foglie.

LEZIONE 34di42 del 18/Dicembre/2003

Rappresentazioni dei grafi (testo §23.1 ed esercizio 23.1-6=il problema della celebrità: un link dallo Utah) http://www.cs.usu.edu/~allanv/cs5050/ch5/ch5.html Strutture di dati: Insiemi disgiunti e loro Operazioni. Applicazione alla determinazione delle componenti connesse di un grafo (§ 22.1). Cenni uso delle foreste per rappresentare insiemi disgiunti (§ 22.3. Solo cenni al §22.2). Unione per rango e compressione dei cammini (§ 22.3).

Lasciamo i B-Alberi ed andiamo al Cap.22 Strutture di dati per insiemi disgiunti. (Estensione degli alberi con puntatori al padre, per rappresentare insiemi disgiunti con un campo per specificare altezza degli alberi e poter fare l’unione efficiente di insiemi disgiunti) Alcune applicazioni richiedono di raggruppare n elementi distinti in una collezione di insiemi disgiunti (insiemi che non hanno elementi in comune), rappresentati con alberi. Le operazioni + importanti saranno: quella di unione degli insiemi e la definire l’appartenza di un elemento ad un insieme (oppure trovare il rappresentante). Vogliamo inoltre distinguere un insieme dall’altro senza dagli un nome. Una cosa interessante e’ che si vedra’ una applicazione dei tipi di dati astratti=dati con operazioni di base. Chiamati infatti Algoritmi Union-Find nella letteratura anglosassone.

§22.1 Una struttura di dati per insiemi disgiunti mantiene/gestisce una collezione S={S1,S2,...,Sk} di insiemi dinamici disgiunti. Dinamici significa che cambiano, tipicamente con la Union, e disgiunti dove presi due elementi/insiemi la loro intersezione e’ vuota. Ogni insieme è identificato da un rappresentante che è semplicemente un membro dell’insieme. In alcune aplicazione non importa [quasi mai] quale sia il rappresentante. Come sempre gli elementi sono oggetti. Le operazioni fondamentali che, definiremo in astratto, sono 3 (di cui una banale:inizializzazione): Make-Set(x) crea un nuovo insieme il cui unico membro (e quindi rappresentante) è x. Dal momento che gli insiemi sono disgiunti dobbiamo richiedere che x non faccia gia’ parte di un altro insieme. Questo perche’ la struttura che andremo a costruire e’ un albero con alcune informazioni nei nodi, in questo caso e’ la radice con il campo che contiene l’altezza dell’albero. Union(x,y) unisce due insiemi dinamici che contengono x e y (x ed y non necessariamente rappresentanti), ad esempio Sx ed Sy, in un nuovo insieme che è l’unione di questi due insiemi, eliminando gli insiemi di partenza. Il rappresentante dell’insieme risultante è un elemento dell’unione Sx U Sy , benché molte realizzazioni di Union scelgano i rappresentanti di Sx o Sy come nuovo rappresentante [per comodita’] posso scegliere un elemento che non era il rappresentante di uno dei due insiemi. Find-Set(x) restituisce un puntatore al rappresentante dell’unico insieme contenente x, unico poiche’ gli insiemi si considerano disgiunti.

Osservazione importante: analizzeremo il tempo di esecuzione in funzione di n=numero di operazioni di make-set e m=numero totale di tutte le operazioni. Poiche’ gli insiemi sono disgiunti ogni Union diminuisce il # di insiemi, quindi posso fare al max n-1 operazioni di Union.

Vediamo una applicazione delle strutture per insiemi disgiunti. Per esempio: determinare le componenti connesse di un grafo non orientato.Fig.22.1. Come puo’ essere sviluppare in astratto la procedura per le componenti connesse.

Le tecniche di visita di un grafo consentono di visitare sistematicamente tutte le componenti connesse di un grafo [nodi], senza perdersi e senza omettere zone. Se c’è un altro grafo scollegato vicino al primo è ovvio che al secondo non ci si arriverà mai. In quel caso se abbiamo un elenco dei vertici vediamo che ci sono altri vertici che non abbiamo visitato sappiamo che c’e’ una componente non connessa e cui dovremmo ‘saltare’. Ora per ogni vertice facciamo una Make-Set e per ogni lato ‘connesso’ facciamo una Union; quando abbiamo finito di unire/analizzare tutti i vertici abbiamo la struttura completa del grafo, vedi Fig.22.1 ... ... Vediamo come realizzare in maniera efficiente questa struttura, un modo ovvio e’ di usare delle liste ovvero ogni componente connessa e’ una lista connessa dei suoi vertici. Anche se non lo vediamo cerchiamo di evincere la struttura dove le operazioni di Make-Set e Find-Set si possono fare in tempo costante O(1), poiche’ la lista e’ organizzata dove ogni elemento ha un puntatore alla testa oltre all’elemento successivo. E l’operazione Union, dove dovro’ aggiornare i puntatori della lista + corta che vado ad ‘aggiungere’, allora il tempo e’ O(m+n logn) con n=#numero elementi cioe’ make-set. § 22.3 Vediamo come fare di meglio usando le ‘foreste’ perche’ ogni insieme disgiunto e’ un albero come in Fig.22.4. Dove i puntatori sono verso il padre e la radice punta a se stessa. Introducendo due euristiche/accorgimenti otteniamo la struttura di dati asintoticamente + veloce conosciuta/possibile. Questo pur di applicare: la “Unione per Rango” e la “Compressione dei Cammini”:

1. Unione per rango/Union by rank. Attaccare albero piccolo sotto la radice dell’albero + grande; quindi far puntare la radice con ‘-‘ nodi alla radice dell’albero con ‘+’ nodi. Dove il rango e’ il limite/estremo superiore dell’altezza del nodo, in generale quindi non e’ l’altezza ed e’ sempre ≥ dell’altezza. Dopo la union aggiorniamo le informazioni contenute nel rappresentante che qui consideriamo la radice. Il rango dei rappresentanti e’ il rango degli alberi, se gli alberi hanno lo stesso rango possiamo scegliere uno dei due. Se ci fossero solo Make and Union il rango sarebbe uguale all’altezza invece non e’ sempre cosi poiche’ il rango puo’ essere cambiato dalla Find. Vediamo come funziona tramite la seconda euristica.

2. Compressione dei Cammini (Euristica semplice ed efficace). Che viene applicata dalla Find-Set, per far si che ogni non nel cammino di accesso punti direttamente alla radice, la compressione del cammino non cambia il rango dell’albero ma ‘schiaccia’ i nodi, di un percorso/cammino di accesso, facendoli puntare direttamente alla radice. Quindi l’altezza potrebbe cambiare, cioe’ ridursi, se questo cammino era il piu’ lungo dell’albero e di conseguenza il rango, che non abbiamo intenzionalmente cambiato/aggiornato, ritrovarsi piu’ lungo/maggiore della nuova altezza. Il codice della Find grazie alla ricorsione e’ estremamente compatto in tre righe di codice. Questo codice di find set procede a ‘due passate’ [facendo su e giu’],poiche per poter assegnare il puntatore a tutti i nodi bisogna prima arrivare alla radice e poi ritornare lungo il percorso/cammino per aggiornare i puntatori.

Come facciamo a valutare il tempo di esecuzione? Usando le due euristiche nel caso peggiore otterremo O(mα(m,n)) dove α(m,n) e’ l’inversa della funzione di Ackermann (l’inversa cresce ‘molto’ lentamente).

Facciamo un passo indietro per capire da dove arriva la Funzione di Ackermann, come facciamo a definire se qualcosa e’ computabile o no? ovvero di formalizzare la definizione di calcolabile per esempio definendo la classe delle funzioni calcolabili, partendo dagli interi: 0. f: Nk -> N 1. ottengo: funzioni base, quali successivo, funzione 0 2. inoltre definisco: composizione di funzioni, ovvero funzioni a cui passo come fattori altre funzioni 3. definsco anche: ricorsione primitiva quindi definisco f(x,n+1) in funzione di f(x,n) quindi f(x,n+1)=h(f(x,n)) dove h e’ una funzione gia’ nota.

Con questi meccanismi non definiamo pero’ tutte le possibili funzioni perche’ ci serve un ulteriore meccanismo di ricorsione, ed Ackermann nel 1928 produce il primo esempio di funzione ricorsiva (cioe’ calcolabile) non primitiva ovvero dove h puo’ essere f stessa; addirittura f dipende da se stessa due volte. In un certo senso la funzione di Ackermann cresce + rapidamente di tutte le funzioni ricorsive, di tutte le funzioni inventabili. Come funziona la Funzione di Ackermann, la quale cresce + rapidamente di tutte le possibili altre funzioni? Fig.22.7 ... ...

LEZIONE 35di42 del 19/Dicembre/2003

Le funzioni ricorsive, la funzione di Ackermann e la sua inversa (testo § 22.4, solo la prima sezione: saltare da "Proprietà dei ranghi" in poi. Per le funzioni ricorsive si può consultare il libro di G. Ausiello et al. http://www.dis.uniroma1.it/~ausiello/InfoTeoRMvo/main.pdf al paragrafo 6.5 oppure http://vigna.dsi.unimi.it/InformaticaTeorica.pdf ). Introduzione Parte IV: Tecniche per progettazione ed analisi: Programmazione dinamica, Algoritmi Greedy.

Riassunto. Strutture di dati per gli insiemi disgiunti con operazioni per strutture di dati astratte: Make, Union, Find per rappresentante. Operazioni utili per trovare componenti connesse di un grafo vedi Fig.22.1. Possiamo realizzare concretamente le tre operazioni in maniera efficiente con liste, meglio con l’euristica dell’unione pesata [liste + corte attaccate alle + lunghe]. Ulteriore miglioramento usando, invece delle liste, gli alberi con entrambe le nuove euristiche: Unione per Rango [attacco l’albero con rango minore ‘sotto’ la radice dell’albero con rango maggiore] e Compressione dei Cammini [tutti i nodi del cammino di accesso puntano alla radice, potenzialmente diminuendo l’altezza dell’albero ma lasciando inalterato il rango, ecco perche’ R≥A]. Rango che aggiorno solo quando faccio Union su alberi con stessa altezza.

Vediamo le prestazioni dell’algoritmo quando usiamo entrambe le euristiche, e nel caso peggiore otterremo O(m α(m,n)) dove α(m,n) e’ l’inversa della funzione di Ackermann; e quindi cresce con ‘esasperante’ lentezza. Addirittura per qualsiasi applicazione si puo’ considerare α(m,n) ≤ 4. Non facciamo la dimostrazione.

La funzione di Ackermann e’ cosi definita sugli interi positivi i, j come potenze iterate: A(1, j) = 2J per j ≥ 2, A(i, 1) = A(i-1,2) per i ≥ 2, A(i, j) = A(i-1,A(i, j-1)) per i, j ≥ 2. Ora l’inversa della Funzione di Ackermann viene definita come [non e’ inversa in senso matematica, cioe’ il loro prodotto non da 1], inversa relativamente alla crescita: α(m,n) = min {i ≥ 1 : A(i, ëm/nû ) > log n}; vuol dire che fissato il valore n ed il suo logaritmo ed in input in valore m, il loro rapporto m/n e’ >1 ne prendo la parte intera e vado sulla riga... ... ... Parte IV Tecniche evolute per la progettazione ed analisi di algoritmi.

In questa parte vedremo nuovi metodi/tecniche per il progettare ed analizzare: Cap.16 Programmazione Dinamica Cap.17 Algoritmi Greedy (vedi algoritmo di Huffman) Cap.18 Analisi Ammortizzata In precedennza abbiamo gia’ visto divide-et-impera, randomizzazione e soluzione delle equazioni di ricorrenza. le nuove tecnice sono un po’ + sofisticate.

1. La programmazione dinamica tipicamente si applica a problemi di ottimizzazione, in cui si deve fare un insiemre di scelte per arrivare ad una soluzione ottima [non necessariamente unica]. La programmazione dinamica non è indicata per risolvere problemi di ordinamento e/o ricerca dove c’e’ una soluzione unica. Per arrivare alla soluzione ottima si fanno delle scelte e vengono fuori dei sottoproblemi dove i parametri sono gli stessi allora la programmazione dinamica e’ efficace quando un sottoproblema si ripresenta da diversi sottoinsiemi. Se lo stesso sottoproblema si ripresenta tante volte la programmazione dinamica è la tecnica migliore perche’ tiene conto dei sottoproblemi appena risolti. Non è sempre alla ricerca di una soluzione ottima, con i numeri di Fibonacci applichiamo questa metodica senza cercare una soluzione ottima. Ma dai due precedenti calcolavamo il corrente e cosi via. Una caratteristica tipica e’ la memorizzazione delle soluzioni intermedie [“memoize”].

2. La differenza tra metodica Algoritmi Greedy e Programmazione Dinamica sono ‘sottili’ nella definizione, dove le Greedy sono + economiche della dinamica nella quale passiamo tutti valori, quindi e’ esauriente/esaustiva poiche’ esauriamo tutte le possibili soluzioni del problema guardando solo quelle ottime soluzioni dei sottoproblemi, risparmiamo un po di lavoro. Con quella Greedy non affrontiamo ‘tutte’ le possibili soluzioni ma trovata quella ‘localmente’ ottima la espandiamo, e quindi non necessariamente funziona sempre.

[Devo ricordare la soluzione dei problemi da qualche parte quindi li devo memorizzare. La tecnica di programmazione dinamica è una tecnica esaustiva a differenza di quella Greedy. Per arrivare alla soluzione ottima si fanno delle scelte non come nella tecnica Greedy che si arriva a una soluzione ottima immediatamente.] A questo punto dovremmo avere un criterio per definire quando una tecnica Greedy raggiunge certamente un risultato ottimo oppure no? Non e’ sempre facile dire se un approccio Greedy sara’ efficace, nel Cap.17 con la Teoria dei Matroidi utile per fare tale determinazione. Se il tipo di problema ha la struttura che corrisponde a quella di un Matroide allora sicuramente l’algoritmo Greedy trova una soluzione ottima. Altrimenti dovremo indagare caso per caso. Esempio di Algoritmo Greedy e’ quello del cambio/resto di monete con numero minimo di monete. Scegliendo il taglio di moneta + grande compatibilemente con il resto rimanente.

3. Riferendoci all’Analisi Ammortizzata possiamo dire che non valutiamo il costo delle singole operazioni, magari non e’ neppure possibile [vedi esempio operazioni su stack push or pop, multipop di arbitrari n elementi da parte dell’utente]. Bensi con metodi che vedremo, per esempio con metodo uno caricando di + le push per avere le multipop gratis/a zero; per esempio con push costo 2=1+1, metodo semplice chiamato degli accantonamenti, costo per ogni operazione. Il secondo metodo e’ [vedi Ackermann] suddivide il costo totale tra tutte le operazioni ovvero se faccio push+pop+multipop avro’ che se faccio n-1 operazioni di push l’operazione di costo massimo multipop costera’ anch’essa n-1, quindi 2(n-1) operazioni con costo medio (2-qualcosa) quindi costo medio ammortizzato. Il terzo metodo del potenziale...assomiglia al primo metodo con una terminologia + ostica

Cap.16 La programmazione dinamica

Programmazione dinamica, cosi come la tecnica divide-et-impera, risolve il problema combinando le soluzioni dei sottoproblemi. Qui programmazione si riferisce ad un metodo tabellare, significa un modo sistematico per costruire una tabella che memorizza/ricorda i valori gia’ calcolati. Divide-et-impera suddivideva il problema in sottoproblemi indipendenti, se i problemi non sono indipendenti ovvero hanno parti in comune non va bene; invece la programmazione dinamica risolve i sottoproblemi e salva le soluzioni in tabella. Le soluzioni ottime posso essere multiple, vedi esempio scacco matto in n modi diversi. Fasi per risolvere un problema con la programmazione dinamica 1. capire/caratterizzare il problema 2. scrivere almeno una soluzione ‘formale’ ricorsiva 3. calcolare le soluzioni con approccio botto-up, dal + piccolo a salire 4. registrare come si e’ arrivati alla soluzione ottima

16.1 L’esempio tipico e’ il prodotto di n matrici, dove c’e’ una notevole differenza sul come effettuiamo i calcoli. Supponendo tre matrici, abbastanza grosse... ... conteggio parentesizzazioni ...

LEZIONE 36di42 del 8/Gennaio/2004

Esempio: il problema del resto (anche il problema 17-1 sul testo). Programmazione dinamica e problemi di ottimizzazione: il prodotto di matrici (testo §16.1).

Riassunto. Programmazione dinamica, con sottoproblemi che si ripetono. Tecniche/Algoritmi Greedy, scelte piu’ facili poiche’ sono ingorde/miopi. Per esempio nel caso di Huffman abbiamo preso i due/caratteri con la frequenza minore da cui costruiamo alberi rappresentano una soluzione ottima.

Per ripasso rivediamo il Problema del Cambio/Resto che consiste nel minimizzare il numero di monete date come resto spiegato nel capitolo 17-1 sul libro.

Con la programmazione dinamica divido il resto n in k e n-k e provo variando k, naturalmente a condizione che non abbia gia’ una moneta di taglio n. Facendo un numero notevole di calcoli e ricorsioni ripetendo i calcoli su medesimi valori. Il trucco per non ri-calcolare sempre i valori della funzione è quello di memorizzarli da qualche parte e richiamarli quando servono, per esempio in una bella tabella. La complessità del problema del resto è dell’ordine di Θ(n2) rispetto al resto n; mentre riferito alla lunghezza del numero (n) e’ addirittura esponenziale; poiché devo trovare il minimo tra le monete che costa n operazioni e poi per trovare gli altri resti devo iterare da 1 fino a n, n volte. L’alternativa Greedy è lineare Θ(n) invece che quadratica Θ(n2) come nella Prog.Dinamica. L’algoritmo Greedy dice che ogni volta prendi la moneta di valore massimo che non supera il resto, invece di provare tutti i valori come si faceva con la Programmazione Dinamica. Se l’insieme di monete è scelto bene l’algoritmo Greedy funziona. Se ad esempio le monete fossero 1, 5, 7 e devo dare resto 10 con l’algoritmo Greedy faccio 7, 1, 1, 1 che è peggio di 5, 5. Quindi non e’/sarebbe ottimo!

Programmazione dinamica, guarderemo solo il problema della moltiplicazione delle matrici; questo perche’ gli altri problemi (sottosequenze comuni per esempio nelle stringhe del genoma, triangolarizzazione dei poligono e’ riconducibile al prodotto di matrici). In molti casi dobbiamo moltiplicare matrici molto grosse (i.e. modellazione flussi aria intorno ad ali, ma anche con programmi di scacchi), seguendo la regola che moltiplicare righeXcolonne che devono avere la stessa cardinalita’/numero l’ordine di moltiplicazione e’ importante, il prodotto di matrici non e’ communtativo quindi non possiamo cambiare ordine. Pero’ l’ordine temporale in cui le moltiplichiamo puo’ cambiare il risultato notevomente e quindi per definire l’ordine possiamo definire un problema di parentesizzazione, dove con 4 matrici avremo 5 modi diversi ci come collochiamo le parentesi (vedi sequenza che conta alberi binari 1-2-5-14). In effetti la parentesizzazione si ‘calcola’ con gli alberi: dove le matrici sono le foglie e i nodi interni sono le operazioni di prodotti delle matrici e la visita dell’albero e’ in ordine ‘solito’; avemmo potuto rappresentare gli alberi anche con le parentesi. In generale la matrici A di dimensione PxP dara’: A i (Pi-1,Pi) ∙ Ai(Pi,Pi+1) quanto costa il prodotto?

Il numero di moltiplicazioni da fare dipende dalle 3 dimensioni (1 dimensione e’ in comune) quindi: Pi-1 ∙ Pi ∙ Pi+1. Quindi ci saranno tre cicli innestati (quindi sospettiamo complessita di n3), se li chiamiamo p,q,r, e’ piu’ chiaro ed il numero totale e’ il loro prodotto. Esempi in cui il risultato cambia notevolemente al cambiare delle parentesi: A1=10x100, A2=100x5, A3=5x50 posso ottenere ((A1A2)A3)=7500 od addirittura (A1(A2 A3))=75000 operazioni. Anche con una macchina veloce se c’e’ un fattore 100 di differenza e’ una notevole differenza.

Ed allora come si fa a trovare la soluzione migliore, si provano tutte le possibili parentesizzazioni e si sceglie la migliore oppure con la rappresentazione ad albero possiamo vederlo dalla relazione/equazione di ricorrenza P(n) come:

1 se n=1

	se n ≥ 2, ho k oggetti a sx ed n-k a dx.

La quale rappresenta la relazione di ricorrenza degli alberi mettendo n-k nodi a dx e k a sx, corrispondenza tra alberi binari con n-1 nodi e parentesizzazioni con n matrici.

Il numero P(n) delle parentesizzazione e’ pari al numero di alberi con n-1 nodi inerni ed e’ contato dai numeri di Catelan Prob.13.4 che dice che l’ennesimo numero cresce come Ω(4n/n3/2), quindi il numero di alberi cresce quasi come 4n, le possibilita’ sono molte/troppe, quindi non vogliamo/possiamo contare tutte le possibili soluzioni. Ora con la programmazione dinamica andra’ bene perche’ guadagneremo nel memorizzare le soluzioni intermedie in cui i casi non sono tutti distinti, sono sovrapposte, questo e’ il vantaggio. Otterremo un numero polinomiale, algoritmo di complessita’ n3 tra i peggiori che abbiamo visto ma ancora polinomiale. Se riusciamo a scrivere una equazione/relazione di ricorrenza (come nel problema del resto) siamo soddisfatti. Come procediamo? Dobbiamo definire bene la grandezza per la quale vogliamo trovare la relazione di ricorrenza, nel nostro caso il minimo numero di moltiplicazioni per calcolare il prodotto delle matrici. ... ... m[i,j]=0 se i=j min{....} se i<j

... ...

LEZIONE 37di42 del 13/Gennaio/2004

Programmazione dinamica. Cenni alla tecnica della memorizzazione. Algoritmi Greedy: il problema della selezione di attività (testo §17.1).

Riassunto. Finendo la programmazione dinamica. Dove se usiamo un sistema di supporto per esempio Mathematica la memorizzazione sara’ fornita come servizio dal sistema. Se adottassimo una tecnica Greedy al prodotto delle matrici moltiplicando le matrici vicine con il minor numero di operazioni, il risultato e’ comunque superiore ai risultati precedenti, quindi la tecnica Greedy basata inizialmente sul prodotto di matrici che danno il minor numero di operazioni non produce una soluzione ottima.

Programmazione dinamica elementi e proprieta’ (Guardare le dispense di Goldwurm, che su questi argomenti sono di buona sintesi): Sottostruttura ottima. Per risolvere un problema di ottimizzazione e’ necessario che i sottoprolemi abbiano una soluzione ottima, per poter ‘costruire’ il problema generale. Generalemente con approccio ricorsivo. Sottoproblemi comuni. Per risolvere un problema con la programmazione dinamica e’ necessario che il numero dei sottoproblemi sia ‘piccolo’ ovvero che i problemi sia sovrapposti e/o si ripetano. Si vede bene nella Fig.26.2. Ricorsione con memorizzazone(Mimoization). E’ una tecnica che consiste nel memorizzare i risultati parziali in una tabella. 16.3 La piu’ lunga sottosequenza comune.Problema un po’ complicato che saltiamo anche se interessante.

Cap.17 Algoritmi Greedy. Gli algoritmi Greedy cercano di risolvere problemi di ottimizzazione e lo fanno attraverso una sequenza di passi/decisioni che portano/rebbero alla soluzione ottima. Mentre le tecniche di programmazione dinamica vagliano tutte le sottosoluzioni, cosa gli algoritmi Greedy non lo fanno.(potremmo dire che l’algoritmo Greedy e’ un cammino tra quelli della programmazione dinamica?quasi quasi si) Come faremo per sapere che la soluzione che troveremo e’ ottima? Partiamo da un esampio semplice sulla selezione di attivita’.

Problema della selezione della attività. Abbiamo un insieme di n attività che vogliono utilizzare una singola risorsa ad esempio un’aula di lezione (si fa solo una lezione per volta in un’aula). Qual è il problema? Il problema della selezione della attività consiste nel selezionare il massimo numero di attività mutuamente compatibili. (Quindi meglio 5 attivita’ di 1 ora che 1 attivita’ di 10 ore). Per riuscire ad ottenere questo dobbiamo sapere cosa vuol dire mutuamente compatibili: vuol dire che non si sovrappongono. Come si fa a sapere se si sovrappongono? Se gli intervalli non si sovrappongono allora gli elementi non si sovrappongono, confrontando gli estremi del segmento di tempo.

Ora la prima cosa da fare dovrebbe essere quella di ordinare le attivita’, con quale ordine? L’ordinamento giusto è quello rispetto all’istante di fine. Poi vedremo che se ordinassimo rispetto all’istante di inizio non funzionerebbe il ns approccio.

Conseguentemente l’algoritmo per una scelta Greedy funziona così: Sia n la lunghezza del vettore S che contiene gli istanti di inizio delle attività . Noi vogliamo selezionare un insieme A di attività, ordinate secondo il tempo di fine. Se non sono ordinate le ordiniamo noi. In generale con un buon algoritmo che funziona sempre ci vuole tempo O(nlogn). Tempo di ordinamento che conteremo se le attivita’ non sono ancora ordinate.

L’insieme di attività lo inizializziamo con l’attività numero 1, cioe’ l’attivita’ che finisce per prima. Prendendo quella che finisce per prima lasciamo disponibile la maggior parte del tempo rispetto a ogni altra attività. Iterando avremo l’elenco di attivita’ compatibili per il massimo numero di attivia’ sulla risorsa. Come siamo sicuri che sia la soluzione ‘ottima’? Potremmo provare con un controesempio ‘migliore’ oppure Teo.17.1.

Dimostrazione in due fasi: prima esiste una soluzione ottima con la scelta Greedy (Greedy puo’ essere giusta); secondo il soottoproblema senza la prima scelta e’ comunque ottima quindi e’ una dimostrazione di tipo ricorsivo.

Elementi/proprieta’ delle tecniche Greedy. Avendo visto la programmazione dinamica e gli algoritmi Greedy qual è meglio utilizzare? Le Greedy in generale sono più veloci delle altre; anche se potrebbe non funzionare. Dato lo stesso problema la soluzione con programmazione dinamica garantisce una soluzione ottima ma richiederà ‘molto’ più tempo che non una tecnica Greedy. Questo dipende dal criterio di convenienza.

Ci sono a anche casi in cui le tecniche esaustive, come programmazione dinamica, richiedono troppo tempo per trovare la soluzione e quindi non accettabile, allora una tecnica Greedy + veloce anche se potrebbe non trovarmi la soluzione ‘ottima’ troverebbe comunque ‘una soluzione’.

Problema dello zaino ( Knapsack Problem). Buon esempio di come piccole variazioni dello stesso problema possono far si che le tecniche Greedy funzionino oppure no. C’è un ladro che deve rubare n elementi ma ha uno zaino che non può contenerli tutti. Il problema può essere considerato in due versioni: frazionario/continuo(possibile prendere anche una frazione dell’oggetto) o discreto(0-1, predere o lasciare). Sul libro è spiegato coi lingotti (oro, argento, platino) che in un caso sono solidi e nell’altro sono in polvere. La tecnica Greedy funziona nel caso continuo valutando il rapporto valore/peso; nel caso discreto invece non da’ una soluzione ottima.

LEZIONE 38di42 del 15/Gennaio/2004

Approccio greedy vs. programmazione dinamica. I problemi dello zaino (testo §17.2). I matroidi e Teo.Rado: esempi e motivazioni (§17.4; per la dimostrazione del teorema 17.5 si può vedere la nota “Problemi su insiemi, matroidi e algoritmi ingordi”). http://homes.dsi.unimi.it/~torelli/problemi.pdf

Riprendiamo, a proposito del problema della selezione di attivita’ con un paio di osservazioni. Le ns attivita’ possono essere rappresentate con un grafo di intervalli in cui i veritici sono i singoli intervalli ed i lati rappresentato le sovrapposizioni tra gli intervalli, ed il nostro problema consiste/traduce nel trovare l’insieme indipendente dei vertici non collegati da lati, vedi Prob.36.1. Trovando la cardinalita’ in tempo polinomiale.

Qual’e’ quindi la complessita’ dell’algoritmo? Dopo aver ordinato gli intervalli (O(logn)) abbiamo un solo ciclo che scorre la lista in tempo Θ(n), quindi l’algoritmo Greedy e’ efficiente.

Osservazioni su esercizi: 17.1-2 Colorazione del grafo (di intervalli): colorare tutti i vertici con il minimo numero di colori in modo tale che nessuna coppia dei vertici adiacenti siano colorati con colori uguali. Con esempio in cui la strategia Greedy non funziona. E come faccio a capire se la tecnica greedy e’ applicabile con successo ovvero trova la/le soluzioni ottime? vedi Teoria dei Matroidi che seguira’.

12. Algoritmi Greedy (Da dispense di Goldwurm).

Una delle tecniche piu’ semplici per la progettazione di algoritmi di ottimizzazione e’ chiamata tecnica greedy. Letteralmente questo termine significa “ingordo”, ma nel seguito preferiremo tradurlo in “miope”. Intuitivamente, questo metodo costruisce la soluzione di un problema di ottimizzazione mediante una successione di passi durante ciascuno dei quali viene scelto un elemento “localmente” migliore; in altre parole a ciascun passo la scelta migliore viene compiuta in un ambito limitato, senza controllare che il procedimento complessivo porti effettivamente al calcolo di una soluzione ottima per il problema. Questa strategia, se da un lato permette solitamente di ottenere algoritmi semplici e facilmente implementabili, dall’altro puo’ portare alla definizione di procedure che non forniscono sempre la soluzione ottima. In questo capitolo vogliamo studiare le proprieta’ degli algoritmi di questo tipo e verificare in quali casi e’ possibile garantire che la soluzione costruita sia effettivamente la migliore.

12.1 Problemi di ottimizzazione.

Per esprimere questi concetti in maniera precisa, introduciamo la nozione di sistema di indipendenza.

Un sistema di indipendenza (che sara’ il primo elemento di un Matroide) e’ una coppia (E, F) nella quale E e’ un insieme finito (come elementi nell’esempio zaino), F e’ una famiglia F di sottoinsiemi di E chiusa rispetto all’inclusione; in altre parole, [F e’ contenuto in 2E] (qui e nel seguito denoteremo con 2E la famiglia di tutti i sottoinsiemi di E) e inoltre:

A Î F Λ B e’ contenuto in A → B Î F, vedi funzione caratteristica di appartenza

E’ evidente che, per ogni insieme finito E, la coppia (E, 2E) forma un sistema di indipendenza.

17.4.1 La formula suddetta ricorda quella dei Matroidi...ma meglio utilizzare il concetto di sistema di indipendenza. ... ... Si pongono allora, a questo livello di generalita’ , due problemi:

1. qual’e’ il tempo di calcolo dell’algoritmo greedy, cioe’ quanti passi di calcolo devono essere compiuti avendo come ingresso un insieme E di n elementi? A questo proposito osserviamo che l’input dell’algoritmo sara’ qui costituito dal solo insieme E e dalla funzione peso w: si suppone che F sia automaticamente definito in maniera implicita mediante una opportuna regola e sia comunque disponibile una routine per verificare quando un insieme A contenuto in E appartiene a F. La famiglia F potrebbe infatti contenere un numero di elementi esponenziale in n e quindi la sua specifica diretta sarebbe improponibile. In generale esiste un criterio per stabilie se un sottoinsieme appartiene o no alla famiglia dei sottoinsiemi indipendenti senza provarli tutti.

2. In quali casi l’algoritmo greedy fornisce effettivamente una soluzione ottima? Qualora l’algoritmo non fornisca la soluzione ottima, si pone un terzo problema, ovvero quello di valutare la bonta’ della soluzione prodotta. Questo porta a studiare una classe di algoritmi, detti di approssimazione, che in generale non forniscono la soluzione migliore a un dato problema ma ne producono una che approssima quella richiesta. In molti casi il calcolo della soluzione ottima e’ troppo costoso in termini di tempo e ci si accontenta di una soluzione approssimata, purche’ ovviamente quest’ultima sia calcolabile in un tempo accettabile. ... 12.2 Analisi della procedura Greedy ... Come si vede la procedura prevede due passi principali: l’ordinamento di un vettore di n elementi e n test per verificare se un insieme X contenuto in E appartiene a F. Possiamo chiaramente eseguire il primo passo in un tempo O(n log n). Il secondo tuttavia dipende dal particolare sistema di indipendenza considerato in ingresso. Se comunque assumiamo di poter verificare l’appartenenza X Î F in un tempo C(n), il costo complessivo di questo controllo non e’ superiore a O(n C(n)). Possiamo quindi concludere affermando che la procedura Greedy richiede al piu’ un tempo O(n log n + n C(n)).

[Deve esistere un elemento b che appartiene all’insieme più grande per cui A U b appartiene ancora alla famiglia. Se esiste un insieme B che appartiene alla famiglia ed ha più elementi di A deve poter regalare ad A un suo elemento per far crescere A. Cioè assicura che l’algoritmo Greedy funziona. Gli insiemi indipendenti massimali in un matroide potranno avere cardinalità diversa? NO perchè se avessero cardinalità diversa allora prendo elementi da quello più grande e lo regalo al piccolo e lo faccio diventare della stessa cardinalità di quello grande (sul libro è la proprietà di scambio).]

Matroidi e Teorema di Rado Vedi Teo.17.10 del libro. Teo: Se la struttura del problema di ottimizzazione e’ quella di un matroide pesato con funzione peso ‘w’ allora la procedura greedy riesce a trovare una soluzione ottima. Ed e’ proprio per questo che ci interessano i matrodi: per stabilire se gli algoritmi greedy trovano una soluzione ottima oppure no. Indipendentemente dalla funzione peso...attenzione quando la funzione peso e’ = 1 per ogni attivita’

12.3 Matroidi e teorema di Rado ( da dispense Bertoni/Goldwurm). Diamo in questa sezione una soluzione parziale alla seconda questione che ci siamo posti: in quali casi l’algoritmo greedy fornisce la soluzione ottima? Il nostro obiettivo e’ quello di caratterizzare la classe dei sistemi di indipendenza per i quali l’algoritmo greedy fornisce la soluzione ottima qualunque sia la funzione peso considerata. Dimostreremo (teorema di Rado) che un sistema di indipendenza verifica la proprieta’ precedente se e solo se esso e’ un matroide. Un sistema di indipendenza (E, F) e’ detto matroide se, per ogni A,B Î F tali che |B| = |A| + 1 (qui |X| indica la cardinalita’ di un insieme X), allora esiste b Î B − A per cui A U {b} Î F. Per esempio, e’ facile verificare che, per ogni insieme finito E, la coppia (E, 2E) forma un matroide. La nozione di matroide e’ stata introdotta nel 1935 da Birkhoff e altri per generalizzare il concetto di dipendenza lineare. Questa nozione ha trovato proficue applicazioni in vari settori, dalla teoria dei grafi agli algoritmi, e puo’ essere considerata un ponte tra l’algebra lineare e la matematica combinatoria. Esempio 12.3 Sia E un insieme finito di vettori di uno spazio vettoriale V. Sia F la famiglia di sottoinsiemi di E formati da vettori linearmente indipendenti. Si puo’ verificare facilmente che (E, F) forma un matroide, detto matroide vettoriale. L’esempio pi`u importante di matroide e’ tuttavia fornito dal sistema di indipendenza (E,FG) definito nell’Esempio 12.1. La seguente proposizione dimostra questa proprieta’. Proposizione 12.1 Per ogni grafo non orientato G = (V,E), la coppia (E,FG) e’ un matroide. La coppia (E,FG) e’ anche chiamata matroide grafico. Un risultato interessante, che fornisce una interpretazione algoritmica dei matroidi, e’ il seguente:

Teorema 12.2 (Rado) Dato un sistema di indipendenza (E,F), le seguenti proposizioni sono equivalenti: a) per ogni funzione peso w : E -> R+, l’algoritmo MIOPE fornisce una soluzione ottima al problema di massimo su input E, F,w; b) (E, F) e’ un matroide.

LEZIONE 39di42 del 16/Gennaio/2004

Il teorema di Rado (o di Borůvka: teorema 17.10 del testo, dispense Goldwurm, teorema 12.2). Visita di grafi in ampiezza e in profondità e ordinamento topologico (solo i concetti principali dei §§ 23.2 (saltare dal lemma 23.1 a fine §), 23.3 (saltare da "Proprietà della visita in profondità" a fine §) e 23.4 (saltare da pag. 467 a fine capitolo). Per tutti gli algoritmi sui grafi fare riferimento alla nota “Una guida alla visita di grafi” http://homes.dsi.unimi.it/~torelli/guida.pdf e vedere gli esempi nelle figure del testo. Vedi appunti Torelli: “Problemi su insiemi, matroidi e algoritmi ingordi”

§17.4 Matroidi fondamenti Teoretici. Il matroide e’ una struttura combinatoria, rappresentabile da una coppia ordinata M=(S,I) che soddisfa le seguenti condizioni: 1.S e’ un insieme finito non vuoto; 2.I e’ una famiglia non vuota di sottoinsiemi indipendenti di S caratterizzati da: se B Î I ed A e’ contenuto in B allora anche A Î I. E diciamo che I e’ ereditario e soddisfa la precendente proprieta’ 3. M soddisfa la proprieta’ di scambio/accrescimento/estensione che e’ quella + caratteristica. Se B contiene qualche elemento in piu’ di A ... ... ... matroide matriciale matroide grafico, sono una classe di matroidi ma non comprendono tutti i matroidi (quelli matriciali sono piu’ generali di questi grafici); il matroide grafico e’ costituito dalle foreste di un grafo

A massimale...

Teo.17.6 tutti i massimali hanno la stessa cardinalita’/dimensione poiche’ non posso piu’ fare estensioni/scambi

Il viceversa del teorema 17.6 NON vale: cioè anche se tutti gli insiemi massimali hanno la stessa cardinalità non è affatto detto che il sistema di indipendenza sia un matroide. Controesempio: siano ab e cd gli unici insiemi indipendenti massimali; d è indipendente perché sottoinsieme di cd, ab ha cardinalità maggiore di quella di d ma non posso estendere d né con a né con b perché né ad né bd sono indipendenti.

... le foreste di un grafo costituisco un matroide ...

12.1 Algoritmo di Kruskal permette di trovare un albero ricoprente minimo (minimum spanning tree). Li vedremo la prosssima settimana.

17.4.2 E’ possibile trasfromare un problema di massimo in un problema di minimo cambiando la funzione di di peso w, associandogli la differenza tra un peso massimo ed il peso originario ... Vediamo come muoverci in un grafo, che a differenza di un albero potrebbe aver dei cicli. Come contrassegnare i vertici per attraversare completamente il grafo senza ‘perderci’? - vertici inesplorati in bianco/white - vertici attivi (in esame) in grigio/grey - vertici disattivati in nero/black

I nodi processati possono essere inseriti in una struttura dati semplice quali liste organizzate come code/stack con FIFO oppure LIFO con una coda ottengo visita in ampiezza: da un nodo visito i vicini a distanza uno poi distanza due etc etc ottenendo le distanze dal nodo di partenza sia in numero di lati che in pesi con uno stack ottengo visita in profondita’ dove parto dal nodo piu’ lontano e poi visitero’ tutto l’albero

LEZIONE 40di42 del 20/Gennaio/2004

Alberi ricoprenti minimi (cap. 24, introduzione). Cenni agli algoritmi di Kruskal e Prim (§24.2: tralasciare i dettagli del codice). L'algoritmo di Dijkstra per la determinazione dei cammini minimi (fig. 25.5).

Da precedenti appunti: Per la visita dei grafi si devono marcare i nodi già visitati. Nel corso della visita si può costruire un albero di visita A in cui ogni nodo ha come padre il nodo dal quale è stato visitato la prima volta: l’albero A ha come elementi i lati del grafo, mentre gli altri insiemi hanno come elementi i vertici del grafo. In realtà se il grafo non è connesso l’insieme A è una foresta ricoprente tutti i vertici del grafo assegnato. Su questo argomento il libro fa un po’ di confusione quindi è bene attenersi a questa lezione. Guardare il problema 5.1 sulla colorazione dei grafi. Un grafo è bipartito quando un insieme di vertici può essere diviso in due insiemi di modo tale che ogni lato collega ogni nodo del primo insieme con quelli del secondo insieme. Se non ci sono cicli di lunghezza dispari allora è dipartito. Ogni albero è colorabile con soli due colori. In un albero non ci sono cicli né di lunghezza pari né di lunghezza dispari e quindi è dipartito. La visita in ampiezza è uno dei più semplici algoritmi per visitare un grafo. Dato un grafo G = (V, E) con uno specifico vertice ‘s’ chiamato sorgente la visita in ampiezza esplora sistematicamente gli archi di G per “scoprire” ogni vertice che sia raggiungibile da s. Essa calcola la distanza da s a ognuno dei vertici raggiungibili e produce un albero BFS (breadth-first search) che ha s come radice e che comprende tutti i vertici raggiungibili da s. I dettagli sono al paragrafo 23.2 del libro. Ordinamento topologico. L’ordinamento topologico viene fatto sui DAG cioè un directed acyclic graph ovvero un grafo orientato aciclico.

da “Una guida alla visita di grafi Mauro Torelli − a. a. 2004-2005 Note al corso di Algoritmi e strutture di dati.” Lo scopo di questa nota è presentare molto sinteticamente delle linee guida per comprendere svariati algoritmi su grafi. Il contenuto della nota, l'esame attento delle figure del testo, che illustrano il comportamento dei diversi algoritmi su esempi specifici (come mostrato a lezione), ed eventualmente il materiale accessibile in rete dalla pagina www.algoteam.dsi.unimi.it sono sufficienti per l'esame, mentre per una comprensione approfondita e l'eventuale realizzazione pratica degli algoritmi è necessario lo studio dettagliato del testo. Per visitare sistematicamente un grafo, a differenza degli alberi, occorre in qualche modo marcare i vertici già visitati: più precisamente, avremo a che fare con vertici inesplorati (che supporremo colorati in bianco (white: denoteremo con W l'insieme dei vertici bianchi), vertici in corso di visita (grigi, insieme C: non abbiamo usato la lettera G per non fare confusione con il simbolo che denota l'intero grafo) e vertici completamente esplorati (neri – black, insieme B). I vertici assumono via via prima il colore bianco, poi diventano grigi e infine neri. Nel corso della visita si può costruire un albero di visita A, in cui ogni nodo ha come padre il nodo a partire dal quale è stato visitato la prima volta: l'albero A ha come elementi lati del grafo, mentre gli altri insiemi hanno come elementi vertici del grafo. In realtà, se il grafo non è connesso, l'insieme A è una foresta ricoprente tutti i vertici del grafo assegnato. L'algoritmo di visita può essere espresso genericamente come segue, con una notazione insiemistica che ignora i dettagli realizzativi ma aiuta a capire l'essenziale. Il grafo in input ha vertici V e lati E. Denoteremo con Adj[u] l'insieme dei vicini del vertice u (contenuti nella lista di adiacenza): formalmente Adj[u]:= {v Î V: uv Î E} quindi esiste un lato tra u e v. Ometteremo come di consueto le parentesi graffe: per esempio, indicheremo con uv il lato {u,v}. Il simbolo ► introduce un commento.

ALGORITMO VISITA(V, E) 0. W ← V; A ← B ← C ← Ø ►coloriamo tutti i vertici di bianco e gli altri sono vuoti 1. finché C U W ≠ Ø ►ci sono ancora bianchi o grigi, unione di grey&white 2. se C = Ø scegli1 u Î W altrimenti scegli2 u Î C ►se non ci sono grigi parti da bianco 3. per ogni v Î Adj[u] ∩ W: A ← A U uv ► u è il padre di v nell'albero A 4. B ← B U u; C ← (C U Adj[u]) – B; W ← W – B – C 5. restituisci A ► restituisce albero

Alla riga 2 dell'algoritmo, la prima procedura scegli1 sceglie, in genere casualmente, un vertice u da W: ciò è necessario soltanto se il grafo non è connesso, e in tal caso l'algoritmo può essere usato per individuare le diverse componenti connesse del grafo, in tempo Θ(V + E) (infatti si devono colorare di bianco i vertici di V e poi esaminare – in tempo costante per ciascuno – i lati di E). Quindi + efficiente della procedura per insiemi disgiunti. La seconda procedura scegli2, che sceglie un vertice u in C, è invece cruciale per determinare le caratteristiche della visita: se interessa solo visitare sistematicamente il grafo, la scelta può essere ancora casuale, altrimenti occorre seguire un ordine stabilito da un'opportuna coda con priorità.Vediamo gli esempi:

1. Come possibile applicazione molto semplice di una visita in ordine casuale possiamo citare lo stabilire se il grafo sia bipartito ovvero 2-colorabile (si veda il problema 5-1 del testo). In questo caso non interessano gli insiemi A, B e C: si colora il nodo di partenza con un colore, tutti i suoi vicini con un altro e poi si alternano i colori. Se non occorre mai cambiare il colore di un nodo già colorato (cioe’ non ci sono conflitti), il grafo è bipartito, altrimenti non lo è.

2. Se scegli2 estrae il vertice u da una coda (FIFO), allora abbiamo la visita in ampiezza (breadth-first search, BFS): i vertici a distanza 1 da quello di partenza sono visitati prima di quelli a distanza 2, e così via: estendendo la struttura dati del grafo con un campo distanza è possibile tener traccia delle distanze e quindi fornire la distanza minima di ciascun nodo da quello di partenza (si veda la figura 23.3 del testo).Ed abbiamo quindi costruito l’albero A.

3. Se scegli2 estrae il vertice u da una pila (LIFO), allora abbiamo la visita in profondità (depth-first search, DFS), in cui i nodi a distanza 1 da quello di partenza sono in fondo alla pila e la visita tende invece ad allontanarsi il più possibile dal nodo di partenza, prima di tornare ad avvicinarsi. In realtà qui abbiamo semplificato un po' troppo: per alcune applicazioni è essenziale la versione ricorsiva dell'algoritmo, in cui solo un primo vicino viene immesso nella pila (non tutti i vicini). La pila è gestita automaticamente dalla ricorsione. Il libro mostra come, estendendo la struttura dati per registrare gli istanti di inizio visita e di fine visita (si veda la figura 23.4) sia poi possibile, per esempio, realizzare il cosiddetto ordinamento topologico (§23.4 del testo), sempre in tempo Θ(V + E). Con la visita in profondita’ possiamo procedere all’Ordinamento topologico di grafi orientati aciclici (DAG directed acyclic graph) utilizzando gli istanti di inizio e fine. In questo modo abbiamo freccie di direzione e vediamo se possiamo ordinare tutti i nodi secondo un certo ordine. ...

4. Se scegli2 estrae il vertice u da una coda con priorità che fornisce il lato uv di peso minimo tra tutti quelli che collegano un vertice v nero a un vertice grigio (come nella figura 24.5 del testo), allora si costruisce "ingordamente" un albero di lati minimi e si ottiene alla fine un albero ricoprente minimo (rispetto alla somma dei pesi dei lati) (se il grafo G è connesso) con l'algoritmo di Prim. Con l’algoritmo di Prim se la coda con priorità è realizzata con un heap binario (come nell'algoritmo di Huffman) il tempo di esecuzione risulta O(E log E) = O(E log V) ( poiche’ sono diversi a meno di una costante due nel caso E=V*V)

5. In alternativa all'algoritmo di Prim si possono scegliere ingordamente/greedy i lati minimi badando solo a non chiudere cicli, quindi costruendo una foresta (che costituisce un matroide, quindi l’algo greedy funziona ottimalmente), che alla fine però risulterà un albero ricoprente minimo, se il grafo è connesso (si veda la figura 24.4: algoritmo di Kruskal). Per stabilire se un lato chiude o no un ciclo si possono usare (la visita in profondita’ oppure) le procedure per insiemi disgiunti applicati agli insiemi di lati e vertici (UNION e FIND-SET) e il tempo di esecuzione è dominato dal tempo O(E log E) per ordinare i lati.

6. Un'ulteriore alternativa (meno nota, ma di interesse non solamente storico) è data dall'algoritmo di Borůvka, che risale al 1926 ed è quindi anteriore alla data di nascita "ufficiale" della teoria dei grafi moderna, che è il 1936, data di pubblicazione del libro di Dénes König, Theorie der endlichen und unendlichen Graphen. L'articolo originale di Borůvka, tradotto dal ceco in inglese e accompagnato da utili commenti si può leggere alla pagina http://citeseer.nj.nec.com/nesetril00otakar.html.

7. In un grafo orientato con lati pesati in cui i pesi rappresentano le distanze (non negative), se scegli2 estrae il vertice u da una coda con priorità che fornisce il vertice più vicino all’albero A costruito sino a quel momento, allora l’algoritmo fornisce l’albero che collega tutti i vertici al nodo di partenza con le distanze minime, in tempo O(E log V) (algoritmo di Dijkstra, si veda la figura 25.5 del testo).

LEZIONE 41di42 del 22/Gennaio/2004

Analisi ammortizzata: metodo degli aggregati e quello degli accantonamenti (cenni al potenziale) (§18.1,§18.2). Esempi: pile con multipop e contatore,vedere §3.4 degli appunti heap.http://homes.dsi.unimi.it/~torelli/note.html Tabelle dinamiche (testo §18.4, saltando da pag. 351 alla fine).

§25.3 Riprendiamo l’algoritmo di Dijkstra: cerca di costruire un albero con le distanze minime da un vertice prefissato, a tutti gli altri. Visitiamo sistematicamente il grafo seguendo i lati orientati ovvero le liste di adiacenza. Utilizziamo il metodo dei nodi bianchi/grigi/neri e si richiede di avere archi di peso non negativo, poiche’ questi diminuiscono la lunghezza del percorso che non e’ possibile. Con complessita’ dove si passano tutti i lati + gestione coda con priorita’, quest’ultima gestiamo in tempo logE=lati e la complessita’ e’ O(ElogE).

Tornando al problema dell’albero ricoprente minimo con Algoritmo di Borůvka. Assomiglia a quello di Kruskal xche’ forma alberi separati (foresta) che poi vengono connessi successivamente ed a quello di Prim che espandendosi forma un solo albero. Il numero di alberi si dimezza ad ogni passo e quindi complessita’ e’ ancora O(ElogE) anche se con caratteristiche diverse dagli algoritmi precedenti.

Cap18. Analisi Ammortizzata. Supponiamo di dover realizzare una pila con operazioni push, pop, e multipop (elimina k elementi ovvero svuota la pila); e di fare una analisi di complessita’, semplice per push e pop mentre non chiara per multipop. Supponiamo che abbiamo Costo ammortizzato (un costo medio/mediato anche se su operazioni non omogenee, costo(tempo) totale/numero operazione)= T(n)/n. Oppure faccio n-1 operazioni di push ed alla ennesima faccio una multipop che svuota la pila; Oppure decido che push costa il doppio con multipop gratis e pop (caso di multipop con k =1) gratis too. In questo modo i costi sono costanti=2n ... Metodo degli Aggregati. aggregando n operazioni anche se non omogenee, ed ottenendo un costo ‘pseudomedio’/per operazione. Metodo degli Accantonamento/Contabilita’. Dove si accantonano tramite le operazioni che costano piu’ del loro costo effettivo/iniziale (esempio il doppio) costi per pagare quelle che saranno considerate ‘costo zero’. Metodo del Potenziale che non vedremo poiche’ seppur corretto e’ ‘ridondande/assomiglia’ con accantonamento dove accantonamento e’ il potenziale disponibile.

Come risolvere il problema del contatore binario con il metodo degli accantonamenti ... ... - passaggio da 0 a 1, + chiara e possiamo ‘caricarla’ dei costi per altre operazioni (quella inversa) con costo ammortizzato 2(due) che permette di ‘pagare tutto’ - passaggio da 1 a 0, pagato dal precedente (considerando che parto con tutti i bit a zero) vedi teorema di Legendre

Problema dimensionamento tabelle dinamiche. ...che vengono allocate dinamicamente oppure tramite incrementi successivi con spostamenti.

Gestione dinamica della dimensione di una tabella analizzata con i due metodi:

1) Metodo aggregati:partendo da array di dim=1 raddoppieremo con multipli/potenze di due... 2) Metodo accantonamenti: rapporto di espansione v=vecchio, n=nuovo l’espansione/carico (v+n)/n ecco che costo ammortizzato (CAM)=costo reale+accantonamento=1+x, costo che verra’ pagato n volte per n inserimenti quindi il costo accantonato=CAN=nx e dobbiamo pagare gli spostamenti v+n ecco che e’ necessatio che nx=v+n ed x=1+(v/n) e quindi costo ammortizzato=CAM=2+(v/n) quindi se: - raddoppio la dimensione della tabella iniziale v=n quindi CAM=2+1=3 - v=(1/2)n quindi triplico array CAM=2.5 - se espando del 50% n=(1/2)v avro’ x=3 e CAM=4 quindi mi costera’ + che espandere +

CAM=(proprio costo effettivo=1) + (proprio costo trasferimento=1) + costi dei ‘vecchi’

=== LEZIONE 42di42 del 23/Gennaio/2004 === – Ultima Lezione AA2003/04

Cenni ai problemi P, NP e NP-completi, NP-hard (introduzione al capitolo 36 del testo). Algoritmi approssimati: rapporto limite (testo pagina 907).Coperture approssimate di vertici (testo §37.1). Cenni al problema del commesso viaggiatore e della copertura di un insieme (§37.2, §37.3, solo i risultati)... Fine corso

Cap.36 Cenni alla classe NP, NP-C. Cosa fare quando non si conoscono soluzioni efficienti? Per esercizi teorici 5/6 nodi sono semplici mentre con 40/50 nodi diventa impossibile. In tutti i problemi studiati sin’ora si trovavano soluzioni in tempo polinomiale O(nk) per qualche costante k, e quindi erano problemi ‘trattabili’, mentre i problemi non-trattabili hanno comportamento super-polinomiale. La classe NP (non deterministico-polinomiale) e’ diversa da classe NP-Completa. Vediamo come esempio il problema della copertura con/dei vertici §37.1...trasformandolo in un problema di decisione (i.e. esiste una copertura con 3 vertici?si). Non si conosce un algoritmo che lo risolva in tempo polinomiale. ... ... I problemi NP-C sono quelli piu’ difficili all’interno della classe NP. ... ... (TSP) Algoritmo commesso viaggiatore appartiene classe NP-C per la decisione ed NP-arduo/difficile per l’ottimizzazione ... ...

Errori presenti nel testo “Introduzione agli Algoritmi’ Cormen. - Pag 199 nel programma FREE-OBJECT free[x] = x è sbagliato. Si sostituisce con free = x - Pag 191 della procedura DEQUEUE nella riga 2. If head (q) == lunghezza q - Pag. 52 nel paragrafo metodo di sostituzione appena dopo l’equazione 4.4 “il metodo consiste nel provare che” T(n) < nlogn infatti anche dopo è minore…