Strutture ed Algoritmi -...

Quaderni di Informatica

Strutture ed Algoritmi

Luigino Calvi

I.I.S. Negrelli-Forcellini - Feltre2017

ii

L. Calvi - Quaderni di Informatica - Strutture ed Algoritmi - 2017

Indice

1 Strutture 11.1 VALORI ED INDIRIZZI . . . . . . . . . . . . . . . . . . . . . . . 21.2 VARIABILI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.3 OGGETTI E RIFERIMENTI . . . . . . . . . . . . . . . . . . . . 31.4 ENTITÀ E LORO ATTRIBUTI . . . . . . . . . . . . . . . . . . . 6

1.4.1 ENTITÀ MUTABILI ED IMMUTABILI . . . . . . . . . 61.4.2 AMBITO DI VISIBILITÀ . . . . . . . . . . . . . . . . . . 61.4.3 ATTRIBUTI DI ACCESSIBILITÀ . . . . . . . . . . . . . 61.4.4 TEMPO DI VITA . . . . . . . . . . . . . . . . . . . . . . . 6

1.5 NOTAZIONI DELLE OPERAZIONI . . . . . . . . . . . . . . . . 71.6 STRUTTURE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.7 CLASSIFICAZIONE DELLE STRUTTURE . . . . . . . . . . . 81.8 OPERAZIONI SULLE STRUTTURE . . . . . . . . . . . . . . . 91.9 MODIFICA DI UNA STRUTTURA . . . . . . . . . . . . . . . . 91.10 TIPOLOGIA DELLE STRUTTURE . . . . . . . . . . . . . . . . 101.11 ELABORAZIONE DI STRUTTURE . . . . . . . . . . . . . . . . 111.12 ITERABILI, ITERATORI E GENERATORI . . . . . . . . . . . 121.13 ESERCIZI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2 Sequenze 152.1 LE SEQUENZE . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.2 RAPPRESENTAZIONI DELLE SEQUENZE . . . . . . . . . . . 172.3 OPERAZIONI SULLE SEQUENZE . . . . . . . . . . . . . . . . 182.4 GENERAZIONE DI SEQUENZE . . . . . . . . . . . . . . . . . . 202.5 COSTRUZIONE DI SEQUENZE . . . . . . . . . . . . . . . . . . 222.6 ACCESSO AGLI ELEMENTI . . . . . . . . . . . . . . . . . . . . 262.7 ELABORAZIONE DI SEQUENZE . . . . . . . . . . . . . . . . . 272.8 ESERCIZI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

iii

iv INDICE

3 Array 353.1 GLI ARRAY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363.2 ESERCIZI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

4 Matrici 414.1 LE MATRICI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424.2 ELABORAZIONE DI MATRICI . . . . . . . . . . . . . . . . . . 434.3 OPERAZIONI SULLE MATRICI . . . . . . . . . . . . . . . . . . 444.4 SOLUZIONE DI UN SISTEMA LINEARE . . . . . . . . . . . . 464.5 ESERCIZI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

5 Fliste 535.1 FLISTE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545.2 ELABORAZIONE DI FLISTE . . . . . . . . . . . . . . . . . . . 565.3 ALGORITMI SULLE FLISTE SEMPLICI . . . . . . . . . . . . 585.4 ALGORITMI SULLE FLISTE COMPOSTE . . . . . . . . . . . 605.5 ARRAY E FLISTE . . . . . . . . . . . . . . . . . . . . . . . . . . 615.6 ESERCIZI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

6 Complessità Computazionale 676.1 LA COMPLESSITÀ COMPUTAZIONALE . . . . . . . . . . . . 686.2 OPERAZIONE DOMINANTE . . . . . . . . . . . . . . . . . . . 696.3 DIMENSIONE DI UN PROBLEMA . . . . . . . . . . . . . . . . 706.4 COMPLESSITÀ DI UN ALGORITMO . . . . . . . . . . . . . . 706.5 COMPLESSITÀ DI UN PROBLEMA . . . . . . . . . . . . . . . 716.6 COMPLESSITÀ ASINTOTICA . . . . . . . . . . . . . . . . . . . 716.7 PROBLEMI INTRATTABILI . . . . . . . . . . . . . . . . . . . . 726.8 ESERCIZI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

7 Ordinamento 797.1 IL PROBLEMA DELL’ORDINAMENTO . . . . . . . . . . . . . 807.2 ORDINAMENTO DI SEQUENZE . . . . . . . . . . . . . . . . . 817.3 FAMIGLIE DI ALGORITMI . . . . . . . . . . . . . . . . . . . . 817.4 ORDINAMENTO A BOLLE . . . . . . . . . . . . . . . . . . . . 827.5 ORDINAMENTO PER SELEZIONE . . . . . . . . . . . . . . . 847.6 ORDINAMENTO PER INSERZIONE . . . . . . . . . . . . . . . 857.7 ORDINAMENTO VELOCE . . . . . . . . . . . . . . . . . . . . . 867.8 ESERCIZI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

L.Calvi - Quaderni di Informatica - Strutture ed Algoritmi - 2017

INDICE v

8 Ricerca 918.1 IL PROBLEMA DELLA RICERCA . . . . . . . . . . . . . . . . 928.2 LA RICERCA IN UNO SPAZIO INFINITO . . . . . . . . . . . 948.3 RICERCA IN UNA SEQUENZA . . . . . . . . . . . . . . . . . . 958.4 RICERCA IN SEQUENZE NON ORDINATE . . . . . . . . . . 958.5 RICERCA IN ARRAY ORDINATI . . . . . . . . . . . . . . . . . 978.6 RICERCA ED ORDINAMENTO . . . . . . . . . . . . . . . . . . 988.7 ESERCIZI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

9 Rappresentazione 1039.1 RAPPRESENTAZIONE . . . . . . . . . . . . . . . . . . . . . . . 1049.2 RAPPRESENTAZIONI CON STRUTTURE . . . . . . . . . . . 1069.3 COMPOSIZIONE DI RAPPRESENTAZIONI . . . . . . . . . . 1079.4 RAPPRESENTAZIONI DI AGGREGAZIONI . . . . . . . . . . 1119.5 OPERAZIONI SULLE STRUTTURE . . . . . . . . . . . . . . . 1139.6 IMPLEMENTAZIONE . . . . . . . . . . . . . . . . . . . . . . . . 1159.7 ESERCIZI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

10 Contenitori 12110.1 CONTENITORI . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12210.2 ATTRAVERSAMENTO DI CONTENITORI . . . . . . . . . . . 12310.3 CONTENITORI DI CONTENITORI . . . . . . . . . . . . . . . 12610.4 TIPOLOGIE DI CONTENITORI . . . . . . . . . . . . . . . . . . 128

10.4.1 SEQUENZE . . . . . . . . . . . . . . . . . . . . . . . . . . 12910.4.2 PILE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13010.4.3 CODE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13110.4.4 CODE A PRIORITÀ . . . . . . . . . . . . . . . . . . . . . 13210.4.5 INSIEMI . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

10.5 IMPLEMENTAZIONE DI CONTENITORI . . . . . . . . . . . 13410.6 ESERCIZI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136

11 Alberi 13911.1 ALBERI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14011.2 RAPPRESENTAZIONI DEGLI ALBERI . . . . . . . . . . . . . 14111.3 METODI DI VISITA DEGLI ALBERI . . . . . . . . . . . . . . 14311.4 ALBERI BINARI . . . . . . . . . . . . . . . . . . . . . . . . . . . 14411.5 OPERAZIONI SUGLI ALBERI BINARI . . . . . . . . . . . . . 14411.6 VISITA DEGLI ALBERI BINARI . . . . . . . . . . . . . . . . . 14511.7 RAPPRESENTAZIONI DI ALBERI BINARI . . . . . . . . . . 14611.8 ALBERI BINARI DI RICERCA . . . . . . . . . . . . . . . . . . 147


vi INDICE

11.9 ESERCIZI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149

12 Grafi 15312.1 GRAFI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15412.2 OPERAZIONI SUI GRAFI . . . . . . . . . . . . . . . . . . . . . 15612.3 CAMMINI E PERCORSI . . . . . . . . . . . . . . . . . . . . . . . 15612.4 TIPOLOGIE DI GRAFI . . . . . . . . . . . . . . . . . . . . . . . 15712.5 RAPPRRESENTAZIONI DEI GRAFI . . . . . . . . . . . . . . . 15812.6 PROBLEMI SUI GRAFI . . . . . . . . . . . . . . . . . . . . . . . 160

12.6.1 Problema del cammino minimo . . . . . . . . . . . . . . . 16012.6.2 Problema del collegamento minimo . . . . . . . . . . . . . 16012.6.3 Problema del commesso viaggiatore . . . . . . . . . . . . 16012.6.4 Problema dell’isomorfismo fra grafi . . . . . . . . . . . . . 16112.6.5 Problema della planarità di un grafo . . . . . . . . . . . . 161

12.7 ESERCIZI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162


Capitolo 1

Strutture

I programmi per computer usualmenteoperano su tabelle d’informazioni. Nel-la maggioranza dei casi queste tabelle nonsono semplicemente masse amorfe di va-lori numerici; esse coinvolgono importantirelazioni strutturali fra i dati elementi.D. Knuth,The Art of Computer Programming

Uno dei concetti fondamentali e trasversali a tutta l’informatica, e non soloall’informatica, si fonda sul meccanismo della composizione di elementi di base,raggruppandoli in un’unica entità che può essere considerata, denominata emanipolata in modo unitario. Questo artificio sottende il concetto di costruire:in fondo, questa non è una scoperta dell’informatica in quanto è la stessastrategia che consente all’artigiano di costruire un cesto intrecciando un fasciodi vimini.

Nella composizione, in taluni casi è sufficiente considerare gli elementi chevengono composti, considerandoli individualmente, come elementi di un in-sieme; in altri casi è importante considerare la struttura con cui gli elementivengono composti. Riprendendo l’esempio sopra, il peso del cesto vuoto puòessere determinato calcolando il peso del fascio di vimini con i quali è compo-sto, ma se si vuole utilizzare il cesto come contenitore, è necessario che i viminisiano intrecciati opportunamente. Poi, nella sua percezione di alto livello, unutente del cesto può trascurare di considerare i singoli vimini e limitarsi aconsiderare la funzionalità del cesto come contenitore di oggetti.

1

2 CAPITOLO 1. STRUTTURE

1.1 VALORI ED INDIRIZZI

Nella memoria del computer sono localizzate le istruzioni ed i dati. I datipossono essere classificati come segue:

• valori: dati che rappresentano informazioni rilevanti per l’applicazionedell’utente (dati del problema, dati intermedi ottenuti nel processo dielaborazione, risultati, . . . )

• indirizzi: dati che individuano una posizione in memoria dove sono me-morizzati istruzioni o dati. Gli indirizzi sono generalmente accessibili so-lo mediante i linguaggi di programmazione di basso livello; nei linguaggidi alto livello vengono mascherati mediante il concetto di riferimento.

1.2 VARIABILI

Un significativo passo di astrazione introdotto dai linguaggi di programmazio-ne di alto livello è consistito nel denotare le istruzioni ed i dati mediante dei no-mi identificativi. Questo artificio ha portato ad una notevole semplificazionenella scrittura dei programmi.

In un programma (sorgente) i dati vengono denotati mediante dei nomiidentificativi detti variabili. Le variabili costituiscono uno dei concetti fon-damentali dei linguaggi di programmazione a paradigma imperativo. Unavariabile identifica una zona di memoria dove è memorizzato un dato; puòessere pensata come una scatola, identificata mediante un nome, contenenteun dato. Con la locuzione variabile x oppure valore della variabile x si deno-ta il dato contenuto nella variabile x, mentre con la locuzione indirizzo dellavariabile x si denota l’indirizzo della posizione di memoria dove è localizzatoil dato individuato dalla variabile x. Una variabile contenente un indirizzo dimemoria viene detta puntatore.

Per rappresentare graficamente la situazione in cui una variabile x contieneun valore val si usa la notazione riportata in figura 1.1.

x val

Figura 1.1: Variabile x contenente il valore val.


1.3. OGGETTI E RIFERIMENTI 3

Nel seguito, come avviene nei linguaggi C/C++, Java, Python ed altri,si utilizzerà l’operatore = per denotare un’assegnazione ad una variabile el’operatore == per denotare un confronto di uguaglianza.

Se exp è un’espressione che, valutata, produce un valore, un’assegnazionedella forma

x = exp

ha l’effetto di valutare l’espressione exp ottenendo un valore che viene poimemorizzato nella variabile x. Ad esempio, un’assegnazione della forma

x = x + 1

ha l’effetto di incrementare di 1 il valore della variabile x. Un’assegnazionedella forma

y = x

ha l’effetto di assegnare alla variabile y il valore della variabile x. In questocaso le due variabili x ed y mantengono comunque un’identità distinta ed unamodifica ad una delle due non si ripercuote sull’altra. Coerentemente contutto ciò, un controllo della forma

x == y

è vero se e solo se le due variabili hanno valori uguali.

1.3 OGGETTI E RIFERIMENTIGli oggetti sono le entità tipiche dei linguaggi orientati agli oggetti. Vengonocreati dinamicamente durante l’esecuzione del programma e vengono denotatimediante degli identificatori detti riferimenti.

Per rappresentare graficamente la situazione in cui un riferimento a denotaun oggetto obj si usa la notazione riportata in figura 1.2.

a obj��-

Figura 1.2: Riferimento a che referenzia l’oggetto obj.

Una differenza significativa fra variabili e riferimenti emerge nelle opera-zioni di assegnazione e nelle comparazioni.



Se a è un identificatore (riferimento) ed exp è un’espressione che, valutata,produce un oggetto, un’assegnazione della forma

a = exp

ha l’effetto di valutare l’espressione exp generando un oggetto che viene refe-renziato da a.

Se a è un riferimento ad un oggetto alfa, con una successiva assegnazionedella forma

b = asi ottiene l’effetto che anche il riferimento b referenzia l’oggetto referenziatoda a; l’oggetto alfa risulta accessibile indifferentemente mediante uno dei dueriferimenti a o b; la situazione è descritta nella figura 1.3.

a��alfa-

b

6

Figura 1.3: Riferimenti a e b che referenziano l’oggetto alfa.

Una successiva assegnazione della forma

a = exp1

dove exp1 è un’espressione che, valutata, genera un oggetto beta, genera lasituazione descritta nella figura 1.4.

a��beta-

b

��alfa-

Figura 1.4: Riferimenti a e b che referenziano due oggetti distinti.


1.3. OGGETTI E RIFERIMENTI 5

Per i riferimenti bisogna distinguere fra le seguenti due forme di compara-zione di uguaglianza:

• i due riferimenti referenziano lo stesso oggetto 1

• i due riferimenti referenziano oggetti uguali 2

Esempio 1. In Python ogni dato è un oggetto; alla luce di questo fatto leseguenti assegnazioni fra liste:

a = [2,4,6]b = [a,5]c = a[0]d = c + a[2]e = [a[1],b[1]]

producono la situazione di memoria descritta nella figura che segue.

a

c

d

e -

6

��

-

-

-

b� �� ?

BBBBN ?

��8

��2��4��6��5

Osservazione. Le due diverse modalità secondo le quali si comportano leoperazioni di assegnazione e comparazione fra variabili che contengono valorie riferimenti che referenziano oggetti vanno sotto il nome di semantica deivalori e semantica dei riferimenti.

1a == b in Java; a is b in Python2a.equals(b) in Java; a == b in Python



1.4 ENTITÀ E LORO ATTRIBUTIRiferendosi indifferentemente ad un valore o ad un oggetto si usa generica-mente il termine entità. Le entità (valori ed oggetti) vengono classificatein base a delle caratteristiche di diversa natura, come descritto nei seguentisottoparagrafi.

1.4.1 ENTITÀ MUTABILI ED IMMUTABILI

Un’entità si dice mutabile se, una volta creata, può essere modificata con dellesuccessive istruzioni; altrimenti l’entità si dice immutabile.

1.4.2 AMBITO DI VISIBILITÀ

Con il termine ambito di visibilità (scope) di un oggetto si denota la porzionedi programma nella quale l’oggetto è visibile ed utilizzabile. Generalmentel’ambito di visibilità di un’entità è costituito dal blocco nel quale l’entità èdefinita.

1.4.3 ATTRIBUTI DI ACCESSIBILITÀ

Le entità visibili possono esibire diversi gradi di accessibilità che dipendonoda chi, da dove e da quando si accede:

• read-only: l’entità è accessibile, ma non modificabile

• read-write: l’entità è accessibile e modificabile

• blocked: l’entità non è momentaneamente accessibile (a causa di uncontemporaneo accesso da parte di un altro processo; tale situazionesi verifica nella gestione di entità condivise da parte di più processiconcorrenti)

1.4.4 TEMPO DI VITA

Con il termine tempo di vita (lifetime) di un’entità si denota il tempo cheintercorre dal momento della creazione di un oggetto al momento in cui vienedistrutto. Spesso il tempo di vita di un’entità corrisponde all’intervallo ditempo nel quale viene eseguito il blocco nel quale l’entità è definita.


1.5. NOTAZIONI DELLE OPERAZIONI 7

1.5 NOTAZIONI DELLE OPERAZIONIL’elaborazione delle entità si fonda sull’esecuzione di operazioni che possonomodificare le entità stesse oppure produrre, come risultato, nuove entità.

Le più frequenti notazioni utilizzate nei linguaggi di programmazione perdescrivere le operazioni sono riportate nell’elenco che segue; nell’esempio de-scritto si fa riferimento all’operazione di addizione fra due numeri a e b.

• infissa: a + b

• funzionale: add(a, b)

• ad oggetti: a.add(b)

1.6 STRUTTURENei vari linguaggi di programmazione le entità vengono spesso classificate nelleseguenti due categorie:

• elementi: sono i valori elementari, atomici, forniti direttamente dallinguaggio; vengono detti anche atomi

• strutture: sono le entità composte da oggetti elementari e da altri oggetticomposti, mediante appositi meccanismi del linguaggio

Gli elementi costituenti una struttura possono essere di diversa natura. Allivello di astrazione predisposto dai tradizionali linguaggi di programmazione,gli elementi costituenti una struttura sono numeri, stringhe, istruzioni elemen-tari del linguaggio ed altro ancora; ad un livello più basso, gli atomi sono ibyte e le istruzioni in linguaggio macchina; ad un livello più alto, in un sistemacomplesso, gli atomi del sistema sono le componenti del sistema stesso.

Le strutture possono essere formate da elementi che sono a loro volta com-posti da elementi più elementari. La potenza dei linguaggi di programmazioneviene esplicata proprio mediante la possibilità di comporre fra loro delle entitàdi base.



1.7 CLASSIFICAZIONE DELLE STRUTTURELe strutture possono essere classificate in base a diverse caratteristiche. Consi-derando la struttura organizzativa interna e le modalità di accesso agli elementicomponenti, le strutture possono essere classificate come segue 3 :

• sequenze: strutture formate da un numero finito di elementi dispostiin sequenza; ogni elemento occupa una ben precisa posizione all’internodella sequenza (dalla posizione 0 in avanti); le sequenze si suddividononelle seguenti tipologie:

– liste: sequenze mutabili denotate con le notazioni [. . . ]– tuple: sequenze immutabili denotate con la notazione (. . . )– stringhe: sequenze immutabili composte da caratteri e denotate con

la tradizionale notazione matematica ” . . . ”

• insiemi: strutture formate da un numero finito di elementi che non han-no un preciso ordine; gli elementi possono essere presenti con una solaoccorrenza; vengono denotati con la notazione {. . .}

• dizionari: strutture formate da un numero finito di elementi individuatida una chiave univoca; inoltre, gli elementi non hanno un preciso ordinee possono essere presenti più volte; in un dizionario un elemento e aventechiave k viene denotato con la notazione k ∶ e; un dizionario viene deno-tato con la notazione {. . .}; in un dizionario a un elemento di chiave kviene acceduto con la notazione a[k]

• successioni: sequenze infinite ed immutabili di elementi che vengonogenerati al momento dell’accesso; vengono denotate con la notazione(. . . )

Le strutture fondamentali sopra descritte possono essere composte fra loroper ottenere strutture molto articolate.

3Coerentemente con le convenzioni del linguaggio Python.


1.8. OPERAZIONI SULLE STRUTTURE 9

1.8 OPERAZIONI SULLE STRUTTUREOgni meccanismo di composizione comporta la definizione di meccanismi diaccesso e di manipolazione degli elementi componenti. Per questo motivosulle strutture sono predisposti degli appositi operatori che sono classificaticome segue:

• costruttori: sono delle operazioni che generano strutture

• selettori: sono delle operazioni che permettono di accedere ad uno spe-cifico elemento della struttura; in taluni casi un selettore può fornire,come risultato, una parte della struttura.

• manipolatori: sono delle operazioni che hanno l’effetto di modificare lastruttura, mediante operazioni di inserimento, eliminazione e modificadi elementi.

Queste categorie di operatori (costruttori, selettori, manipolatori) sonorealizzate con diverse modalità, dando origine a diverse tipologie di struttura.

Le strutture possono essere classificate in base alle operazioni che possonoessere eseguite:

• in base alle modalità di accesso agli elementi componenti: le operazionidi accesso agli elementi componenti una struttura sono realizzate condiverse modalità e danno luogo a diverse tipologie di strutture

• in base alle operazioni di modifica: le operazioni di inserimento, elimina-zione e modifica degli elementi di una struttura possono essere realizzatecon diverse modalità

A seconda delle operazioni permesse, le strutture assumono diversi nomi (se-quenze, insiemi, pile, code, . . . ).

1.9 MODIFICA DI UNA STRUTTURALa modifica di una struttura può avvenire con diverse modalità:

• modificando un elemento presente

• inserendo un nuovo elemento

• eliminando un elemento presente



Operativamente, una operazione di modifica può essere realizzata secondodue diverse modalità:

• modalità funzionale: l’operazione genera una nuova struttura che costi-tuisce il risultato dell’operazione

• modalità procedurale: l’operazione modifica la struttura alla quale vieneapplicata; tale modalità è applicabile solo se l’argomento dell’operazioneè un riferimento che identifica una struttura

Solitamente i due approcci sono entrambi disponibili nella maggior partedei linguaggi di programmazione e possono essere utilizzati interscambievol-mente. Essi tuttavia sono profondamente diversi e rientrano in due paradigmidi programmazione distinti; il primo (paradigma funzionale) suggerisce spessodelle soluzioni ricorsive e non richiede l’uso di variabili, riferimenti ed asse-gnazioni; il secondo approccio (paradigma procedurale) si fonda sul fatto cheun’operazione modifica direttamente la struttura alla quale viene applicata; inquesti casi solitamente si fa ricorso ad algoritmi basati su cicli e si fa uso di va-riabili, riferimenti e assegnazioni che permettono di modificare selettivamenteun elemento della struttura.

1.10 TIPOLOGIA DELLE STRUTTURELe strutture possono essere classificate anche in base agli elementi componenti:

• in base al tipo degli elementi componenti: se tutti gli elementi sono dellostesso tipo le strutture vengono dette omogenee, altrimenti vengono detteeterogenee

• in base alla struttura degli elementi componenti: se tutti gli elementi sonoelementari (numeri, valori logici, caratteri, stringhe, . . . ) le strutturevengono dette semplici o piatte, altrimenti, se le strutture costituite daelementi che sono a loro volta delle strutture, vengono dette composte ostrutturate

Esempio 2. A seguire sono riportate alcune espressioni di strutture eterogenee:

[7, FALSE]

[′+′,8,5,3,6,2]

[”Mario”, ”Rossi”,2, ”maggio”,2012]


1.11. ELABORAZIONE DI STRUTTURE 11

Esempio 3. A seguire sono riportati alcuni esempi di strutture composte:

[ [ [ ] ], [ ] ]

[3, [4,5],2, [ [6], [ ] ] ]

[ [”Mario”, ”Rossi”], [2, ”maggio”,2012] ]

[ [”rosso”, [255,0,0] ], [”verde”, [0,255,0] ] ]

Esempio 4. Una struttura composta si presta a descrivere un’espressione, rap-presentando in modo uniforme operatori di diverse arietà e di diverse notazioni,mediante la generica notazione

[⊗, x1, . . . , xn]dove ⊗ denota un generico operatore e gli argomenti xi sono delle genericheespressioni. La seguente tabella descrive alcuni esempi di espressioni descrittein notazione algebrica e nella corrispondente notazione mediante strutturecomposte.

notazione algebrica notazione mediante sequenza2 + 3 [+,2,3]a/(b + c) [/, a, [+, b, c] ]x cos(1/x) [∗, x, [cos, [/,1, x] ] ]

