Riassunto teoria di FTP - Fondamenti teorici e programmazione

LE FASI DELLA PROGRAMMAZIONE

1. SPECIFICA: definizione del problema. Prevede la descrizione dello stato iniziale (dati iniziali, input) del problema e

dello stato finale atteso (risultato, output).

2. ALGORITMO: consiste nell’individuazione di un procedimento risolutivo che consenta di ottenere i risultati attesi.

Prevede tre passi: 1. individuare una soluzione; 2. dimostrare che la soluzione trovata sia corretta; 3. scegliere tra più

soluzioni corrette quella ottimale.

3. CODIFICA: consiste nel tradurre l’algoritmo in un linguaggio di programmazione noto all’esecutore. Se il linguaggio

di descrizione è uguale al linguaggio di programmazione allora la codifica è superflua. Si ottiene come risultato un

programma eseguibile al calcolatore.

Il linguaggio di programmazione deve essere costituito da:

 Programma: algoritmo;

 Dati in ingresso (input): informazioni iniziali;

 Dati ausiliari: informazioni utilizzate dall’algoritmo;

 Dati in uscita (output): informazioni finali.

4. ESECUZIONE: consiste nella messa a punto del programma. Due possibilità:

- Compilazione: il programma viene tradotto in un linguaggio macchina ed eseguito;

- Interpretazione: il programma viene eseguito da un emulatore che ne calcola il risultato.

JAVASCRIPT

E’ un linguaggio di script (/ing): linguaggio di programmazione che permette di scrivere “script” (programmi scritti

per un particolare ambiente).

- permette di esprimere tutte le funzioni calcolabili;

- deve essere eseguito all’interno di un browser;

- rende dinamiche le pagine web;

- è interpretato;

- non è tipato.

STRINGHE: “sequenze di caratteri” con cui si scrivono programmi.

VARIABILI: introducono nomi simbolici a cui sono associati dei valori. I valori possono cambiare durante l’esecuzione

della funzione. E’ costituita da: var identificatore = espressione;

- var: keyword (parola riservata);

- identificatore: nome della variabile (sequenza di lettere, cifre, caratteri speciali);

- espressione: valore associato;

- localizzazione di memoria (dove il valore è memorizzato);

- tipo: insieme dei valori che la variabile può assumente (non il Javascript: non è un linguaggio tipato).

Se una variabile viene dichiarata ma non inizializzata (es. var x;) il suo valore è undefined.

COSTANTI: nomi simbolici a cui è associato un valore che rimane invariato durante l’esecuzione. Si usano le lettere

maiuscole per distinguere le costanti dalle variabili.

PROGRAMMA: sequenza di istruzioni. Ogni istruzione viene eseguita successivamente alla precedente e fa

riferimento allo stato corrente del calcolatore. Ogni istruzione può modificare lo stato.

ASSEGNAMENTO

Sintassi: identificatore = espressione

Semantica: consiste nell’assegnare ad una variabile un valore che sarà effettivo a partire dallo stato successivo.

Comporta dunque una modifica dello stato. All’interno di un’espressione, la variabile è legata al valore che le è stato

associato in quel momento (nello stato corrente).

ESPRESSIONE: costrutto sintattico che restituisce un valore.

ISTRUZIONI CONDIZIONALI

1. ISTRUZIONE IF-ELSE

Sintassi: if (espressione)

istruzione1;

else istruzione2;

Dove:

- espressione: è un’espressione booleana;

- istruzione 1: rappresenta il ramo then (un’unica istruzione);

- istruzione 2: rappresenta il ramo else (un’unica istruzione).

Semantica:

1. Viene prima valutata l’espressione.

2. Se l’espressione è vera viene eseguita l’istruzione 1; se l’espressione è falsa viene eseguita l’istruzione 2.

2. ISTRUZIONE IF

Sintassi: if (espressione)

istruzione;

Semantica:

1. Viene prima valutata l’espressione.

2. Se l’espressione è vera viene eseguita l’istruzione, altrimenti non si fa nulla.

AMBIGUITA’ SINTATTICA: l’else fa riferimento all’if più vicino. Affinché si riferisca ad un if precedente, occorre

inserire gli if intermedi in un blocco {}.

3. ISTRUZIONE SWITCH

Sintassi: switch (espressione) {

case espressione-1: istruzione-1;

break;

…

case espressione-n: istruzione-n;

break;

default: istruzione-default;

}

Semantica:

1. Viene prima valutata l’espressione, ottenendo un valore X.

2. Vengono valutate in sequenza le espressioni dei case: se il valore ottenuto dall’espressione case è uguale ad X

allora vengono eseguite le sue istruzioni.

