Algoritmi e Calcolo Parallelo 2012/2013 - Algoritmi e Strutture Dati
-
Upload
pier-luca-lanzi -
Category
Documents
-
view
467 -
download
0
description
Transcript of Algoritmi e Calcolo Parallelo 2012/2013 - Algoritmi e Strutture Dati
![Page 1: Algoritmi e Calcolo Parallelo 2012/2013 - Algoritmi e Strutture Dati](https://reader036.fdocumenti.com/reader036/viewer/2022081413/5482dc17b4af9f12188b46b2/html5/thumbnails/1.jpg)
Prof. Pier Luca Lanzi
Algoritmi e Strutture DatiAlgoritmi e Calcolo Parallelo
![Page 2: Algoritmi e Calcolo Parallelo 2012/2013 - Algoritmi e Strutture Dati](https://reader036.fdocumenti.com/reader036/viewer/2022081413/5482dc17b4af9f12188b46b2/html5/thumbnails/2.jpg)
Prof. Pier Luca Lanzi
Riferimenti
• Bertossi Alan A., Montresor Alberto. “Algoritmi e strutture di dati” (seconda edizione), CittàStudi 2010
• Stanley B. Lippman, Barbara E. Moo, Josee Lajoie“C++ Primer”, 5th Edition Addison-Wesley
2
![Page 3: Algoritmi e Calcolo Parallelo 2012/2013 - Algoritmi e Strutture Dati](https://reader036.fdocumenti.com/reader036/viewer/2022081413/5482dc17b4af9f12188b46b2/html5/thumbnails/3.jpg)
Prof. Pier Luca Lanzi
Tipo di Dato Astratto
• Dato In un linguaggio di programmazione, un dato è
un valore che una variabile può assumere
• Tipo di dato astrattoUn modello matematico, dato da una collezione
di valori e un insieme di operazioni ammesse su questi valori
• Tipi di dati primitiviForniti direttamente dal linguaggioEsempi: int (+,-,*,/, %), boolean (!, &&, ||)
3
![Page 4: Algoritmi e Calcolo Parallelo 2012/2013 - Algoritmi e Strutture Dati](https://reader036.fdocumenti.com/reader036/viewer/2022081413/5482dc17b4af9f12188b46b2/html5/thumbnails/4.jpg)
Prof. Pier Luca Lanzi
Tipi di Dati Astratti
• Sono definiti da due parti: la specifica e l’implementazione
• La specifica è il manuale d'uso, nasconde i dettagli implementativi all'utilizzatore
• L’implementazione è la realizzazione vera e propria
• EsempiNumeri reali (la specifica) – IEEE754
(l’implementazione)Grafi (la specifica) – matrici d’adiacenza
(l’implementazione)
4
![Page 5: Algoritmi e Calcolo Parallelo 2012/2013 - Algoritmi e Strutture Dati](https://reader036.fdocumenti.com/reader036/viewer/2022081413/5482dc17b4af9f12188b46b2/html5/thumbnails/5.jpg)
Prof. Pier Luca Lanzi
Strutture Dati
• I dati sono riuniti in insiemi detti strutture di dati Sono particolari tipi di dato, caratterizzati più
dall'organizzazione dei dati più che dal tipo dei dati stessi Il tipo dei dati contenuti può essere addirittura
parametrico Esempio: un vettore di interi, un vettore di stringhe
• Una struttura di dati è composta da Un modo sistematico di organizzare i dati Un insieme di operatori che permettono di manipolare la
struttura
• Tipologie di strutture di dati: Lineari / non lineari (presenza di una sequenza) Statiche / dinamiche (variazione di dimensione,
contenuto) Omogenee / disomogenee (dati contenuti)
5
![Page 6: Algoritmi e Calcolo Parallelo 2012/2013 - Algoritmi e Strutture Dati](https://reader036.fdocumenti.com/reader036/viewer/2022081413/5482dc17b4af9f12188b46b2/html5/thumbnails/6.jpg)
Prof. Pier Luca Lanzi
Sequenza
• Struttura di dati Dinamica e lineare Contenente elementi generici (Item), potenzialmente
anche duplicati Ordine all’interno della sequenza è importante
• Interfaccia È possibile aggiungere / togliere elementi, specificando la
posizione s = s1, s2, ..., sn
L’elemento si è in posizione posi
Esistono le posizioni (fittizie) pos0, posn+1
È possibile accedere direttamente ad alcuni elementi (testa / coda)
È possibile accedere sequenzialmente a tutti gli altri elementi
6
![Page 7: Algoritmi e Calcolo Parallelo 2012/2013 - Algoritmi e Strutture Dati](https://reader036.fdocumenti.com/reader036/viewer/2022081413/5482dc17b4af9f12188b46b2/html5/thumbnails/7.jpg)
Prof. Pier Luca Lanzi
Operazioni su Sequenze (1) 7
![Page 8: Algoritmi e Calcolo Parallelo 2012/2013 - Algoritmi e Strutture Dati](https://reader036.fdocumenti.com/reader036/viewer/2022081413/5482dc17b4af9f12188b46b2/html5/thumbnails/8.jpg)
Prof. Pier Luca Lanzi
Operazioni su Sequenze (2) 8
![Page 9: Algoritmi e Calcolo Parallelo 2012/2013 - Algoritmi e Strutture Dati](https://reader036.fdocumenti.com/reader036/viewer/2022081413/5482dc17b4af9f12188b46b2/html5/thumbnails/9.jpg)
Prof. Pier Luca Lanzi
Insiemi
• Struttura dati “generale”: insieme dinamicoPuò crescere, contrarsi, cambiare contenutoOperazioni base: inserimento, cancellazione,
verifica contenimento Il tipo di insieme (= struttura) dipende dalle
operazioni
• Elementi Elemento: oggetto “puntato” da un
riferimento/puntatoreComposto da: campo chiave di identificazione,
dati satellite, campi che fanno riferimento ad altri elementi dell'insieme
9
![Page 10: Algoritmi e Calcolo Parallelo 2012/2013 - Algoritmi e Strutture Dati](https://reader036.fdocumenti.com/reader036/viewer/2022081413/5482dc17b4af9f12188b46b2/html5/thumbnails/10.jpg)
Prof. Pier Luca Lanzi
Operazioni su Insiemi 10
![Page 11: Algoritmi e Calcolo Parallelo 2012/2013 - Algoritmi e Strutture Dati](https://reader036.fdocumenti.com/reader036/viewer/2022081413/5482dc17b4af9f12188b46b2/html5/thumbnails/11.jpg)
Prof. Pier Luca Lanzi
Dizionari
• Il dizionario rappresenta una relazione univoca R : D → C Insieme D è il dominio (elementi detti chiavi) Insieme C è il codominio (elementi detti valori)
• Associazione chiave-valore
• Operazioni ammesse:Ottenere il valore associato ad una particolare
chiave (se presente), o nil altrimenti
Inserire una nuova associazione chiave-valore, cancellando eventuali associazioni precedenti;
Rimuovere un’associazione chiave-valore esistente
11
![Page 12: Algoritmi e Calcolo Parallelo 2012/2013 - Algoritmi e Strutture Dati](https://reader036.fdocumenti.com/reader036/viewer/2022081413/5482dc17b4af9f12188b46b2/html5/thumbnails/12.jpg)
Prof. Pier Luca Lanzi
Operazioni su Dizionari 12
![Page 13: Algoritmi e Calcolo Parallelo 2012/2013 - Algoritmi e Strutture Dati](https://reader036.fdocumenti.com/reader036/viewer/2022081413/5482dc17b4af9f12188b46b2/html5/thumbnails/13.jpg)
Prof. Pier Luca Lanzi
13Alberi e Grafi
• Un albero ordinato Un insieme finito di “nodi” Un nodo particolare è designato
come radice I rimanenti nodi, se esistono, sono
partizionati in insiemi ordinati e disgiunti, anch’essi alberi ordinati
• Grafi Insiemi di nodi e archi che
connettono i nodi
• Operazione tipica è la visita o ispezionecompleta di tutti i nodi
![Page 14: Algoritmi e Calcolo Parallelo 2012/2013 - Algoritmi e Strutture Dati](https://reader036.fdocumenti.com/reader036/viewer/2022081413/5482dc17b4af9f12188b46b2/html5/thumbnails/14.jpg)
Prof. Pier Luca Lanzi
Discussione
• Le specifiche viste finora possono essere arricchite
• Operatori min() e max() nel tipo di dato Set, se esiste ordinamento totale
• Concetti di insieme e dizionario sono collegati Insieme delle chiavi/insieme dei valoriScorrere tutte le chiavi
14
![Page 15: Algoritmi e Calcolo Parallelo 2012/2013 - Algoritmi e Strutture Dati](https://reader036.fdocumenti.com/reader036/viewer/2022081413/5482dc17b4af9f12188b46b2/html5/thumbnails/15.jpg)
Prof. Pier Luca Lanzi
Implementazione
• Alcune realizzazioni sono “naturali”Sequenza ↔ listaAlbero astratto ↔ albero basato su puntatori
• Esistono tuttavia realizzazioni alternative Insieme come vettore booleanoAlbero come vettore dei padri
• La scelta della struttura di dati ha riflessi sull’efficienza e sulle operazioni ammesseDizionario come hash table: lookup in tempo
O(1), ma niente ordinamentoDizionario come albero: lookup in tempo O(log
n), con ordinamento
15