x+1ax+by [/, [+, x,1], [+, [∗, a, x], [∗, b, y] ]

1.11 ELABORAZIONE DI STRUTTURELe strutture possono essere elaborate mediante alcune operazioni di tipo ge-nerale, descritte mediante il seguente esempio.Esempio 5. A partire dalla seguente lista composta:

[1, [2,3], [ [′x′] ] ]si possono ottenere le seguenti trasformazioni irreversibili:

• appiattimento (flat) : si ottiene la lista semplice [1,2,3,′ x′,4]

• scheletro (skel) : si ottiene la lista [ [ ], [ [ ] ] ]

• struttura anonima (struct) : si ottiene la lista [∗, [∗,∗], [ [∗] ] ]

• struttura tipizzata (type) : si ottiene la lista [int, [int, int], [ [char] ] ]



1.12 ITERABILI, ITERATORI E GENERATORIUn iterabile è un oggetto contenitore di elementi che può essere elaborato inun ciclo for come descritto nell’algoritmo 1.

Algoritmo 1 - Ciclo per l’elaborazione di un iterabile1: for elemento in iterabile do2: elabora(elemento)3: end for

Un iteratore è un oggetto mediante il quale si può accedere ad una serie dielementi. Se k è un iteratore, con next(k) si ottiene il prossimo elemento.

Generalmente gli iteratori non hanno vita autonoma ma vengono utilizzaticome strumento per accedere agli elementi di un contenitore iterabile. Sea è un oggetto iterabile, con iter(a) si ottiene un oggetto iteratore medianteil quale si può accedere agli elementi dell’iterabile. Pertanto, una formaalternativa di elaborazione di un iterabile è descritta nell’algoritmo 2.

Algoritmo 2 - Ciclo per l’elaborazione di un iterabile mediante un iteratore1: k = iter(iterabile)2: loop3: elabora(next(k))4: end loop

La terminazione del ciclo può essere impostata con una condizione sullagrandezza dell’iterabile oppure gestendo l’eccezione StopIteration che vienesollevata nel caso in cui l’iteratore esaurisca la serie degli elementi.

Un generatore è un particolare iteratore che non opera in simbiosi con uniterabile ma fornisce gli elementi generandoli al momento in cui vengono ri-chiesti. I valori vengono forniti dal generatore richiamando il metodo next sulgeneratore. Un generatore viene definito in modo analogo ad una funzione,con la differenza che usa un’istruzione yield al posto di return per fornireil valore. Quando l’esecuzione raggiunge un’istruzione yield viene generatoil valore risultante e la funzione o metodo viene sospesa ma viene mantenutolo stato dell’esecuzione e dei valori locali. Il controllo dell’esecuzione vieneceduto al chiamante. Quando la funzione viene richiamata nuovamente, l’ese-cuzione riprende dall’istruzione che segue yield. Mentre l’istruzione returncausa la distruzione dell’ambiente della funzione al momento dell’uscita dellafunzione, l’istruzione yield conserva l’ambiente fino alla successiva chiamatadel metodo next; ciò consente al generatore di conservare il proprio stato.


1.13. ESERCIZI 13

1.13 ESERCIZI1. Con riferimento alla situazione riportata nella figura 1.4, eseguire lo

scambio fra i due oggetti alfa e beta (senza ricreare nuovamente i dueoggetti).

2. Descrivere graficamente al situazione che si crea con le assegnazioni

a = [1,2,3,4]b = [a,a[2]]

Spiegare come si evolve la situazione con la sequenza di assegnazioni

a[0] = a[1]a[1] = b[1]a[2] = b

3. Descrivere una struttura in grado di descrivere i dati anagrafici di unapersona, costituiti da cognome, nome, data di nascita.

4. Descrivere mediante una struttura l’espressione algebrica

1 − ab + 2c

5. Determinare la sequenza che si ottiene appiattendo la struttura

[ [4, [3],6, [ [1,8] ] ]

6. Analizzare le proprietà delle relazioni fra strutture descritte nel seguenteelenco:

(a) sR1 t se e solo se flat(s) = flat(t)(b) sR2 t se e solo se skel(s) = skel(t)(c) sR3 t se e solo se struct(s) = struct(t)(d) sR4 t se e solo se type(s) = type(t)


Capitolo 2

Sequenze

Nella sua forma più semplice, una tabel-la può essere una lista lineare di elemen-ti, quando le sue proprietà strutturali rile-vanti includono la risposta a questioni co-me: quale elemento è il primo della lista?qual è l’ultimo? quali elementi precedonoe seguono un dato elemento? quanti ele-menti ci sono nella lista? C’è molto dadire sulla struttura perfino su questo casoapparentemente semplice.D. Knuth,The Art of Computer Programming

Le sequenze sono strutture formate da un numero finito di elementi dispo-sti in fila, uno dopo l’altro; ogni elemento occupa una ben precisa posizioneall’interno della sequenza.

Il concetto di sequenza è più forte del concetto di insieme, in quanto una se-quenza stabilisce anche la posizione d’ordine degli elementi componenti. Nonsi tratta quindi di una semplice composizione insiemistica degli elementi, madi una composizione in sequenza in quanto ogni elemento della struttura ècaratterizzato da una sua specifica posizione.

Il meccanismo di sequenzializzazione fornisce il supporto per lo sviluppodi moltissimi ed importantissimi algoritmi, come gli algoritmi di ricerca edi ordinamento. Inoltre, le sequenze costituiscono un meccanismo spessoutilizzato per realizzare delle particolari strutture di dati astratte.

15

16 CAPITOLO 2. SEQUENZE

2.1 LE SEQUENZE

Gli elementi che costituiscono una struttura possono essere organizzati in di-versi modi; una delle forme più elementari di organizzazione è costituita dallasequenzializzazione che consiste nel disporre (fisicamente) o considerare (vir-tualmente) gli elementi in fila, uno dopo l’altro, secondo lo schema descrittonella figura 2.1. Per compatibilità con molti linguaggi di programmazione(C/C++, Java, Python) le posizioni degli elementi in una sequenza inizianodalla posizione 0.

● ● ● ● ● ● ● ● ●0 1 2 3 4 5 6 7 8

Figura 2.1: Una sequenza di 8 elementi.

Il formalismo per denotare le sequenze è descritto nella seguente definizio-ne.

DEFINIZIONE 1. Con il termine sequenza si indica una struttura di ele-menti, detti atomi, disposti in fila, uno dopo l’altro; in generale, un atomo ouna sequenza viene chiamato elemento. Se a0, . . . , an sono degli elementi, lascrittura

[a0, . . . , an]

denota la sequenza costituita dagli elementi a0, . . . , an, mentre la scrittura

[ ]

denota la sequenza vuota, ossia la sequenza composta da nessun elemento.Data una sequenza a = [a0, . . . , an] e degli indici i, j tali che 0 ≤ i ≤ j ≤ n,la sequenza [ai, . . . , aj] dicesi sottosequenza di a. Se i = 0 la sottosequenza èdetta prefisso (di a); se j = n la sottosequenza è detta suffisso (di a).Se h e k sono due numeri naturali con

range(h, k)

si denota la sequenza di numeri naturali da h a k − 1 mentre con

range(k)

si denota la sequenza di numeri naturali da 0 a k − 1.


2.2. RAPPRESENTAZIONI DELLE SEQUENZE 17

Esempio 6. Dalla definizione di sequenza, si può immediatamente riconoscereche i seguenti sono degli esempi di sequenze:

[ ]

[7]

[3,2,5]

2.2 RAPPRESENTAZIONI DELLE SEQUENZE

Una sequenza [a0, a1, . . . , an] viene spesso descritta graficamente mediante unoschema a tabella come quello riportato nella figura 2.2.

a0 a1 . . . an

Figura 2.2: Rappresentazione grafica tabellare della sequenza [a0, a1, . . . , an].

In talune considerazioni, specialmente nel caso di sequenze composte, risul-ta utile descrivere una sequenza mediante uno schema ad albero: una genericasequenza [a0, . . . , an] viene descritta come illustrato nella figura 2.3.

��

��

��

��

@@@@@@@@R

◻

a0 a1 . . . an

Figura 2.3: Rappresentazione grafica ad albero della sequenza [a0, a1, . . . , an].

Esempio 7. La sequenza [a, [b], [ [ ], c, d] ] è descritta dall’albero riportato infigura 2.4.



?

◻�

��

��

@@@@@R

a

?

◻

?

◻��

BBBBBN

b � c d

Figura 2.4: Rappresentazione grafica ad albero della sequenza[a, [b], [ [ ], c, d] ]. Il simbolo � denota l’operatore di sequenzializzazio-ne se si trova in un nodo interno, mentre denota la sequenza vuota se si trovasu un nodo foglia.

2.3 OPERAZIONI SULLE SEQUENZELa costruzione di una sequenza [a0, . . . , an] può essere vista come l’applicazio-ne dell’operatore [ ] in notazione distribuita applicato agli operandi a0, . . . , an.Tale operazione viene detta sequenzializzazione.

Data una generica sequenza a, con

len(a)

si denota la lunghezza di a, ossia il numero di elementi che la compongono. Lasequenza vuota [ ] ha lunghezza 0.

L’operazione di concatenazione fra due sequenze produce come risultatouna sequenza costituita dagli elementi della prima sequenza seguiti dagli ele-menti della seconda; l’operazione di concatenazione viene solitamente denotatamediante l’operatore binario infisso + come segue:

[a0, . . . , an] + [b0, . . . , bm] = [a0, . . . , an, b0, . . . , bm]

Spesso, qualora non risulti ambiguo, nei testi il segno + dell’operatore di con-catenazione viene omesso e le due liste da concatenare vengono semplicementescritte affiancate. La sequenza vuota [ ] costituisce l’elemento neutro (sinistroe destro) per l’operazione di concatenazione. L’operazione di concatenazio-ne gode della proprietà associativa, ossia, per generiche sequenze a, b, c, valel’identità (a b)γ = a(b c); l’operazione di concatenazione non gode invece dellaproprietà commutativa, ossia, in generale, a b ≠ b a.

Le operazioni di inserimento in testa ed aggiunta in coda di un elemen-to in una sequenza possono essere espresse tramite l’operatore [ ] di sequen-zializzazione e l’operatore + di concatenazione, come illustrato dai seguenti


2.3. OPERAZIONI SULLE SEQUENZE 19

esempi:[x] + [p, q, r] = [x, p, q, r]

[p, q, r] + [x] = [p, q, r, x]

Sulle sequenze si può applicare l’operazione di ripetizione: il risultato dellaripetizione di una sequenza a = [a0, . . . , an] per una costante naturale k ècostituito da una sequenza ottenuta concatenando k sequenze a, ossia

k ∗ [a0, . . . , an] = [a0, . . . , an, a0, . . . , an, . . . ]

L’espressione naturale k è detta ripetitore. Il valore k = 1 costituisce l’ele-mento neutro per l’operazione di ripetizione di sequenze, ossia 1 ∗ a = a. Perconvenzione si pone 0∗a = [ ]. L’operazione di ripetizione può essere espressaanche in notazione postfissa, nella forma a ∗ k.

L’operazione di ripetizione di sequenze realizza anche il meccanismo dicostruzione e dimensionamento iniziale: l’espressione

n ∗ [x]

produce una sequenza di n elementi; ciascun elemento della sequenza vieneinizializzato con il valore x.

L’operazione di ripetizione di una sequenza per un numero gode di alcuneinteressanti proprietà; in particolare, se a è una sequenza e h e k sono duenumeri naturali, vale la proprietà

h ∗ a + k ∗ a = (h + k) ∗ a

Esempio 8. A seguire sono riportati alcuni esempi di operazioni e corrispon-denti calcoli sulle liste:

[1,2,3] + [4,5] → [1,2,3,4,5]5 ∗ [0] → [0,0,0,0,0]

4 ∗ [1,2] → [1,2,1,2,1,2,1,2]2 ∗ [3 ∗ [4]] → [[4,4,4], [4,4,4]]

Esempio 9. Le operazioni di aggregazione e ripetizione di elementi possonocombinarsi in tutti i modi possibili in modo da costituire un’effettiva algebracon proprie specifiche proprietà; segue qui un esempio di calcolo che illustra



come si opera in quest’algebra:

[0,1] + 2 ∗ (2 ∗ [0] + [1]) + [0] → [0,1] + 2 ∗ ([0,0] + [1]) + [0]→→ [0,1] + 2 ∗ [0,0,1] + [0]→→ [0,1] + [0,0,1] + [0,0,1] + [0]→→ [0,1] + [0] + [0,1] + [0] + [0,1] + [0]→→ [0,1,0] + [0,1,0] + [0,1,0]→→ 3 ∗ [0,1,0]

Esempio 10. Nel contesto dei linguaggi di programmazione le sequenze possonoessere denotate mediante degli identificatori e questi identificatori possonoessere usati come elementi costituenti altre sequenze; un esempio di questapossibilità è riportato nella sequenza di assegnazioni nella porzione di codicePython che segue.

a = [1,2,3] # a = [1,2,3]b = [4,5,6,7,8] # b = [4,5,6,7,8]c = a+b # c = [1,2,3,4,5,6,7,8]d = [a,b] # d = [[1,2,3],[4,5,6,7,8]]

2.4 GENERAZIONE DI SEQUENZEIn molte situazioni serve generare una sequenza come risultato dell’elabora-zione di un’altra. A questo scopo è predisposto il meccanismo denominatolist comprehension la cui sintassi è

[ espressione for valore in iterabile if condizione ]

Questa espressione produce una sequenza contenente i valori dell’iterabilesoddisfacenti alla condizione sottoposti alla valutazione dell’espressione. Laclausola if è opzionale.

Esempio 11. La sequenza [0,1,2,3,4,5,6,7,8,9] dei primi 10 numeri naturalipuò essere generata mediante l’espressione

[k for k in range(10)]

Esempio 12. La sequenza [0,4,16,36,64] dei quadrati dei numeri pari minoridi 10 può essere generata mediante l’espressione

[k*k for k in range(10) if k%2 == 0]


2.4. GENERAZIONE DI SEQUENZE 21

Esempio 13. La sottosequenza dei numeri pari di una sequenza a può esseregenerata come segue:

[k for k in a if k%2 == 0]

È possibile elaborare al volo una sequenza risultato senza averla completa-mente generata e memorizzata in una variabile concreta; a questo scopo è pre-disposto il meccanismo detto generator comprehension, che consiste nella con-nessione del meccanismo list comprehension con il meccanismo dei generatori;la sintassi è analoga a quella del meccanismo list comprehension:

( espressione for valore in iterabile if condizione )

Esempio 14. La chiamata

sum(x**2 for x in range(1,11))

ha come argomento della funzione sum un generatore di espressioni che forniscei quadrati dei numeri da 1 a 10 e fornisce come risultato complessivo il valore385. Il vantaggio di questa chiamata, rispetto alla chiamata

sum([x**2 for x in range(1,11)])

consiste nel fatto che questa seconda crea esplicitamente la sequenza dei qua-drati e successivamente viene elaborata. Il vantaggio risulta particolarmentesensibile in termini di prestazioni nel caso di grandi sequenze.Esempio 15. Il seguente esempio illustra la generazione di una successione dielementi, uno alla volta, al momento della richiesta, mediante il meccanismogenerator expression.

# quadrato dei numeri naturali pari ed inferiori a 20

# mediante un ciclo:for i in (k*k for k in range(20) if k%2==0):

print(i)

# mediante un generatore:g = (k*k for k in range(20) if k%2==0)for i in range(10):

print(next(g))



2.5 COSTRUZIONE DI SEQUENZE

Molti problemi sono caratterizzati dall’avere delle sequenze come risultato. Inquesti casi l’algoritmo risolvente il problema costruisce, generalmente medianteun adeguato controllo ciclico la cui forma dipende dallo specifico problema,una sequenza che costituirà alla fine il risultato del problema. Tale sequenzarisultato viene spesso costruita accodando man mano degli elementi, a partiredalla sequenza iniziale vuota. Il seguente esempio illustra la tecnica appenadescritta.Esempio 16. Sviluppiamo un algoritmo per scomporre un numero naturalein fattori primi. Facciamo riferimento all’usuale metodo di scomposizionedescritto dallo schema riportato nella figura 2.5 dal quale si ricava 126 = 2⋅32 ⋅7.In questo caso il risultato può essere rappresentato dalla sequenza [2,3,3,7].

126 263 321 37 71

Figura 2.5: Schema della scomposizione in fattori primi del numero 126.

Seguendo la traccia sopra, si arriva all’algoritmo 3.

Algoritmo 3 - Sequenza dei divisori primi di un numero naturaleInput: numero naturale nOutput: sequenza dei divisori primi di n1: inizializza la sequenza vuota a dei divisori2: considera d = 2 come primo potenziale divisore3: while n > 1 do4: while n è divisibile per d do5: accoda d alla sequenza dei divisori6: dividi n per d7: end while8: considera il numero primo successivo di d9: end while

10: return sequenza a dei divisori primi

Nell’algoritmo 3 rimangono ancora da esplicitare le soluzioni di alcunisottoproblemi; fra questi, l’unico di una qualche complessità è il seguente:


2.5. COSTRUZIONE DI SEQUENZE 23

considera il numero primo successivo di d

In prima approssimazione (anche se non ottimale) questo problema può essererisolto con l’istruzione

incrementa d di 1

La soluzione completa è riportata nell’algoritmo 4.

Algoritmo 4 - Lista dei divisori primi di un numero naturaleInput: numero naturale nOutput: lista dei divisori primi di n1: a← [ ]2: d← 23: while n > 1 do4: while (n%d) = 0 do5: a← a + [d]6: n← n/d7: end while8: d ++9: end while

10: return a

A seguire è riportata la codifica Python dell’algoritmo 4.

# sequenza dei divisori primi di ndef listaDivisori(n):

a = []d = 2while n>1:

while (n%d) == 0:a = a+[d]n = n // d

d += 1return a

Osservando che nessun numero pari, escluso 2, è primo, l’algoritmo discomposizione 4 risulta più efficiente se il divisore d viene incrementato di dueunità ad ogni ciclo, ossia se l’istruzione di incremento di d viene sostituita conincrementa d di 2.Esempio 17. L’algoritmo sviluppato nell’esempio precedente può essere adat-tato in modo che vengano determinati i fattori del numero n con le rispettive



molteplicità (vedi tabella 2.6). Una tabella di questo formato può essererappresentata mediante la sequenza di coppie [ [2,1], [3,2], [7,1] ].

fattore molteplicità2 13 27 1

Figura 2.6: Tabella della scomposizione del numero 126.

A seguire è riportato l’algoritmo che generalizza la tavola di traccia ripor-tata nella figura 2.6, in due versioni a diverso livello di dettaglio (algoritmi 5e 6).

Algoritmo 5 - Sequenza dei divisori primi di un numero naturaleInput: numero naturale nOutput: sequenza dei divisori primi di n1: inizializza la sequenza vuota dei divisori2: considera d = 2 come primo potenziale divisore3: while n > 1 do4: determina la molteplicità m del divisore d5: if m > 0 then6: accoda la coppia [d,m] alla sequenza dei divisori7: end if8: considera il numero primo successivo di d9: end while

10: return sequenza dei divisori primi


2.5. COSTRUZIONE DI SEQUENZE 25

Algoritmo 6 - Sequenza dei divisori primi di un numero naturaleInput: numero naturale nOutput: sequenza dei divisori primi di n1: a← [ ]2: d← 23: while n > 1 do4: m← 05: while (n%d) = 0 do6: m ++7: n← n/d8: end while9: if m > 0 then

10: a← a + [ [d,m] ]11: end if12: d ++13: end while14: return a

A seguire è riportata la codifica in linguaggio Python dell’algoritmo 6.

# sequenza dei divisori di un numero (con molteplicita’)def divisori(n):

a = []d = 2while n > 1:

m = 0while (n % d) == 0:

m += 1n //= d

if m > 0:a = a + [[d,m]]

d += 1return a



2.6 ACCESSO AGLI ELEMENTIOltre alle operazioni viste nei paragrafi precedenti mediante le quali è pos-sibile costruire o elaborare una sequenza mediante delle operazioni native omediante un’espressione (list comprehension e generator comprehension), inmolte situazioni si presenta la necessità di costruire o elaborare una sequen-za mediante un algoritmo, accedendo ed agendo individualmente sui singolielementi della sequenza.

L’accesso agli elementi di una sequenza può avvenire con diverse modalità:

• accesso mediante iteratori:poiché le sequenze sono contenitori iterabili, è possibile accedere ai loroelementi mediante il meccanismo degli iteratori descritto negli algorit-mi 1 e 2; questo meccanismo risulta indicato quando si debbano elaboraresequenzialmente tutti gli elementi di una sequenza.Esempio 18. Nel linguaggio Python liste, tuple, insiemi e dizionari sonocontenitori iterabili. La seguente porzione di codice illustra una tipicaelaborazione di una sequenza.

a = [10,20,30,40]

# accesso mediante iteratore implicitofor x in a:

print(x)

# accesso mediante iteratore esplicitok = iter(a)for i in range(len(a)):

print(next(k))

• accesso con indice:una modalità di accesso caratterizzante le sequenze è fornita dall’ac-cesso mediante indice; se a è una sequenza e k un numero naturale oun’espressione che valutata fornisce un numero naturale, l’espressione

a[k]

identifica il k-esimo elemento della sequenza a; similmente, nelle stesseipotesi, l’espressione

a[h ∶ k]fornisce una copia della sequenza a, composta dagli elementi dalla posi-zione h alla posizione k − 1.


2.7. ELABORAZIONE DI SEQUENZE 27

Esempio 19. Nella seguente porzione di codice Python vengono costruitetutte le possibili coppie formate dagli elementi della sequenza a.

# prodotto cartesiano degli elementi di una sequenzaa = [1,2,3,4]for h in a:

for k in a:print([h,k])

2.7 ELABORAZIONE DI SEQUENZE

La forma più elementare di elaborazione consiste nel passare in esame tuttigli elementi della sequenza ed elaborarli sequenzialmente. A questo scopo èpredisposto il controllo della forma riportata nell’algoritmo 7.

Algoritmo 7 - Elaborazione sequenziale di una sequenzaInput: sequenza a1: for x in a do2: elabora elemento x3: end for

Esempio 20. Calcolo della somma degli atomi di una sequenza numerica piatta.

Algoritmo 8 - Somma degli elementi di una sequenza semplice numericaInput: sequenza aOutput: somma degli elementi della sequenza a1: s← 02: for x in a do3: s← s + x4: end for5: return s

Con riferimento all’algoritmo 7, se la sequenza a da elaborare è composta,l’elemento x dell’elaborazione superficiale può essere a sua volta una sequenza.Nel caso in cui sia necessaria una elaborazione in profondità fino ad arriva-re agli atomi componenti, è sufficiente adattare l’algoritmo 7 ricorrendo aiseguenti due operatori:



• operazione di controllo di atomicità:

isatom(x)

il risultato è TRUE se x è un atomo, FALSE altrimenti

• operazione di controllo di lista nulla:

isempty(a)

che è equivalente alla condizione a = [ ] or a = ( ).

Il questo caso l’algoritmo, per gestire in modo generico i livelli di annida-mento della sequenza, assume la forma ricorsiva riportata nell’algoritmo 9.

Algoritmo 9 - elabora(a) : elaborazione in profondità di una sequenzaInput: sequenza a1: for x in a do2: if isatom(x) then3: elabora l’atomo x4: else5: elabora(x)6: end if7: end for

Esempio 21. Calcolo della somma degli atomi di una sequenza numerica com-posta.

Algoritmo 10 - somma(a) : somma elementi di una sequenza compostaInput: sequenza aOutput: somma degli elementi della sequenza composta a1: s← 02: for x in a do3: if isatom(x) then4: s← s + x5: else6: s← s + somma(x)7: end if8: end for9: return s


2.8. ESERCIZI 29

Gli schemi di elaborazione riportati negli algoritmi 7 e algoritmi 9 nonsono adatti nel caso in cui debbano essere elaborati solo alcuni elementi dellasequenza (ad esempio nel caso in cui si debba ricercare se un dato valore èpresente in una sequenza).

2.8 ESERCIZI1. Calcolare le seguenti espressioni:

(a) [1][0](b) 2 ∗ [1][0](c) (2 ∗ [1])[0](d) 1 ∗ [2] + [3](e) (5 ∗ [4])[(3 ∗ [2])[1]](f) ([1] + 2 ∗ [3] + [4] ∗ 5)[6]

2. Sia x un atomo e m,n due numeri naturali. Discutere se le seguentiespressioni sono equivalenti:

(a) (m ∗ n) ∗ [x](b) m ∗ (n ∗ [x])(c) n ∗ (m ∗ [x])(d) m ∗ [n ∗ [x] ]

3. Date le sequenze a = [x], b = [y], scrivere un’espressione che rappresentila sequenza [x,x, . . . , x, y, y, . . . , y] costituita da k atomi x e da k atomiy.

4. Date le sequenze a = [x], b = [y], scrivere un’espressione che rappresentila sequenza [x, y, x, y, . . . , x, y] costituita da k atomi x e da k atomi yalternati.

5. Data la sequenza a = [1,2,3], calcolare le seguenti espressioni:

(a) a + a(b) 2 ∗ a(c) [a] + [a](d) 2 ∗ [a](e) [a + a]



(f) [2 ∗ a]

6. Scrivere delle espressioni che generino le seguenti sequenze:

(a) [1,1,1,1,1,1,1,1,1,1](b) [1,2,3,4,5,6,7,8,9,10](c) [1,2,1,2,1,2,1,2,1,2](d) [1,1,1,1,1,2,2,2,2,2](e) [1,2,3,4,5,1,2,3,4,5]

7. Scrivere delle espressioni che generino le seguenti sequenze di dimensione16:

(a) [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0](b) [0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1](c) [0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1](d) [0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1]

8. Dato il numero naturale n, generare le seguenti sequenze:

(a) [1,2,3, . . . , n](b) [n,n − 1, . . . ,3,2,1](c) [1,1,2,1,2,3,1,2,3,4, . . . ,1,2, . . . , n](d) [1,2,2,3,3,3, . . . , n, n, . . . , n]

9. Data una sequenza di numeri naturali, determinare la sottosequenza deinumeri pari e quella dei numeri dispari. Analogamente per una sequenzacomposta.

10. Data una sequenza determinare la sottosequenza degli elementi di posi-zione pari e quella degli elementi di posizione dispari.

11. Dato il numero naturale n, usando il meccanismo list comprehension,generare le seguenti sequenze:

(a) sequenza dei numeri da 1 a n(b) sequenza dei primi n numeri naturali dispari(c) sequenza dei numeri pari minori o uguali a n(d) sequenza dei divisori di n


2.8. ESERCIZI 31

(e) sequenza dei numeri primi minori o uguali a n(f) sequenza delle coppie di numeri naturali che danno per prodotto n

12. Determinare le eventuali soluzioni intere di un’equazione di secondogrado.

13. Risolvere un’equazione di secondo grado, gestendo anche i casi in cui leradici siano complesse non reali.

14. Determinare la sequenza delle cifre (in base 10) di un dato numeronaturale.

15. Data una sequenza di cifre binarie, determinare il numero corrisponden-te; ad esempio, alla sequenza [1,1,0,1] corrisponde il numero 13.

16. Dato un numero naturale rappresentante una quantità di denaro espressain centesimi di Euro, determinare il più piccolo insieme di monete (da 1,2, 5, 10, 20, 50 centesimi di Euro) equivalente alla data cifra. Esprimereil risultato mediante una sequenza di coppie.

17. Risolvere il problema della torre di Hanoi, determinando la sequenzadelle mosse da eseguire.

18. Il triangolo di Pascal è costituito da numeri naturali disposti in righe;ogni riga è formata da un numero di numeri uguale al numero di rigae, disponendo le righe in modo centrato, ogni numero è la somma deidue numeri adiacenti della riga superiore. A seguire è riportata unaporzione del triangolo.

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

(a) Determinare il k-esimo numero dell’n-esima riga del triangolo diPascal (tale numero viene detto binomiale di n su k).

(b) Determinare l’n-esima riga del triangolo di Pascal.(c) Determinare la sequenza delle prime n righe del triangolo di Pascal

([ [1], [1,1], [1,2,1], . . . ])



19. Determinare le coppie di numeri naturali che danno per prodotto undato numero naturale.

20. Determinare tutte le possibili scomposizioni in addendi non nulli di undato numero naturale (indipendentemente dall’ordine); ad esempio, ilnumero n = 4 può essere scomposto in addendi come segue:

4 = 44 = 1 + 34 = 2 + 24 = 1 + 1 + 24 = 1 + 1 + 1 + 1

e la soluzione può essere espressa mediante la sequenza

[ [4], [1,3], [2,2], [1,1,2], [1,1,1,1] ]

21. Dato un numero naturale < 100, determinare la più piccola sequenzadi monetine centesimi di taglio 1,2,5,10,20,50. Ad esempio, dato ilnumero 96 si deve determinare la sequenza [50,20,20,5,1].

22. Suddividere una sequenza piatta di numeri naturali in due parti: unacontenente i numeri pari e l’altra i numeri dispari.

23. Determinare la media degli elementi presenti in una sequenza piatta,escludendo il valore minimo ed il valore massimo.

24. Eliminare da una sequenza piatta gli elementi duplicati, lasciando unasola occorrenza di ciascun elemento.

25. Determinare i numeri primi presenti in una sequenza piatta di numerinaturali.

26. Determinare il massimo e le sue posizioni, in una sequenza piatta dinumeri.

27. Determinare il numero di atomi presenti in una sequenza composta.

28. Determinare la sequenza degli atomi di una sequenza composta; adesempio, data la sequenza composta [ [1,2],3, [4, [ ], [ [5],6] ] ] si devedeterminare la sequenza semplice [1,2,3,4,5,6].


2.8. ESERCIZI 33

29. Comprimere una sequenza piatta di 0 e 1, comprimendo le sottosequenzedi elementi uguali contigui, ottenendo una sequenza composta, comedescritto dal seguente esempio:

[1,1,1,0,0,1,1,1,1,1,0,0,0,0,0,0,0]→ [[3,1], [2,0], [5,1], [7,0]]

Seguendo lo stesso criterio, decomprimere una sequenza composta riot-tenendo la sequenza piatta corrispondente.


Capitolo 3

Array

Per niente faciliuomini così poco allineatili puoi chiamare ai numeri di ierise nella notte non li avranno cambiati.I. Fossati,dal testo della canzoneLa Musica Che Gira Intorno!

Gli array sono delle particolari sequenze piatte ed omogenee; sono mutabilinei singoli elementi componenti ma hanno una dimensione statica, definita almomento della creazione dell’array; sono caratterizzati dal metodo di accessoad indice nella forma a[i].

Gli array costituiscono una forma di composizione frequentemente utiliz-zata essendo di supporto a molti importanti algoritmi (ricerca, ordinamento,. . . ). Sono predisposti in quasi tutti i linguaggi di programmazione moderni.

35

36 CAPITOLO 3. ARRAY

3.1 GLI ARRAYQualora una sequenza venga elaborata mediante un particolare operatore diaccesso, come descritto nella seguente definizione, viene detta array.

DEFINIZIONE 2. Un array è una sequenza piatta, omogenea, mutabile,di dimensione statica, caratterizzata dall’operatore di selezione ad indice: sea = [a0, . . . , an] è una sequenza di elementi ed e è un’espressione numericanaturale che, valutata, vale il valore naturale i, allora

a[e]

denota l’i-esimo elemento della sequenza a, ossia ai. Per indicare un array ilcui generico elemento è ai si usa spesso la notazione [ai].

L’operatore di accesso mediante indice viene usato anche per modificareun array, secondo la seguente sintassi: se a è un array, e un’espressione che,valutata, vale il numero naturale i ed esp è una generica espressione, con lasintassi

a[e]← esp

si ottiene l’effetto di modificare l’i-esimo elemento dell’array a, assegnandogliil valore ottenuto dalla valutazione dell’espressione esp.

Lo schema generale di elaborazione di un array è descritto dall’algorit-mo 11.

Algoritmo 11 - Elaborazione di un array a di dimensione nInput: array a = [a0, . . . , an]1: for i in range(len(a)) do2: elabora l’elemento ai

3: end for

Nei vari esempi che seguono sono evidenziate le varie caratteristiche degliarray. Gli esempi sono descritti in linguaggio Python.Esempio 22. Gli array sono delle strutture di dimensione statica, cioè unavolta creati non possono subire modifiche alla loro lunghezza. La seguenteporzione di codice illustra alcune tipiche modalità di creazione di un array didimensione 10.

a = [2,4,3,1,7,2,5,4,6,3]b = 10*[0]c = [k for k in range(10)]


3.2. ESERCIZI 37

Esempio 23. Il seguente esempio illustra la tipica forme di elaborazione ciclicadegli elementi di un array, calcolando la somma dei valori dell’array:

a = [2,4,3,1,7,2,5,4]somma = 0for i in range(len(a)):

somma += a[i]# somma = 28

Esempio 24. Gli array sono strutture mutabili e possono essere modificaticambiandone il valore degli elementi componenti mediante un’assegnazione;l’esempio che segue calcola nell’array a i primi 10 numeri della successione diFibonacci.

a = 10*[1]for i in range(2,len(a)):

a[i] = a[i-2]+a[i-1]# a = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

Esempio 25. Il fatto che un array sia una struttura mutabile favorisce spessoun approccio procedurale; quando vengono elaborati mediante una funzione,gli array vengono gestiti come argomenti aventi direzionalità di out ed inout.La seguente funzione modifica l’array a modificando gli elementi negativi alloro valore assoluto.

def assoluto(a):for i in range(len(a)):

if a[i]<0:a[i] = -a[i]

3.2 ESERCIZI1. Valutare le seguenti espressioni coinvolgenti gli array:

(a) [4,5,6,7] [3](b) ([1,2,3] ∗ 2)[1](c) (8 ∗ [1])[2] + 3(d) ((3 + 4) ∗ [1 + 2])[2] + 3

2. Determinare il massimo di un array di numeri.

3. Determinare il massimo e la sua frequenza, in un array di numeri.

4. Determinare, mediante un’unica scansione, i due valori più grandi pre-senti in un array di numeri.



5. Determinare il massimo comune divisore di un array di numeri naturali.

6. Decidere se all’interno di un dato array è presente un dato valore.

7. Determinare la frequenza con la quale compare un dato valore in unarray.

8. Determinare il prodotto degli elementi di un array di numeri.

9. Determinare il risultato dell’operazione and eseguita su tutti gli elementidi un array di valori booleani. Analogamente per l’operatore or.

10. Determinare la media degli elementi di un array di numeri. Si assumal’ipotesi che l’array contenga almeno un elemento.

11. Determinare la media degli elementi di un array numerico, escludendodalla media i valori uguali a zero.

12. Determinare il valore dell’elemento più vicino alla media degli elementidi un array di numeri. Ad esempio, l’elemento più vicino alla media 3.2dell’array [2,7,1,4,2] è 4.

13. Valutare la media k-filtrata, dei valori di un array numerico di dimen-sione n ottenuta facendo la media aritmetica degli n−k elementi dell’ar-ray scartando i k elementi più lontani dalla media aritmetica dell’arrayoriginale.

14. Dato un array numerico a di dimensione n, valutare lo scarto quadraticomedio di a, definito dalla seguente espressione:

¿ÁÁÀ(

n

∑k=1

(ak −m)2) /n

essendo m la media dei valori dell’array.

15. Sia a un array di n di numeri reali positivi e w un array di n numerireali non negativi (detti pesi) tali che ∑n

k=1wk = 1. Calcolare i valori


3.2. ESERCIZI 39

delle seguenti medie pesate:

A(a,w) =n

∑k=1

akwk (media aritmetica)

H(a,w) = 1∑n

k=1wk

ak

(media armonica)

G(a,w) =n

∏k=1

(ak)wk (media geometrica)

Q(a,w) =¿ÁÁÀ

n

∑k=1

akwk (media quadratica)

Dimostrare che valgono le disuguaglianze H ≤ G ≤ A ≤ Q.

16. Un array a contiene i distacchi parziali dei vari concorrenti in una gara,ossia a[i] rappresenta il distacco del concorrente i-esimo dal concorrente(i − 1)-esimo (a[0] = 0 per il primo concorrente). Determinare l’arraycontenente i distacchi complessivi dal primo concorrente.

17. Rovesciare un array in modo che il primo elemento venga scambiato conl’ultimo, il secondo con il penultimo e così via.

18. Ruotare un array [a0, a1, . . . , an] di una posizione a sinistra in modo daottenere la configurazione [a1, . . . , an, a0]. Analogamente per otteneredelle rotazioni a sinistra ed a destra di k posizioni.

19. Determinare l’ampiezza del più piccolo intervallo contenente tutti i nu-meri di un array.

20. Determinare la distanza fra il valore minimo ed il valore massimo deglielementi che compaiono in un array. Stabilire per quale tipologia dielementi dell’array il problema è ben formulato.


Capitolo 4

Matrici

In situazioni più complicate, la tabella po-trebbe essere un array bi-dimensionale, opotrebbe essere un array n-dimensionaleper valori più elevati di n; potrebbe esse-re una struttura ad albero, rappresentanterelazioni gerarchiche o suddivisioni; o po-trebbe essere una complessa struttura conmolti legami con un grande numero di in-terconnessioni come possiamo trovare in uncervello umano.D. Knuth,The Art of Computer Programming

In molte situazioni i dati vengono allocati in strutture bidimensionali aforma di tabella rettangolare composta da righe e colonne. Dal punto divista strutturale si tratta di sequenze composte da array di array della stessalunghezza. La struttura bidimensionale dei dati delle matrici si riscontra inmoltissime applicazioni pratiche ed in moltissimi giochi.

41

42 CAPITOLO 4. MATRICI

4.1 LE MATRICI

Le matrici sono delle particolari forme di array, come descritto dalla definizioneche segue.

DEFINIZIONE 3. Una matrice (bidimensionale) è un array composto daarray della stessa lunghezza.

Da questa definizione discende che una matrice è descrivibile mediante unatabella bidimensionale strutturata in righe e colonne.

Esempio 26. L’array

[ [2,3,7,1], [5,8,4,2], [3,0,2,5] ]

costituisce una matrice bidimensionale. Una tale matrice viene usualmentedescritta in forma tabellare come segue:

2 3 7 15 8 4 23 0 2 5

In linguaggio Python questa matrice può essere creata con la seguente asse-gnazione:

a = [[2,3,7,1],[5,8,4,2],[3,0,2,5]]

Spesso una matrice viene creata inizialmente secondo un ben specifico sche-ma; ad esempio: elementi tutti uguali, elementi disposti secondo uno speci-fico pattern di riempimento. In queste situazioni risulta comodo creare edinizializzare la matrice mediante il meccanismo list comprehension.

Esempio 27. Le seguenti porzioni di codice illustrano la creazione di alcunematrici mediante il meccanismo list comprehension.

# matrice zero 3 x 5 (composta da tutti 0)a = [5*[0] for i in range(3)]

# matrice unitaria 5 x 5 (1 sulla diagonale principale)b = [[1 if i==j else 0 for i in range(5)] for j in range(5)]


4.2. ELABORAZIONE DI MATRICI 43

Se a denota una matrice bidimensionale, coerentemente con la notazioneusata per l’operatore di selezione ad indice, con la notazione

a[i]

si denota l’array costituito dall’i-esima riga della matrice a, mentre con

a[i][j]

si denota il j-esimo elemento dell’i-esima riga della matrice a. Per semplicitàdi scrittura, l’elemento a[i][j] viene spesso indicato con la notazione aij . Perindicare una matrice il cui generico elemento è aij si usa spesso la notazione[aij].

Con la scritturaa[i][j]← esp

si ottiene l’effetto di assegnare all’elemento a[i][j] il valore ottenuto dallavalutazione dell’espressione esp.

Se a è una matrice, len(a) denota il numero di righe di a e len(a[0])il numero di colonne di a. Per semplicità di scrittura queste due funzionivengono indicate con nr(a) e nc(a).

4.2 ELABORAZIONE DI MATRICILo schema generale di elaborazione di una matrice bidimensionale a di n righeed m colonne è descritto nell’algoritmo 12.

Algoritmo 12 - Elaborazione di una matrice a di dimensioni n ×mInput: matrice a di dimensione n ×m1: for i in range(n) do2: for j in range(m) do3: elabora l’elemento a[i][j]4: end for5: end for

Nel caso in cui gli elementi di una matrice vengano elaborati in sola lettura,senza essere modificati, si può adottare lo schema descritto nell’algoritmo 13.



Algoritmo 13 - Elaborazione di una matrice a di dimensioni n ×mInput: matrice a di dimensione n ×m1: for riga in a do2: for e in riga do3: elabora l’elemento e4: end for5: end for

Accade spesso di elaborare una matrice accedendo a tutti gli elementi senzatener conto della loro strutturazione bidimensionale in righe e colonne. Inqueste situazioni si può elaborare una matrice n × m considerandola comeun array unidimensionale di dimensione nm. Lo schema dell’elaborazione èdescritto nell’algoritmo 14.

Algoritmo 14 - Elaborazione di una matrice a di dimensioni n ×mInput: matrice a di dimensione n ×m1: for k in range(n ∗m) do2: elabora l’elemento a[k/m][k%m]3: end for

4.3 OPERAZIONI SULLE MATRICIConsideriamo ora delle operazioni fra matrici numeriche, operazioni che sipresentano in moltissime applicazioni e per questo frequentemente eseguitesugli elaboratori.

DEFINIZIONE 4. Siano a = [aij], b = [bij] due matrici numeriche n ×m.Si definisce come somma a + b fra le due matrici a e b la matrice c = [cij] didimensioni n ×m il cui generico elemento cij è definito da

cij = aij + bij

L’operazione di somma fra matrici richiede che le due matrici abbiano le stessedimensioni. Quando due matrici soddisfano a questo vincolo sulle dimensionisi dice che le due matrici sono somma-compatibili.

Adattando a questa definizione lo schema generale dell’algoritmo 12, ilcalcolo della somma fra due matrici numeriche può essere descritto mediantel’algoritmo 15.


4.3. OPERAZIONI SULLE MATRICI 45

Algoritmo 15 - Somma fra matriciInput: matrici a e b di dimensione n ×mOutput: matrice c = a + b1: for i in range(n) do2: for j in range(m) do3: cij ← aij + bij

4: end for5: end for6: return c = [cij]

L’operazione di moltiplicazione fra matrici si basa sulla seguente

DEFINIZIONE 5. Sia a = [aij] una matrice numerica n ×m e b = [bij] unamatrice numerica m× p. Si definisce come prodotto a∗ b fra le due matrici ae b la matrice c = [cij] di dimensioni n×p il cui generico elemento cij è definitoda

cij =m−1∑k=0

aik bkj

L’operazione di prodotto richiede che il numero di colonne della prima ma-trice sia uguale al numero di righe della seconda. Due matrici che soddisfinoa questo vincolo sulle dimensioni vengono dette prodotto-compatibili. Spessol’operazione di moltiplicazione fra due matrici a e b viene indicata sempli-cemente giustapponendo le due matrici, con la notazione ab. Il calcolo delprodotto fra due matrici numeriche, basato direttamente sulla definizione datasopra, è descritto dall’algoritmo 16.

Esempio 28. Applicando l’algoritmo 16 si ricava il seguente prodotto:

203

421

12

30

21

35

827

1263

1045

22618

∗ =



Algoritmo 16 - Prodotto fra matriciInput: matrici a di dimensione n ×m e b di dimensione m × pOutput: matrice c = a ∗ b (di dimensione n × p)1: for i in range(n) do2: for j in range(m) do3: cij ← 04: for k in range(m) do5: cij ← cij + aik bkj

6: end for7: end for8: end for9: return c = [cij]

4.4 SOLUZIONE DI UN SISTEMA LINEARESia A una matrice quadrata di dimensioni n×n e b un vettore n-dimensionale.A seguire è riportato l’algoritmo per la soluzione di un sistema lineare Ax = bmediante ilmetodo di riduzione di Gauss con pivoting parziale. Il procedimen-to si basa sulla trasformazione del sistema Ax = b in un sistema equivalente(avente la stessa soluzione) riducendo la matrice A ad una matrice aventetutti 0 nel triangolo inferiore sinistro. La seconda fase del procedimento con-siste nel calcolo a ritroso delle incognite: xn−1 → xn−2 → ⋅ ⋅ ⋅ → x1 → x0. Ilprocedimento è descritto nell’algoritmo 17 e raffinato nell’algoritmo 18.

Algoritmo 17 - Soluzione del sistema lineare Ax = bInput: matrice A di dimensioni n × n, vettore b di dimensione nOutput: vettore x = [xi] (di dimensione n) delle incognite1: # riduzione a 0 degli elementi del triangolo inferiore sinistro2: for j in range(n) do3: ricerca della riga p del pivot4: scambio delle righe j ↔ p5: riduzione a 0 degli elementi della j-esima colonna6: end for7: # soluzione del sistema con valutazione a ritroso delle incognite xi

8: for i in reversed(range(n)) do9: calcola xi a partire dalla conoscenza di xi+1, . . . , xn−1

10: end for11: return vettore x = [xi]


4.4. SOLUZIONE DI UN SISTEMA LINEARE 47

Algoritmo 18 - Soluzione del sistema lineare Ax = bInput: matrice A = [aij] di dimensione n × n, vettore b di dimensione nOutput: vettore x = [xi] (di dimensione n) delle incognite1: # riduzione a 0 degli elementi del triangolo inferiore sinistro2: for j in range(n) do3: # ricerca della riga p del pivot4: p← j5: for k in range(j + 1, n) do6: if ∣akj ∣ > ∣apj ∣ then7: p← k8: end if9: end for

10: # scambio delle righe j ↔ p11: if j ≠ p then12: for k in range(n) do13: scambia ajk ↔ apk

14: end for15: scambia bj ↔ bp

16: end if17: # riduzione a 0 degli elementi della j-esima colonna18: for i in range(j + 1, n) do19: f ← aij/ajj

20: for k in range(n) do21: aik ← aik − ajk ∗ f22: end for23: bi ← bi − bj ∗ f24: end for25: end for26: # soluzione del sistema con valutazione a ritroso delle incognite27: for i in reversed(range(n)) do28: s← 029: for k in range(i + 1, n) do30: s← s + aik ∗ xk

31: end for32: xi ← (bi − s)/aii

33: end for34: return vettore x = [xi]



4.5 ESERCIZI1. Descrivere graficamente la rappresentazione in memoria della matrice

riportata nell’esempio 26.

2. Valutare le seguenti espressioni coinvolgenti le matrici:

(a) [ [3,4,5], [6,7] ] [2] [1](b) (5 ∗ (4 ∗ [1,2,3]))[2]

3. Dire qual è l’effetto della seguente porzione di algoritmo agente su unamatrice quadrata a di dimensione n:

1: for i in range(n) do2: for j in range(n) do3: aij ← aji

4: end for5: end for

Analogamente, spiegare l’effetto sostituendo l’istruzione aij ← aji conl’istruzione di scambio aij ↔ aji.

4. Costruire delle matrici rettangolari secondo i seguenti schemi:

0 0 0 0 0 0 0 1 0 1 0 10 1 1 1 1 0 1 0 1 0 1 00 1 1 1 1 0 0 1 0 1 0 10 1 1 1 1 0 1 0 1 0 1 00 0 0 0 0 0 0 1 0 1 0 1

5. Costruire una matrice quadrata di ordine n con gli n2 numeri naturali1,2,3, . . . , n2, secondo gli schemi sotto riportati:

1 2 6 7 15 21 22 23 24 253 5 8 14 16 20 7 8 9 104 9 13 17 22 19 6 1 2 1110 12 18 21 23 18 5 4 3 1211 19 20 24 25 17 16 15 14 13


4.5. ESERCIZI 49

6. Costruire delle matrici di numeri secondo i seguenti formati, riferiti amatrici di dimensioni m = 5, n = 6:

11 12 13 14 15 16 1 2 3 4 5 621 22 23 24 25 26 7 8 9 10 11 1231 32 33 34 35 36 13 14 15 16 17 1841 42 43 44 45 46 19 20 21 22 23 2451 52 53 54 55 56 25 26 27 28 29 30

7. Costruire una matrice di numeri come illustrato dallo schema che segue,riferito ad una matrice di dimensioni m = 5, n = 14:

0 1 2 3 4 5 6 7 8 9 0 1 2 31 2 3 4 5 6 7 8 9 0 1 2 3 42 3 4 5 6 7 8 9 0 1 2 3 4 53 4 5 6 7 8 9 0 1 2 3 4 5 64 5 6 7 8 9 0 1 2 3 4 5 6 7

8. Costruire una matrice quadrata ad anelli concentrici, mettendo 1 sull’a-nello esterno, 2 nel secondo anello e così via.

9. Costruire una matrice 5 × 10 con numeri casuali secondo le regole delleestrazioni del lotto.

10. Costruire una matrice quadrata con i valori 0 e 1, mettendo il valore 1(e 0 altrove) secondo i seguenti schemi:

(a) sulla diagonale principale(b) sulla diagonale secondaria(c) su entrambe le diagonali(d) sui bordi della matrice(e) sul triangolo superiore destro(f) sul triangolo superiore sinistro(g) sul triangolo inferiore destro(h) sul triangolo inferiore sinistro(i) sulle righe di indice pari(j) sulle colonne di indice pari



11. Costruire una matrice quadrata n × n che costituisca la tabella di addi-zione modulo n.

12. Costruire una matrice quadrata n × n con i numeri naturali costituentila tavola pitagorica della moltiplicazione.

13. Costruire una matrice quadrata di ordine n dispari con i numeri coni numeri naturali 1,2, ..., n2 posizionando il numero 1 al centro e poiproseguendo a spirale in senso antiorario.

14. Data una matrice numerica di dimensioni 24 × 365 contenente le tem-perature di ogni ora dei giorni di un dato anno, determinare il giornodell’anno avente la temperatura media più bassa; determinare il giornoavente la massima escursione termica.

15. Determinare l’indice di riga di una matrice numerica per il quale lasomma degli elementi è massima.

16. Determinare in una matrice bidimensionale binaria il rettangolo di mag-gior superficie composto da tutti 1.

17. Determinare il valore minimo ed il valore massimo fra quelli presenti inuna matrice numerica.

18. Determinare il minimo ed il massimo e la loro frequenza, in una matricenumerica.

19. Decidere se all’interno di una matrice è presente un dato elemento.

20. Ricercare se e dove è presente un dato valore in una matrice.

21. Determinare quante volte un dato elemento è presente all’interno di unamatrice.

22. Decidere se una matrice è composta da elementi tutti uguali.

23. Contare il numero di elementi distinti presenti in una matrice.

24. Decidere se in una data matrice esistono due righe uguali.

25. Determinare il prodotto degli elementi di una matrice di numeri. Ot-timizzare il procedimento, terminando il calcolo quando si incontra unelemento di valore zero.


4.5. ESERCIZI 51

26. Contare il numero di numeri primi presenti in una matrice di numerinaturali.

27. Determinare l’elemento che compare con maggiore frequenza in unamatrice.

28. Determinare la frequenza dell’elemento che compare con maggiore fre-quenza in una matrice.

29. Una matrice rettangolare contiene numeri naturali distinti estratti daun’urna; il valore 0 rappresenta la non presenza di un valore non estratto.Decidere se due dati numeri formano un ambo, ossia se sono entrambipresenti in una stessa riga della matrice.

30. Ricercare se in una matrice di caratteri è presente (orizzontalmente overticalmente) una data parola.

31. Decidere se una data matrice quadrata costituisce un quadrato magico.

32. Costruire una matrice quadrata di numeri naturali con i numeri 1,2, ..., n2

in modo da formare un quadrato magico.

33. Decidere se una data matrice numerica 9×9 è corretta in base alle regoledel gioco del sudoku.

34. Realizzare un risolutore del gioco del sudoku.

35. Ruotare una matrice quadrata di 90o a destra rispetto al suo centro.

36. Data una matrice di caratteri composta dai soli caratteri ’ ’ (spazio) e’*’ (muro), decidere se esiste un percorso che attraversa la matrice dauna casella del bordo ad un’altra casella del bordo (eventualmente anchesullo stesso lato).

37. Data una matrice di caratteri ’ ’ (spazio)’ e ’*’, determinare il numerodi isole presenti, interpretando il carattere ’*’ come terra ed il carattere’ ’ come acqua.

38. In una matrice a un elemento aij dicesi punto di sella se esso è maggioredi tutti gli elementi dell’i-esima riga e minore di tutti gli elementi dellaj-esima colonna, oppure, simmetricamente, minore di tutti gli elementidell’i-esima riga e maggiore di tutti gli elementi della j-esima colonna.Determinare i punti di sella di una matrice numerica.



39. In un’aula rettangolare si devono predisporre in file allineate delle posta-zioni per svolgere un esame. Per evitare possibili copiature vengono pre-disposte 4 prove distinte, individuate mediante i numeri 1,2,3,4. Perrappresentare la disposizione dell’aula ed il numero della prova corri-spondente a ciascuna postazione viene utilizzata una matrice. Riempireuna matrice rettangolare con i numeri 1,2,3,4 in modo che caselle conti-gue non contengano valori uguali; preferibilmente fare in modo tale che,se due elementi sono uguali, le due corrispondenti caselle abbiano unadistanza, secondo la metrica Manhattan, la maggiore possibile.

40. Data una matrice 3×N contenenti le dimensioni (larghezza,altezza, pro-fondità di N scatole a forma di parallelepipedo, determinare le dimensio-ni della più piccola scatola in grado di contenerle tutte (una alla volta),mantenendo fra loro parallele le facce della scatola esterna e della scatolainterna.

41. Realizzare le seguenti operazioni matematiche sulle matrici: addizio-ne, moltiplicazione, opposta, inversa, trasposta, determinante, discuten-do nei vari casi quali devono essere le dimensioni delle matrici affinchél’operazione sia possibile.

42. Risolvere con il metodo di Cramer un sistema lineare della forma Ax = b,essendo A la matrice quadrata dei coefficienti e b il vettore dei termininoti. Comparare i tempi di esecuzione dell’algoritmo di Cramer conquelli dell’algoritmo di riduzione di Gauss.


Capitolo 5

Fliste

Prima di considerare due programmi realiin Lisp, vorrei far notare che in Lisp nonsi chiamano programmi ma espressioni. Enon le si esegue, le si valuta. Il risultatodella valutazione è semplicemente un valo-re; non vi sono effetti collaterali. Lo statodell’universo rimane invariato.G Chaitin, Alla ricerca di Omega

Le fliste sono delle particolari liste caratterizzate da specifici operatori diaccesso agli elementi; la modalità di elaborazione delle fliste è quella tipica delparadigma funzionale, la cui carta di identità è riportata nella citazione sopra.

Le fliste costituiscono una importante struttura dati, così potente e duttileche si presta a supplire a tutte le altre strutture organizzative. Ne è confermail fatto che alcuni linguaggi di programmazione (Lisp, Prolog, Logo, Askelled altri), pur con sintassi ed impostazioni diverse, hanno le fliste come unicastruttura dati disponibile.

53

54 CAPITOLO 5. FLISTE

5.1 FLISTEDal punto di vista strutturale le fliste sono delle liste caratterizzate da specificioperatori per la creazione, per l’accesso agli elementi e per la loro elaborazione.Questi operatori sono definiti secondo l’impostazione del paradigma funziona-le: il risultato di un’operazione è sempre un atomo o una flista; inoltre lefliste sono gestite come oggetti immutabili in quanto non esistono operatoriper modificare una flista.

DEFINIZIONE 6. Una flista1 è una lista sulla quale sono ammessi solopochi e specifici operatori descritti nell’elenco che segue, dove con x si denotaun atomo e con a e b generiche fliste:

• empty() : costruttore di una flista vuota:

empty()→ [ ]

• cons(x, a) : costruttore di una flista avente x come primo elemento egli elementi della flista a a seguire:

cons(x, [a0, a1, . . . , an])→ [x, a0, a1, . . . , an]

• first(a) : operatore il cui risultato è costituito dal primo elementodella flista:

first([a0, a1, . . . , an]) = a0

Se a = [ ] o a = Null, allora first(a) = Null.

• rest(a) : operatore il cui risultato è costituito dalla flista ottenutaescludendo il primo elemento:

rest([a0, a1, . . . , an]) = [a1, . . . , an]

Anche in questo caso, se a = [ ] o a = Null, allora rest(a) = Null.

• isempty(a) : predicato che ritorna True se a è la flista vuota [ ], Falsealtrimenti.

• isatom(a) : predicato che ritorna True se a è un atomo, False altrimen-ti.

1Il termine flista deriva da functional list.


5.1. FLISTE 55

L’insieme di operatori elencato precedentemente costituisce un insiemecompleto di operazioni per elaborare le fliste. Il ricorso al valore nullo Null co-me risultato delle operazioni inconsistenti, fornisce robustezza a questo insiemedi operazioni.

Indicando con a una generica flista, le tre operazioni cons, first e restsono fra loro legate dalla proprietà invariante

cons(first(a), rest(a)) = a

Il meccanismo fondamentale per generare una flista a partire dalla fli-sta vuota consiste nella composizione dell’operatore cons secondo il seguenteschema:

cons(a0, cons(a1, cons(a2, . . . , cons(an, empty()))))

Per semplicità di scrittura, tale flista viene scritta nella forma [a0, a1, . . . , an].L’operatore cons permette di realizzare l’operazione env di imbustamento(envelope) che converte un elemento e in una flista costituita dall’elementoe:

env ∶ e→ [e]

può essere realizzato mediante l’operatore cons, come segue:

cons(e, empty())→ [e]

Gli operatori first e rest costituiscono un meccanismo alternativo peraccedere agli elementi di una flista, consentendone l’elaborazione.Esempio 29. Gli esempi che seguono illustrano le operazioni sopra descritte.Si noti l’uso delle parentesi per forzare l’associatività a destra.

cons(8, [ ])→ [8]

cons(1, cons(2, cons(3, [ ])))→ [1,2,3]

cons(3, [7,2,5,4])→ [3,7,2,5,4]

first([0,1,2,3,4])→ 0

rest([0,1,2,3,4])→ [1,2,3,4]

rest(rest(([0,1,2,3,4]))→ [2,3,4]

first(rest([0,1,2,3,4]))→ 1

isatom([])→ False



isatom([3,4])→ False

isatom(7)→ True

Gli elementi componenti le fliste possono essere, a loro volta, delle fliste,costituendo così delle fliste composte; data questa struttura ricorsiva, le flistevengono generalmente elaborate mediante degli algoritmi ricorsivi. Il predi-cato isatom costituisce l’operatore per gestire la struttura composta di unaflista, ai vari livelli di annidamento, in modo ricorsivo; il predicato isemptycostituisce il test per chiudere la ricorsione.

5.2 ELABORAZIONE DI FLISTE

L’elaborazione di una flista si basa principalmente sull’uso degli operatori firste rest che consentono di accedere agli elementi. Le fliste possono essere elabo-rate con due meccanismi formalmente diversi ma computazionalmente equiva-lenti. Una prima modalità consiste nell’elaborazione degli elementi della flistain modalità iterativa, mediante un ciclo, come descritto nell’algoritmo 19.

Algoritmo 19 - Elaborazione di una flista a in modalità iterativaInput: flista a1: b← a2: while ¬isempty(b) do3: elabora l’elemento first(b)4: b← rest(b)5: end while

Una modalità di elaborazione alternativa, e più coerente con l’imposta-zione funzionale, è descritta nell’algoritmo 20. Tale algoritmo si fonda sulladefinizione ricorsiva di flista.

Algoritmo 20 - Elaborazione di una flista a in modalità ricorsivaInput: flista a1: if ¬isempty(a) then2: elabora l’elemento first(a)3: elabora la flista rest(a)4: end if


5.2. ELABORAZIONE DI FLISTE 57

Esempio 30. Applichiamo gli algoritmi 19 e 20 alla determinazione del k-esimoelemento di una flista a. Nella modalità iterativa e ricorsiva i due algoritmisi scrivono come descritto negli algoritmi 21 e 22. Come si può dedurre dalconfronto dei due algoritmi, la versione ricorsiva risulta più concisa e leggibiledella corrispondente versione iterativa.

Algoritmo 21 - item(a, k) : k-esimo elemento della flista a (ver. iterativa)Input: lista a, numero naturale kOutput: k-esimo elemento della flista a1: t← a2: i← 03: while i < k do4: t← rest(t)5: i + +6: end while7: return first(t)

Algoritmo 22 - item(a, k) : k-esimo elemento della flista a (ver. ricorsiva)Input: flista a, numero naturale kOutput: k-esimo elemento della flista a1: if k = 0 then2: return first(a)3: else4: return item(rest(a), k − 1)5: end if

Osservazione. L’operatore item, per questione di efficienza, viene solita-mente prediposto come operatore elementare e viene realizzato direttamentesulla struttura dati fisica che implementa la flista. Il ricorso all’operatoreitem, al di là di ogni considerazione di efficienza computazionale, risulta co-munque sconsigliato all’interno di un contesto di programmazione funzionale,la quale si basa sull’elaborazione di una flista secondo lo schema descritto nel-l’algoritmo 22. Talvolta, per enfatizzare l’approccio funzionale, il controllocondizionale if-then-else viene sostituito dall’operatore condizionale ternarioif, espresso nella notazione funzionale if(condizione, expTrue, expFalse); perconvergere verso la ricorsione è necessario che l’operatore if venga valutato inmodo cortocircuitato.



5.3 ALGORITMI SULLE FLISTE SEMPLICIA seguire sono riportati degli algoritmi elementari per l’elaborazione dellefliste, adottando l’impostazione ricorsiva.Esempio 31. Lunghezza di una flista semplice:

Algoritmo 23 - length(a) : lunghezza della flista aInput: flista a = [a0, . . . , an]Output: n1: if isempty(a) then2: return 03: else4: return 1 + length(rest(a))5: end if

Esempio 32. Somma degli elementi di una flista semplice di numeri:

Algoritmo 24 - somma(a) : somma degli elementi della flista aInput: flista a = [a0, . . . , an] di numeriOutput: a1 + ⋅ ⋅ ⋅ + an

1: if isempty(a) then2: return 03: else4: return first(a) + somma(rest(a))5: end if

Esempio 33. Concatenazione di due fliste:

Algoritmo 25 - conc(a, b) : concatenazione delle due fliste a e bInput: fliste a e bOutput: concatenazione fra a e b1: if isempty(a) then2: return b3: else4: return cons(first(a), conc(rest(a), b))5: end if


5.3. ALGORITMI SULLE FLISTE SEMPLICI 59

Esempio 34. Massimo elemento in una flista semplice:

Algoritmo 26 - massimo(a) : massimo della flista semplice aInput: flista semplice aOutput: massimo della flista semplice a1: if isempty(a) then2: return Null3: else if length(a) = 1 then4: return first(a)5: else6: return max(first(a),massimo(rest(a)))7: end if

Esempio 35. Flista costituita dai primi n numeri naturali:

Algoritmo 27 - numeri(n) : flista [1,2, . . . , n]Input: numero naturale nOutput: flista [1,2, . . . , n]1: if n = 0 then2: return empty()3: else4: return conc(numeri(n − 1), env(n))5: end if

Esempio 36. Rovescio di una flista:

Algoritmo 28 - rev(a) : rovescio della flista aInput: flista a = [a0, . . . , an]Output: flista [an, . . . , a0]1: if isempty(a) then2: return empty()3: else4: return conc(rev(rest(a)), env(first(a)))5: end if



Esempio 37. Ricerca di un elemento in una flista semplice:

Algoritmo 29 - ricerca(a, x) : ricerca se nella flista a è presente xInput: flista a = [a0, . . . , an], elemento xOutput: True se e solo se x è presente nella flista a1: if isempty(a) then2: return False3: else if first(a) = x then4: return True5: else6: return ricerca(rest(a), x)7: end if

Esempio 38. Fusione di due fliste ordinate:

Algoritmo 30 - fusione(a, b) : fusione di due fliste ordinate a e bInput: fliste a e b ordinate (crescentemente)Output: flista ottenuta dalla fusione di a e b1: if isempty(a) then2: return b3: else if isempty(b) then4: return a5: else if first(a) < first(b) then6: return conc(env(first(a)), fusione(rest(a), b))7: else8: return conc(env(first(b)), fusione(a, rest(b)))9: end if

5.4 ALGORITMI SULLE FLISTE COMPOSTE

Gli algoritmi per l’elaborazione di fliste composte risultano talvolta di nonfacile scrittura in quanto si devono gestire parecchi casi. Qualora la strutturaorganizzativa della flista risulti ininfluente per l’algoritmo, risulta più facileconvertire dapprima la flista composta in una flista piatta e successivamen-te applicare l’algoritmo su quest’ultima. Queste situazioni si verificano adesempio nei seguenti casi:

• ricerca di un elemento nella lista


5.5. ARRAY E FLISTE 61

• elaborazione (conteggio, somma, . . . ) di tutti gli elementi

L’algoritmo di appiattimento è presentato nell’esempio che segue.Esempio 39. Una utile operazione, detta flat, su una flista composta consistenel determinare la flista semplice formata dagli atomi della flista; ad esem-pio la flista [ [1, [2] ],3, [ [ [4],5] ], [ [ [6] ],7], [8] ], appiattita, produce la flista[1,2,3,4,5,6,7,8]. Questa operazione è descritta nell’algoritmo 31.

Algoritmo 31 - flat(a) : flista degli atomi della flista aInput: flista aOutput: flista degli atomi di a1: if isempty(a) then2: return empty()3: else if isatom(first(a)) then4: return cons(first(a), f lat(rest(a)))5: else6: return conc(flat(first(a)), f lat(rest(a)))7: end if

5.5 ARRAY E FLISTEArray e fliste sono delle strutture aggregative equivalenti dal punto di vistastrutturale (sono entrambe delle sequenze), ma differenziate dal diverso mec-canismo di accesso e manipolazione degli elementi componenti: gli array ven-gono elaborati modificandone direttamente gli elementi, secondo un’imposta-zione tipicamente procedurale-imperativa; le fliste vengono, invece, elaboratein modalità funzionale (e spesso ricorsiva) mediante delle funzioni che ritorna-no fliste come risultato. Tale differenza fra array e fliste non è solo formale esuperficiale ma induce una profonda differenza sui meccanismi algoritmici perla loro elaborazione.

Benché gli operatori di accesso agli elementi di un array e di una flista sia-no utilizzabili contemporaneamente, si preferisce utilizzarli in modo esclusivo.Il tipico metodo di elaborazione di un array avviene come segue: si definisceinizialmente l’array di una data dimensione; successivamente l’array viene ela-borato mediante l’uso combinato dell’operatore di accesso e dell’operatore diassegnazione. Invece, il tipico metodo di elaborazione di una flista può esseredescritto come segue: a partire dalla flista vuota, mediante l’uso combinatodegli operatori di flista, si ottiene una flista risultato.



5.6 ESERCIZI

1. Valutare le seguenti espressioni:

(a) first([1,2,3])(b) rest([1,2,3])(c) first(rest([1,2,3]))(d) first([0]) == [0](e) cons(first([1]), rest(first([ [1,2,3] ])))(f) first([1 > 2]) < first(rest([3 > 4,5 < 6]))

2. Risolvere la seguente equazione (nell’incognita x):

[len(x)] = x

3. Decidere se una flista è formata da un solo elemento (eventualmentecomposto).

4. Analizzare le operazioni relative alle fliste, discutendo quali sono totalie quali sono parziali, indicando per queste ultime la precondizione chedeve essere verificata affinché l’operazione sia applicabile. Discuterequali strategie si possono adottare per il controllo che l’invocazione ditali operazioni non generi errore.

5. Sia a una generica flista di n elementi. Stabilire per quali valori di n eper quale struttura della flista a risulta valutabile l’espressione

first(rest(first(rest(a))))

Determinarne il valore.

6. Sia a = [a0, a1, . . . , an] una generica flista di n + 1 elementi. Stabilire ilvalore delle seguenti espressioni:

(a) size(rest(a))(b) first(rest(rest(a)))

7. Invertire una flista composta da due soli elementi.

8. Scrivere delle espressioni che forniscano, ciascuna, gli atomi della flista[ [ [1],2],3, [4, [5] ],6] ].


5.6. ESERCIZI 63

9. Data la fista a = [x, y, z], scrivere un’espressione che produca la flista[z, y, x].

10. Data la flista a = [x], scrivere, in funzione di a, un’espressione cherappresenti la flista [ [x], x, [ ] ].

11. Date le due fliste a = [p, q, r] e b = [x, y], scrivere un’espressione coinvol-gente solo a e b che, valutata, costituisca la flista [p, [x], [q, r] ].

12. Inserire in una flista semplice un dato elemento in una data posizione.Ad esempio, inserendo nella flista [5,2,6,1,8] l’elemento 7 alla posizione4 si ottiene la lista [5,2,6,1,4,8].

13. Data una flista a = [a0, . . . , an], determinare la flista ottenuta da a me-diante una rotazione a destra di una posizione in modo ciclico, ottenendola flista a′ = [an, a0, . . . , an−1].

14. Data una flista a = [a0, . . . , an], determinare la flista ottenuta da amediante una rotazione a sinistra di una posizione in modo ciclico,ottenendo la flista a′ = [a2, . . . , an, a0].

15. Decidere se una flista semplice è composta da elementi tutti uguali.

16. Decidere se due fliste semplici sono uguali (basandosi sull’operatore diuguaglianza fra atomi). Le due fliste devono avere la stessa lunghezzaed avere gli elementi uguali nelle stesse posizioni.

17. Decidere se una flista semplice è ordinata.

18. Eliminare i valori ripetuti in una flista semplice, mantenendo la pri-ma occorrenza degli elementi che sono presenti più di una volta; adesempio, data la flista [4,1,3,4,1,1,2,3,7, ,3], si deve ottenere la flista[4,1,3,2,7].

19. Eliminare i valori ripetuti in una flista semplice ordinata; ad esempio,data la flista [3,4,4,4,6,8,9,9], si deve ottenere la flista [3,4,6,8,9].

20. Determinare la flista degli elementi di una flista semplice a maggiori diun dato elemento x.

21. Data una flista semplice di numeri naturali, determinare la sottolista deinumeri pari.

22. Data una flista semplice, determinare la sottolista degli elementi diposizione pari.



23. Date due fliste semplici, determinare la flista degli elementi comuni delledue fliste.

24. Una fista semplice di numeri naturali contiene le cifre che rappresentanoun numero in notazione decimale. Determinare il numero corrisponden-te. Ad esempio alla flista [3,7,4] corrisponde il numero 374.

25. Una flista semplice di numeri naturali contiene le cifre che rappresentanoun numero in notazione decimale. Determinare la flista corrispondenteal successivo. Ad esempio, data la lista [3,5,9] si dovrà determinare laflista [3,6,0].

26. Determinare la distanza fra due n-fliste a = [a0, ...., an] e b = [b0, ..., bn]di numeri, sommando le distanze delle coppie di elementi corrispondenti:

dist(a, b) = Σ∣ai − bi]

27. Comprimere e decomprimere una lista, secondo i seguenti schemi ditrasformazione di evidente interpretazione.

(a) [a, b, b, c, d, d, d, d]↔ [ [a,1], [b,2], [c,1], [d,4] ](b) [a, b, b, c, d, d, d, d]↔ [a,1, b,2, c,1, d,4](c) [a, b, b, c, d, d, d, d]↔ [a, [b,2], c, [d,4] ]

28. Comprimere e decomprimere una flista semplice numerica, secondo loschema di trasformazione descritto nel seguente esempio:

[2,3,4,5,7,9,10]↔ [ [2,5],7, [9,10] ]

29. Una flista è formata dalle coppie di elementi che sono in una relazione diequivalenza. Determinare le fliste formate dalle fliste di elementi dellapartizione indotta dalla relazione di equivalenza.

30. Decidere se una flista è semplice.

31. Determinare la somma degli elementi di una flista semplice numerica.Analogamente per una flista composta.

32. Determinare il numero di atomi di una flista composta; ad esempio, ilnumero di atomi della flista [1, [2,3],4, [5] ] è 5.

33. Decidere se due fliste semplici sono uguali. Analogamente per due flistecomposte.


5.6. ESERCIZI 65

34. Decidere se in una flista semplice è presente un dato elemento. Analo-gamente per una flista composta.

35. Determinare il rovescio di una flista composta; ad esempio, il rovesciodella flista [1, [2,3],4, [5] ] è la flista [ [5],4, [2,3],1].

36. Determinare il livello (di annidamento) di una flista composta (ossial’altezza dell’albero che la rappresenta); ad esempio: l’atomo 3 ha livello0; la flista semplice [2,4,6] ha livello 1; la flista [1,3, [4] ] ha livello 2; laflista [1, [3,2,5], [7, [6,7] ],8] ha livello 3.

37. Decidere se una flista semplice è contenuta all’interno di un’altra flistasemplice. Ad esempio la flista [3,1,4] è contenuta nella flista [3,2,3,1,4]ma non è contenuta nella flista [5,3,2,1,4]. Estendere al caso un cui ledue fliste possano essere composte.

38. Con struttura di una lista si intende la lista ottenuta sostituendo ciascunatomo con un simbolo convenzionale (∗); ad esempio la struttura dellalista [a, [b, c], d, [ [e], f] ] è la lista [∗, [∗,∗],∗, [ [∗],∗] ]. Data una flista,determinarne la struttura. Due liste aventi la stessa struttura sono detteisomorfe; ad esempio sono isomorfe le seguenti due liste: [ [a], b, [ ] ],[ [1],2, [ ] ]. Decidere se due date fliste sono isomorfe.

39. Con scheletro di una lista si intende la lista in cui vengono eliminatitutti gli atomi e vengono mantenute solo le parentesi di annidamento; adesempio lo scheletro della lista [a, [b, c], d, [ [e], f] ] è la lista [ [ ], [ [ ] ] ].Data una flista, determinarne lo scheletro.


Capitolo 6

Complessità Computazionale

Come la teoria della ricorsività, tracciando una li-nea di separazione tra ciò che una macchina puòfare e ciò che non può fare, costituisce un primo li-vello di approssimazione allo studio delle proprietàdel calcolo automatico, così la teoria della comples-sità costituisce un secondo livello di approssima-zione poiché consente di caratterizzare ciò che unamacchina può fare in una determinata quantità ditempo e di memoria.G.Ausiello, Complessità di calcolo delle funzioni

Il tempo di esecuzione di un dato programma dipende da diversi fattori:velocità di elaborazione del calcolatore, quantità dei dati da elaborare, gran-dezza della memoria a disposizione, linguaggio di programmazione utilizzato.La complessità computazionale si pone l’obiettivo di analizzare in generale laqualità degli algoritmi, a prescindere dai fattori tecnici relativi al sistema dielaborazione, che risultano marginali; in particolare lo studio è finalizzato a ri-partire gli algoritmi in algoritmi efficienti ed algoritmi non efficienti. Questaclassificazione degli algoritmi induce un’equivalente ripartizione dei problemi:problemi trattabili, ossia risolvibili in tempi ragionevoli e problemi intrattabili,ossia problemi che, qualsiasi algoritmo si adotti, superano la potenza di cal-colo di qualsiasi calcolatore esistente e futuro. La vaghezza di questa linea diseparazione è solo apparente in quanto esiste, in realtà, un abisso fra le dueclassi.

67

68 CAPITOLO 6. COMPLESSITÀ COMPUTAZIONALE

6.1 LA COMPLESSITÀ COMPUTAZIONALE

I criteri in base ai quali stabilire la qualità di un algoritmo possono basarsisulle caratteristiche intrinseche dell’algoritmo (lunghezza, leggibilità) oppuresulle risorse richieste dall’algoritmo (tempo di CPU impiegato, memoria RAMoccupata).

La complessità computazionale studia gli algoritmi in relazione alla quan-tità di risorse impiegate. Il parametro più caratterizzante e significativo nellavalutazione della complessità di un algoritmo è costituito dal tempo di elabo-razione impiegato per l’esecuzione dell’algoritmo. Il parametro tempo risultaancora poco espressivo in quanto fa riferimento ad una particolare esecuzionedi una istanza del problema su una data macchina. È chiaramente poco signi-ficativa, infatti, una frase del tipo: L’algoritmo di ordinamento A impiega 6.2secondi ad essere eseguito in quanto non è precisato né il numero di elementida ordinare, né la loro disposizione iniziale, né la macchina sulla quale vieneeseguito l’algoritmo. Inoltre, un tale approccio al problema richiederebbesempre delle prove per poter confrontare due algoritmi. Quando il tempo diesecuzione è elevato (un’ora o addirittura un secolo!) tale approccio pragma-tico non è più chiaramente attuabile. Ed è proprio in questi casi estremi cheè utile sapere (senza provare!) la complessità di un algoritmo per stimare iltempo di esecuzione, senza eseguire l’algoritmo. Ad esempio, se si dispone diun algoritmo per il calcolo del determinante di una matrice si vorrebbe sape-re in anticipo quant’è approssimativamente il tempo che sarà necessario pereseguire l’algoritmo.

Dalle osservazioni precedenti si deduce che il problema della valutazionedella complessità degli algoritmi non ammette una soluzione di tipo prag-matico della forma ”prova e vedi” ma deve essere affrontato sulla carta. Ènecessario pertanto astrarre le considerazioni senza fare riferimento ad alcunamacchina particolare. Questo passaggio è facilmente attuabile se si assumel’ipotesi (plausibile) che il tempo di esecuzione di un imprecisato numero k dioperazioni elementari è proporzionale a k e che il numero k sia una funzio-ne f crescente della misura n dei dati da elaborare. Pertanto, tale funzionef(n) può essere assunta come misura del tempo impiegato, per le varie istanzedel problema aventi valori diversi di n. Per quanto riguarda la misura dellacomplessità dell’input su cui deve lavorare l’algoritmo è sufficiente definire unvalore che esprime la dimensione del problema. Per quanto riguarda i valoriparticolari che può assumere un input di data lunghezza, si considerano leseguenti situazioni: caso ottimo, caso medio, caso pessimo.


6.2. OPERAZIONE DOMINANTE 69

6.2 OPERAZIONE DOMINANTELa complessità computazionale di un algoritmo rappresenta una stima deltempo di elaborazione impiegato per l’esecuzione dell’algoritmo; tale stima deltempo viene indirettamente ottenuta contanto il numero di passi elementarisvolti nell’esecuzione dell’algoritmo. Questa valutazione indiretta permettedi svincolare la misura del tempo impiegato senza riferirsi ad una particolaremacchina. Questa trasposizione dalla misura del tempo al conteggio dei passielementari non costituisce comunque un concetto assoluto in quanto dipendeda cosa si intende per passo elementare; ed inoltre dipende anche dal modocon cui si rappresentano i dati sui quali opera l’algoritmo. Il concetto dipasso elementare risulta perfettamente definito qualora si consideri l’esecutorecostituito da una macchina di Turing: in questo caso il passo elementare è rap-presentato da una transizione di stato dell’automa ossia dall’esecuzione di unaquintupla. Poiché gli algoritmi vengono descritti con formalismi diversi dallequintuple di una macchina di Turing, risulta necessario estendere il concettodi passo elementare ad altri formalismi. Con algoritmi ad un più alto livello siincontrano dei passi elementari di diversa natura e computazionalmente nonuniformabili; ci possono essere delle assegnazioni, delle addizioni, delle mol-tiplicazioni, delle valutazioni di condizioni. Per semplificare il calcolo dellacomplessità è stato introdotto il concetto di operazione dominante.

DEFINIZIONE 7. Si chiama operazione dominante o caratteristica diun algoritmo l’operazione che viene eseguita con maggiore frequenza; nel casodi operazioni eseguite con la stessa frequenza si considera quella più onerosain termini di tempo impiegato per la sua esecuzione.

Esempio 40. Nella tabella che segue sono riportati alcuni problemi e la corri-spondente operazione dominante.

Problema Operazione dominantecalcolo del fattoriale moltiplicazione fra due numeriscomposizione di un numero calcolo del resto della divisionericerca in un array confronto fra due elementiordinamento di un array confronto fra due elementimoltiplicazione fra due matrici moltiplicazione fra due numeritorre di Hanoi spostamento di un discocommesso viaggiatore calcolo della lunghezza di un percorso

Tabella 6.1: Problemi e corrispondenti operazioni dominanti.



6.3 DIMENSIONE DI UN PROBLEMAUn problema, o più propriamente una classe di problemi è costituita da mol-te istanze di problemi il cui tempo di risoluzione dipende dalla grandezzadell’input, come precisato nella definizione che segue.DEFINIZIONE 8. La dimensione di un problema è un numero naturaleche esprime un’opportuna (rispetto all’operazione dominante) misura dei datidi input del problema.

Nonostante l’apparente vaghezza del termine opportuna che compare nelladefinizione precedente, la dimensione di un problema è facilmente identifica-bile, come emerge dall’esempio che segue.Esempio 41. La seguente tabella descrive la dimensione di alcuni importantiproblemi.

Problema Dimensione del problemacalcolo del fattoriale numero di cui si calcola il fattorialescomposizione di un numero numero di cifre del numeroricerca in un array numero di elementi dell’arrayordinamento di un array numero di elementi dell’arraymoltiplicazione fra due matrici dimensione delle matricitorre di Hanoi numero di dischi da spostarecommesso viaggiatore numero di città da visitare

Tabella 6.2: Problemi e corrispondenti dimensioni.

6.4 COMPLESSITÀ DI UN ALGORITMOIn funzione dell’operazione dominante e della dimensione di un problema èpossibile definire una misura del tempo impiegato da un algoritmo. Il concettoè precisato dalla seguente definizione.DEFINIZIONE 9. La complessità di un algoritmo è una funzione cheesprime il numero di operazioni dominanti in funzione della dimensione delproblema.Esempio 42. Il problema della moltiplicazione fra due matrici quadrate dilato n ha dimensione n. L’operazione dominante è la moltiplicazione. Iltradizionale algoritmo di moltiplicazione righe-per-colonne ha complessità n3

in quanto richiede l’esecuzione di n moltiplicazioni per il calcolo di ciascunodegli n2 elementi della matrice risultante.


6.5. COMPLESSITÀ DI UN PROBLEMA 71

6.5 COMPLESSITÀ DI UN PROBLEMABasandosi sul concetto di complessità di un algoritmo è possibile stabilire lacomplessità di un problema, come precisato nella seguente definizione.

DEFINIZIONE 10. La complessità di un problema è la complessità delmiglior algoritmo che lo risolve.

Esempio 43. Il problema dell’ordinamento di un array di dimensione n hacomplessità, nel caso medio, pari a n logn, in quanto esistono algoritmi diordinamento che hanno una tale complessità; d’altra parte si può dimostrareche, in generale, non si può ordinare un array con meno di n logn confronti.

6.6 COMPLESSITÀ ASINTOTICALa complessità di un algoritmo e di un problema risulta importante e deci-siva per valori grandi della dimensione del problema. Si danno le seguentidefinizioni.

DEFINIZIONE 11. Date due funzioni f e g, reali a valori reali, si dice chela funzione f è O grande di g, e si scrive f è O(g) oppure f ∈ O(g), se esisteuna costante reale c > 0 ed un numero reale x0 tale che per x ≥ x0 si abbiaf(x) ≤ c g(x).

DEFINIZIONE 12. La complessità asintotica di un algoritmo o di unproblema è la complessità per valori grandi della dimensione del problema;viene denotata con la notazione O (o grande).

Esempio 44. L’affermazione: "Il problema della Torre di Hanoi ha una com-plessità computazionale asintotica pari a O(2n). significa che per spostare ndischi da un piolo ad un altro, per n grande, si esegue un numero di spostamentiproporzionale a 2n.Esempio 45. Il problema della moltiplicazione di due matrici quadrate di ordi-ne n ha una complessità non nota. Il tradizionale algoritmo di moltiplicazionerighe-per-colonne ha una complessità asintotica pari a n3; il migliore algoritmoattualmente conosciuto ha una complessità asintotica pari a n2,78 ma attual-mente non si conosce una limitazione inferiore per la complessità asintoticadegli algoritmi di moltiplicazione di matrici.



Esempio 46. La seguente tabella riporta una lista di problemi e le loro corri-spondenti complessità asintotica nel caso medio.

Problema Complessità asintotica del problemaricerca in un array ordinato O(logn)ricerca in un array non ordinato O(n)ordinamento di un array O(n logn)moltiplicazione fra due matrici non è notacommesso viaggiatore O(n!)

Esempio 47. Analizziamo la complessità del seguente schema di algoritmo,dove n denota la dimensione del problema ed op l’operazione dominante.

1: for i from 1 to n do2: for j from i + 1 to n do3: op4: end for5: end for6: for i from 1 to 2 ∗ n do7: op8: end for

La complessità consiste nel numero di operazioni op che vengono eseguitedall’algoritmo ed è pari a

((n − 1) + (n − 2) +⋯ + 1) + 2n = n(n − 1)/2 + 2n = (n2 + 3n)/2

Di conseguenza la complessità asintotica è pari a

O(n2)

6.7 PROBLEMI INTRATTABILIIl più potente calcolatore che si possa immaginare di costruire non potrà esserepiù grande dell’universo, non potrà essere fatto di componenti di elaborazio-ne più piccoli dei protoni, non potrà trasmettere le informazioni fra le suecomponenti ad una velocità superiore alla velocità della luce. Un semplicecalcolo porta alla conclusione che un tale ipotetico calcolatore non potrebbe


6.7. PROBLEMI INTRATTABILI 73

essere composto da più di 10126 componenti. Anche ammettendo che le in-formazioni di questo calcolatore venissero trasmesse fra le sue componenti aduna velocità uguale a quella della luce, esistono numerosi problemi di grandeinteresse pratico che, anche per moderati valori della dimensione del proble-ma, tengono in scacco questo calcolatore estremo per 20 miliardi di anni, ossiaper un tempo paragonabile a quello dell’universo. Esistono problemi che, purrisolvibili sul piano teorico in quanto si conoscono degli algoritmi risolutivi,non sono effettivamente risolvibili in quanto richiederebbero tempi esageratianche per il più potente calcolatore immaginabile. Questi problemi vengonodetti problemi intrattabili.

L’esistenza di problemi intrattabili può sembrare, a prima vista, un aspettonegativo, un’evidenziazione di un limite della scienza e della tecnica. Sembraparadossale, ma, invece, questi problemi costituiscono l’elemento fondante dialcune tecnologie: l’intrattabilità del problema della fattorizzazione in primidi un numero naturale è alla base di tutti i sistemi basati sulla crittografia;l’esplosione dell’albero delle mosse del gioco degli scacchi comporta l’intratta-bilità del problema di determinare una strategia vincente nella conduzione delgioco in una partita a scacchi a causa dell’intrattabilità del problema di un’ana-lisi esaustiva dell’albero delle mosse e questo, nonostante l’eccezionale velocitàe complessità dei calcolatori attuali, lascia margini di battaglia alla pari al-l’uomo che gioca a scacchi contro il computer, almeno ai grandi maestri degliscacchi; ed anche se un computer batte agevolmente anche un buon scacchista,le mosse brillanti, ingegnose, artistiche rimangono prerogativa dell’uomo.

La linea di demarcazione fra problemi trattabili e problemi intrattabilidipende dalla tipologia della funzione di complessità: i problemi trattabilisono caratterizzati da funzioni di complessità polinomiali, mentre i problemiintrattabili hanno funzioni di complessità di categoria esponenziale. La figu-ra 6.1 dispone in linea di complessità crescenti un insieme di funzioni che siincontrano spesso nell’analisi degli algoritmi.

complessità polinomiali complessità esponenziali

logn√n n n logn n2 n3 n10 2n n! nn

Figura 6.1: Complessità polinomiali ed esponenziali di alcune funzioni che siincontrano frequentemente nell’analisi degli algoritmi.



Nella tabella 6.3 è riportato il tempo in secondi che impiega un calcola-tore che esegue 1 milione di operazioni al secondo a risolvere un problema didimensione n.

f(n) n = 10 n = 20 n = 30 n = 40 50 n = 100log2 n 3.3 µs 4.3 µs 4.9 µs 5.3 µs 5.6 µs 6.6 µs√

n 3.1 µs 4.5 µs 5.5 µs 6.3 µs 7.0 µs 10 µsn 10 µs 20 µs 30 µs 40 µs 50 µs 100 µs

n log2 n 33 µs 86 µs 147 µs 213 µs 282 µs 664 µsn2 100 µs 400 µs 900 µs 1600 µs 2500 µs 10000 µsn3 1 ms 8 ms 27 ms 64 ms 125 ms 1 sec2n 1 ms 1 sec 17 min 12 g 35 a 4 ⋅ 1016 an! 3.6 sec 8 ⋅ 104 a 8 ⋅ 1018 a 3 ⋅ 1034 a 9 ⋅ 1050 a 3 ⋅ 10154 ann 2.8 h 3 ⋅ 1012 a 6 ⋅ 1035 a 4 ⋅ 1050 a 3 ⋅ 1071 a 3 ⋅ 10186 a

Tabella 6.3: Tempi delle funzioni di complessità di alcune funzioni. Le unitàdi misura dei tempi sono: µs = microsecondi, ms = millisecondi, sec = secondi,min = minuti, g = giorni, a = anni.

Nella tabella 6.4 è riportata la dimensione del problema risolvibile in unadata quantità di tempo, sempre nell’ipotesi di disporre di un calcolatore cheesegue 1 milione di operazioni al secondo.

f(n) 1 sec 1 min 1 ora 1 giorno 1 mese 1 anno 1 secolo

log2 n 10400000 10107 10109 101010 101012 101013 101015

√n 1012 4 ⋅ 1015 1019 7 ⋅ 1021 7 ⋅ 1024 1027 1031

n 106 6 ⋅ 107 4 ⋅ 109 9 ⋅ 1010 3 ⋅ 1012 3 ⋅ 1013 3 ⋅ 1015

n log2 n 9 ⋅ 104 106 2 ⋅ 108 4 ⋅ 109 1011 1012 1014

n2 103 8 ⋅ 103 6 ⋅ 104 3 ⋅ 105 2 ⋅ 106 6 ⋅ 106 6 ⋅ 107

n3 100 392 1533 4414 13715 31551 1464522n 20 26 32 36 41 45 51n! 10 11 13 14 15 16 18nn 7 8 9 10 11 12 13

Tabella 6.4: Dimensioni dei problemi risolvibili in una data quantità di tempoin funzione della complessità f(n) dei problemi.


6.8. ESERCIZI 75

Un’analisi, anche superficiale, delle due tabelle 6.3 e 6.4 evidenzia chel’evoluzione tecnologica dei calcolatori non potrà intaccare il carattere di in-trattabilità dei problemi.

Osservazione. Da tutte le precedenti considerazioni risulta coerente de-signare come polinomiali i problemi trattabili e come esponenziali i problemiintrattabili. La macchina di Turing costituisce lo strumento per tracciarela linea di demarcazione fra problemi risolvibili e problemi irrisolvibili. Ladistinzione fra problemi trattabili e problemi intrattabili viene invece stabilitain base alla funzione di complessità del problema. La figura 6.2 descrive laclassificazione dei problemi, evidenziando, all’interno dei problemi risolvibili,i problemi trattabili e quelli intrattabili. Ci sono dei problemi per i quali nonè attualmente noto a quale di queste due categorie appartengono.

'

&

$

%

problemirisolvibili

��

problemitrattabili

��

problemiintrattabili

probleminon risolvibili

Figura 6.2: Problemi non risolvibili, risolvibili, trattabili ed intrattabili.

6.8 ESERCIZI1. Ordinare le seguenti funzioni di complessità:

√n logn10 n! n logn nn 10n 10n logn n10 10100 log2 n

2. Siano A1 ed A2 due algoritmi funzionalmente equivalenti aventi rispetti-vamente complessità c1(n) = n logn e c2 = n

√2. Stabilire quale dei due

algoritmi è preferibile, per n sufficientemente grande.



3. Determinare per quale valore n0 (punto di taglio) della dimensione ndel problema un algoritmo A1 di complessità polinomiale f(n) = n10

risulta preferibile rispetto ad un equivalente algoritmo A2 di complessitàesponenziale g(n) = (1.1)n. Fare delle considerazioni in merito allaconclusione.

4. Descrivere mediante dei diagrammi di Venn le seguenti classi di proble-mi: problemi risolvibili, problemi non risolvibili, problemi polinomiali,problemi esponenziali.

5. Valutare la complessità e la complessità asintotica delle seguenti porzionidi algoritmi, essendo op l’operazione dominante ed n la dimensione delproblema.

1: for i from 1 to n2 do2: for j from 1 to 2n do3: op4: end for5: end for

1: for i from 1 to n do2: for j from i to n do3: op4: end for5: end for

1: k ← n2: while k > 0 do3: for i from 1 to n do4: op5: end for6: k ← k/27: end while


6.8. ESERCIZI 77

1: k ← n2

2: while k > 0 do3: for i from 1 to 2n do4: op5: end for6: k ← k/27: end while

6. Scrivere e valutare la complessità degli algoritmi che risolvono i seguentiproblemi:

(a) calcolo del fattoriale di un numero naturale(b) ricerca di un elemento in un array(c) moltiplicazione fra due matrici(d) problema della torre di Hanoi

7. Si consideri il problema P : Decidere se un array contiene elementi tuttiuguali fra loro. Spiegare perchè il problema P ′: Decidere se un arraycontiene elementi tutti diversi fra loro. è sostanzialmente diverso dalproblema P .

8. Dimostrare che il problema Decidere se due array hanno elementi incomune ha una complessità asintotica nel caso pessimo non superiore aO(n log n).

Nota. Per ciascuno dei seguenti problemi svolgere i seguenti punti: de-scrivere un algoritmo risolutivo; stabilire in cosa consistono i casi otti-mo, medio, pessimo; valutare la complessità e la complessità asintoticadell’algoritmo nel caso pessimo; stabilire la complessità del problema.

9. Determinare quante volte è presente un dato elemento in un array.

10. Determinare quante volte è presente un dato elemento in un array ordi-nato.

11. Determinare il più piccolo numero naturale non appartenente ad un datoarray di numeri naturali.

12. Decidere se un array di numeri interi contiene tutti i valori compresi frail minimo ed il massimo degli elementi contenuti nell’array.



13. Decidere se un dato array di numeri naturali è ordinato crescentementeed è composto da valori contigui; ad esempio l’array di numeri naturalia = [5,6,7,8,9] è ordinato crescentemente ed ha gli elementi contigui,mentre non lo sono gli array b = [5,7,8,6,9], c = [4,6,7,8,9].

14. Decidere se due array (di uguali dimensioni) sono una permutazione unodell’altro, ossia se contengono gli stessi valori, con la stessa frequenza,indipendentemente dalla posizione.

15. Decidere se un array contiene elementi tutti uguali fra loro.

16. Decidere se un dato array è composto da elementi tutti distinti.

17. Determinare il numero di elementi distinti presenti in un array.

18. Determinare la massima distanza fra tutte le possibili coppie di numeridi un array.

19. Determinare la coppia di elementi di un array aventi la massima distanzareciproca.

20. Determinare la distanza della coppia di punti più distanti presenti in unarray di punti.

21. Determinare il valore dell’elemento mediano in un array numerico didimensione dispari. L’elemento mediano è il valore che in un ipoteticoordinamento dell’array verrebbe a trovarsi nella posizione mediana.

22. Decidere se due date stringhe soddisfano alla relazione d’ordine lessi-cografico sulle stringhe, ossia decidere se la prima precede la seconda,secondo l’usuale ordine del vocabolario.


Capitolo 7

Ordinamento

Le tecniche di ordinamento forniscono inol-tre eccellenti illustrazioni delle idee genera-li coinvolte nell’analisi degli algoritmi, cioèle idee utilizzate per determinare le carat-teristiche di efficienza degli algoritmi cosic-chè si possa fare una scelta intelligente frametodi in competizione.D. Knuth,The Art of Computer Programming

Nelle situazioni della vita quotidiana il problema dell’ordinamento si pre-senta molto frequentemente. Ad esempio, un giocatore di carte affronta unproblema di ordinamento quando deve disporre inizialmente le carte che glisono state distribuite, al fine di essere agevolato nelle successive fasi del gioco.

L’ordinamento di elementi (numeri o altre tipologie di dati) costituisce unadelle forme di elaborazione più frequenti: si stima che oltre il 25 per cento deltempo di elaborazione impiegato dai computer sia impegnato per ordinare.

79

80 CAPITOLO 7. ORDINAMENTO

7.1 IL PROBLEMA DELL’ORDINAMENTOIl problema dell’ordinamento può essere formulato come segue:

Dato un insieme di elementi sui quali è definito un criteriod’ordine, disporli in sequenza, uno dopo l’altro, in modo cheogni elemento preceda gli elementi uguali o più grandi.

In modo più formalizzato e più utile per impostare gli algoritmi di or-dinamento, il problema dell’ordinamento, nella sua formulazione generale, siesprime come segue:

Data una sequenza di elementi [a0, a1, . . . , an−1] dove ciascunai è confrontabile con gli altri, determinare una sequenza a′ =[a′0, a′1, . . . , a′n−1] che sia una permutazione della sequenza a eche sia ordinata, ossia a′0 ≤ a′1 ≤ ⋅ ⋅ ⋅ ≤ a′n−1.

Esempio 48. Ordinare la sequenza di numeri

27 32 15 11 54 78 15 23

significa operare una permutazione degli elementi in modo da ottenere lasequenza

11 15 15 23 27 32 54 78

Il problema dell’ordinamento viene risolto adottando due possibili impo-stazioni:

• modalità funzionale: la sequenza da ordinare viene esaminata ma nonviene modificata; viene generata un’altra sequenza che costituisce ilrisultato del processo di ordinamento

• modalità procedurale: la sequenza da ordinare viene modificata (median-te assegnazioni e scambi di elementi) ed alla fine risulta ordinata

Spesso, negli usuali linguaggi di programmazione a paradigma imperativo(C, Python, Java) viene adottata la modalità procedurale.


7.2. ORDINAMENTO DI SEQUENZE 81

7.2 ORDINAMENTO DI SEQUENZESpesso il problema dell’ordinamento viene definito in un contesto imperati-vo in cui la sequenza a è un array modificabile; in questo caso si tratta dideterminare una permutazione p dell’insieme {0,1, . . . , n − 1} in modo che lasequenza [ap(0), ap(1), . . . , ap(n−1)] risulti ordinata. La permutazione p vienecostruita modificando direttamente l’array a; il problema si traduce quindinella seguente formulazione.

Dato un array a = [a0, a1, . . . , an−1], permutarne gli elementiin modo tale che

a0 ≤ a1 ≤ ⋯ ≤ an−1

7.3 FAMIGLIE DI ALGORITMIEsistono moltissimi procedimenti adatti per ordinare una sequenza di elementi;questi procedimenti costituiscono uno dei capitoli più importanti della teoriadell’elaborazione delle informazioni. Questi algoritmi di ordinamento possonoessere classificati in diverse famiglie a seconda dell’idea generale sulla quale sisviluppano. Si possono distinguere le seguenti famiglie:

• ordinamento per scambio: si eseguono confronti fra coppie di elementi;quando si incontrano due elementi fuori ordine, vengono scambiati

• ordinamento per selezione: si individua l’elemento più piccolo; tale ele-mento viene separato dagli altri; si individua poi il minimo della parterimanente e si prosegue con la stessa modalità

• ordinamento per inserzione: si considerano gli elementi uno alla volta;ciascun elemento viene inserito nella posizione appropriata, rispetto aquelli già considerati, con una tecnica simile a come i giocatori di cartele ordinano in mano, raccogliendole una ad una

Nota. Nelle pagine che seguono i vari procedimenti di ordinamento vengo-no descritti mediante un algoritmo generico e vengono poi codificati mediante illinguaggio Python che, per la sua sintassi essenziale, ben si presta a descriveregli algoritmi.



7.4 ORDINAMENTO A BOLLE

La strategia dell’ordinamento a bolle (bubble-sort) si basa sull’idea di far salire,per passi successivi, verso la fine dell’array gli elementi maggiori, attraversodegli scambi fra elementi adiacenti:

Si confrontano i primi due: se sono fuori ordine vengono scam-biati; si ripete il procedimento con il secondo ed il terzo e cosìvia, fino alla fine dell’array. Alla fine del primo ciclo l’ele-mento maggiore è sicuramente posizionato alla fine dell’array.Si inizia allora un altro ciclo per far salire al penultimo po-sto l’elemento immediatamente minore e così via fino ad averordinato tutto l’array.

L’algoritmo che esprime questa strategia può essere descritto come segue:

Algoritmo 32 - Ordinamento a bolle (bubble-sort)Input: array a da ordinareOutput: l’array a è ordinato1: for i in range(len(a)) do2: for j in range(len(a) − i − 1) do3: if aj > aj+1 then4: scambia aj ↔ aj+15: end if6: end for7: end for

La codifica in linguaggio Python si scrive:

# ordinamento dell’array a# mediante l’algoritmo "bubble sort"def bubbleSort(a):

for i in range(len(a)):for j in range(len(a)-i-1):

if a[j] > a[j+1]:# scambio a[j] <-> a[j+1]t = a[j]a[j] = a[j+1]a[j+1] = t


7.4. ORDINAMENTO A BOLLE 83

L’analisi della complessità dell’algoritmo bubble-sort, nella versione pre-cedentemente riportata, risulta molto facile in quanto l’algoritmo esegue unuguale numero di confronti indipententemente dai valori presenti nell’array.In particolare, indicando con n il numero di elementi dell’array, alla primapassata vengono svolti n − 1 confronti, alla seconda n − 2 e così via per lesuccessive passate, fino ad arrivare a svolgere 1 confronto all’ultima passataquando vengono confrontati gli elementi a0 e a1. Vengono complessivamentesvolti

T (n) = (n − 1) + (n − 2) + ⋅ ⋅ ⋅ + 1 = n(n − 1)/2confronti e pertanto la complessità asintotica risulta pari a O(n2).

Le prestazioni dell’algoritmo bubble-sort sono particolarmente scadenti inquanto richiede che vengano fatti molti confronti e scambi affinché un elementoraggiunga la propria destinazione finale.

L’algoritmo bubble-sort esegue, ad ogni ciclo, una passata su tutta la por-zione dell’array non ancora ordinata. Per questo motivo, se in una passatanon avvengono scambi, significa che l’array è ordinato. Un’ulteriore ottimiz-zazione si basa sull’osservazione che ad ogni passata basta spingersi nell’arrayfino alla posizione in cui alla precedente passata era stato eseguito l’ultimoscambio. Come caso estremo, se l’array è inizialmente già ordinato è suffi-ciente un’unica scansione degli elementi per riconoscere che l’array è ordinatoe concludere il processo di ordinamento. Il procedimento basato su questaidea può essere codificato mediante la seguente funzione Python:# ordinamento dell’array a# mediante l’algoritmo "bubble sort" ottimizzatodef bubbleSortOpt(a):

ultimo = len(a)-1 # ultimo elemento non ancora ordinatowhile ultimo > 0:

scambiato = -1 # ultimo elemento scambiatofor i in range(ultimo):

if a[i] > a[i+1]:t = a[i]a[i] = a[i+1]a[i+1] = tscambiato = i

ultimo = scambiato

Questo algoritmo, nonostante l’idea di ottimizzazione che realizza, ha unacomplessità asintotica pari a O(n2). Offre invece buone prestazioni nel casoin cui l’array da ordinare sia quasi ordinato. Nel caso estremo in cui l’arraysia già ordinato (caso ottimo per l’algoritmo bubble-sort) l’algoritmo eseguen − 1 confronti ed ha dunque una complessità asintotica pari a O(n).



7.5 ORDINAMENTO PER SELEZIONEL’ordinamento per selezione (selection-sort) si basa su una strategia naturalee spontanea che le persone applicano per ordinare un insieme di elementi. Lastrategia è descrivibile come segue:

Determina il minimo fra gli elementi dell’array e scambialo conil primo. Determina il minimo fra gli elementi dell’array, esclu-so il primo, e scambialo con il secondo. Determina il minimodell’array, esclusi i primi due, e scambialo con il terzo e cosìvia, fino a quando la porzione di array da ordinare si è ridottaad un unico elemento.


Algoritmo 33 - Ordinamento per selezione (selection-sort)Input: array a da ordinareOutput: l’array a è ordinato1: for i in range(len(a)) do2: determina la posizione p del valore minimo della porzione [a0, . . . , an−1]3: if p ≠ i then4: scambia ap ↔ ai

5: end if6: end for

A seguire è riportata la codifica in linguaggio Python:

# ordinamento dell’array a# mediante l’algoritmo "selection sort"def selectionSort(a):

for i in range(len(a)):# determinazione minimo di a[i..n]m = a[i] # valore minimop = i # posizione del minimofor j in range(i+1,len(a)):

if a[j] < m :m = a[j]p = j

if p != i :# scambio a[p] <-> a[i]a[p] = a[i]a[i] = m


7.6. ORDINAMENTO PER INSERZIONE 85

Le prestazioni dell’algoritmo selection-sort sono indipendenti dai valoridell’array di input e, per questo, i casi ottimo, medio e pessimo coincidono.Dall’analisi dell’algoritmo emerge che vengono svolte n−1 selezioni del minimo;l’i-esima selezione richiede n − i confronti; pertanto il numero complessivo diconfronti è pari a

T (n) =n−1∑i=1

n − i = (n − 1) + (n − 2) +⋯ + 1 = n(n − 1)2

La complessità asintotica di questo algoritmo risulta, in tutte le situazioni,pari a O(n2).

7.6 ORDINAMENTO PER INSERZIONE

L’ordinamento per inserzione (insertion-sort) applica la stessa strategia cheusa un giocatore di carte per raccogliere le carte ad una ad una e disporlein mano in modo ordinato. Il procedimento può essere descritto in mododiscorsivo come segue:

A partire dal secondo elemento fino all’ultimo, inserisci l’ele-mento al posto giusto fra quelli compresi fra il primo e quelloche si sta inserendo, spostando a destra di una posizione glielementi maggiori di quello che si sta inserendo.


Algoritmo 34 - Ordinamento per inserzione (insertionsort)Input: array a da ordinareOutput: l’array a è ordinato1: for i in range(1, len(a)) do2: sposta a destra di una posizione gli elementi della porzione già

ordinata[a0, . . . , ai−1] composta dagli elementi maggiori di ai

3: memorizza ai nella locazione lasciata libera dall’ultimo elementospostato a destra

4: end for

A seguire è riportata la codifica in linguaggio Python:



# ordinamento dell’array a# mediante l’algoritmo "insertion sort"def insertionSort(a):

for i in range(1,len(a)):t = a[i]p = iwhile p > 0 and a[p-1] > t:

a[p] = a[p-1]p -= 1

a[p] = t

Nel caso di ordinamento per inserzione il numero di iterazioni del ciclo forpiù esterno è pari a n − 1. Nel caso pessimo l’elemento i-esimo che vieneinserito richiede che esso venga confrontato con tutti gli elementi già inseritie quindi richiede che vengano svolti i − 1 confronti. Il numero complessivo diconfronti richiesto è dunque pari a

T (n) =n

∑i=2i − 1 = 1 + 2 +⋯ + (n − 1) = n(n − 1)

2

La complessità asintotica risulta dunque pari a O(n2).

7.7 ORDINAMENTO VELOCEL’algoritmo di ordinamento quick-sort appartiene alla categoria di algoritmidi ordinamento veloce ed è uno dei più utilizzati. In molti linguaggi è giàimplementato nativamente nel linguaggio. Le varie implementazioni dell’al-goritmo si basano su un’idea, risalente al 1960, dell’informatico C.A.R. Hoare.L’algoritmo si basa sulla seguente strategia:

Scegliere un valore a caso (perno); ripartire l’array in due por-zioni: nella prima mettere tutti gli elementi minori o ugualial perno, nella seconda elementi maggiori o uguali al perno.Ripetere poi ricorsivamente l’ordinamento su entrambe le por-zioni dell’array. La chiusura della ricorsione è costituita dallacondizione di avere un array di un solo elemento. La partizio-ne rispetto al perno avviene ponendo inizialmente due indicialle estremità della porzione di array da ordinare, avvicinan-doli verso il centro, scambiando gli elementi quando si arrivaad elementi da scambiare, in quanto fuori ordine rispetto alperno.


7.7. ORDINAMENTO VELOCE 87

In notazione algoritmica, la sopra descritta strategia si esprime come segue:

Algoritmo 35 - Ordinamento di un array (quick-sort)Input: array aOutput: l’array a è ordinato1: if c’è più di un elemento da ordinare then2: poni due indici i e j agli estremi dell’array da ordinare3: scegli un elemento a caso (perno)4: avanza contemporaneamente i due indici i e j verso il centro scambiando

fra loro i due elementi quando sono fuori ordine rispetto al perno5: applica ricorsivamente il procedimento alle due porzioni di array poste

alla sinistra ed alla destra del perno6: end if

A seguire è riportata la codifica in linguaggio Python, basata sulla seguentefunzione ricorsiva che ordina la porzione di array compresa fra i due indici led r:

# ordinamento dell’array a# dalla posizione l(eft) alla posizione r(ight)# mediante l’algoritmo "quick sort"def qsort(a, l, r):

if l < r:i = lj = rperno = a[l]while i < j :

while a[i] < perno:i += 1

while a[j] > perno:j -= 1

if i <= j :a[i], a[j] = a[j], a[i] # scambioi += 1j -= 1

qsort(a,l,j)qsort(a,i,r)



L’ordinamento dell’intero array avviene mediante la seguente funzione:

# ordinamento dell’array a# mediante l’algoritmo "quick sort"def quickSort(a):

qsort(a,0,len(a)-1)

Per l’algoritmo quick-sort il caso ottimo si ha quando la sequenza vieneripartita rispetto al perno, ad ogni passo, in due parti perfettamente bilan-ciate (il perno va a collocarsi sempre al centro della sequenza). In questocaso la complessità asintotica risulta pari a O(n logn). Il caso pessimo, checorrisponde al caso in cui le ripartizioni rispetto al perno risultino sempre com-pletamente sbilanciate (viene scelto come perno il valore minimo o massimofra gli elementi della sequenza), ha una complessità asintotica pari a O(n2).

7.8 ESERCIZI1. Discutere la complessità degli algoritmi di ordinamento nel caso in cui

la sequenza sia inizialmente già ordinata.

2. Descrivere una rete di ordinamento corrispondente all’algoritmo bubble-sort, per ordinare un array composto da 8 elementi.

3. Analizzare il caso ottimo per l’algoritmo insertion-sort.

4. Discutere la complessità dell’algoritmo quick-sort nel caso in cui la se-quenza sia inizialmente già ordinata e come perno venga scelto il primoelemento della porzione di sequenza da ordinare.

5. Descrivere la situazione dell’array [5,6,8,1,2,7,5,3,9,6,8,4] dopo avereseguito un ciclo dell’algoritmo quick-sort prendendo come perno il primoelemento dell’array.

6. Spiegare cosa significa la frase: L’algoritmo di ordinamento quick-sortha una complessità asintotica nel caso medio pari a O(n logn).

7. Fare una tabella che riporti la complessità asintotica degli algoritmidi ordinamento bubble-sort, insertion-sort, selection-sort, quick-sort, neidiversi casi ottimo, medio, pessimo.

8. Ricercare nella letteratura informatica gli algoritmi di ordinamentomerge-sort e heap-sort e confrontarne la complessità con quella degli algoritmipresentati in questo capitolo.


7.8. ESERCIZI 89

9. Su una rivista si trova la seguente frase: Gli algoritmi di ordinamentodella classe A hanno, nel caso pessimo, una complessità asintotica paria O(n2). Spiegare cosa significa la frase. Dire quali, fra gli algoritmidi ordinamento studiati, appartengono alla classe A di cui si parla nellarivista citata.

10. Su una rivista si legge: "Il prof. Dalla Balla ha scoperto un algoritmodi ordinamento di array avente, nel caso medio, complessità uguale an log (logn)". Dire se il prof. Dalla Balla ha fatto una scoperta degnadi nota e se è credibile.

11. Decidere se un array è ordinato (crescentemente o decrescentemente).

12. Descrivere un algoritmo di complessità lineare per ordinare un array divalori booleani. Motivare perché tale algoritmo non contraddice la teoriache afferma che il problema dell’ordinamento di un array ha complessitàasintotica pari a O(n logn).

13. Decidere se due array sono uno una permutazione dell’altro.

14. Decidere se due array contengono gli stessi elementi. Valutarne la com-plessità. Dimostrare che la complessità asintotica del problema è nonsuperiore a O(n logn).

15. Decidere se un array è composto da elementi tutti distinti. Valutare, nelcaso ottimo e nel caso pessimo, la complessità, dell’algoritmo descritto.Motivare perché la complessità asintotica del problema in questione ènon superiore a O(n logn).

16. Determinare la frequenza massima con la quale compare l’elemento aven-te la più alta frequenza all’interno di un array. Valutare la complessi-tà dell’algoritmo. Motivare perché il problema in questione ha unacomplessità asintotica non superiore a O(n logn).


Capitolo 8

Ricerca

Cosa faresti se uno ti desse un grandeelenco telefonico e ti chiedesse di trova-re il nome della persona il cui numero è795-6841?D. Knuth,The Art of Computer Programming

La ricerca di informazioni rappresenta uno dei problemi più importantidella programmazione in quanto rappresenta la forma più frequente di ela-borazione in diversi ambiti applicativi; di più, questa forma di elaborazionecostituisce elemento strategico per diverse attività: si pensi, ad esempio, ai mo-tori di ricerca nel web ed alla ricerca nelle basi di dati; disporre di algoritmi diricerca veloci costituisce uno dei fattori decisivi di successo di un’applicazioneinformatica ed addirittura di un’intera azienda.

91

92 CAPITOLO 8. RICERCA

8.1 IL PROBLEMA DELLA RICERCAMoltissimi problemi rientrano nella categoria dei problemi di ricerca che,in generale, si possono formulare come segue:

Dato un insieme A ed una proprietà P , determinare glielementi x ∈ A che soddisfano alla proprietà P .

Spesso l’insieme A è un contenitore con una propria struttura organizzativainterna e degli specifici metodi per accedere agli elementi; frequentemente laproprietà P coincide con l’essere uguale ad un elemento fissato.

Il problema della ricerca risulta correlato alle strutture dati: si usano spessodelle strutture dati più articolate che non la semplice organizzazione sequen-ziale (ad esempio, gli alberi) proprio per rendere più efficienti i procedimentidi ricerca.

Ad un livello molto generale i problemi di ricerca si inquadrano nelleseguenti due forme:

R1: Ricercare in un contenitore tutti gli elementi soddisfacenti

R2: Ricercare in un contenitore se esistono elementi soddisfacenti

Nonostante l’apparente somiglianza, queste due forme di ricerca vengonorisolte con strategie sostanzialmente diverse in quanto nel primo caso bisognaanalizzare tutti gli elementi del contenitore mentre nel secondo caso si terminanon appena viene trovato un elemento soddisfacente.

Nel primo caso la ricerca si concretizza passando in rassegna tutti gli ele-menti del contenitore e quindi, in definitiva, dipende dalla struttura internadel contenitore; se esso è iterabile tutto il problema viene ricondotto a come ilcontenitore stesso gestisce il suo attraversamento e dal punto di vista dell’al-goritmo di ricerca esterno non rimane niente da fare: si tratta semplicementedi passare in rassegna tutti gli elementi e registrare quelli soddisfacenti, checostituiranno, alla fine, il risultato della ricerca.

Risultano, invece, molto interessanti gli algoritmi che si incaricano di ri-solvere il secondo tipo di ricerca; è questa la forma che viene usata più fre-quentemente. Per questa forma di ricerca, lo schema generale è descrittonell’algoritmo 36.


8.1. IL PROBLEMA DELLA RICERCA 93

Algoritmo 36 - Ricerca se esiste un elemento soddisfacenteInput: insieme A in cui cercare, proprietà P da soddisfareOutput: TRUE se e solo se esiste un elemento x ∈ A tale che P (x)1: while ¬ (trovato alcun elemento) ∧ (lo si può ancora trovare) do2: ricerca l’elemento3: end while4: return esito della ricerca

Questo è un algoritmo così generale che può essere considerato uno schemadi algoritmo che può essere adattato in tanti modi, a seconda dello specificoproblema di ricerca che si sta considerando, a seconda della struttura delcontenitore A ed a seconda della particolare strategia di ricerca attuata; inparticolare sono frequentemente adottate le seguenti due strategie:

a) passare in rassegna sequenzialmente tutti gli elementi di A

b) restringere ripetutamente l’insieme A ad un suo sottoinsieme