3. Se non esiste alcuna espressione il cui valore è uguale ad X, allora vengono eseguite le istruzioni di default.

Se manca il “break” ed è stata trovata un’espressione il cui valore è uguale ad X, verranno eseguite tutte le istruzioni

anche quelle delle espressioni a seguire. Perciò quando si omette il break diventa rilevante l’ordine dei case.

Se viene usato “return” al posto del break: termina l’esecuzione della funzione switch, non sono del costrutto case!

ISTRUZIONI ITERATIVE

Sono costrutti che permettono di ripetere determinate istruzioni più volte.

- Iterazione determinata: un numero fissato di volte. [FOR]

- Iterazione indeterminata: un numero non fissato di volte, finché la condizione rimarrà vera. [WHILE]

1. ISTRUZIONE WHILE

Sintassi: while (espressione)

istruzione;

Dove:

- espressione: è la guardia del ciclo;

- istruzione: è il corpo del ciclo (può essere un blocco {}).

Semantica:

1. Viene prima valutata l’espressione;

2. Se l’espressione è vera, si esegue l’istruzione e si torna ad eseguire il while;

3. Se l’espressione è falsa, si termina l’esecuzione del while. Dunque se l’espressione è falsa fin dall’inizio, il corpo del

while non verrà mai eseguito!

2. ISTRUZIONE DO-WHILE

Sintassi: do

istruzione;

while (espressione);

Semantica:

1. Il corpo viene prima dell’espressione, dunque l’istruzione si esegue sempre almeno una volta!

2. Se l’espressione è vera, si esegue una seconda volta l’istruzione e il ciclo ricomincia; altrimenti si termina.

3. ISTRUZIONE FOR

Sintassi: for (istruzione-1; espressione; istruzione-2)

istruzione-3;

Dove:

- istruzione 1: inizializza la variabile di controllo;

- espressione: verifica quando deve terminare il ciclo;

- istruzione 2: incrementa la variabile di controllo alla fine del corpo del ciclo (aggiornamento della variabile);

- istruzione 3: è il corpo del ciclo.

Semantica:

L’istruzione for precedente equivale a:

istruzione-1;

while (espressione) {

istruzione-3;

istruzione-2;

}

4. ISTRUZIONE FOR-IN (per gli array non associativi). E’ un’abbreviazione del for.

Sintassi: Equivale a:

for (ide in nomeArray) for (ide = 0; ide < nomeArray.length; i++)

istruzione; istruzione;

ARRAY

Permettono di definire dati strutturati.

Sono composti da elementi (omogenei nei linguaggi tipati; disomogenei in Javascript).

Ogni elemento si identifica all’interno dell’array grazie ad un numero d’ordine, detto “indice” dell’elemento.

Il numero di elementi dell’array è detto “lunghezza” (o dimensione) dell’array.

In Javascript, gli array sono dinamici: il numero degli elementi è variabile.

SINTASSI - DICHIARAZIONE DI VARIABILE ARRAY:

1. Dichiarazione di un array vuoto:

var nomeArray = [ ];

var nomeArray = new Array ( ); nei linguaggi ad oggetti.

2. Dichiarazione della variabile e inizializzazione degli elementi con il valore undefined.

var nomeArray = new Array (n); dove con “n” indico il numero finito degli elementi. Es. var vet = new Array (8); in

cui la variabile vet è dichiarata e inizializzata ad un array di 8 elementi undefined.

3. Dichiarazione di variabile e inizializzazione degli elementi:

var nomeArray = [n1, n2, n3, …, nk]; come ad esempio var vet = [2, 4, 5, -6, -3, 0];

var nomeArray = new Array (n1, n2, n3, …, nk); equivalente al precedente, es. var vet = new Array (2, 4, 5, -6, -3, 0);

In entrambi i casi viene dichiarata la variabile array e inizializzata con i valori interi (2, 4, 5, -6, -3, 0).

Ogni elemento dell’array è denotabile usando il nome dell’array (vettore) e l’indice ad esso associato. Gli array sono

indicizzati a partire da 0, quindi gli indici di un array di 6 elementi varieranno nell’intervallo, detto “range”, [0,5].

nomeArray [i]; indica l’elemento dell’array di indice “i”.

MODIFICA DI UN ARRAY:

Si utilizza il comando di assegnamento, ponendo a sinistra l’espressione che denota l’elemento di un array.

Es. var i = 2;

vet [i + 1] = readnum();

Assegna al 4° elemento (che ha indice 3) il valore letto dall’input.

L’espressione che compare all’interno delle parentesi [ ] può essere una qualunque espressioni purché calcoli un

intero >= a zero.

LO STATO CON GLI ARRAY:

Lo stato viene esteso perché è necessario avere due tipi di memoria:

