Tipi aggregati - Algoritmi e strutture dati

Esempio: bag of integer: {1, 1, 3, 5, 5, 5}, in questo caso abbiamo due

istanze dell’elemento etichettato 1 e 3 istanze dell’elemento

etichettato 5. Gli elmenti in se sono indistinguibili: tutti i 5 sono uguali

ma ne ho 3.

Una possibile implementazione del bag è con i contatori, ad esempio

l’elemento 1 è presente 2 volte, se un elemento è presente 0 volte vuol

dire che non c’è, non fa parte del bag. Il fatto di tenere il conto di

quanti elementi ho di un certo valore ci permette anche qui di avere

rappresentazioni compatte.

Sui bag vengono definite le operazioni:

·8 Operatori di insiemi: c’è una leggera variante, infatti le

operazioni come quelle di unione e di intersezione tra due bag

vengono interpretate come operazioni di minimo e massimo, per

cui se io faccio l’unione di due bag, prendo gli elementi che ci

sono con il conteggio massimo, cioè se un bag contiene un

elemento che vale 1 e un altro ne contiene 2, l’unione ne

contiene 2, l’intersezione contiene invece il minimo

·9 Uguaglianza:

La struttura bag ci permete di capire quanti elementi dello stesso

valore sono presenti in una certa collezione quando non ci interessa

distinguere i singoli elementi, non hanno un’identità individuale ma

sono tutti interscambiabili.

L’ordinamento non è rilevante.

Le bag hanno un’importante applicazione nell’interpretazione

semantica dei testi, cioè capire i testi, quindi vengono ad esempio

utilizzate per le mail, o per capire se i luoghi da visitare sono belli o

meno

Sequence

SEQUENZE OF <BASE_TYPE>

La sequenza è un tipo omogeneo, quindi fatto di oggetti base dello

stesso tipo, i cui valori sono sequenze ordinate.

Stiamo aggiungendo elementi di aggregazione, infatti il set non ha

ordinamento e non conta il numero di volte in cui compaiono gli

elementi. Il bag non ha ordinamento ma conta il numero di elementi

uguali che ci sono. La sequenza non conta di per se ma considera

l’ordine e gli elementi possono avere lo stesso valore.

L’ordinamento è riferito all’ordine degli elementi, non ai valori,

l’ordinamento che c’è sui valori è un’altra cosa, l’ordinamento delle

sequenze è quello imposto dalla creazione della sequenza. Quindi

l’ordinamento delle sequenze lo imponiamo noi nel momento in cui

mettiamo i valori.

Esempio: Sequenze of integer: (1, 3, 2, 4, 1, 5) che è diverso da (1, 1,

2, 3, 4, 5)

Come nel bag due elementi possono avere l stesso valore, ma sono

elementi distinti.

Vedremo che ci sono algoritmi di ordinamento che hanno il compito di

riordinare una sequenza partendo dall’ordinamento che ha in input e

ottenendo una sequenza di uscita dove l’ordinamento della sequenza e

quello dei tipi base coincidono, quindi in questo caso diventerebbe (1,

1, 2, 3, 4, 5), cioè l’ordinamento che io ho imposto alla sequenza e

l’ordinamento che la sequenza avrebbe se io considerassi la relazione

d’ordine del tipo base vengono a coincidere.

Vediamo le operazioni sulle sequenze:

·10 isEmpty: è una domanda che ci dice se la sequenza è vuota

e non contiene elementi. La sequenza che non contiene elementi

è una sequenza.

·11 Head/Tail: Head è l’elemento che viene per primo

nell’ordine che io ho imposto, Tail è l’ultimo elemento che io ho

aggiunto alla coda

·12 First/Next: First è l’elemento a cui sono arrivato e next è il

successivo, è un iteratore, cioè una funzione che ha uno stato,

che sa dove è arrivata nella sequenza e permette di andare a

individuare l’elemento successivo sapendo l’elemento corrente

della sequenza. Questo serve ad accelerare l’esecuzione di molti

algoritmi che diversamente dovrebbero visitare nuovamente una

sequenza dall’inizio cioè enumerare tutti gli elementi nell’ordine

naturale di quella particolare struttura dati, nel caso delle liste

l’ordinamento è quello in cui vengono scritti gli elementi. La

visita di una struttura dati produce una sequenza. Questa

operazione di visita e produzione di sequenze, in alcuni linguaggi

è detta serializzazione, cioè se io visito una struttura dati in un

ordine particolare produco una sequenza che è l’equivalente

serializzato di quella struttura dati. L’utilità di una visita con

serializzazione è che io posso prendere una struttura dati

complessa, che può avere più dimensioni, e la trasformo in una

struttura monodimensionale, questo è un modo per generare dei

file che sono strutture seriali intrinsecamente sequenziali, un file

ha infatti una sequenza di elementi. Ovviamente esiste anche la

deserializzazione che è l’operazione inversa, cioè parto da un file

e costruisco di nuovo la struttura non serializzata.

La serializzazione è in generale una operazione semplice, la

deserializzazione (parsing) è invece molto complicata

·13 Equal: uguaglianza

·14 Empty

·15 Estrazione di prefissi, cioè dall’inizio fino a un certo punto

·16 Estrazione di suffissi, cioè da un certo punto fino alla fine

·17 sottosequenze, cioè pezzi di sequenza che si trovano da