La strategia a) si traduce nell’algoritmo 37.

Algoritmo 37 - Ricerca di un elemento (caso a)Input: insieme A in cui cercare, proprietà P da soddisfareOutput: TRUE se e solo se esiste un elemento x ∈ A tale che P (x)1: trovato← FALSE2: trovabile← ∣A∣ > 03: while (¬ trovato) ∧ trovabile do4: considera un elemento x ∈ A non ancora esaminato5: if P (x) then6: trovato← TRUE7: else if non ci sono più elementi da esaminare then8: trovabile← FALSE9: end if

10: end while11: return trovato

La seconda strategia di ricerca (b)) si traduce nell’algoritmo 38. La restri-zione dell’insieme T ad un suo sottoinsieme proprio (istruzione 8 dell’algorit-mo 38) può essere realizzata, ad esempio, eliminando l’elemento x dall’insiemeT stesso, oppure delimitando lo spazio di ricerca.



Algoritmo 38 - Algoritmo di ricerca (caso b)Input: insieme A in cui cercare, proprietà P da soddisfareOutput: TRUE se e solo se esiste un elemento x ∈ A tale che P (x)1: trovato← FALSE2: T ← A3: while (¬ trovato) ∧ (T ≠ ∅) do4: considera un elemento x ∈ T non ancora esaminato5: if P (x) then6: trovato← TRUE7: else8: restringi T ad un suo sottoinsieme proprio9: end if

