Riassunto teoria di FTP - Fondamenti teorici e programmazione

RICERCA LOGARITMICA IN UN ARRAY ORDINATO

Con un array ordinato l’operazione di ricerca è più semplice perché termina nel momento in cui si trova l’elemento.

Questo procedimento di ricerca trova l’elemento mediano: se è minore la ricerca si concentrerà sugli elementi ad

esso successivi, altrimenti (se è maggiore) sugli elementi ad esso precedenti. Si continua così trovando il mediano del

mediano. Se l’elemento trovato corrisponde con quello ricercato, si termina l’esecuzione del programma.

function ricercaBin (vet, x) { Si tratta di un’iterazione indeterminata.

var i=0, j=vet.length, trovato=false; Inizialmente si esamina tutta la porzione dell’array (j=vet.length).

while (i < j && !trovato) { Viene calcolato l’elemento mediano ((i+j)/2).

med=Math.floor ((i+j)/2); - Se il numero non si trova nella sequenza si restituisce “false”.

if (vet[med]==x) - Se il numero è minore dell’elemento mediano si cerca nella

trovato=true; porzione di array precedente (j=med-1).

else if (vet[med] > x) - Se il numero è maggiore dell’elemento mediano si cerca nella

j=med-1; porzione di array successiva (i=med+1).

else i=med+1; - Se il numero si trova nella sequenza si restituisce “true”.

}

return trovato; Es. In un array var vet = [1, 2, 7, 11, 20, 27] si ricerca 8.

} 8 > 7 che è l’elemento mediano, dunque si cerca nella porzione di

array successiva. Ma 8 < 11 e questo vuol dire che, essendo un

array ordinato, non si troverà nelle posizioni successive.

L’esecuzione del programma termina restituendo “false”.

OPERAZIONI CHE SFRUTTANO LA DINAMICITA’ DEGLI ARRAY

1. Aggiungere uno o più elementi in fondo all’array usando l’operazione di assegnamento.

vet[vet.length]=readnum(); per aggiungere un elemento di indice vet.length con valore letto dall’input.

vet[vet.length+2]=readnum(); per aggiungere due elementi di indice vet.length e vet.length+1 con valore undefined

e un elemento con indice vet.length+2 e valore letto dall’input.

- Se una struttura dati (array) è statica, ovvero il numero dei suoi elementi non cambia, ha senso avviare una

procedura di ordinamento al momento dell’inizializzazione.

- Se una struttura dati è dinamica, bisogna mantenerla ordinata, inserendo i nuovi elementi in modo tale da

rispettare l’ordinamento. Per inserire un nuovo elemento al posto giusto bisogna: 1. scorrere gli elementi per

decidere la posizione che gli compete; 2. spostare verso destra di una posizione gli elementi maggiori per fare spazio.

2. PROCEDURA DI ORDINAMENTO PER INSERZIONE (insOrd)

function insOrd (vet, x) {

Bisogna prima definire una procedura che sposta var i=0, trovato=false;

tutti gli elementi di un array verso destra di una while (i<vet.length && !trovato) {

posizione a partire dalla posizione data. if (vet[i] < x)

i++;

SHIFT A DESTRA else trovato=true;

function shiftRD (vet, from) { }

var j; if (!trovato)

for (j=vet.length; j>from; j--) vet[vet.length]=x;

vet[j] = vet[j-1]; else {

} shiftRD (vet, i);

Bisogna fornire la posizione di partenza. vet[i]=x;

- vet: indica l’array in cui ci sono gli elementi. }

- from: indica la posizione di partenza. }

Bisogna aggiungere un nuovo elemento all’array - i: indica la posizione in cui va inserito il nuovo elemento,

che ha come valore il valore dell’elemento che si ovvero la posizione del primo elemento che risulta > del

trova in ultima posizione, che quindi non va perso! valore inserito. Non cambia nulla in caso di valori ripetuti.

3. ALTRE SOLUZIONI DI insOrd

Una seconda soluzione utilizza la funzione insertInPos.

function insertInPos (vet, p, x) { function insOrd (vet, x) {

var j; var i=0;

for (j=vet.length; j>p; j--) { while (i<vet.length && vet[i]<x) {

vet[j] = vet[j-1]; i++;

vet[j] = x; insertInPos (vet, i, x);

} }

} }

Questa funzione utilizza tre parametri: La condizione (i<vet.length && vet[i]<x) è corretta

- vet: l’array; per la regola di valutazione stretta dell’&&: se la