- l’ambiente che rappresenta le variabili come insiemi di coppie;

- lo heap in cui sono memorizzati i dati strutturati (gli array e gli oggetti).

Le variabili che assumono come valore un array occupano nell’ambiente un “indirizzo di memoria”, detto reference

(indicato graficamente con una freccia o con ref ), che individua l’area dello heap in cui è memorizzato l’array.

i

Quest’aria di memoria sarà costituita da tante locuzioni di memoria quanti sono i dati strutturati.

L’operatore di uguaglianza opera sui reference: due variabili array sono uguali se condividono la stessa area di

memoria vet1 = vet2; in tal caso, modificandone uno si modifica anche l’altro. Gli operatori di confronto non sono

definiti su array, tuttavia confrontare due array non genera errore ma calcola sempre false.

PROCEDURE: sono funzioni che non calcolano un valore, ma producono modifiche allo stato.

La differenza tra procedure e funzioni:

- Le procedure sono un’astrazione delle istruzioni.

- Le funzioni sono un’astrazione degli operatori.

In generale, non contengono un’istruzione “return” (e se la contengono sarà del tipo “return ;” che non comporta il

calcolo di nessun valore ma solo la cessione del controllo al chiamante).

Semantica:

1. E’ analoga a quella della chiamata di funzione, ma una chiamata di procedura è un’istruzione.

2. Il passaggio dei parametri avviene per valore (come nel caso delle funzioni).

3. Il controllo viene restituito al chiamante al termine dell’esecuzione del corpo della procedura (o con return).

Javascript non distingue tra funzioni e procedure!

ARRAY DINAMICI

Il numero degli elementi dell’array può cambiare durante l’esecuzione del programma, dunque cambia anche la

lunghezza. Per questo motivo la dimensione (lunghezza) di un array è una proprietà predefinita dell’array.

Sintassi: nomeArray.length

MANIPOLAZIONE DELLE STRINGHE:

Le stringhe sono array di caratteri, dunque gli operatori degli array possono essere usati anche sulle stringhe.

Tuttavia le stringhe NON sono modificabili: ogni tentativo di modifica viene ignorato, ma non dà alcun errore!

La sintassi per selezionare un elemento di un array può essere usata anche con le stringhe, come anche il calcolo

della lunghezza, ad esempio:

var s = “ciao”;

a = s[0];

write (a);

write (s.length);

Calcola e stampa la stringa contenente il carattere “c”. E stampa “4” per la lunghezza.

ORDINAMENTO:

Serve per modificare l’array di partenza, non ne costruisce uno nuovo.

Ordinamento per selezione del minimo (SELECTION SORT)

function selSort (vet) { function minPos (vet, from, to) {

var i, temp, k; var min=from;

for (i=0; i

k=minPos (vet, i, vet.length-1); if (vet[from] < vet[min])

temp=vet[i]; min=from;

vet[i]=vet[k]; return min;

vet[k]=temp; }

} Calcola la posizione (e non il valore) dell’elemento dell’array

} che contiene il valore minimo relativamente alla porzione di

Ad ogni interazione mette in posizione i-esima array contenuta tra i valori dei due indici passati come

l’elemento minimo. Per scambiare due valori in parametri (i, vet.length-1).

un array occorre salvare il valore di uno dei - from: indice del primo elemento da esaminare. Si parte da

valori in una variabile temporale (temp). from+1 (from++) per confrontare il primo elemento minimo

- k: è il risultato della funzione minPos che indica con l’elemento successivo.

la posizione. - to: indice del primo elemento da non esaminare che si

In posizione zero va inserito l’elemento minimo. trova al di fuori dell’array, corrisponde infatti all’ultimo

elemento + 1.

Ordinamento a bolle (BUBBLE SORT)

Si fanno galleggiare gli elementi più piccoli verso l’inizio dell’array, scambiandoli con quelli adiacenti. Si inizia a fare il

confronto dal basso portando l’elemento più piccolo in posizione i.

Si usano due for annidati:

function bubbleSort (vet) { - il più esterno itera sulle i posizioni dell’array;

var temp, i, j; - il più interno porta l’elemento più piccolo dalla

for (i=0; i

for (j=vet.length-1; j>i; j--) - temp: memorizza il valore di un elemento dell’array;

if (vet[j] < vet[j-1]) { - i: indica la posizione dell’elemento in cui si porta

temp=vet[j]; l’elemento minimo;

vet[j]=vet[j-1]; - j: scorre le posizioni per stabilire qual è il minimo.

vet[j-1]=temp; Ad ogni passo (vet[j] < vet[j-1]) si confrontano i due

} elementi adiacenti: il minore si porta verso l’alto. Se

} non è minore, non si effettua lo scambio.

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

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.