10: end while11: return trovato

8.2 LA RICERCA IN UNO SPAZIO INFINITOLo spazio di ricerca può influenzare in modo decisivo l’algoritmo di ricerca,come evidenziano i seguenti due esempi.Esempio 49. Consideriamo il seguente problema:

Determinare un numero positivo x in modo che si abbia x2 = 2.Il risultato è x =

√2 se si ammette che il numero x possa essere un numero

reale, mentre il problema non ammette soluzione se si impone che il numero xdebba essere razionale. In tali casi nella definizione del problema deve essereprecisato lo spazio di ricerca, ossia l’insieme in cui ricercare gli eventuali possi-bili risultati del problema. Lo spazio di ricerca è un parametro fondamentaleper caratterizzare il problema. Nella maggior parte dei casi lo spazio di ricercarisulta definito implicitamente dal contesto in cui è formulato il problema.

Nel caso in cui lo spazio di ricerca sia infinito bisogna adottare delle tec-niche diverse, tali che non prevedano, evidentemente, di passare in rassegnatutti gli elementi dello spazio.Esempio 50. I seguenti due problemi possono essere inquadrati come problemidi ricerca in uno spazio infinito:P1: Risolvere un’equazione di secondo grado ax2 + bx + c = 0.

P2: Scomposizione in fattori primi di un dato numero naturale n.In questi casi lo spazio di ricerca è costituito dall’insieme (infinito) dei numeri;questi problemi vengono risolti calcolando il risultato.