- p: posizione in cui inserire l’elemento; prima condizione i<vet.length è falsa, la seconda

- x: elemento da inserire. condizione vet[i]<x non viene valutata!

La funzione sposta a destra tutti gli elementi, La condizione è lecita perché l’and è lazy!

aumentando anche la dimensione dell’array per

poter memorizzare un elemento in più.

Quindi oltre a fare lo shift, fa anche l’inserzione.

Una terza soluzione utilizza il metodo SPLICE, un metodo predefinito su oggetti array.

Sintassi: nomeArray.splice (p, 0, x); function indOrd (vet, x) {

Non prende come parametro il vettore (array). var i=0;

E’ un metodo costituito da un numero di while (i<vet.length && vet[i]<x) {

parametri variabili: i++;

1° parametro: indica la posizione (indice) su cui si vet.splice (i, 0, x);

va ad effettuare la modifica dell’array; }

2° parametro: indica il numero di elementi che }

vanno eliminati a partire dalla posizione indicata;

3° parametro: possono essere uno o più parametri

che indicano i valori da inserire a partire dalla

posizione indicata dal 1° parametro.

ALTRI METODI PER ELIMINARE O AGGIUNGERE ELEMENTI IN UN ARRAY

La rimozione di un elemento da un array non è un’operazione primitiva e si può effettuare solo attraverso i metodi.

1. Metodo SPLICE: indicando la posizione del primo elemento da rimuovere e il numero di elementi da rimuovere.

Sintassi: nomeArray.splice (p, 1) in cui viene rimosso l’elemento in posizione p.

function elimina (vet, x) {

var i=0;

while (i<vet.length && vet[i]<x)

i++;

if (i != vet.length)

vet.splice (i, 1);

}

2. Metodo PUSH: inserisce come ultimo elemento dell’array il valore risultante dalla valutazione dell’espressione

(parametro attuale).

Sintassi: nomeArray.push (espressione);

3. Metodo POP: rimuove l’ultimo elemento dell’array e lo restituisce come risultato. E’ un metodo senza argomenti.

Sintassi: nomeArray.pop();

4. Equivalente al metodo push è l’operazione di assegnamento che sfrutta la lunghezza dell’array:

Sintassi: nomeArray [nomeArray.length] = x;

MERGE DI DUE ARRAY ORDINATI:

Restituisce un nuovo array, piuttosto che modificare uno già esistente.

Si scandiscono A e B finché entrambi contengono elementi e si seleziona l’elemento più piccolo tra i due esaminati

che viene dinamicamente aggiunto a C. Ci saranno tre indici, uno per ciascun array.

function merge (A, B) {

var C = new Array();

var i=0, j=0, k=0;

while (i < A.length && j < B.length) { I due array si confrontano, copiando in C l’elemento

if (A[i] < B[j]) { più piccolo tra l’elemento di A e quello di B.

C[k] = A[i];

i++;

}

else {

C[k] = B[j];

j++;

}

k++;

}

while (i < A.length) { Quando gli elementi di un array terminano vengono

C[k] = A[i]; copiati in C gli elementi rimasti dell’altro array.

i++;

k++;

}

while (j < B.length) {

C[k] = B[j];

j++;

k++;

}

return C;

}

ARRAY MULTIDIMENSIONALI

Sono array che hanno per elementi degli array.

Es. di matrice 3x4: var m = [ [1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12] ];

In questo caso, per la prima dimensione (righe) l’indice va da 0 a 2; per la seconda dimensione (colonne) l’indice va

da 0 a 3. La prima dimensione corrisponde al numero di array contenuti; la seconda corrisponde al numero di

elementi contenuti.

m.length = 3 perché l’array contiene tre elementi (ovvero tre array).

m[1].length = 4 perché calcola il numero di elementi contenuti nell’elemento 1 di m, ovvero [1, 2, 3, 4].

1. E’ possibile modificare gli elementi leggendoli 2. Array i cui elementi hanno una diversa dimensione

dall’input: var m = new Array(3);

var m = [new Array(3), new Array(3), new var i, j;

Array(3)]; for (i=0; i<m.length; i++)

var i, j; m[i] = new Array(readnum());

for (i=0; i<m.length; i++) for (j=0; j<m[i].length; j++)

for (j=0; j<m[i].length; j++) (m[i] [j]) = readnum();

(m[i] [j]) = readnum();

In cui m[i].length viene valutato ad ogni iterazione Attenzione: definire array a più dimensioni con un

