Appunti esame Tecnologie informatiche per la comunicazione

ALGORITMI IN PSEUDOCODICE: CONDIZIONI

Scelta di una tra due possibili alternative. Es.

Se la somma dei punti dei 3 esercizi assegnati è maggiore o uguale a 18 allora studente sarà promosso
Altrimenti integrazione con orale richiesta
if (voto >= 18)
    Stampa("Studente promosso con voto: " + voto)
else
    Stampa("Integrazione orale richiesta")

CONDIZIONI NIDIFICATE

Due o più condizioni da valutare
Es. Se non piove:
if (not raining)
    Se temperatura=caldo
    if (temperature=="hot")
        allora vai in piscina
        go (swimming)
    altrimenti
        else vai a fare trekking
        go (trekking)
    altrimenti
        else film in TV
        watch (TV)

CONDIZIONI NIDIFICATE... MULTIPLE (PIÙ ALTERNATIVE)

Es. Se non piove
Problema: stampare tutti i numeri da 1 a 10
Soluzione:
if (not raining)
    if (temp <= 20)
        Stampa(1)
        Stampa(2)
        Stampa(3)
        gioca a basket ...
    altrimenti
        Stampa(10)
        in piscina

(trekking)film in TV

else if (temp>20 and temp<=24)play (basket)

else

ISTRUZIONI CHE SI RIPETONO go (swimming) else watch (TV)

STRUTTURE ITERATIVE: CICLI (LOOP)

Si dice ciclo (loop) una sequenza di istruzioni che deve essere ripetuta più volte consecutivamente.

Elementi di una struttura iterativa

Inizializzazione: stato iniziale che viene modificato all'interno del ciclo

Test: confronto dello stato corrente con la condizione di terminazione

Modifica: modifica dello stato ad ogni ripetizione

Le principali strutture iterative possono essere di tre tipi:

1. while

2. do/while

3. for

WHILE

Esegue una o più istruzioni fintantoché la condizione espressa è soddisfatta (è chiamato while-do)

La condizione viene valutata prima di eseguire il ciclo

Se la condizione è falsa non viene eseguito il ciclo

1. Viene valutata la condizione

2. Se è vera esegue il blocco (istruzioni e modifica stato)

3. Torna su a valutare nuovamente la condizione

4. Se è falsa

passa ad eseguire le istruzioni successive al blocco

Inizializzazione: stato iniziale che viene modificato all'interno del ciclo

Test: confronto dello stato corrente con la condizione di terminazione

Modifica: modifica dello stato ad ogni ripetizione

Es: stampa tutti i numeri da 1 a 10

var n=1;
while (n <= 10) {
    stampa(n);
    n=n+1;
}

Es. Vendita dei biglietti d'ingresso cinema XY. Posti in sala 250. Ogni biglietto 3D 10€. Calcolare incasso totale.

var n=250, incasso=0, tempo=100;
while (n<=250 & tempo>0) {
    StampaBiglietto(n);
    incasso=incasso+10;
    n=n+1;
    tempo= tempo-min;
}
Stampa(incasso);

DO / WHILE

Esegue una o più istruzioni fintantoché la condizione espressa è soddisfatta

Valuta la condizione dopo aver eseguito il blocco (chiamato repeat-until)

Anche se la condizione è inizialmente falsa, il blocco viene eseguito almeno una volta

Esempio: Stampa i numeri da 1 a 1000:

for (i=0; i<=1000; i++) {
    Stampa(i);
}

RICERCA DI UN VALORE ALL'INTERNO DI UN ELENCO

Dato un elenco di valori ordinato, trovare il valore che soddisfa la ricerca

Ricerca sequenziale:

Partire dal primo elemento della lista e confrontarlo con il termine ricercato, proseguire fintantoché si trova il risultato.

Es. Dato elenco ordinato di nomi trovare il nome Mevio

Dato un elenco di valori ordinato, trovare il valore che soddisfa la ricerca.

Ricerca binaria: divide-et-impera

1. Trovare elemento centrale della lista (metà)
2. L'elemento centrale è maggiore o minore dell'elemento cercato? In altre parole è nella prima parte o nella seconda parte?
3. Mi sposto nella prima o seconda parte e ripeto il ciclo

Es. Ricerca del nome John nella lista:

1. Trovo elemento centrale della lista
2. Confronto valore con elemento ricercato
3. Se elemento = elemento ricercato stop

Strutture iterative... ripetere una o più istruzioni al verificarsi di una condizione (while, do/while, for)