8.3. RICERCA IN UNA SEQUENZA 95

8.3 RICERCA IN UNA SEQUENZAConsideriamo ora il caso particolare di ricerca in una sequenza A. In questocontesto gli algoritmi di ricerca possono essere classificati in base a diversecaratteristiche:

• modalità di accesso alla sequenza:

– accesso sequenziale alla sequenza (la sequenza si comporta come uncontenitore iterabile)

– accesso diretto 1 agli elementi della sequenza (nella tipica notazionead indice a[k]);

• ordinamento della sequenza:

– la sequenza non è ordinata– la sequenza è ordinata

• tipologia del risultato:

– ricerca se esiste un elemento soddisfacente– ricerca tutti gli elementi soddisfacenti

Le varie combinazioni di queste situazioni producono algoritmi diversi perstrategia e per efficienza.

8.4 RICERCA IN SEQUENZE NON ORDINATENel caso di ricerca se in una sequenza non ordinata A è presente un elemento x,l’algoritmo 37 assume la forma riportata nell’algoritmo 39. Questo algoritmodi ricerca viene utilizzato anche nel caso in cui la sequenza A sia un genericocontenitore iterabile. Nel caso in cui il contenitore A soddisfi a dei requisitipiù forti (ad esempio, sia ordinato) si possono usare degli algoritmi di ricercaspecifici e più efficienti.