cosicché il programma calcolerà correttamente numero di elementi diverso per ogni o qualche

anche se il numero di elementi di m[i] è diverso elemento può essere fonte di errori!

per ogni riga i.

MATRICI: sono tabelle con un numero M di righe e un numero N di colonne. La matrice ha dimensione M x N.

Se M=N la matrice è quadrata e gode di alcune proprietà: ha una diagonale principale e una secondaria.

Ad esempio, var m = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ]; è una matrice che ha dimensione 3x3.

La diagonale principale è formata dagli elementi: 1, 5, 9.

La diagonale secondaria è formata dagli elementi: 3, 5, 7.

CALCOLO DELLA MATRICE SOMMA

var A = [ [4, 8, 1, 4], [0, 10, 7, 8], [-5, 7, 13, 2] ];

var B = [ [0, 3, -6, 4], [1, 6, 0, 3], [-12, 15, 16, 4] ];

A + B = C dove C avrà le stesse dimensioni di A e B, dunque 3x4.

var C = [ [4, 11, -5, 8], [1, 16, 7, 11], [-17, 22, 29, 6] ];

E’ necessario inizializzare gli elementi di C come array vuoti per potervi accedere e aggiungere nuovi elementi.

function sommaMat (A, B) {

var C = new Array();

for (i=0; i<A.length; i++) {

C[i] = new Array();

for (j=0; i<A[i].length; j++)

C[i][j] = A[i][j] + B[i][j];

}

return C;

}

ARRAY ASSOCIATIVI

Gli indici sono stringhe. Per definirli è possibile:

1. dichiarare un array vuoto e poi aggiungere elementi;

2. dichiarare e inizializzare array associativi come segue:

var nomeArray = {

“s ”: espressione ,

1 1

“s ”: espressione ,

2 2

…

“s ”: espressione

k k

}

dove s è una sequenza di caratteri.

i

ISTRUZIONE FOR-IN (per gli array associativi):

Sintassi: for (ide in nomeArray)

istruzione;

Dove:

- nomeArray: nome della variabile il cui valore è un array associativo;

- ide: identificatore che assume i valori degli indici (stringhe) degli elementi dell’array associativo, nell’ordine in cui

sono stati elencati;

- istruzione: è il corpo del for-in.

QUANDO USARE ARRAY E QUANDO USARE ARRAY ASSOCIATIVI?

Non bisogna usare gli array per definire strutture dati i cui elementi non sono omogenei (anche se in Javascript è

consentito non essendo tipato), in questo caso è meglio usare gli array associativi.

Se si tratta di sequenze di elementi omogenei sui quali si invocano le stesse funzioni è preferibile usare gli array.

COSA SUCCEDE SE PASSO UN ARRAY COME PARAMETRO? E SE LO PASSO COME ELEMENTO?

- Se passo un array come elemento di un altro array allora si tratta di un array multidimensionale;

- Se passo un array come parametro in realtà passo il reference dell’array e ciò permetterà alla funzione di

modificare gli elementi dell’array.

GRAFI

Definizione: una coppia (V, E) dove V è un insieme finito ed E è una relazione (adiacenza) binaria su V.

V: insieme dei nodi o vertici.

E: insieme degli archi.

Gli archi sono coppie (v1, v2): l’arco esce da v1 (sorgente) ed entra in v2 (destinazione); v2 è adiacente a v1.

Nei grafi orientati possono esistere archi (v, v) da un vertice a se stesso, detti “cappi” (hanno lunghezza 1).

Nei grafi non orientati la relazione di adiacenza è simmetrica: non esiste il concetto di arco che entra o esce; se

esiste l’arco (v1, v2) = (v2, v1) si avrà che v2 è adiacente a v1 e viceversa. Non si sono cappi.

ALTRE DEFINIZIONI

- Dato un grafo G, un cammino di lunghezza k da un vertice u ad un vertice u è una sequenza di vertici (v , v , …, v )

1 0 1 k

tale che u=v e u =v e (v -1, v ) appartiene ad E per i=1, …, k.

0 1 k i i

- La lunghezza di un cammino è data dal numero di archi che lo compongono.

- Un vertice u è raggiungibile da un vertice u se esiste un cammino da u a u.

1 1

- Un cammino si dice “semplice” se tutti i vertici sono distinti.

- Grafo aciclico: non contiene cicli.

CICLI

In un grafo orientato, un cammino (v , v , …, v ) forma un ciclo se v =v .

0 1 k 0 k