Strutture ricorsive... strutture che richiamano se stesse (ripetono un blocco di istruzioni) permettono di scrivere un algoritmo con pochi passi.

Algoritmo di ricerca binaria è un esempio di struttura ricorsiva

Le istruzioni dell'algoritmo sono eseguite un numero arbitrario di volte, ma ogni volta su un sottoinsieme di dati via, via più piccolo

Algoritmo di ricerca binaria (dettagliato): RicercaElemento(lista)

1. Se Lunghezza(lista)==0- Ricerca finita, nessun elemento trovato
2. Trovo elemento centrale della lista (suddivido lista in due parti)
3. Se elemento centrale == elemento cercato Stampa(elemento centrale) STOP;
4. Se elemento minore o maggiore al valore cercato:

Esegui RicercaElemento (listaA) nella

prima parte della sotto lista- Esegui RicercaElemento (listaB) nella seconda parte della sotto lista

Vantaggi:

• Sono eleganti
• Permettono di scrivere poche linee di codice per risolvere un problema anche molto complesso

Svantaggi:

• Prestazioni: le chiamate ricorsive ad un medesimo blocco di istruzioni (metodo o funzione) sono più lente
• Occupano molte risorse di sistema, poiché ogni chiamata lascia la precedente in sospeso e le risorse (memoria e processore) vengono nuovamente allocate, tante volte quante sono le chiamate complessive.

Strutture ricorsive vengono convertite in strutture iterative

EFFICIENZA DEGLI ALGORITMI

Quando trovo un algoritmo ha senso verificare se è efficiente. Analisi dell'efficienza di un algoritmo (complessità di un algoritmo) in termini di risorse minime necessarie (tempo di calcolo e memoria) per arrivare alla soluzione di un problema.

Si misura stimando i tempi di esecuzione di un algoritmo in tre scenari di utilizzo:

Caso peggiore- Caso medio- Caso migliore

Es. Stima del tempi di un algoritmo di ricerca sequenziale su una lista di 30.000 nomi

Ipotizzando che le operazioni di spostamento e confronto su ogni elemento della lista costino 10 millisecondi

RICERCA SEQUENZIALE su una lista di 30.000 nomi:

Dopo molteplici ricerche possiamo avere casi in cui l'elemento cercato è:

1. Nelle prime posizioni (casi migliori) pochi millisecondi
2. Collocato nella metà della lista posizioni (casi medi) In media 15.000 nomi controllati - 150 secondi (2 minuti e mezzo) per ogni ricerca
3. Collocato in fondo alla lista posizioni o non è ricompreso nella lista (casi peggiori). In media 30.000 nomi controllati - 300 secondi (5 minuti) per ogni ricerca!

In generale il caso medio di ricerca su una qualsiasi lista di "n" elementi richiede al più n/2 operazioni. Caso peggiore n operazioni

RICERCA BINARIA su una lista di 30.000 nomi:

1. 30.000/2 = 15.000

15.000/2 = 7.5003. 7.500/2 = 3.7504. 3.750/2 = 1.8755. ...

6. 15.1,8/2 = 0,9

Con al max 15 operazioni trovo l'elemento cercato (caso peggiore)

Se ogni operazione costa 10 millisecondi —> 150 millisec. 0,15 secondi!

In generale il caso peggiore di ricerca su una qualsiasi lista di "n" elementi richiede al più log(n)2 operazioni

EFFICENZA DEGLI ALGORITMI

Si esprime l'efficienza dell'algoritmo considerando il caso peggiore

Si esprime usando la notazione Θ (carattere maiuscolo greco theta) seguito dal valore

Es. Efficienza ricerca sequenziale Θ(n)

Efficienza ricerca binaria Θ( log2(n) )

Programming Languages (chapter 6)

LINGUAGGI DI PROGRAMMAZIONE

Linguaggio di programmazione Linguaggio formale definito da un insieme di regole per tradurre in modo non ambiguo le istruzioni di un algoritmo

I linguaggi di programmazione possono essere classificati in diversi modi:

1. Evoluzione storica: prima, seconda, terza, quarta,

La traduzione mi serve un ASSEMBLER. Es. MovR5 R6 4056

Vantaggi: rapidità nella scrittura, migliore leggibilità, efficienza (programmo molto veloci ed efficienti)…

Svantaggi: linguaggio che usa la stessa logica del linguaggio macchina (rinomina le istruzioni); dipendente dalla CPU (op-code) riscrivere il codice per ogni tipo di CPU!; obbliga ilà