1Si assume l’ipotesi che l’accesso ad un elemento avvenga in tempo costante, indi-pendentemente dal suo indice di posizione; in questa ipotesi la sequenza viene dettaarray.



Algoritmo 39 - Ricerca di un elemento in una sequenza (non ordinata)Input: sequenza a = [a0, . . . , an−1] in cui cercare, elemento x da ricercareOutput: TRUE se e solo se x è presente in a1: trovato← FALSE2: i← 03: while (¬ trovato) ∧ (i < len(a) do4: if ai = x then5: trovato← TRUE6: else7: i← i + 18: end if9: end while

10: return trovato

Nell’analisi della complessità degli algoritmi di ricerca si assume come di-mensione del problema il numero n degli elementi della sequenza e come ope-razione dominante il confronto fra un elemento della sequenza con l’elementoda ricercare. Per l’algoritmo 39 il caso pessimo corrisponde al caso in cuil’elemento x non sia presente nella sequenza (oppure sia presente all’ultimaposizione). In questo casola complessità dell’algoritmo è pari a O(n). Nell’i-potesi che gli elementi siano distribuiti in modo uniforme nella sequenza, anchenel caso medio la complessità risulta pari a O(n) (media delle complessità ditutti i casi possibili).

A seguire è riportata la codifica in linguaggio Python dell’algoritmo 39,nel caso in cui la proprietà P consista nell’essere uguale all’elemento x.

# ricerca sequenzialedef sequentialSearch(a,x):

i = 0trovato = Falsewhile not trovato and i < len(a):

if a[i] == x:trovato = True

else:i += 1

return trovato


8.5. RICERCA IN ARRAY ORDINATI 97

8.5 RICERCA IN ARRAY ORDINATINel caso di array ordinati l’algoritmo di ricerca può essere migliorato sfrut-tando la proprietà di ordinamento e di accesso diretto agli elementi. L’ideafondamentale consiste nell’analizzare l’elemento mediano dell’array; l’esito diquesto confronto permette di stabilire se l’elemento considerato sia uguale aquello cercato, e, nel caso contrario, stabilire su quale delle due metà l’ele-mento cercato si possa eventualmente trovare; con un unico confronto vienescartata metà dell’array.

Algoritmo 40 - Ricerca di un elemento in un array ordinatoInput: array a = [a0, . . . , an−1] ordinato in cui cercare, elemento x da ricercareOutput: TRUE se e solo se x è presente in a1: primo← 02: ultimo← n − 13: trovato← FALSE4: while (¬ trovato) ∧ (primo ≤ ultimo) do5: medio← (primo + ultimo)/26: if a[medio] = x then7: trovato← TRUE8: else if x < a[medio] then9: ultimo←medio − 1

10: else11: primo←medio + 112: end if13: end while14: return trovato

Il caso ottimo si verifica quando il valore cercato è presente nell’elementoche sta nella posizione di mezzo dell’array. In questo caso la complessitàasintotica è O(1) come per il caso ottimo dell’algoritmo di ricerca lineare.

Nel caso pessimo lo spazio di ricerca viene ripetutamente diviso a metàfino a restare con un unico elemento da confrontare con il valore cercato. Ilnumero di iterazioni del ciclo risulta pari al numero di dimezzamenti che èuguale a ⌈log2 n⌉; pertanto la complessità asintotica è O(logn).

In linguaggio Python l’algoritmo 40, viene codificato come segue:



# ricerca binariadef binarySearch(a,x):

primo = 0ultimo = len(a) - 1trovato = Falsewhile not trovato and primo <= ultimo:

medio = (primo + ultimo) // 2if a[medio] == x:

trovato = Trueelif x < a[medio]:

ultimo = medio-1else:

primo = medio+1return trovato

8.6 RICERCA ED ORDINAMENTO

Gli algoritmi di ricerca ed ordinamento sono fortemente connessi fra loro. Neè conferma il seguente esempio.

Esempio 51. Consideriamo il problema di decidere se un array è compostoda elementi tutti distinti. Una soluzione di questo problema può basarsisulla seguente idea: Confrontare ciascun elemento con tutti gli elementi chelo precedono. L’algoritmo basato su questa idea è il seguente:

Algoritmo 41 - Decisione se un array è composto da elementi distintiInput: array a = [a0, . . . , an−1]Output: TRUE se e solo se (a[i] ≠ a[j] per ogni i, j (i ≠ j))1: distinti← TRUE2: i← 13: while distinti ∧ (i < len(a)) do4: ricerca se a[i] è presente nella porzione di array a[0...i − 1]5: if è presente then6: distinti← FALSE7: else8: i + +9: end if

10: end while11: return distinti


8.6. RICERCA ED ORDINAMENTO 99

Il problema di ricerca della linea 4 può essere risolto efficientemente adot-tando una ricerca con sentinella sulla porzione di array a[0..i].

Nel caso pessimo (tutti gli elementi sono distinti fra loro) la complessitàdell’algoritmo è pari a

T (n) = 1 + 2 + ⋅ ⋅ ⋅ + (n − 1) = n(n − 1)2

∈ O(n2)

dove l’ultimo addendo corrisponde al numero di confronti richiesti per con-trollare che l’ultimo elemento non sia presente nella sottosequenza degli n − 1confronti che precedono.Esempio 52. Scriviamo un algoritmo per determinare la frequenza degli ele-menti di un array aventi la massima frequenza.

Algoritmo 42 - Calcolo della frequenza massima in un arrayInput: array a di dimensione nOutput: massima frequenza degli elementi di a1: fmax← 02: for i from 0 to n − 1 do3: f ← frequenza di a[i]4: if f > fmax then5: fmax← f6: end if7: end for8: return fmax

La complessità della funzione frequenza è n; essendo che questa funzioneviene richiamata n volte all’interno del ciclo for, si conclude che l’algoritmoha complessità asintotica pari a O(n2). Si lascia per esercizio la valutazionedella complessità del problema.



8.7 ESERCIZI

1. Analizzare la complessità della ricerca su un array, distinguendo il casoin cui l’array sia ordinato e nel caso in cui non sia ordinato.

2. Spiegare cosa si intende con la frase L’algoritmo di ricerca binaria inun array ordinato ha complessità asintotica logaritmica. Motivare per-chè l’algoritmo di ricerca binaria su un array ordinato ha complessitàasintotica O(log n).

3. Discutere ed evidenziare, avvalendosi anche di opportuni esempi, alcu-ni nessi logici ed operativi esistenti fra i problemi di ordinamento ed iproblemi di ricerca.

4. Determinare quante volte un dato valore è presente in un array. Valutarela complessità dell’algoritmo. Spiegare perché in questo caso ha pocosenso parlare di complessità nel caso pessimo, medio, ottimo.

5. Decidere se in un dato array a è presente un dato elemento x nelleposizioni comprese fra due dati indici naturali p e q (p ≤ q).

6. Determinare il numero di elementi uguali ad un dato elemento presentiun un array ordinato.

7. Determinare le posizioni in cui è presente un dato elemento in un array.

8. Dati due array, determinare il più piccolo elemento presente in entrambigli array.

9. Ricercare se e dove è presente un dato valore in una data matrice.

10. Contare il numero di numeri primi presenti in una matrice.

11. Determinare l’elemento che compare con maggiore frequenza in unamatrice.

12. Una matrice rettangolare contiene numeri naturali estratti da un’urna; ilvalore 0 rappresenta la non presenza di un valore non estratto. Deciderese due dati numeri formano un ambo, ossia se sono entrambi presenti inuna stessa riga della matrice.

13. Ricercare se in una matrice di caratteri è presente (orizzontalmente overticalmente) una data parola.


8.7. ESERCIZI 101

14. All’inizio del secolo scorso il matematico Hardy andò in taxi all’ospedalea fare visita all’amico e collega Ramanujan. Esordì citando il numerodel taxi con il quale era venuto, annotando che, per lui, si trattava di unnumero piuttosto insignificante. A tali parole Ramanujan replicò che,nientaffatto, il numero era piuttosto interessante, essendo il più piccolonumero naturale esprimibile in due modi diversi come somma di duecubi. Determinare tale numero.


Capitolo 9

Rappresentazione

[...] l’intelligenza dipende in modo cru-ciale dalla capacità di costruire descrizionidi livello superiore di certi raggruppamenticomplessi [...].D. R. Hofstadter, Gödel, Escher,Bach

In questo capitolo vengono analizzate le modalità con cui rappresentare glioggetti mediante la composizione di entità elementari, ponendo l’accento sullarappresentazione della struttura organizzativa di oggetti composti, formati daaggregazioni di oggetti più elementari. Si tratta di definire delle strutturedati che fotografano gli oggetti. La rappresentazione di un oggetto compostosi fonda sulla rappresentazione dei singoli oggetti elementari, ma la strutturaorganizzativa non dipende dalla rappresentazione degli oggetti componenti. Ildiscorso che segue lo si incontra in quasi tutti i linguaggi di programmazionee va sotto il nome di strutture organizzative dei dati.

103

104 CAPITOLO 9. RAPPRESENTAZIONE

9.1 RAPPRESENTAZIONERappresentare significa stabilire una corrispondenza fra gli elementi di dueambienti diversi 1 . Dato un insieme A ed un insieme B una rappresentazioneè una corrispondenza

rap ∶ A→ BLa corrispondenza inversa viene detta interpretazione:

int ∶ B → A

La potenza del meccanismo di rappresentazione risiede e dipende dallaricchezza e duttilità della struttura dell’insieme B. Nell’informatica, nel con-testo della soluzione dei problemi, l’insieme A viene detto spazio dei problemie rappresenta il contesto in cui sorgono e si analizzano i problemi, mentre l’in-sieme B viene detto spazio delle soluzioni e costituisce l’ambiente in cui vienedescritta la soluzione del problema e viene svolta la fase di elaborazione.

Le sequenze costituiscono il tipico spazio delle soluzioni in ambito infor-matico. In pratica, gli oggetti coinvolti nel problema vengono trasformati insequenze (di oggetti più elementari) per essere elaborati mediante i linguaggidi programmazione.Esempio 53. Uno dei più classici esempi di rappresentazione nell’ambito del-l’informatica è dato dalla codifica dei numeri naturali mediante stringhe bi-narie, formate da 0 e 1. In questo caso la funzione di rappresentazione ècaratterizzata dal prototipo

N→ String

Esempio 54. Le sequenze [...] sono oggetti informatici; nel momento in cui sor-ge la necessità di descriverle su un libro o sulla lavagna diventano oggetti visua-lizzabili sotto forma di sequenza di caratteri; in pratica questa trasformazionecorrisponde ad una rappresentazione della forma

Sequenze→ String

Esempio 55. Introducendo un sistema di assi cartesiani, un punto del pianopuò essere rappresentato mediante la coppia delle sue coordinate:

punto P del piano → [x, y]

Su questa utilizzatissima funzione di rappresentazione si fonda il ramo dellaMatematica nota con il nome di geometria analitica.

1Questa corrispondenza deve essere preferibilmente ma non necessariamente univoca, nelsenso che ad un elemento a di A possono corrispondere più elementi di B. La corrispondenzainversa deve essere, invece, univoca.


9.1. RAPPRESENTAZIONE 105

Esempio 56. La modalità di rappresentazione viene definita in funzione delleoperazioni che si devono svolgere nello spazio delle soluzioni. Ad esempio,nel caso in cui l’obiettivo sia la determinazione delle radici di un’equazione disecondo grado, l’equazione può essere rappresentata mediante la terna dei suoicoefficienti (tralasciando il nome identificativo dell’incognita):

equazione ax2 + bx + c = 0→ [a, b, c]

Esempio 57. Un esempio di rappresentazione tratto dalla quotidianità è datodalla mappa dei percorsi di una metropolitana. In questo caso la funzione dirappresentazione è caratterizzata dal prototipo

Realtà →Disegno

Figura 9.1: Le mappe dei trasporti pubblici di Londra, benché fossero dispo-nibili dal 1908, erano oggetti di inafferrabile complessità. La mappa dellametropolitana di Londra riportata in figura venne progettata da Harry Becknel 1931. Viene considerata come un classico del design ed ha ispirato lerappresentazioni dei sistemi di trasporto urbano di tutto il mondo.

Il meccanismo della rappresentazione ed interpretazione sta a fondamentodel tradizionale processo di risoluzione di un problema, eseguendo una tra-sformazione dallo spazio dei problemi allo spazio delle soluzioni dove avvienela fase di elaborazione; successivamente avviene la fase di interpretazione deirisultati ottenuti, come schematizzato nella figura 9.2.



risultati reali risultati codificati

dati codificatirappresentazione

interpretazione

elaborazione

dati reali -

�

?

Figura 9.2: Schema delle fasi della rappresentazione dei dati ed interpretazionedei risultati.

9.2 RAPPRESENTAZIONI CON STRUTTURE

Le strutture, grazie alla possibilità di essere composte da elementi costituiti aloro volta da strutture, risultano uno strumento molto versatile che si presta arappresentare qualsiasi oggetto, comunque articolato e comunque complesso.

Come avviene per ogni forma di rappresentazione, individuato un insiemeA di oggetti da rappresentare, si tratta di definire una funzione

rap ∶ A→ Struttura

che ad ogni elemento dell’insieme A associa una struttura che ne è la rappre-sentazione.

La notazione utilizzata per descrivere una struttura deve essere sufficiente-mente vicina alle strutture dati previste dai linguaggi di programmazione (alfine di poter rendere possibile l’implementazione) ma sufficientemente astrattaper non essere vincolata ad uno specifico linguaggio di programmazione ed aidettagli implementativi dei tipi di dato strutturati (array, . . . ) predisposti dailinguaggi. In seguito, per descrivere una struttura, adotteremo la notazionea struttura anonima

[. . . ]

oppure la notazione a struttura labellata

T [. . . ]

dove T è un identificatore di tipo; in questi due casi si parla anche di strutturatipizzata.


9.3. COMPOSIZIONE DI RAPPRESENTAZIONI 107

9.3 COMPOSIZIONE DI RAPPRESENTAZIONILa rappresentazione di un oggetto può avvenire attraverso passi successivi incui ogni livello costituisce la rappresentazione del livello precedente.Esempio 58. Per descrivere i confinamenti fra regioni geografiche si usa soli-tamente uno schema grafico come quello riportato in figura 9.3, dove vengonotrascurate le informazioni di tipo metrico e considerate solo le informazionitopologiche relative ai confinamenti.

h

a b

c d

f

g

e

Figura 9.3: Rappresentazione grafica dei confinamenti fra regioni.

Lo schema riportato in figura 9.3 può essere trasformato biunivocamentenel grafo isomorfo riportato nella figura 9.4.

t tt tt tt t

@@@@

��

��@@

@@

��

��

��

��

��

��

��

a b

c

d

ef

g

h

Figura 9.4: Grafo corrispondente alla mappa dei confinamenti fra regioniriportata nella figura 9.3.



Questo grafo risulta più semplicemente traducibile nelle strutture dati pre-disposte dai linguaggi di programmazione che consentono delle efficienti formedi elaborazione. Ad esempio, può essere rappresentato mediante una matricebinaria le cui righe e colonne sono individuate dagli identificatori dei nodi,come descritto nella figura 9.5 .

a b c d e f g h

a 1 1b 1 1 1 1 1c 1 1 1d 1 1 1e 1 1f 1 1 1 1 1g 1 1 1h 1 1 1

Figura 9.5: Matrice binaria che rappresenta il grafo riportato nella figura 9.4(per semplicità non sono indicati i valori uguali a 0).

Le matrici binarie che rappresentano grafi composti da molti vertici risul-tano spesso costituite da un’alta percentuale di valori uguali a 0. Questematrici, dette matrici sparse, vengono rappresentate, in modalità compressa,registrando solamente i valori non nulli; ad esempio, il grafo riportato nellafigura 9.4 può essere rappresentato anche mediante una sequenza di coppie,ciascuna delle quali rappresenta un arco che congiunge due nodi:

[[a, b], [a, h], [b, c], [b, f], [b, g], [b, h], [c, d], [c, f], [d, e], [d, f], [e, f], [f, g], [g, h]]

Esempio 59. Un’espressione è un oggetto matematico che viene tradizional-mente scritto, su un testo di Matematica, con una notazione della forma

(3x)2 + xy

Nel contesto del codice sorgente di un linguaggio di programmazione o nelleoperazioni di input/output testuale a carattere, questa espressione può esserescritta come stringa nella forma

(3x)**2+x*y


9.3. COMPOSIZIONE DI RAPPRESENTAZIONI 109

Tale rappresentazione risulta poco comoda ai fini dell’elaborazione dell’espres-sione (valutazione per specifici valori delle incognite, semplificazione, deriva-zione, operazioni fra espressioni, . . . ). Per queste forme di elaborazione risultapreferibile una rappresentazione ad albero come descritto nella figura 9.6.

m+m̂ m*

��

��

ZZZZZ

m* m2 mx my�

��

@@@@

��

��

@@@@

m3 mx

JJJJ

Figura 9.6: Rappresentazione ad albero dell’espressione (3x)2 + xy.

L’albero riportato nella figura 9.6 può a sua volta essere descritto medianteuna struttura, come segue:

[+, [ ,̂ [∗,3, x],2], [∗, x, y] ]Esempio 60. La situazione in cui una cartella a contiene due cartelle b e c; lacartella c contiene una cartella d e due file f e g può essere descritta mediantelo schema grafico riportato nella figura 9.7.

a

b c

d m mf g

��

@@@

��

@@@

Figura 9.7: Albero di cartelle e file.

L’albero descritto nella figura 9.7 può essere rappresentato mediante laseguente struttura, dove i valori 0 e 1 stanno a specificare se si tratta di una



cartella o di un file.

[ [a,0], [ [b,0] ], [ [c,0], [ [d,0], [f,1], [g,1] ] ] ]

C’è da notare che non ogni struttura della forma sopra rappresenta una ef-fettiva porzione di file system, in quanto bisogna imporre il vincolo che unfile non contenga cartelle o file. Per prevenire queste situazioni di struttureincoerenti si delega la creazione e la modifica della struttura a delle opera-zioni, appositamente predisposte, che intervengono sulla struttura in modocontrollato.Esempio 61. Si vuole definire una rappresentazione di un sistema a blocchicostituito da blocchi collegati fra loro in serie o in parallelo. Un esempio diquesto tipo di sistema a blocchi è riportato nella figura 9.8.

a

b

c d e

Figura 9.8: Sistema a blocchi.

L’idea sulla quale si basa la rappresentazione di un sistema a blocchi èdescritta nella figura 9.9. Analogamente si possono rappresentare gli accop-piamenti in serie ed in parallelo di più di due blocchi.

β

α

α βrap( ) = [s, rap(α), rap(β)]

rap( ) = [p, rap(α), rap(β)]

Figura 9.9: Rappresentazione di blocchi in serie ed in parallelo. α e β sonoblocchi o elementi atomici e p ed s sono dei metasimboli che qualificano latipologia (serie o parallelo) dell’accoppiamento fra due blocchi.


9.4. RAPPRESENTAZIONI DI AGGREGAZIONI 111

Il precedente sistema a blocchi può essere rappresentato mediante l’albe-ro riportato nella figura 9.10 dove i nodi interni indicano se i sottoblocchirappresentati dai due sottoalberi figli sono connessi in serie o in parallelo.

mp

mp ms

a b c d e

��

��

@@@@@

��

AAAAA

��

AAAAA

Figura 9.10: Albero che rappresenta il sistema a blocchi di figura 9.8.

Tale albero a sua volta può essere rappresentato mediante la struttura chesegue:

[p, [p, [a, b] ], [s, [c, d, e] ] ]

9.4 RAPPRESENTAZIONI DI AGGREGAZIONILe strutture si prestano a rappresentare qualsiasi forma di aggregazione dielementi. Ne sono testimonianza gli esempi che seguono. I primi due esempievidenziano che una stessa struttura può rappresentare due aggregazioni chedal punto di vista concettuale ed operativo sono completamente diverse (in-siemi e sequenze). Il meccanismo della rappresentazione deve essere pertantocompletato definendo le operazioni che caratterizzano l’oggetto rappresentato.Esempio 62. Un insieme di elementi può essere rappresentato mediante unastruttura come descritto nella figura 9.11. Questa rappresentazione nonè biunivoca in quanto ogni permutazione della sequenza [a, b, c, d, e, f] puòessere considerata accettabile rappresentazione dell’insieme considerato nellafigura 9.11.


112 CAPITOLO 9. RAPPRESENTAZIONE'

&

$

%a

b

cd

e

f

[a, b, c, d, e, f]

Figura 9.11: Insieme e corrispondente rappresentazione mediante unastruttura.

Esempio 63. Una sequenza di elementi può essere rappresentata mediante unastruttura come descritto nella figura 9.12. In questo caso la corrispondenza èbiunivoca.

a b c d e f

[a, b, c, d, e, f]

Figura 9.12: Sequenza e corrispondente rappresentazione mediante unastruttura.

Esempio 64. Una matrice di elementi può essere rappresentata mediante unastruttura composta come descritto nella figura 9.13.

a bc de f

[ [a, b], [c, d], [e, f] ]

Figura 9.13: Matrice e corrispondente rappresentazione mediante unastruttura.


9.5. OPERAZIONI SULLE STRUTTURE 113

Esempio 65. Un albero di elementi può essere rappresentato mediante unastruttura composta come descritto nella figura 9.14.

��

@@

��

@@

a

b c

d e f

[a, [b], [c, [d, e, f] ] ]

Figura 9.14: Albero e corrispondente rappresentazione mediante unastruttura.

Esempio 66. Un grafo (insieme di elementi fra loro interconnessi) può essererappresentato mediante una struttura come descritto nella figura 9.15.

�� @@

@@ �� @@

��

a e

b c

d f

[ [a, b], [a, c], [b, c], [b, d], [c, e], [c, f], [d, f] ]

Figura 9.15: Grafo e corrispondente rappresentazione mediante una struttura.

9.5 OPERAZIONI SULLE STRUTTURELa rappresentazione di un oggetto costituisce solo una parte della fase di im-plementazione in quanto, per poter utilizzare un oggetto, è necessario poterapplicare su di esso delle operazioni. La fase di rappresentazione viene per-tanto completata con la fase di definizione delle operazioni che mascherano lastruttura dati sottostante. È proprio l’insieme delle operazioni utilizzabili checaratterizza gli oggetti. La struttura dati non viene percepita per quello cheè, ma viene protetta e nascosta da un insieme di operazioni che definiscono unlivello semantico che caratterizza l’interfaccia e le funzionalità espletate daglioggetti. Questo livello offre diversi vantaggi:



• maschera la struttura dati sottostante

• predispone delle operazioni astratte caratterizzanti l’oggetto

• evita la complessità che deriverebbe da un accesso diretto alla strutturadati

• permette che si possa facilmente cambiare l’implementazioneEsempio 67. Consideriamo l’insieme P dei polinomi in una indeterminata x acoefficienti reali; ad esempio: 4,−7x, 2x2 − 5x + 3, x3 − 2x + 1. Sui polinomi sipossono eseguire le seguenti operazioni:

P : ∅ → P // polinomio zerogrado : P → N // grado del polinomiocoeff : P ×N → R // coefficiente di xn

aggiunta : P ×R ×N → P // aggiunta di un monomiovalore : P ×R → R // valore in un puntoderivata : P ×N → P // derivata di ordine nintegrale : P → P // integrale indefinitointegrale : P ×R2 → R // integrale definito su [a, b]stringa : P → String // conversione a stringa

Un polinomio di grado n della forma

an xn + an−1 x

n−1 +⋯ + a1 x + a0

può essere rappresentato mediante un array di dimensione n + 1 contenente,in ordine di grado, i coefficienti dei monomi del polinomio:

[a0, a1, . . . , an−1, an]Nel caso in cui il polinomio sia sparso, ossia molti dei coefficienti siano nulli,si può adottare la rappresentazione che registra le coppie [ak, k] costituite daicoefficienti ak (non nulli) ed il grado del corrispondente monomio.

Usando queste due modalità di rappresentazione, il polinomio

4x7 + 6x5 − 3x2 + 2

viene rappresentato, rispettivamente, dalle due sequenze

[2,0,− 3,0,0,6,0,4][ [2,0], [−3,2], [6,5], [4,7] ]

Il criterio per la scelta della struttura dati si basa sulla semplicità e sul-l’efficienza delle operazioni che dovranno essere svolte.


9.6. IMPLEMENTAZIONE 115

9.6 IMPLEMENTAZIONENei vari linguaggi di programmazione le operazioni sugli oggetti vengono rea-lizzate adottando diversi paradigmi:

• funzionale: l’operazione viene realizzata mediante una funzione aventel’oggetto come argomento; anche nel caso di operazioni di aggiornamentodell’oggetto, esso non viene modificato e viene ritornato come risultatouna copia dell’oggetto modificato. Ad esempio, l’operazione avente perargomento un oggetto a ed un elemento x avrebbe la seguente forma:

operazione(a, x)

Per ottenere l’effetto di modificare un oggetto a nel contesto del paradig-ma funzionale si deve derogare dal paradigma puro e, appoggiandosi alparadigma procedurale, si può ricorrere ad un’assegnazione nella forma

a = operazione(a, x)

• procedurale: l’operazione viene realizzata mediante una procedura in cuil’oggetto compare come argomento di inout; ad esempio, un’operazioneavente argomento x su un oggetto a avrebbe la seguente forma:

operazione(a, x)

Il risultato dell’operazione viene ottenuto come modifica dell’oggetto a.

• ad oggetti: l’operazione viene realizzata mediante un metodo d’istan-za rivolto all’oggetto; ad esempio, l’operazione rivolta all’oggetto a edavente argomento un elemento x avrebbe la seguente forma:

a.operazione(x)

A seguire è riportato un modulo in linguaggio Python che costituisce unnucleo di funzioni che permettono di gestire polinomi in una indetermina-ta, adottando il paradigma funzionale e la rappresentazione mediante array.In questa soluzione un polinomio diventa direttamente un riferimento allastruttura dati che lo rappresenta.



# costruttore di un polinomio zerodef Polinomio():

return [0]

# grado del polinomio pdef grado(p):

return len(p)-1

# coefficiente del monomio di grado n del polinomio pdef coeff(p,n):

return p[n]

# polinomio con l’aggiunta del monomio c*x^n al polinomio pdef aggiunta(p,c,n):

r = list(p) # copia di pif n>len(r):

r.extend((n-len(r)+1)*[0])r[n] = creturn r

Basandosi su queste funzioni di base si possono definire delle altre funzionidi livello più alto, che risultano indipendenti dalla specifica rappresentazionesottostante.

# valutazione del polinomio p nel punto x# (metodo di Horner, di complessita’ O(n))def valore(p,x):

v = 0for i in range(grado(p),-1,-1):

v = (v+coeff(p,i))* xreturn v

# stringa del polinomio pdef stringa(p):

s = ’’for i in reversed(range(grado(p)+1)):

if coeff(p,i) != 0:if s != ’’ and coeff(p,i)>0:

s += ’+’if coeff(p,i)!=1:

s += str(coeff(p,i))if i>0:

s += ’x^’+str(i)return s


9.6. IMPLEMENTAZIONE 117

A seguire è riportata una porzione di codice che richiama le funzioni suipolinomi definite sopra.

p = Polinomio()p = aggiunta(p,2,5) # +2x^5p = aggiunta(p,-3,7) # -3x^7p = aggiunta(p,-5,0) # -5p = aggiunta(p,1,4) # x^4print(’stringa(p) =’,stringa(p)) # stringa(p) = -3x^7+2x^5+x^4-5print(’p(2) =’,valore(p,2)) # p(2) = -618

Una versione alternativa al modulo di funzioni presentate sopra consistenell’adottare il paradigma orientato agli oggetti; questa soluzione alternativasi realizza definendo la classe Polinomio che implementa i metodi di base chedipendono dalla struttura dati utilizzata per rappresentare un polinomio edalla classe PolinomioX che estende la classe Polinomio definendo dei metodibasati sui metodi della classe Polinomio. A seguire è riportato il codice delleclassi Polinomio e PolinomioX.

class Polinomio:

# costruttore di polinomio zerodef __init__(self):

self.p = [0]

# grado del polinomiodef grado(self):

return len(self.p)-1

# coefficiente del monomio di grado ndef coeff(self,n):

return self.p[n]

# polinomio con l’aggiunta del monomio c*x^ndef aggiunta(self,c,n):

r = list(self.p) # copia di pif n>len(r):

r.extend((n-len(r)+1)*[0])r[n] = cself.p = r



class PolinomioX(Polinomio):

# valutazione del polinomio nel punto x# (metodo di Horner, di complessita’ O(n))def valore(self,x):

v = 0for i in range(self.grado(),-1,-1):

v = (v+self.coeff(i))* xreturn v

# conversione in stringadef __str__(self):

s = ’’for i in reversed(range(self.grado()+1)):

if self.coeff(i) != 0:if s != ’’ and self.coeff(i)>0:

s += ’+’if self.coeff(i)!=1:

s += str(self.coeff(i))if i>0:

s += ’x^’+str(i)return s

A seguire è riportata una porzione di codice che utilizza dei polinomi gestitimediante i metodi delle due classe Polinomio e PolinomioX.

p = PolinomioX()p.aggiunta(2,5) # +2x^5p.aggiunta(-3,7) # -3x^7p.aggiunta(-5,0) # -5p.aggiunta(1,4) # x^4print(’p =’,p) # p = -3x^7+2x^5+x^4-5print(’str(p) =’,str(p)) # str(p) = -3x^7+2x^5+x^4-5print(’p(2) =’,p.valore(2)) # p(2) = -618


9.7. ESERCIZI 119

9.7 ESERCIZI1. Rappresentare mediante delle strutture le seguenti classi di oggetti:

(a) numeri complessi(b) segmenti del piano cartesiano(c) triangoli del piano cartesiano(d) polinomi in più indeterminate

2. Rappresentare mediante delle strutture le seguenti classi di oggetti:

(a) insieme di elementi(b) sequenze di insiemi di elementi(c) poligono del piano cartesiano

3. Rappresentare mediante delle strutture le seguenti classi di oggetti:

(a) posizione del gioco della dama(b) posizione del gioco degli scacchi(c) posizione del gioco del tris (tic-tac-toe)(d) configurazione del gioco delle 8 regine(e) configurazione del cubo di Rubik

4. Rappresentare mediante una struttura il sistema a blocchi riportato nellafigura che segue.

a

b

c

d

5. Discutere il fatto che possano esistere diverse rappresentazioni di unostesso schema a blocchi. Determinare quando due rappresentazionidistinte rappresentano uno stesso sistema a blocchi.

6. Rappresentare mediante una struttura un generico circuito elettrico concomponenti R, L, C.



7. Rappresentare mediante una struttura una mappa di una metropolitanacostituita da varie linee che connettono le varie stazioni, analogamentea quanto descritto nella nella figura 9.1.

8. Un quad-tree è una partizione di un rettangolo ottenuta mediante leseguenti operazioni di base: si parte da un rettangolo. Si procedeselezionando un punto interno a qualche rettangolo e si disegnano duesegmenti di divisione del dato rettangolo, paralleli ai lati dei rettangoligià costruiti. Rappresentare un quad-tree mediante una struttura.

r rr rr

Figura 9.16: Quad-tree.

9. Descrivere una struttura dati adeguata a rappresentare un generico poli-nomio in una indeterminata (ad esempio, 4x3−5x2+7). Con riferimentoalla struttura dati scelta, realizzare le operazioni di addizione, sottrazio-ne, moltiplicazione e divisione fra polinomi. Realizzare le operazioni peril calcolo di derivate, integrali indefiniti ed integrali definiti sui polinomi.

10. Descrivere una struttura dati adeguata a rappresentare un generico po-ligono del piano cartesiano i cui vertici sono labellati, ossia individuatiunivocamente mediante un nome identificativo. Con riferimento allastruttura dati scelta, determinare il perimetro e l’area di un poligono.


Capitolo 10

Contenitori

Vedremo che non c’è niente di magico, mi-sterioso o difficile sui metodi per trattarestrutture complesse.D. Knuth,The Art of Computer Programming

Un contenitore è un tipico design pattern che caratterizza la maggior partedelle strutture dati e caratterizza a livello astratto qualsiasi struttura compostada oggetti più elementari. Le varie tipologie di contenitori sono caratterizzateda un insieme di operazioni generali applicabili ad ogni categoria di contenitoree da un insieme di operazione specifiche che caratterizzano le diverse tipologiedi contenitore.

121

122 CAPITOLO 10. CONTENITORI

10.1 CONTENITORIUn contenitore è un aggregato di oggetti che viene considerato come un oggettoindividuale. Per indicare che C è un contenitore di generici oggetti di tipo Esi utilizza la notazione C

E. Graficamente un generico contenitore di oggetti

può essere descritto come nella figura 10.1.

'

&

$

%s ss ss s s

Figura 10.1: Contenitore di oggetti.

Un contenitore, a differenza di un generatore, si caratterizza per il fattoche gli elementi non vengono generati dal contenitore ma vengono dapprimainseriti nel contenitore e successivamente acceduti ed estratti. In base a questacaratterizzazione, in generale, su un contenitore risultano applicabili diversecategorie di operazioni:

• operazioni per inserire elementi

• operazioni per eliminare elementi

• operazioni per accedere agli elementi

• operazioni per interrogare lo stato del contenitore

Il criterio in base al quale gli elementi vengono inseriti nel e forniti dalcontenitore dipende e caratterizza ciascun specifico contenitore. Tale criterioindirizza inoltre la scelta della struttura dati fisica con la quale memorizzaregli elementi nel contenitore.

Senza entrare nei dettagli delle specifiche sintattiche di un dato linguaggiodi programmazione, un’operazione viene in genere descritta mediante una spe-cifica funzionale della forma che segue (riferita all’operazione di inserimentodi un elemento nel contenitore):

inserisci ∶ CE×E → C

E


10.2. ATTRAVERSAMENTO DI CONTENITORI 123

10.2 ATTRAVERSAMENTO DI CONTENITORIUn contenitore, indipendentemente dalla sua struttura organizzativa interna,deve poter essere ispezionato e consentire l’accesso ai suoi elementi. Unastruttura dati che, in un qualche modo, permette di essere attraversata, vienedetta attraversabile o iterabile.

'

&

$

%s ss ss s s-

@@��XXXX

��HH�

��

-

Figura 10.2: Contenitore iterabile.

Un contenitore attraversabile viene detto contenitore iterabile. L’attra-versamento di un contenitore può essere realizzato mediante delle funzioniche consentono dall’esterno il movimento attraverso il contenitore, oppuremediante degli iteratori.

L’esigenza di attraversare un contenitore è così sentita che, nei vari lin-guaggi di programmazione, i contenitori sono intrinsecamente iterabili e siconformano alla gerarchia di derivazione fra classi descritta nella figura 10.3.

ContenitoreIterabile

Contenitore Iterabile

IsA IsA

@@

@@@I

��

Figura 10.3: Struttura gerarchica delle classi dei contenitori iterabili.



Un contenitore iterabile consente l’implementazione di interessanti algo-ritmi di elaborazione, indipendentemente dalla struttura dati fisica usata permemorizzare gli elementi:

• contare gli elementi

• ricercare se è presente un dato elemento

• determinare l’elemento minimo

Un iterabile a è, per definizione, un oggetto in grado di fornire, mediantela funzione iter(a), un iteratore k il quale consente di attraversare l’iterabile,che l’ha generato ed al quale è associato, richiamando la funzione next(k) chefornisce, ad ogni chiamata, il successivo elemento dell’iterabile.

L’attraversamento di un contenitore iterabile viene solitamente svolto me-diante un ciclo come descritto nell’algoritmo 43.

Algoritmo 43 - Elaborazione di un iterabile a mediante un iteratore esplicito1: k ← iter(a)2: loop3: x← next(k)4: elabora(x)5: end loop

In alternativa all’algoritmo 43, l’attraversamento di un iterabile può essereeseguito senza l’utilizzo diretto di un iteratore, ma avvalendosi di un appositociclo for specifico per gli iterabili, come descritto nell’algoritmo 44.

Algoritmo 44 - Elaborazione di un iterabile a mediante un iteratore implicito1: for x in a do2: elabora(x)3: end for


10.2. ATTRAVERSAMENTO DI CONTENITORI 125

Esempio 68. Nel linguaggio Python le sequenze sono dei contenitori iterabili.Nella seguente porzione di codice Python è descritto l’accesso ad una sequenzamediante un iteratore esplicito e mediante un iteratore implicito.

# creazione della sequenzaa = [10,20,30,40]

# accesso mediante iteratore esplicitok = iter(a)for i in range(len(a)):

x = next(k)print(x)

# accesso mediante iteratore implicitofor x in a:

print(x)

Nota. Un fastidioso problema di interferenza fra i metodi di un conteni-tore ed i metodi degli iteratori che lo attraversano insorge quando i metodimodificatori di un contenitore ed i metodi di accesso al contenitore mediantedegli iteratori vengono usati contemporaneamente e non operano in modo mu-tuamente esclusivo, nel senso che, ad esempio, mentre si sta attraversando uncontenitore con un iteratore, il contenitore viene modificato. A seguire sonodescritte delle possibili soluzioni:

• creare una copia del contenitore nel momento in cui viene creato l’i-teratore e, per tutta la sua vita, l’iteratore fa riferimento a questacopia

• il contenitore viene reso non modificabile (read-only) quando ci sonodegli iteratori attivi su di lui

• tutti gli iteratori attivi su un contenitore vengono invalidati nel momentoin cui il contenitore viene modificato



10.3 CONTENITORI DI CONTENITORII contenitori possono essere classificati come segue:

• contenitori semplici o piatti: gli elementi contenuti nel contenitore sonooggetti elementari atomici.

'&

$%

s s s s s ss s s s

Figura 10.4: Contenitore semplice o piatto.

• contenitori composti o strutturati: gli elementi contenuti nel contenitorepossono essere a loro volta dei contenitori; questa possibilità consentel’aggregazione di elementi secondo schemi gerarchici.

'

&

$

%#" !

'

&

$

%��s s s

s s s ss s

Figura 10.5: Contenitore composto o strutturato.

Un contenitore può contenere oggetti generici; in particolare un contenito-re può contenere altri contenitori come suoi elementi. Quando si elabora uncontenitore considerando i suoi elementi "di primo livello" si parla di elabora-zione superficiale; quando l’elaborazione viene trasmessa ricorsivamente suglielementi che sono a loro volta dei contenitori si parla di elaborazione in pro-fondità. Ad esempio, con riferimento all’esempio riportato nella figura 10.6,il "conteggio superficiale degli elementi" fornisce il valore 5; il "conteggio inprofondità" fornisce il valore 9; la "ricerca superficiale del valore 6" fornisceil valore false, mentre la "ricerca in profondità del valore 6" fornisce il valoretrue.


10.3. CONTENITORI DI CONTENITORI 127'

&

$

%

'&$%

'

&

$

%��9

26

3 17

8

6 4

Figura 10.6: Contenitore di contenitori.

Molte operazioni di elaborazione di un contenitore possono essere svol-te utilizzando il meccanismo di attraversamento predisposto dal contenitorestesso; per elaborare un contenitore di contenitori è necessario differenziare l’e-laborazione superficiale dall’elaborazione in profondità. Per questo si ricorread un predicato per decidere se un elemento x è un atomo:

isatom(x)

ed a un predicato per decidere se un contenitore è vuoto:

isempty(x)

L’elaborazione può basarsi sullo schema descritto nell’algoritmo 45.

Algoritmo 45 - Elaborazione di un elemento x di un contenitore iterabile1: if isatom(x) then2: elaborazione dell’elemento x3: else4: elaborazione ricorsiva del contenitore x5: end if

Innestando l’algoritmo 45 al posto della linea 2 nell’algoritmo 44 si ottieneun algoritmo per elaborare in profondità un generico contenitore iterabile.



Esempio 69. Nella porzione di codice Python che segue viene calcolato ilnumero di atomi di una struttura composta.

# controllo di atomicita’def isatom(a):

return not isinstance(a,(list,tuple))

# controllo di struttura vuotadef isempty(a):

return a == [] or a == ()

# numero di atomi di una struttura compostadef atomi(a):

n = 0for x in a:

if isatom(x):n += 1

elif not isempty(a):n += atomi(x)

return n

#---- main ----#numero di elementi di una struttura compostaa = [3,[[4,[]],[5]],[1,2,3],8]print(’n. atomi di’,a,’=’,atomi(a))

10.4 TIPOLOGIE DI CONTENITORICome tutte le strutture astratte, i contenitori non rendono visibile all’esternola loro struttura organizzativa interna; essi risultano manipolabili solo attra-verso delle operazioni che agiscono secondo specifici criteri e vincoli che carat-terizzano le diverse tipologie di questi contenitori. In base a questi criteri,i contenitori possono essere classificati in sottocategorie che si diversificanofra loro per le specifiche operazioni di inserimento, accesso, modifica, elimi-nazione, estrazione ed interrogazione sugli elementi. Il comportamento ed ilrisultato di questi metodi dipende dai seguenti parametri:

• caratteristiche del contenitore al quale viene applicata l’operazione

• ordine temporale con cui gli elementi vengono inseriti

• valore dell’elemento che si tenta di inserire/modificare/eliminare

• valore degli elementi presenti nel contenitore


10.4. TIPOLOGIE DI CONTENITORI 129

• politica di gestione dei duplicati

• politica di gestione delle modalità di accesso agli elementi del contenitore(secondo il pattern iterabile-iteratore oppure mediante metodi specifici)

Imponendo alcuni vincoli alle operazioni su un contenitore si possono averele seguenti importanti tipologie di contenitori, come descritto nei sottopara-grafi che seguono.

10.4.1 SEQUENZE

Le sequenze costituiscono una delle forme più utilizzate di contenitori. Sonocaratterizzate da una struttura lineare di elementi disposti in fila; le operazionidi inserimento, accesso e modifica vengono precisate in funzione di un indicedi posizione.

'

&

$

%?

6

(1, β) 4 η

α β γ δ η κ

0 1 2 3 4 5

Figura 10.7: Una sequenza composta da 6 elementi. Sono evidenziate le ope-razioni di modifica dell’elemento presente ad una data posizione e l’operazionedi accesso all’elemento posto ad una data posizione.

Le seguenti operazioni caratterizzano una sequenza statica, ossia una se-quenza la cui dimensione viene fissata, in modo definitivo, al momento dellacreazione.

SeqE

: N → SeqE

// sequenza di lunghezza nlength : Seq

E→ N // lunghezza della sequenza

update : SeqE×N ×E → Seq

E// modifica di un elemento

element : SeqE×N → E // accesso ad un elemento

Una sequenza viene generalmente rappresentata mediante un array.



10.4.2 PILE

Le pile o stack sono dei contenitori nei quali l’inserimento e l’estrazione dielementi avviene con la politica Last-In-F irst-Out (LIFO); è accessibile ed èpossibile estrarre solo l’ultimo elemento inserito. Considerando uno stack co-me una struttura lineare di elementi, l’inserimento, l’accesso e la cancellazionedi elementi sono possibili solo su un’estremità.

'

&

$

%

in out

?

-

α

β

γ

Figura 10.8: Uno stack, ottenuto con l’inserimento sequenziale degli elementiα, β e γ. L’elemento γ è l’unico elemento accessibile.

Uno stack risulta caratterizzato dalle seguenti operazioni di base:

StackE

: ∅ → StackE

// stack vuotoisEmpty : Stack

E→ B // controllo di stack vuoto

push : StackE×E → Stack

E// inserimento elemento

pop : StackE

→ StackE

// eliminazione elementotop : Stack

E→ E // elemento di testa

Uno stack viene generalmente rappresentato mediante un array per me-morizzare gli elementi ed una variabile intera (stack pointer) che indica laposizione nell’array dell’ultimo elemento inserito.



10.4.3 CODE

Le code o queue sono dei contenitori nei quali l’inserimento e l’estrazione dielementi avviene con la politica F irst-In-F irst-Out (FIFO); è accessibile edè possibile estrarre solo il primo elemento inserito. Considerando una codacome una struttura lineare di elementi, l’inserimento avviene su un estremo el’accesso e la cancellazione sull’altro estremo.

'

&

$

%

in out

-

6

αβγδ

Figura 10.9: Una coda, ottenuta con l’inserimento sequenziale degli elementiα, β, γ e δ. L’elemento α è l’unico elemento accessibile.

Una coda risulta caratterizzata dalle seguenti operazioni di base:

QueueE

: ∅ → QueueE

// coda vuotaisEmpty : Queue

E→ B // controllo di coda vuota

enqueue : QueueE×E → Queue


dequeue : QueueE

→ QueueE

// eliminazione elementofront : Queue

E→ E // elemento in testa

Una coda viene solitamente rappresentata mediante un array circolare do-ve gli elementi della coda vengono inseriti in una porzione dell’array le cuiestremità sono individuate da due indici di posizione, considerando l’arraycircolare ottenuto saldando virtualmente fra loro le due estremità dell’array egestendo lo sforamento degli indici di posizione rientrando dall’altro estremo.



10.4.4 CODE A PRIORITÀ

Una coda a priorità o priority queue è un contenitore di elementi sui qualiè definito un criterio d’ordine. È possibile inserire gli elementi senza alcunvincolo ed è possibile accedere ed estrarre l’elemento minimo fra quelli presenti.

'

&

$

%

stuvw y{ } ~ ~

in out

?

6

Figura 10.10: Una coda a priorità.

Una coda a priorità risulta caratterizzata dalle seguenti operazioni di base:

PQueueE

: ∅ → PQueueE

// coda a priorità vuotaisEmpty : PQueue

E→ B // controllo di coda vuota

insert : PQueueE×E → PQueue


remove : PQueueE

→ PQueueE

// eliminazione minimoelement : PQueue

E→ E // elemento minimo

Per rendere efficienti le operazioni di inserimento e cancellazione, una codaa priorità viene rappresentata mediante una struttura ad albero (heap) aventela caratteristica di mantenere gli elementi ordinati, garantendo una comples-sità costante O(1) per l’operazione di accesso (all’elemento minimo) e, perle operazioni di inserimento e cancellazione, con complessità asintotica pari aO(logn), indicando con n il numero di elementi inseriti.



10.4.5 INSIEMI

Gli insiemi o set sono dei contenitori che ammettono l’inserimento di un ele-mento solo se se non già presente nell’insieme; la selezione ed estrazione di unelemento avviene in modo casuale.

'

&

$

%

in out

?

6

α βγ

δ ηκ

Figura 10.11: Un insieme composto da 6 elementi.

Un insieme risulta caratterizzato dalle seguenti operazioni di base:

SetE

: ∅ → SetE

// insieme vuotoisEmpty : Set

E→ B // controllo di insieme vuoto

size : SetE

→ N // cardinalità dell’insieme∪ : Set2

E→ Set

E// unione di due insiemi

∩ : Set2E

→ SetE

// intersezione di due insiemi− : Set2

E→ Set

E// differenza di due insiemi

exists : SetE×E → B // test di presenza di dato elemento

insert : SetE×E → Set


select : SetE

→ E // selezione elementoremove : Set

E×E → Set

E// eliminazione elemento

Un insieme può essere rappresentato mediante una sequenza. Per ren-dere efficiente l’operazione di ricerca, la sequenza che rappresenta l’insiemeviene generalmente mantenuta ordinata; questa soluzione comporta però unaggravio per l’operazione di inserimento degli elementi. Una soluzione dicompromesso consiste nell’utilizzare una rappresentazione ad albero.



10.5 IMPLEMENTAZIONE DI CONTENITORIUn contenitore può essere realizzato memorizzando gli elementi in una strut-tura dati fisica; tipicamente vengono usati array, catene e strutture con punta-tori. Alcuni linguaggi di programmazione predisposngono questi contenitoriin modo nativo oppure mediante librerie di funzioni o classi di oggetti 1.

Le varie classi di contenitori vengono realizzate mediante una classicatecnica implementativa che si svolge attraverso i seguenti passi:

1. definizione di un’interfaccia, definendo i prototipi delle operazioni 2

2. individuazione di una struttura dati adeguata per supportare in modoefficiente le operazioni specificate al punto 1.

3. codifica in un linguaggio di programmazione delle operazioni specificateal punto 1. adottando la struttura dati descritta al punto 2.

Esempio 70. A seguire è riportata l’implementazione in linguaggio Python deicontenitori stack, adottando una modalità orientata agli oggetti, usando unasequenza per memorizzare gli elementi.

class Stack:

# costruttore di uno stack vuotodef __init__(self):

self.a = []

# testa dello stackdef top(self):

if len(self.a)>0:return self.a[len(self.a)-1]

else:return None

# controllo di stack vuotodef isEmpty(self):

return len(self.a) == 0

# inserimento elementodef push(self,x):

self.a.append(x)

1Ad esempio la classe Vector o la classe ArrayList delle librerie Java.2Oppure usando un costrutto sintattico specifico del linguaggio; ad esempio interface

nel linguaggio Java.


10.5. IMPLEMENTAZIONE DI CONTENITORI 135

# eliminazione elemento di testadef pop(self):

if len(self.a)>0:self.a.pop()

return None

Esempio 71. La seguente funzione in linguaggio Python descrive una tipicaapplicazione degli stack. Viene controllato se una stringa di parentesi tonde,quadre e graffe è bilanciata; in questo esempio le parentesi non devono sod-disfare al tradizionale vincolo parentesi tonde dentro parentesi quadre dentroparentesi graffe; è sufficiente una coincidenza di tipologia di parentesi. Adesempio la stringa ([]){({})[[]{}]} è bilanciata mentre non lo è la stringa([]){(][)}.

# controllo di bilanciamento di parentesidef checkPar(str):

s = Stack() # stack vuotoop = "({[" # parentesi apertecp = ")}]" # parentesi chiusefor c in str: # per ciascun carattere della stringa

if c in op:s.push(c)

else:if s.isEmpty():

ris = Falseelse:

if op.index(s.top()) == cp.index(c):s.pop()

else:break

return s.isEmpty()



10.6 ESERCIZI1. Convertire un contenitore iterabile in stringa (adottando delle idonee

convenzioni).

2. Decidere se un contenitore iterabile è piatto.

3. Decidere se un contenitore iterabile è composto da elementi tutti distintifra loro.

4. Determinare il numero di elementi elementari (non contenitori) presen-ti in un contenitore iterabile, mediante un’elaborazione superficiale emediante un’elaborazione in profondità.

5. Determinare l’elemento minimo presente in un contenitore iterabile, me-diante un’elaborazione superficiale e mediante un’elaborazione in pro-fondità.

6. Decidere se in un contenitore iterabile è presente un dato elemento, me-diante un’elaborazione superficiale e mediante un’elaborazione in pro-fondità.

7. Determinare la frequenza con la quale è presente un dato elemento in uncontenitore iterabile, mediante un’elaborazione superficiale e medianteun’elaborazione in profondità.

8. Determinare il prodotto cartesiano di due iterabili (A ×B oppure A2).

9. Discutere cosa possa significare il concetto di uguaglianza fra due conte-nitori. Stabilire se due contenitori sono uguali.

10. Determinare il massimo livello di annidamento di un contenitore di con-tenitori; si assuma la convenzione che un contenitore piatto abbia livellodi annidamento pari a 0.

11. Descrivere la situazione finale che si ottiene, a partire da una situazio-ne iniziale di stack vuoto, eseguendo la seguente sequenza di operazioni:push(A), push(B), pop, push(C), push(D), pop, push(E). Con riferi-mento alla situazione finale, indicare quali sono gli elementi direttamenteaccessibili.

12. Descrivere la situazione finale che si ottiene, a partire da una situazioneiniziale di coda vuota, eseguendo la seguente sequenza di operazioni:enqueue(A), enqueue(B), dequeue, enqueue(C), enqueue(D), dequeue,


10.6. ESERCIZI 137

enqueue(E). Con riferimento alla situazione finale, indicare quali sonogli elementi direttamente accessibili.

13. Descrivere la situazione finale che si ottiene, a partire da una situazio-ne iniziale di coda a priorità vuota, eseguendo la seguente sequenza dioperazioni: insert(5), insert(7), remove, insert(4), insert(2), remove,insert(6). Con riferimento alla situazione finale, indicare quali sono glielementi direttamente accessibili.

14. Valutare un’espressione aritmetica espressa in notazione RPN, usandouno stack.

15. Ordinare una sequenza, usando una coda a priorità.

16. Una sequenza dinamica è una sequenza nella quale sono possibili leoperazioni di inserimento, accodamento ed eliminazione di elementi.Specificare le operazioni che caratterizzano una sequenza dinamica.

17. Una doppia coda o deque (double ended queue) è una coda in cui si posso-no inserire, eliminare ed accedere agli elementi da entrambe le estremità.Specificare le operazioni che caratterizzano una doppia coda.

18. Un bucket-array è un contenitore nel quale si possono inserire più ele-menti (anche multipli) in una stessa posizione individuata da un indicenumerico naturale, a partire dall’indice 0. Specificare le operazioni checaratterizzano un bucket-array. Costruire un bucket-array di dimensio-ne N contenente alla posizione k i divisori (con molteplicità) del numerok. Ad esempio, se N = 10, il corrispondente bucket-array è il seguente:

[ [], [1], [2], [3], [2,2], [5], [2,3], [7], [2,2,2], [3,3], [2,5] ]

19. Un sacco (detto anche bag) è un contenitore piatto di elementi. In unsacco gli elementi possono essere presenti con una molteplicità; ad esem-pio b a c b b c è un sacco che contiene 6 elementi, dove l’elemento b èpresente con una molteplicità 3. Specificare le operazioni che caratteriz-zano un sacco. Descrivere una struttura dati adeguata a rappresentareun sacco.


Capitolo 11

Alberi

Ogni genere posto ad un nodo alto dell’al-bero comprende le specie che ne dipendo-no, ogni specie subordinata a un genere èun genere per la specie che le è subordina-ta, sino all’estremità inferiore dell’albero,dove sono collocate le specie specialissime osostanze seconde, come ad esempio uomo.U. Eco, Dall’albero al labirinto

Gli alberi costituiscono una tipologia di contenitori particolarmente impor-tante, per il loro largo uso che ne viene fatto in informatica, per la ricchezza eprofondità dei problemi che permettono di descrivere e trattare e per l’eleganzadelle soluzioni che suggeriscono.

139

140 CAPITOLO 11. ALBERI

11.1 ALBERIDEFINIZIONE 13. Un albero (radicato) è un insieme vuoto oppure un in-sieme non vuoto di elementi detti nodi in cui esiste un nodo speciale dettoradice e gli altri nodi sono ripartiti in una sequenza ordinata di n ≥ 0 sottoin-siemi T1, . . . , Tn, detti sottoalberi o figli della radice, ciascuno dei quali è unalbero. Una sequenza di alberi viene detta foresta. Si dicono foglie di unalbero gli elementi dell’albero che non hanno sottoalberi. Diconsi discendentidi un nodo tutti gli elementi che appartengono ai sottoalberi del nodo stes-so. Un nodo dicesi padre dei nodi (figli) che costituiscono la radice dei suoisottoalberi. Tali nomenclature derivate per analogia con i gradi di parentelapossono essere estese. Ad esempio, due nodi figli di uno stesso padre vengonodetti fratelli. Dicesi cammino da un nodo p ad un nodo discendente q unasuccessione di nodi (n1, . . . , nk) tali che n1 = p, nk = q, ni è padre di ni+1,per ogni i = 1, k − 1. Un arco è il cammino che unisce due nodi adiacenti(padre-figlio). La lunghezza di un cammino (n1, . . . , nk) è rappresentata dalnumero di archi che uniscono il primo nodo all’ultimo nodo, ossia k − 1. Laprofondità di un nodo è uguale alla lunghezza del cammino dalla radice al no-do stesso. L’altezza di un albero è pari alla massima propondità dei suoi nodifoglia. Un livello di un albero è costituito dai nodi aventi la stessa profondità.Il numero massimo dei figli di uno stesso nodo viene detto grado (dell’albero).Un albero di grado k dicesi completo se ogni nodo, esclusi i nodi foglia ed alpiù i nodi padri delle foglie, ha esattamente k figli.

Il termine albero è mutuato direttamente dalla botanica, anche se usual-mente, per questioni di praticità grafica, si usa rappresentare gli alberi con laradice in alto. La figura 11.1 illustra un esempio di albero.

lalb lc ld

��

��

HHHHH

HH

le lf lg lh�

��

@@@

��

@@@

li ll lm ln

JJJ

Figura 11.1: Albero di grado 3, altezza 3, costituito da 12 nodi (di cui 5 sononodi interni e 7 sono foglie), strutturati in 4 livelli.


11.2. RAPPRESENTAZIONI DEGLI ALBERI 141

Osservazione. Gli alberi vengono solitamente definiti in modo ricorsi-vo, come descritto nella precedente definizione; ciò suggerisce in molti casi lastruttura dati (ricorsiva) per la loro rappresentazione e la forma degli algoritmi(ricorsivi) che si adottano per trattare queste strutture.

11.2 RAPPRESENTAZIONI DEGLI ALBERIUn metodo per rappresentare un albero T , vuoto oppure costituito da una radi-ce r e dalla sequenza di sottoalberi [T1, . . . , Tn], consiste nella rappresentazionea struttura, ossia:

rap(T ) = { [ ] se T è vuoto[r, rap(T1), . . . , rap(Tn)] altrimenti

Graficamente un albero non vuoto composto dalla radice r e dalla sequen-za di sottoalberi [T1, . . . , Tn] può essere rappresentato come descritto nellafigura 11.2.

jr��

BBBBBBB

��

BBBBBBB

��

BBBBBBB

T1 T2 Tn

��

��

��

��

PPPP

PPPP

PPPPP

. . .

Figura 11.2: Rappresentazione ricorsiva di un albero composto dalla radice re dalla sequenza di sottoalberi [T1, . . . , Tn].

Esempio 72. L’albero descritto nella figura 11.1 viene rappresentato mediantela struttura

[a, [b, [e], [f, [i], [l], [m] ] ] , [c], [d, [g], [h, [n] ] ] ]



Una rappresentazione alternativa consiste nell’utilizzo dei diagrammi diVenn, come descritto nella figura 11.3.

'

&

$

%

a'

&

$

%

b

c

�

�

�

�

'

&

$

%

d��e'&

$%

f��

gh��i l m n

��

Figura 11.3: Rappresentazione di un albero mediante diagrammi di Venn.

Un’altra rappresentazione mediante parentesi adotta la sintassi del lin-guaggio Lisp, come descritto nella figura 11.4.

(a(b(e)(f(i)(l)(m)))(c)(d(g)(h(n))))

Figura 11.4: Rappresentazione di un albero mediante parentesi.

Un albero può essere descritto anche mediante una scrittura indentata deinodi, come illustrato nella figura 11.5. Questa notazione risulta utile quandosi voglia rappresentare un albero in modo testuale ed in modo che risultifacilmente decifrabile la relazione di gerarchia fra i nodi stessi.

abefilm

cdg

hn

Figura 11.5: Rappresentazione di un albero mediante indentazione.


11.3. METODI DI VISITA DEGLI ALBERI 143

La rappresentazione indentata suggerisce un’altra possibilità di rappresen-tazione: un albero viene rappresentato mediante una sequenza di coppie [x,n]dove x denota l’elemento ed n il grado di indentazione. Questa modalità dirappresentazione è descritta nella figura 11.6.

[ [a,0], [b,1], [e,2], [f,2], [i,3], [l,3], [m,3], [c,1], [d,1], [g,2], [h,2], [n,3] ]

Figura 11.6: Rappresentazione di un albero mediante sequenza di coppie.

11.3 METODI DI VISITA DEGLI ALBERIVisitare un albero significa attraversarlo e produrre una sequenza piatta de-gli elementi memorizzati nei nodi dell’albero. Si possono adottare diversestrategie di visita:

• visita in ordine anticipato:

1. visita la radice2. visita i sottoalberi in ordine anticipato

• visita in ordine differito:

1. visita i sottoalberi in ordine differito2. visita la radice

Esempio 73. Le visite in ordine anticipato e differito dell’albero descritto nellafigura 11.1 producono rispettivamente le seguenti sequenze:

[a, b, c, f, i, l,m, c, d, g, h, n]

[e, i, l,m, f, b, c, g, n, h, d, a]



11.4 ALBERI BINARI

DEFINIZIONE 14. Dicesi albero binario un un albero nel quale ogni nodoha al più due figli.

Un’equivalente definizione ricorsiva, più utile, è la seguente:

DEFINIZIONE 15. Dicesi albero binario un insieme vuoto oppure una terna[r, T

L, T

R] in cui T

Le T

Rsono alberi binari detti, rispettivamente, figlio sinistro

e figlio destro.

La figura 11.7 illustra un esempio di albero binario.

mamb mc

��

��

ZZZZZ

md me mf��

��

��

��

@@@@

mg mh mi

JJJJ

JJJJ

Figura 11.7: Rappresentazione di un albero binario composto da 9 nodistrutturati in 4 livelli.

11.5 OPERAZIONI SUGLI ALBERI BINARI

Denotando con BE l’insieme degli alberi binari composti da elementi di ti-po E, gli operatori sugli alberi binari possono essere descritti, in notazionefunzionale, dal seguente elenco:


11.6. VISITA DEGLI ALBERI BINARI 145

BE

: ∅ → BE

// costruttore (albero vuoto)B

E: E → B

E// costruttore (albero radice)

BE

: E ×B2E→ B

E// costruttore (albero con figli)

left : BE

→ BE

// selettore del figlio sinistroright : B

E→ B

E// selettore del figlio destro

root : BE

→ E // selettore della radiceisEmpty : B

E→ B // test se l’albero è vuoto

11.6 VISITA DEGLI ALBERI BINARIUn albero binario può essere visitato secondo le strategie di seguito descritte:

• visita in ordine preordine:

1. visita la radice2. visita il figlio sinistro in preordine3. visita il figlio destro in preordine

• visita in ordine inordine o in ordine simmetrico:

1. visita il figlio sinistro in inordine2. visita la radice3. visita il figlio destro in inordine

• visita in postordine:

1. visita il figlio sinistro in postordine2. visita il figlio destro in postordine3. visita la radice

Esempio 74. Visitando l’albero riportato nella figura 11.7 mediante una visitain preordine, inordine e postordine si ottengono, rispettivamente, le seguentisequenze:

[a, b, d, g, h, c, e, i, f]

[g, d, h, b, a, e, i, c, f]

[g, h, d, b, i, e, f, c, a]



11.7 RAPPRESENTAZIONI DI ALBERI BINARI

Gli alberi binari, essendo dei casi particolari di liste non lineari, possono essererappresentati derivando il metodo di rappresentazione delle liste non lineari.Poiché questa rappresentazione è poco efficiente, viene usualmente scelta unarappresentazione specifica (in tale modo si perde però, in un linguaggio orien-tato agli oggetti, la possibilità di derivare la classe degli alberi binari dallaclasse delle liste lineari).

Un albero binario vuoto può essere rappresentato graficamente da un sim-bolo convenzionale, ad esempio ○. Un albero binario non vuoto T = (r, T

L, T

R)

può essere rappresentato graficamente come descritto nella figura 11.8.

jr��

BBBBBBB

��

BBBBBBB

TL

TR

��

@@

@@

Figura 11.8: Rappresentazione ricorsiva di un albero binario.

Questo schema di rappresentazione può essere immediatamente ricondottoad una rappresentazione mediante una struttura ricorsiva:

[r, rap(TL), rap(T

R)]

chiudendo la ricorsione rappresentando l’albero vuoto con [ ].Esempio 75. L’albero binario riportato nella figura 11.7 viene rappresentatomediante la seguente struttura:

[a, [b, [d, [g, [ ], [ ] ], [h, [ ], [ ] ], [ ] ], [c, [e, [ ], [i, [ ], [ ] ] ], [f, [ ], [ ] ] ] ]

Un albero binario completo o quasi completo può essere efficientementerappresentato mediante una strutturazione sequenziale dei suoi elementi. Inaltri termini, un albero binario è rappresentabile mediante una sequenza. L’al-bero viene completato con dei nodi contenenti il valore nullo (indicato con ●);


11.8. ALBERI BINARI DI RICERCA 147

successivamente si memorizzano per livelli tutti i nodi dell’albero completocosì costruito. La rappresentazione sequenziale di un albero di altezza h ri-chiede una sequenza di al più 2h+1 − 1 elementi. Serve inoltre un particolarevalore, non appartenente al tipo di base E, per rappresentare l’elemento nullo,ossia non esistente.Esempio 76. La figura 11.9 descrive la rappresentazione sequenziale per livellidell’albero binario riportato nella figura 11.7.

a b c d ● e f g h ● ● ● i ● ●0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

Figura 11.9: Rappresentazione sequenziale dell’albero binario riportato nellafigura 11.7

Si ricava facilmente che, dato un elemento di posizione k nella sequenzaa che rappresenta l’albero, gli elementi che costituiscono la radice del figliosinistro, del figlio destro e del padre (se k > 0) sono individuati mediante leseguenti relazioni:

root(left(a[k])) = a[2k + 1]root(right(a[k])) = a[2k + 2]root(father(a[k])) = a[⌈(k − 1)/2⌉]

11.8 ALBERI BINARI DI RICERCAL’obiettivo degli alberi binari di ricerca è quello di permettere degli algorit-mi di ricerca con complessità logaritmica, non degradando al contempo lacomplessità dell’inserimento ordinato di nuovi elementi, mantenendo questaoperazione ad una complessità logaritmica (gli array e le liste concatenate nonpermettono di mantenere entrambe queste performances sia per la ricerca cheper l’inserimento).

DEFINIZIONE 16. Un albero binario di ricerca (ABR) è un albero binarioin cui ogni nodo è maggiore o uguale dei nodi del sottoalbero sinistro e minoreo uguale dei nodi del sottoalbero destro.

Per l’elaborazione di un ABR risulta più utile la seguente definizionericorsiva:



DEFINIZIONE 17. Un albero binario di ricerca (ABR) è un albero binariovuoto oppure è un albero binario [r, TL, TR] dove TL è un albero binario vuotooppure è un albero binario di ricerca avente la radice minore o uguale di r eTR è un albero vuoto oppure è un albero binario di ricerca avente la radicemaggiore o uguale di r.

l5l4 l8

��

��

ZZZZZ

l2 l6 l9��

��

��

@@@@

l1 l3 l7

JJJ

JJJ

Figura 11.10: Rappresentazione di un albero binario di ricerca.

Gli ABR vengono solitamente impiegati come struttura dati sulla qualeeseguire efficientemente delle ricerche. L’algoritmo 46 costituisce la tipicaforma della ricerca in un ABR.

Algoritmo 46 - ricercaABR(a, x) - Algoritmo di ricerca in un ABRInput: ABR a, elemento xOutput: TRUE se e solo se x è presente in a1: if isEmpty(a) then2: return FALSE3: else if root(a) = x then4: return TRUE5: else if root(a) < x then6: return ricercaABR(left(a), x)7: else8: return ricercaABR(right(a), x)9: end if

Se l’ABR a è perfettamente bilanciato, la complessità della ricerca èO(logn),dove n è il numero dei nodi; nel caso in cui l’ABR sia completamente sbilan-ciato, la complessità della ricerca è lineare, ossia pari a O(n).


11.9. ESERCIZI 149

11.9 ESERCIZI1. Ricostruire graficamente l’albero binario rappresentato dalla seguente

struttura:

[7, [4, [ ], [8, [3, [ ], [ ] ], [5, [ ], [ ] ] ] ], [9, [ ], [6, [ ], [ ] ] ] ]

2. Il seguente array descrive un albero binario rappresentato a livelli.

5 3 6 ● 2 7 8 ● ● 1 4 ● ● ● 9

Stabilire se si tratta di un albero binario di ricerca.

3. Il seguente array descrive un albero binario rappresentato a livelli.

6 3 4 ● 8 7 2 ● ● 5 1 ● ● 9 ●

Dire come si modifica l’array se vengono eliminate tutte le foglie.

4. Stabilire se un dato array costituisce una rappresentazione a livelli di unalbero binario.

5. Eliminare tutte le foglie da un albero binario rappresentato a livellimediante un array.

6. Una visita in preordine ed una in inordine di un albero binario produconorispettivamente le seguenti sequenze:

a b c d e f g

c b e d f a g

Ricostruire graficamente l’albero binario.

7. Determinare il numero di nodi di un albero binario.

8. Determinare il numero di foglie di un albero binario.

9. Determinare il numero di nodi interni di un albero binario.

10. Determinare la somma dei valori presenti in un albero binario di numeri.

11. Determinare il massimo valore presente in un albero binario.

12. Determinare il massimo valore delle foglie di un albero binario.



13. Determinare l’insieme dei valori delle foglie di un albero binario.

14. Decidere se un dato elemento è presente in un albero binario.

15. Determinare quante volte è presente un dato elemento in un alberobinario.

16. Determinare il numero di elementi distinti di un albero binario.

17. Determinare l’altezza di un albero binario.

18. Determinare la larghezza (massimo numero di nodi che si trovano su unostesso livello) in un albero binario.

19. Decidere se un albero binario è perfettamente bilanciato.

20. Determinare il valore minimo ed il valore massimo assumibile dall’altezzadi un albero binario costituito da n nodi.

21. Definire un coefficiente di bilanciamento di un albero binario che esprimail grado di bilanciamento dell’albero.

22. Un albero binario si dice completamente sbilanciato se ogni suo nodoha al più un figlio. Decidere se un albero binario è completamentesbilanciato.

23. Decidere se due alberi binari sono uguali.

24. Decidere se due dati alberi binari sono isomorfi (stessa forma), ossia sehanno la stessa struttura, indipendentemente dai valori dei loro nodi.

25. Decidere se un albero binario è incluso in un altro.

26. Descrivere una strategia per elaborare un albero binario senza ricorrerealla ricorsione.

27. Descrivere graficamente un ABR i cui nodi sono costituiti dai caratteridella parola ALGORITMO. Evidenziare graficamente i cammini di ricercadei caratteri T e Q. Rappresentare l’albero mediante un array.

28. Decidere se in un ABR è presente un dato elemento.

29. Studiare la complessità della ricerca in un ABR in funzione del nume-ro n dei nodi, dell’altezza h dell’albero e del grado di bilanciamento.Distinguere i casi ottimo, medio e pessimo.


11.9. ESERCIZI 151

30. Determinare quante volte in un ABR è presente un dato elemento.

31. Determinare l’elemento più grande presente in un ABR.

32. Determinare in un ABR il numero di elementi compresi fra due datiestremi.

33. Costruire un ABR a partire da una sequenza di elementi, prendendoil primo elemento della sequenza come radice dell’albero ed inserendonell’albero gli elementi dal secondo in poi senza spostare gli elementi giàinseriti.

34. Illustrare, con un esempio, la seguente proprietà: Una visita inordine(in ordine simmetrico) di un ABR produce una sequenza ordinata deinodi. Utilizzando questa proprietà, costruire un ABR a partire da unagenerica sequenza di nodi.

35. Ordinare una sequenza basandosi sulla proprietà che afferma che la visitapreordine di un ABR genera una sequenza ordinata.

36. Decidere se un dato albero binario è un ABR.

37. Un’espressione aritmetica composta da operatori binari infissi espressanella usuale notazione algebrica con parentesi, può essere rappresentatasotto forma di albero binario (detto albero sintattico) dove i nodi nonterminali contengono gli operatori e le foglie gli operandi. Descriveremediante un albero sintattico l’espressione (7 + (6 − 2)) ∗ 3. Valutareun’espressione rappresentata mediante un albero sintattico.

38. Determinare la distanza di due nodi di un albero binario definita comela lunghezza del minimo cammino che li congiunge.

39. Discutere la complessità della ricerca in un ABR, in funzione del numeron dei nodi e del grado di bilanciamento dell’albero.


Capitolo 12

Grafi

Il problema dei ponti di König-sberg.

Storicamente si fa risalire la teoria dei grafi al 1736 quando il grande ma-tematico svizzero Leonard Euler pubblicò un lavoro in cui veniva risolto ilfamoso problema dei ponti di Königsberg, schematizzato nella figura riportatain alto.

I grafi sono strutture che rivestono interesse per un’ampia gamma di campiapplicativi. Costituiscono una struttura matematica discreta che può esserestudiata dal punto di vista algebrico, indipendentemente dalle specifiche areeapplicative. La teoria dei grafi costituisce un’importante parte della combina-toria; i grafi inoltre sono utilizzati in aree come topologia, teoria degli automi,funzioni speciali, geometria dei poliedri, algebre di Lie.

153

154 CAPITOLO 12. GRAFI

12.1 GRAFI

Intuitivamente un grafo è una rete di nodi (rappresentati mediante dei punti) edi collegamenti fra di essi (rappresentati mediante delle linee di congiunzione).I grafi vengono utilizzati per descrivere modelli di sistemi e processi studiatinell’informatica (programmi, circuiti, reti di computer, mappe di siti), nell’in-gegneria (sistemi fluviali, reti stradali, trasporti), nella chimica, nella biologiamolecolare, nella ricerca operativa, nella organizzazione aziendale, nella lingui-stica strutturale, nella storia (alberi genealogici, filologia dei testi). I seguentiesempi danno un’idea di alcuni campi applicativi dei grafi:

- una rete stradale può essere rappresentata mediante un grafo in cui inodi sono le città e le linee rappresentano i collegamenti fra le città

- le reti logiche sono rappresentabili mediante dei grafi in cui i nodi sonole porte logiche and, or e not e le linee corrispondono ai collegamenti frale porte

- la struttura di un ipertesto è rappresentabile mediante un grafo in cui inodi sono le pagine e le linee sono i collegamenti fra le pagine

- le molecole possono essere rappresentate mediante dei grafi in cui i nodisono gli atomi che le compongono e le linee esprimono i legami fra gliatomi

I termini fondamentali della teoria dei grafi sono riportati nella seguentedefinizione.

DEFINIZIONE 18. Un grafo è costituito da un insieme di elementi dettivertici o nodi o punti e da un insieme di lati che collegano coppie di vertici1. Due vertici u, v connessi da un lato vengono detti estremi del lato; unlato risulta identificato dalla coppia formata dai suoi estremi (u, v). Un latoavente due estremi coincidenti si dice cappio. Un lato risulta individuatodalla coppia non ordinata dei vertici che collega e graficamente viene denotatomediante una linea che congiunge i due vertici; se la coppia viene considerataordinata si parla di arco e viene denotato graficamente mediante una lineaorientata dal primo al secondo vertice. Un grafo composto solo da archi èdetto grafo orientato (o diretto) o digrafo.

1Una coppia di vertici può essere unita da più lati o archi; in questi casi si parla di lati(archi) multipli o multilati (multiarchi) ed il grafo viene detto multigrafo. In caso contrariosi parla di grafo semplice. In questo capitolo si considerano solo grafi semplici.


12.1. GRAFI 155

L’ordine di un grafo è il numero dei suoi vertici mentre la sua grandezza èil numero dei suoi lati. Un grafo G di ordine n e grandezza m viene denotatocon G(n,m). Un grafo completo di ordine n, denotato con Kn è un grafo nonorientato con n vertici in cui ogni coppia di vertici è connesso da un lato.

t t t

t t t t

t

��

��

@@

@@

@@H

HHH

HHH

HHHH

Figura 12.1: Grafo composto da 8 vertici e 12 lati.

Figura 12.2: Alcuni grafi della famiglia Kn.



12.2 OPERAZIONI SUI GRAFIPer individuare e definire le operazioni sui grafi risulta utile riferirsi allaseguente definizione formale.DEFINIZIONE 19. Un grafo è una coppia G = (V,E) dove

- V è un insieme di elementi detti vertici

- E è un insieme di elementi detti lati costituiti da coppie di elementi diV , ossia E ⊆ V × V

Il grafo G = (∅,∅), privo di vertici e di lati, è detto grafo nullo.Le operazioni fondamentali che si possono eseguire su un grafo sono sinte-

ticamente descritte nel seguente elenco:

• creare un grafo vuoto

• aggiungere un vertice u

• aggiungere un lato a congiungente due vertici u e v

• eliminare un dato vertice u (ed i lati ad esso collegati)

• eliminare il lato congiungente due dati vertici u e v

• ottenere la lista dei lati uscenti da un dato vertice u

• ottenere la lista dei lati congiungenti un dato vertice u

12.3 CAMMINI E PERCORSIUn cammino da un vertice u ad un vertice v è una successione di vertici di-stinti (v1, . . . , vn) tali che v1 = u, vn = v ed inoltre per ogni i = 1, . . . , n − 1,(vi, vi+1) è un lato del grafo. Se v1 = vn il cammino viene detto circuito ociclo. Il numero dei lati del cammino è detto lunghezza del cammino. Se siammette che i vertici possano essere ripetuti il cammino viene detto percorso.Se il cammino passa per tutti i lati una sola volta viene detto euleriano. Ungrafo contenente almeno un cammino euleriano viene detto grafo euleriano.Un circuito è detto hamiltoniano se passa una sola volta per tutti i vertici delgrafo (escluso il primo). Un grafo contenente almeno un circuito hamiltonianoviene detto grafo hamiltoniano. Un grafo si dice connesso se esiste un cam-mino congiungente ogni coppia dei suoi vertici. Nel caso di grafi orientati uncammino viene detto catena e risulta composta da una successione di verticitali che due vertici contigui siano connessi da un arco.


12.4. TIPOLOGIE DI GRAFI 157

TEOREMA 1. Un grafo G connesso è euleriano se e solo se ogni vertice diG è pari.

Il risultato espresso dal teorema precedente fornisce la soluzione (in ne-gativo) al famoso problema dei ponti di Königsberg in quanto, nel grafo cherappresenta il problema, esistono vertici di grado dispari (tutti i vertici hannogrado dispari).

12.4 TIPOLOGIE DI GRAFIIn un grafo si possono memorizzare informazioni in diversi modi:

• orientando il lato, ottenendo un grafo orientato

• memorizzando delle informazioni nei nodi; tali informazioni vengonodette label o etichette ed il grafo che si ottiene viene detto grafo labellato

• memorizzando delle informazioni nei lati; tale informazioni vengono det-te pesi e il grafo che si ottiene viene detto grafo pesato

La figura 12.3 descrive un grafo orientato, pesato e labellato.

a b c

d e f g

h

-

6

@@@

@@I 6

��

-

6

�

�

HHHHHH

HHHHj

��

��

�

α β

γ δ ε η κ

λ µ ν

φ π

Figura 12.3: Grafo orientato, pesato e labellato.



12.5 RAPPRRESENTAZIONI DEI GRAFIUn grafo viene rappresentato mediante delle strutture dati elementari. Ven-gono abitualmente utilizzate le strutture predisposte dagli usuali linguaggi diprogrammazione: array, liste, matrici. La particolare scelta dipende dal-la tipologia del grafo e dalle operazioni che si intendono realizzare e, quin-di, dal particolare problema da risolvere. A seguire sono descritte alcunerappresentazioni dei grafi:

• rappresentazione mediante insiemi:basandosi direttamente sulla definizione 19, un grafo può essere rappre-sentato mediante l’insieme dei vertici e dei lati o degli archi.Ad esempio il grafo orientato e labellato

a b c

d e f

-

6

@@@

@@I 6

��

-

�

�

viene rappresentato mediante la seguente coppia di insiemi:

({a, b, c, d, e, f},{(a, b), (a, d), (b, d), (b, e), (b, f), (c, b), (d, e), (f, e)})

• rappresentazione mediante matrice di adiacenza:un grafo di n nodi può essere rappresentato mediante una matrice bina-ria, identificando ciascun nodo mediante un valore naturale progressivo,1,2,3, . . . , n; la matrice risulta composta dai valori 0 ed 1 per indicare,rispettivamente, la non presenza e la presenza dei collegamenti fra i varinodi.Ad esempio il grafo

t t t

t t t

��

@@

@@@@

1 2 3

4 5 6

viene rappresentato mediante la matrice binaria


12.5. RAPPRRESENTAZIONI DEI GRAFI 159

0 1 0 1 0 01 0 1 1 1 10 1 0 0 0 01 1 0 0 1 00 1 0 1 0 10 1 0 0 1 0

La rappresentazione di un grafo mediante una matrice di adiacenza èutilizzabile nel caso di grafi orientati e non orientati; in quest’ultimocaso la matrice risulta simmetrica. Una matrice di adiacenza è utiliz-zabile anche nel caso di grafi pesati nel quale caso al posto dell’1 vienemesso il valore del peso dell’arco corrispondente. Spesso, nella matricedi adiacenza vengono indicati solo i valori non nulli e vengano lasciatinon definiti i valori corrispondenti allo 0. Nel caso di un grafo labellato,alla matrice binaria bisogna aggiungere un array dove sono registrati leinformazioni dei vertici.

• rappresentazione mediante lista di adiacenza:la rappresentazione mediante una lista di adiacenza si basa sull’idea dirappresentare ciascun nodo con ad esso associata una lista i cui elementirappresentano gli archi uscenti dal nodo stesso; l’elemento corrispondentead un generico nodo u ha la struttura

(u, insieme dei lati uscenti da u)

Ad esempio il grafo orientato, labellato e pesato

a b c

d e f

-

6

@@@

@@I 6

��

-

�

�

α β

γ δ ε ηη

λ µ

viene rappresentato mediante la struttura composta

{(a,{(b,α), (d, γ)}), (b,{(d, δ), (e, ε), (f, η)}), (c,{(b, β)}),

(d,{(e, λ)}), (f,{(e, µ)})}



12.6 PROBLEMI SUI GRAFI

Esistono molti problemi, della natura più svariata, che possono essere ricon-dotti, affrontati ed eventualmente risolti all’interno della teoria dei grafi. Aseguire sono descritti alcuni di questi problemi.

12.6.1 Problema del cammino minimo

Dato un grafo orientato e pesato determinare un cammino di peso minimoda un nodo di partenza ad un nodo di arrivo, ossia un cammino per il qualeè minima la somma dei pesi degli archi che lo compongono. Si tratta di untipico problema dei trasporti. Si pensi ad esempio al problema di minimizzarei consumi per il trasporto da una città ad un’altra. L’algoritmo risolutivo piùnoto è attribuito a E. W. Dijkstra ed ha una complessità O(n2) dove n è ilnumero dei nodi.

12.6.2 Problema del collegamento minimo

Dato un grafo non orientato pesato che rappresenta una rete di collegamentifra i vertici, si vuole eliminare i collegamenti superflui e mantenere solo quelliindispensabili in modo da minimizzare il costo totale. Ciò corrisponde a volertrovare un albero di supporto minimo di un grafo non orientato connesso.Una della applicazioni più significative è quella del progetto di una rete dicomunicazioni in cui i vertici rappresentano delle città. Per questo problemasono noti algoritmi di complessità polinomiale.

12.6.3 Problema del commesso viaggiatore

Il problema del commesso viaggiatore fu considerato per la prima volta agliinizi degli anni ’30 del secolo scorso, anche se, sotto altra veste, comparveall’interno della teoria dei grafi già nel diciannovesimo secolo. Il problema puòessere enunciato come segue: Dato un grafo orientato e pesato, determinareun circuito hamiltoniano (ossia passante una sola volta per tutti i vertici delgrafo) di costo minimo. Nella sua formulazione più caratteristica il problemasi enuncia come segue: Un commesso viaggiatore deve visitare un dato numerodi città. Ogni città è collegata a tutte le altre da una strada di cui si conoscela lunghezza. Determinare il percorso più breve che passa per ogni città unasola volta e ritorna alla città di partenza.


12.6. PROBLEMI SUI GRAFI 161

12.6.4 Problema dell’isomorfismo fra grafi

Dati due grafi G1 e G2 si dicono isomorfi (stessa forma) se sono sostanzialmentelo stesso grafo, cioè se è possibile trovare una corrispondenza biunivoca f frai nodi di G1 e G2 in modo tale che esiste un arco da u a v in G1 allora esisteun arco f(u) in G2 e viceversa. A tutt’oggi, non si conoscono algoritmi nonesponenziali rispetto al numero dei nodi; nel caso peggiore si è infatti semprecostretti a provare n! permutazioni possibili dei nodi di uno dei due grafi.

12.6.5 Problema della planarità di un grafo

Un grafo non orientato dicesi planare se è possibile disegnarlo su un pianosenza sovrapporre i lati. Il problema della planarità si enuncia come segue:Dato un grafo non orientato e connesso, stabilire se è planare o meno, ed even-tualmente farlo vedere. Il problema ha interesse pratico nella progettazionedi reti stradali, circuiti stampati, ecc. in cui si vuole evitare di sovrapporre deicollegamenti. Già Eulero aveva trovato una semplice condizione necessaria:m ≤ 3n−6 dove n indica il numero dei nodi ed m il numero dei lati. Nel 1974 èstato scoperto un algoritmo lineare rispetto ad n che risolve questo problema.



12.7 ESERCIZI1. Definire cos’è un grafo pesato, non orientato e labellato. Fare un esempio

di un tale grafo, contenente 5 vertici e 7 lati. Descrivere una strutturadati adeguata a rappresentare il grafo.

2. Descrivere una situazione in cui risulta idoneo ricorrere ad un grafo pe-sato, non orientato e non labellato. Fare un esempio di un tale grafo,composto da 5 vertici e 8 lati. Descrivere una struttura dati adeguata arappresentare il grafo.

3. Descrivere un grafo non orientato, non pesato e non labellato, compo-sto da 6 vertici e 8 lati. Descrivere una struttura dati adeguata arappresentare il grafo.

4. Descrivere un grafo orientato, non pesato e non labellato, avente 6 verticie 11 lati. Descrivere una struttura dati adeguata a rappresentare il grafo.

5. Descrivere un grafo orientato, pesato e non labellato, avente 6 vertici e 7archi. Descrivere una struttura dati adeguata a rappresentare il grafo.

6. Descrivere un grafo non orientato, pesato e labellato, avente 6 vertici e11 lati. Descrivere una struttura dati adeguata a rappresentare il grafo.

7. Disegnare e stabilire la tipologia del grafo rappresentato dalla seguentematrice di adiacenza:

1 0 1 10 0 1 01 0 0 10 1 0 1

Descrivere la matrice che si ottiene aggiungendo un altro vertice connessocon archi ai primi due vertici e scambiando il verso all’arco congiungentei vertici 2 e 3.

8. Descrivere un grafo orientato, non pesato e non labellato, avente 6 verticie 11 archi. Rappresentare il grafo mediante una matrice.

9. Disegnare e rappresentare mediante una matrice il grafo K5. Stabilire,motivando le affermazioni, se il grafo è planare.

10. Disegnare e stabilire la tipologia del grafo rappresentato dalla seguentematrice di adiacenza:


12.7. ESERCIZI 163

0 ∞ 7 ∞6 0 ∞ ∞∞ 5 2 34 ∞ ∞ 0

11. Determinare la grandezza del grafo Kn.

12. Dimostrare che il grafo K4 è planare mentre non lo è K5.

13. Stabilire se i seguenti grafi sono euleriani. In caso affermativo determi-narne un ciclo euleriano.

14. Descrivere sinteticamente, mediante un esempio, i seguenti problemi suigrafi:

(a) problema del commesso viaggiatore(b) problema del minimo albero di supporto(c) problema della planarità di un grafo(d) problema del cammino minimo.


Strutture ed Algoritmi -...

Documents

Transcript of Strutture ed Algoritmi -...