In un grafo non orientato, un cammino (v , v , …, v ) forma un ciclo se v =v e k>=3.

0 1 k 0 k

CONNESSIONE

Un grafo non orientato può essere:

- connesso: se per ogni coppia di vertici (u, u1) esiste un cammino da u ad u1; ma anche se ha una sola componente

connessa. Le componenti connesse di un grafo sono le classi di equivalenza della relazione “raggiungibile da”.

1

- non connesso: se non esiste alcun cammino.

Un grafo orientato può avere delle componenti connesse e si dice:

- fortemente connesso: se per ogni coppia di vertici (u, u1) esiste un cammino da u ad u1; ma anche se ha una sola

componente connessa. Le componenti connesse di un grafo sono le classi di equivalenza della relazione

“mutuamente raggiungibile da”.

Grafo orientato con componenti connesse: Grafo orientato fortemente connesso:

ALBERI

Albero libero: è un grafo non orientato connesso aciclico.

Foresta: è un grafo non orientato sconnesso aciclico, di cui ogni componente è un albero.

Albero libero: Foresta con due componenti:

Se il grafo è ciclico allora non si tratta di un albero!

PROPRIETA’ DEGLI ALBERI LIBERI

- due vertici qualsiasi in V sono connessi da un unico cammino semplice.

- se un qualunque arco viene rimosso da E il grafo diventa sconnesso (l’albero diventa una foresta).

- se un qualunque arco viene aggiunto ad E il grafo diventa ciclico (non è più un albero).

- il numero degli archi è uguale al numero dei vertici meno 1, dunque |E|=|V|-1.

ALBERI RADICATI

Sono alberi liberi in cui un vertice viene designato come radice dell’albero.

I nodi sono i vertici dell’albero.

Dato un albero radicato con radice r, per un qualunque nodo u deve esistere un unico cammino da r a u (detto

“connessione”). Sia esso (r, v , v , …, v , u) si definiscono:

1 2 k

- i nodi r, v , v , …, vk sono detti antenati propri di u;

1 2

- u è un discendente proprio di r, v , v , …, v .

1 2 k

- ogni nodo è sia antenato che discendente di se stesso.

- il nodo v è detto padre di u.

k

- il nodo u è detto figlio di v .

k

- la radice dell’albero non ha antenati propri.

- i nodi figli di uno stesso nodo sono detti fratelli.

- i nodi che non hanno discendenti sono detti foglie o nodi esterni.

- i nodi che hanno discendenti sono detti nodi interni.

- il grado di un nodo è il numero dei figli del nodo.

- la lunghezza del cammino dalla radice ad un nodo u è detta profondità di u.

- l’altezza è la profondità del cammino più lungo dalla radice ad un nodo foglia.

ALBERI ORDINATI, ALBERI POSIZIONALI E ALBERI BINARI

Alberi ordinati: sono alberi in cui i figli di ciascun nodo sono ordinati: primo figlio, secondo figlio, ecc….

Alberi posizionali: sono alberi ordinati in cui ogni figlio ha una posizione specifica. Si dice “completo di dimensione k”

quando ogni nodo è un nodo foglia oppure ha k figli. I più usati sono gli alberi binari.

Alberi binari: sono alberi posizionali in cui ogni nodo ha al più due figli. Due definizioni:

- è un albero vuoto che non contiene alcun nodo;

- è una struttura che contiene un nodo radice, un sottoalbero sinistro (o figlio sinistro) e un sottoalbero destro (o

figlio destro).

ALBERO BINARIO DI RICERCA

Ad ogni nodo sono associate delle informazioni e l’operazione da compiere è la ricerca di un nodo con una data

etichetta. Le etichette appartengono ad un dominio su cui è definito un ordinamento.

Per ogni nodo valgono le seguenti condizioni:

- le etichette di tutti i nodi del sottoalbero sinistro precedono nell’ordinamento l’etichetta del nodo da inserire;

- le etichette di tutti i nodi del sottoalbero destro seguono nell’ordinamento l’etichetta del nodo da inserire.

La ricerca avviene confrontando l’etichetta (r) del nodo radice con l’etichetta (e) del nodo da inserire e riapplicando

ricorsivamente la funzione sul sottoalbero sinistro (r > e) o sul sottoalbero destro (r < e).

Le etichette devono essere tutte distinte.

- Se l’albero è bilanciato, i nodi esaminati saranno nel peggiore dei casi h = log n.

2

- Se l’albero non è bilanciato, i nodi aumentano e nel caso peggiore diventano n.