una posizione a un’altra posizione

Nella teoria generale dell’elaborazione dei testi si definiscono

sottostringhe le sottosequenze che si trovano esattamente uguali

nella stringa originale, cioè nell’esempio fatto (3, 2, 4, 1) è una

sottostringa di simboli, invece si chiamano sottosequenze le

sequenze che compaiono nella sequenza originale ma

possibilmente con dei buchi, quindi se io considero la

sottosequenze (3, 4, 5) è una sottosequenza e non è una

sottostringa, è una sottosequenza perché gli elementi compaiono

nella stringa originale nello stesso ordine, però ci sono dei buchi

in mezzo, quindi non è una sottostringa.

Nell’eleborazione dei testi è importante distinguere sottostringhe

e sottosequenze perché una sottostringa deve esistere uguale a

una stringa originale.

Se voglio fare una ricerca spesso non sono interessato alle

sottostringhe ma alle sottosequenze perché le sottosequenze si

trovano nello stesso testo originale ma possibilmente con delle

varianti.

L’utilizzo della sottostringa va bene se siamo certi che non ci

sono errori o varianti nel testo originale, altrimenti si ricorre alla

sottosequenza o sottostringa approssimata, quindi qualcosa che

va abbastanza vicino

·18 Append: aggiunta elementi alla fine

·19 Togliere elementi all’inizio o alla fine della sequenza.

Quando tolgo un elemnto la sequenza di accorgia, se aggiungo

l’elemento si allunga. Ogni elemento che io aggiungo o tolgo da

una sequenza ne modifica la lunghezza, cioè il size cioè il

numero di elementi di quella sequenza.

Lo standard considera le sequenze come tipi aggregati omogenei, che

vuol dire tutti gli elementi base hanno lo stesso tipo, i linguaggi di

programmazione spesso consentono una generalizzazione delle

sequenze in cui i tipi base possono avere elementi diversi, un esempio

è proprio il linguaggio python: una lista in python, che è proprio di fatto

una sequenza, può essere fatta da oggetti di tipo diverso, questo ha

senso perché così questa struttura è molto più flessibile, quello che

rimane della sequenza è: eliminiamo il vincolo che sia una struttura

omogenea ma il resto è sempre come prima: esiste un ordinamento

che è quello di costruzione e posso andare a individuare elementi

all’interno della lista, togliere elementi, aggiungere elementi dove

voglio nella sequenza.

Esiste una categoria molto importante di sequenze che sono le

sequenze di caratteri, le chiameremo stringhe, quindi una stringa di

caratteri è una sequenza di caratteri, è così importante che le stringhe

esistono come tipo nativo in molte architetture di macchina.

Array

ARRAY <INDEX_TYPE> OF <BASE_TYPE>

Di solito si pensa all’array come array di numeri, come A[i] dove i è un

intero.

L’array è in realtà un tipo fatto da elementi omogenei, quella del tipo

base, quindi array di record, ed è un sottoinsieme del prodotto

cartesiano tra un insieme finito detto indice e il tipo base.

Esempio: array [1:4] of integer ((1, 56), (2, 35), (3, 77), (4, 78))

In questo caso il tipo base è [1:4] cioè il sottocampo di interi che va da

1 a 4, è un tipo finito ed è fondamentale che sia così. L’array mette in

collegamento gli interi, che sono invece uno spazio molto ampio, e

questo tipo base, avrò quindi i seguenti 4 elementi: (1, 56), (2, 35), (3,

77), (4, 78), quindi abbiamo che come primo valore da 1 a 4 e poi tutte

le altre possibili combinazioni, ma l’array che consideriamo è un

elemento del prodotto cartesiano, cioè un sottoinsieme particolare.

Quindi l’array in se mappa un insieme finito su un insieme

potenzialmente infinito (che non può essere infinito nella macchina ma

potenzialmente molto numeroso).

Il tipo astratto non ha in se una nozione di ordinamento dell’indice,

cioè 1, 2, 3, 4 sono ordinati perché gli interi sono ordinati, ma potrei

fare un array indicizzato sugli insiemi rosso, verde e blu, che è un

insieme enumerato e i tipi enumerati non sono ordinati.

Quindi l’array non è ordinato su un indice perché l’indice potrebbe non

avere un ordinamento naturale. L’importante è che sia un sottotipo

finito, cioè che comunque noi possiamo enumerare i valori e mettere in

collegamento il valore del tipo indice con un valore che sta invece nel

tipo base. Gli array sono omogenei.

Se noi poniamo ulteriori restrizioni a queste cose otteniamo

rappresentazioni (con tipi concreti) degli array che possono essere

diverse e più o meno efficienti in termini di tempo di accesso, ad

esempio se limitiamo il tipo indice ad essere un sottotipo intero

abbiamo gli array che sono normalmente implementati nelle macchine,

dove addirittura l’architettura di macchina ci mette a disposizione

l’indirizzamento base più indice e noi a velocità estremamente elevata

riusciamo a individuare l’elemento corrispondente all’indice che

consideriamo, questo è però un caso molto particolare in cui gli indici

sono interi e nel caso delle macchine partono da 0, se lo faccio partire

da 100 ho sprecato 100 elementi di memoria. Se poi andiamo ai tipi

enumerati, ad esempio considerando i colori, allora non abbi