Algoritmi e Strutture Dati

Algoritmi e

Strutture Dati

Bruno Bertaccini

Gestione Informatica dei Dati

CdL in Statistica

Bruno Bertaccini (mail to: [email protected])

La programmabilità degli elaboratori



Gli elaboratori elettronici sono macchine programmabili:

l’utilizzatore deve fornire loro un’insieme di istruzioni che indichino le operazioni da compiere

ed i dati su cui operare.

Un insieme coerente di tali istruzioni si chiama PROGRAMMA

Tali istruzioni, una volta memorizzate nella memoria centrale, verranno prese in considerazione dalla CPU

che si occuperà dell’attivazione dei dispositivi necessari alla loro elaborazione

Introduzione



Un elaboratore elettronico, a differenza di quanto ci si potrebbe aspettare, è in grado di compiere

SOLO operazioni estremamente semplici (es: una radice quadrata, una funzione trigonometrica richiedono

programmi specifici)

Tuttavia un elaboratore è molto veloce e può eseguire un gran numero di operazioni

nell’unità di tempo(la velocità dipende anche dal fatto che le operazioni

sono appunto elementari)

Introduzione

OPERAZIONI ELEMENTARI



Classificazione delle istruzioni elementari in base alla diversità delle funzioni svolte dall’elaboratore e agli effetti che queste hanno sui dati.

Le operazioni elementari

1. Istruzioni aritmetiche e logiche

2. Istruzioni di trasferimento

3. Istruzioni di input-output

4. Istruzioni di controllo

5. Istruzioni ausiliarie



Istruzioni Aritmetiche e Logiche.servono ad eseguire operazioni aritmetiche ( + ,- , * , / ) elogiche (NOT, AND, OR)sui dati presenti nella memoria centrale

Istruzioni di Trasferimento.permettono lo spostamento dei dati all’interno della memoria centrale e tra questa e i registri presenti nella unità aritmetico logica (ALU) della CPU




Istruzioni Input-Output.consentono l’immissione e l’emissione dei dati nella e dalla memoria centrale; il dialogo avviene generalmente con in i dispositivi di I/O e e con le memorie ausiliarie.

Istruzioni di Controllo.guidano lo svolgimento dell’elaborazione controllando l’ordine di esecuzione delle istruzioni elementari;sono eseguite dalla unità di controllo (CU) della CPU.

Istruzioni Ausiliarie.sono deputate a riordinare alcuni dispositivi fisici dell’elaboratore e a controllarne lo stato.




Operazione Elementare (generalizzata)

codice operativo operando


indica il tipo di operazione da compiere

identifica i dati o i dispositivi che interessano l’operazione

L’insieme dei codici operativi e le regole che guidano il modo di esprimere gli operatori costituiscono un sistema di programmazione, un sistema completo

per gestire il funzionamento dell’elaboratore ed indirizzarlo alla risoluzione di un determinato

problema.



Il linguaggio macchina ed i linguaggi simboliciTale sistema è detto LINGUAGGIO MACCHINA perché è il SOLO comprensibile dall’unità di controllo dell’elaboratore.Il Linguaggio Macchina varia da elaboratore ad elaboratore ed è estremamente complicato da utilizzare ed interpretare da parte dell’utilizzatore.

Generalmente vengono utilizzati altri linguaggi di programmazione, i cosiddetti LINGUAGGI SIMBOLICI, basati su una modalità di espressione di operatori ed operandi più simili ai criteri usati dal linguaggio umano.



Il linguaggio macchina ed i linguaggi simboliciUn programma espresso per mezzo di un linguaggio simbolico non è direttamente utilizzabile dall’unità di controllo dell’elaboratore;

sarà prima necessario TRADURLO per mezzo di un apposito programma nell’unico linguaggio comprensibile alla CU: il linguaggio macchina appunto.


Gli ALGORITMI


Gli Algoritmi

Algoritmi: aspetti definitori

I problemi umani la cui soluzione è demandata ad un elaboratore sono notoriamente MOLTO COMPLESSI.(es: per x = 1.347)

Ma un elaboratore è in grado di svolgere SOLO OPERAZIONI ELEMENTARI e NON operazioni complesse.

Come è possibile allora utilizzare un elaboratore per risolvere un problema

complesso?

2( ) 2 3 5f x x x



Occorre SCOMPORRE il problema complesso in una serie di operazioni elementari in grado di poter essere compiute da un esecutore che non riesce ASSOLUTAMENTE a prendere in considerazione il problema nella sua interezza.

Tale procedimento è detto PROCESSO ALGORITMICO

ed il risultato di tale processo è dettoALGORITMO

Gli Algoritmi



L’ALGORITMO è una serie finita e completa di operazioni elementari ordinate alla soluzione di un problema, da effettuare meccanicamente, ossia attraverso una esecuzione precisa delle regole, senza implicare alcuna conoscenza del caso da trattare.

Le operazioni in cui viene scomposto il processo risolutivo del problema devono essere comprensibili ed eseguibili dall’entità cui l’algoritmo è destinato, entità che può non necessariamente essere l’elaboratore.

In pratica esisterà sempre un limite preciso al numero di istruzioni che possono comporre l’algoritmo e al tempo di esecuzione dello stesso, limite dettato dalle caratteristiche dell’elaboratore.

Gli Algoritmi


Algoritmi: caratteristiche

Un ALGORITMO adatto ad essere utilizzato da un elaboratore deve rispondere ad alcune proprietà essenziali; deve cioè essere:

effettivo;

definito e non ambiguo;

generale;

finito.

Gli Algoritmi



Deve avere un punto di partenza e deve essere EFFETTIVOcioè deve avere un punto di partenza ed ogni operazione deve produrre un certo e bendeterminato risultato ogni volta che si presentano le stesse condizioni.

Deve essere DEFINITO e NON AMBIGUOè necessario ciò che sia stato previsto ogni aspetto che il problema può assumere durante la fase risolutiva e che ogni espressione sia interpretabile in maniera univoca senza ambiguità.

Gli Algoritmi



Deve essere GENERALEossia utilizzabile per una serie o classe di problemi.Dominio dell’algoritmo: insieme dei dati che possono essere elaborati e le condizioni che ne permettono l’elaborazione

Deve essere FINITOdeve cioè poter giungere al suo termine dopo che sia stato eseguito un numero anche elevatissimo ma finito di istruzioni(poiché spesso le istruzioni possono essere eseguite in modo ciclico – loop -, sarà necessario che non sia possibile prevedere loop non aventi limite finito).

Gli Algoritmi


Analisi e Programmazione

ANALISI: fase di comprensione del problema, in base all’obiettivo da perseguire. Conduce ad un disegno articolato del problema stesso.

Gli Algoritmi

Ogni problema che l’uomo si pone comporta una serie di azioni (“decisioni”) stabilite in base allo stato dell’informazione disponibile all’insorgere del problema stesso: si effettua una rassegna degli elementi determinanti alla soluzione, elencando gli elementi necessari e quelli disponibili.

Vengono “decise” le azioni da compiere e la loro sequenza temporale.



Generalizzazione della fase d’Analisi:

definizione dei dati in ingresso;

definizione dei risultati in uscita;

individuazione dei termini del problema e dei possibili metodi risolutivi;

determinazione della necessità e della disponibilità di risorse (di calcolo e memorizzazione);

generalizzazione del problema (definizione di una classe di problemi da risolvere);

descrizione informale dell’algoritmo o degli algoritmi necessari a risolvere la procedura.

Gli Algoritmi



PROGRAMMAZIONE: ha lo scopo di descrivere le operazioni che l’elaboratore deve eseguire per risolvere il problema.

Gli Algoritmi

Fase della programmazione

insieme delle attività e delle funzioni che trasformano il bisogno (necessità di risolvere il problema con un elaboratore) in una richiesta di formulazione,

costruzione e definizione delle regole di comportamento per la soluzione di classi di processi di elaborazione, fatte ad un insieme di risorse di calcolo.



Tecnica TOP-DOWN: si definiscono inizialmente un insieme d’azioni a grandi linee (macro istruzioni) e si procede per raffinamenti successivi, fino ad arrivare ad operazioni elementari che l’esperienza designa come indipendenti dal linguaggio di programmazione utilizzato per scrivere il programma.

Tecnica BOTTOM-UP: parte dai singoli dati e dalle operazioni elementari da compiere su di essi, arrivando, per aggregazione, ad una o più procedure automatiche.

Gli Algoritmi



Indipendentemente dalla tecnica usata, la programmazione si concretizza nei seguenti passi:

Gli Algoritmi

definizione formale dell’algoritmo, spesso in forma grafica tramite un diagramma a blocchi;

stesura del programma nel linguaggio di programmazione prescelto;

prova del programma.La programmazione è sicuramente

un processo creativo non vincolato da regole, che deve tenere in considerazione alcuni criteri di

ottimizzazione quali i tempi di calcolo e l’occupazione delle memorie.


Esempi di algoritmi

Gli Algoritmi

Una ricetta di cucina.

Lettura di due valori numerici e stampa del maggiore tra i due

Lettura di due valori numerici A e Be stampa di (A-B)^2

Lettura del valore numerico n e calcolo di

Lettura di due valori numerici M e N (con M>=N) e calcolo del M.C.D.

Ordinamento di una sequenza di numeri

0

2n

i

i


Algoritmi rilevanti

Gli Algoritmi

Progetto Genoma Umano per la mappatura dei 100000 geni del DNA umano;

Navigazione Internet: percorsi ottimali che i dati devono percorrere in rete per il rapido accesso a grandi quantità di informazioni e motori di ricerca;

Percorso stradale minimo data una certa rete viaria (es: mappe in internet);

Compressione del testo, crittografia e firme digitali;

Allocazione ottimale dei prodotti negli scaffali di un supermercato (P. L. e Game Theory);

Gestione delle code;

…


Efficienza di un Algoritmo

Quand’è che un Algoritmo è EFFICIENTE?

Gli Algoritmi

quando è CORRETTO: cioè produce il risultato atteso;

quando è VELOCE (in termini di tempo impiegato per produrre il risultato);

quando è PARSIMONIOSO (in termini di risorse allocate per produrre il risultato).


Strutture dati

(fondamenti)


Classificazione

Strutture dati

Variabili numeriche

Variabili carattere

Bit

Intere

Reali (razionali)

Complesse

precisione singola

precisione doppia


Strutture di memorizzazione

Strutture dati

Variabili singole

Vettori: una sequenza indicizzabile di valori numerici dello stesso tipo es: stringa = vettore di caratteri

Matrici: una sequenza indicizzabile di vettori dello stesso tipo

Array: matrici multidimensionali

Liste: array differenziabili per tipo di valori memorizzabili


I DIAGRAMMI a BLOCCHI

(o Diagrammi di Flusso)


Aspetti definitori

I Diagrammi a Blocchi

I Diagrammi a Blocchi sono uno strumento molto utilizzato in informatica per una chiara e semplice esposizione in forma grafica degli algoritmi.

Sono uno strumento fondamentale per l’analista (servono a definire in modo schematico il processo algoritmico di scomposizione di un problema), danno una visione immediata dell’iter risolutivo e facilitano il controllo di correttezza logica dell’algoritmo.

Inoltre hanno anche uno scopo comunicativo: la documentazione di un algoritmo nel tempo.È infatti molto più facile leggere un algoritmo schematizzato mediante un diagramma a blocchi che leggerne la sua traduzione in uno specifico linguaggio di programmazione.


Aspetti definitori


Requisiti essenziali di un Diagramma a Blocchi:

• deve esistere un solo blocco di inizio;

• deve essere previsto almeno un blocco di fine;

• il diagramma può esibire un numero finito di blocchi di controllo;

• il diagramma può prevedere un numero finito di blocchi relativi sia ad operazioni aritmetiche e logiche che di I/O.


Simboli e regole di costruzione


Punto di Inizio e punti di Fine

Operazioni Aritmetiche e Logiche

Operazioni di Input/Output

Decisioni

Sottoprogrammi

Connessioni ad un qualsiasi punto del diagramma



Regole di implementazione:

• ogni blocco logico/aritmetico o di I/O deve avere una sola linea in ingresso e una sola in uscita;

• ogni blocco di controllo deve avere una sola linea in ingresso e due (o più) linee in uscita;

• una linea può inserirsi in un blocco o in un’altra linea;

• dall’unico blocco iniziale parte una sola linea, seguendo la quale, attraverso un insieme non vuoto di blocchi deve potersi raggiungere uno dei blocchi finali.

Simboli e regole di costruzione



es. 1 : scambio di due valori numerici

semplice scambio di 2 valori numerici immessi da tastiera nelle variabili A e B

START

AUX = BB = A

A = AUX

INPUT AINPUT B

PRINT APRINT B

STOP




semplice scambio di 2 valori numerici immessi da tastiera nelle variabili A e B

START

INPUT AINPUT B

PRINT APRINT B

STOP

ScambiaA con B

AUX = BB = A

A = AUX

ScambiaA con B

dove




scambio di 2 valori numerici immessi da

tastiera nelle variabili A e B solo se il primo è

maggiore del secondo

START

INPUT AINPUT B

PRINT APRINT B

STOP

A > B

Sì

No

ScambiaA con B



es. 3 : somma dei valori di un vettore

Somma di una certa sequenza di valori, immessi da tastiera

all’interno di un vettore

START

INPUT N

No

DIM V[N]

INPUT V[1]…

INPUT V[N]

J = 1S = 0

J <= N

S = S + V[J]

J = J + 1

PRINT S

Sì

STOP



es. 3 : somma dei valori di un vettore

Somma degli elementi di un vettore V già presente in

memoriaSTART

No

J = 1S = 0

J <= N

S = S + V[J]

J = J + 1

PRINT S

Sì

STOP

Sommavettore



es. 4 : ricerca del minimo di un vettore

Ricerca del minimo di un vettore V già presente in

memoria

START

No

min = V[1]N = length(V)

J = 2

J <= NPRINT

min

Sì

STOP

V[J] < min

Sì

min = V[J]

J = J +1

No

Minimo diun vettore



es. 5 : somma, media, min e max di un vettore

Somma, media, min e max di una sequenza di

valori, immessi da tastiera

all’interno di un vettore

START

INPUT N

DIM V[N]

INPUT V[1]…

INPUT V[N]

Sommavettore

Minimo di unvettore

Massimo diun vettore

STOPA

A

media = S/N

PRINTmedia



es. 6 : calcolo di una serie parziale

Lettura del valore numerico n e calcolo di

0

2n

i

i

START

INPUT N

No

J = 0S = 0

J <= N

S = S + 2^J

J = J + 1

PRINT S

Sì

STOP



es. 7 : calcolo del MCD (algoritmo di Euclide)

Lettura di due valori numerici M e N

(con M>=N) e calcolo del M.C.D.

START

INPUT NINPUT M

No

M > N

Q = INT(N/M)

R = N - M*Q

PRINT”MCD :”, M

Sì

STOP

ScambiaM con N

R = 0N = M

M = R

SìNo



es. 7 : calcolo del MCD (algoritmo inefficiente)

Lettura di due valori numerici M e N

(con M>=N) e calcolo del M.C.D.con un algoritmo

inefficiente

START

INPUT NINPUT M

No

M > N

Sì

ScambiaM con N

Q = INT(N / J)R = N - J*Q

J = M

R = 0

J = J - 1

No PRINT”MCD :”, J

STOP

Sì



es. 8 : radici di un polinomio di 2° grado

Ricerca delle due radici reali x1 e x2, di

una equazione del tipo

, ,a b c

2 0ax bx c

2 4b ac

se

2

bx

a

2

bx

a

>0 :

=0 :

<0 : non esistono radici reali




Ricerca delle due radici reali x1 e x2, di

una equazione del tipo2 0ax bx c

START

INPUTA,B,C

delta =B*B-4*A*C

deltaPRINT

”non esistonoradici reali”

STOP

rad = 0

rad =SQRT(delta)

X1 =(-B + rad)/(2*A)

X2 =(-B - rad)/(2*A)

PRINTX1, X2

STOP

< 0

= 0

> 0



es. 9 : ricerca in un vettore

Verifica della presenza di un certo elemento A all’interno di un vettore

V preesistente in memoria

START

INPUT A

J = 1N = length(V)

A = V[J] STOPPRINT

”elementotrovato”

Sì

J > N

No

STOPPRINT

”elementonon trovato”

Sì

J = J +1

No



es. 10 : ordinamento

di un vettoreOrdinamento di un

vettore V preesistente in memoria:

un’ipotesi di lavoroStart

Stop

1:

2:

3:

4:

5:

6:

7 4 3 8

7 4 3 8

4 7 3 8

3 7 4 8

3 7 4 8

3 4 7 8

3 4 7 8

3 4 7 8



es. 10 : ordinamento

di un vettoreOrdinamento

di un vettore V preesistente in

memoria

START

N = length(V)

I = 1

I <= (N-1)

J <= N

J = I + 1

V[I] > V[J]

ScambiaV[I] con V[J]

J = J + 1

I = I + 1

PRINTV

STOP

No

Sì

Sì

Sì

No

No

SORTvettore




(alg. dicotomico)

START

SORTV

A < V[L1]or

A > V[L2]

INPUT A

PRINT A“non trovato”

STOP

Sì

L1 = 1L2 = length(V)

PRINT A“trovato”

STOP

A = V[L1]or

A = V[L2]

Sì

No

med =INT ( (L1 + L2) / 2 )

A >= V[med]

No

L2 = med L1 = med

SìNo

Verifica della presenza di un certo elemento A

all’interno di un vettore V preesistente in memoria,

previa ordinamento

Attenzione: possibilità di loop

infinito




(alg. dicotomico)

Verifica della presenza di un certo elemento A

all’interno di un vettore V preesistente in memoria,

previa ordinamento

START

SORTV

A < V[L1]or

A > V[L2]

INPUT A

PRINT A“non trovato”

STOP

Sì

L1 = 1L2 = length(V)

PRINT A“trovato”

STOP

A = V[L1]or

A = V[L2]

Sì

No

med =INT ( (L1 + L2) / 2 )

A >= V[med]

No

L2 = med L1 = med

SìNo

L1 = L2 - 1

No

Sì


Lo PSEUDOLINGUAGGIO

un ponte verso i linguaggi di programmazione


Lo pseudolinguaggio

La traduzione del diagramma a blocchi in pseudolinguaggio

Condizioni: IF (condizione) THENinizio bloccoistruzione 1istruzione 2…fine blocco

ELSEinizio bloccoistruzione 1istruzione 2…fine blocco



Condizioni:

IF (condizione) THEN

[blocco istruzioni]

ELSE IF (condizione) THEN

[blocco istruzioni]

ELSE

[blocco istruzioni]

Lo pseudolinguaggio



Condizioni: SWITCH (espressione)

CASE (condizione1):

[blocco istruzioni]

CASE (condizione2):

[blocco istruzioni]

CASE (condizione3):

[blocco istruzioni]

…

OTHER:

[blocco istruzioni]

NON in tutti i

linguaggi diprogrammazion

e

Lo pseudolinguaggio



Iterazioni: FOR (variabile) = (inizio) TO (fine) (step)

inizio bloccoistruzione 1istruzione 2…fine blocco

WHILE (condizione)inizio bloccoistruzione 1istruzione 2…fine blocco

Lo pseudolinguaggio


Lo pseudolinguaggio


main {input Ainput BAUX = BB = AA = AUXprint Aprint B}

START

AUX = BB = A

A = AUX

INPUT AINPUT B

PRINT APRINT B

STOP



START

INPUT AINPUT B

PRINT APRINT B

STOP

A > B

Sì

No

ScambiaA con B

main {input Ainput Bif (A > B) then {

AUX = BB = AA = AUX}

print Aprint B}

Lo pseudolinguaggio


es. 3 : somma dei valori di un vettoreSTART

INPUT N

No

DIM V[N]

INPUT V[1]…

INPUT V[N]

J = 1S = 0

J <= N

S = S + V[J]

J = J + 1

PRINT S

Sì

STOP

main {input Ndim V(N)S = 0for I = 1 to N {

input V(I)S = S + V(I)}

print S}

Lo pseudolinguaggio


es. 4 : ricerca del minimo di un vettore

main {input Ndim W(N)for I = 1 to N {

input W(I)}

MIN = minimo(W)print MIN}

minimo(V) {N = length(V)M = V(1)for I = 2 to N {

if (V(I) < M) then {M = V(I)}

}return (M)}

Lo pseudolinguaggio


es. 6 : calcolo della serie parziale0

2n

i

i

START

INPUT N

No

J = 0S = 0

J <= N

S = S + 2^J

J = J + 1

PRINT S

Sì

STOP

main {input NS = 0for I = 0 to N {

S = S + 2^I}

print S}

Lo pseudolinguaggio


es. 7 : calcolo del MCD (algoritmo di Euclide)

START

INPUT NINPUT M

No

M > N

Q = INT(N/M)

R = N - M*Q

PRINT”MCD :”, M

Sì

STOP

ScambiaM con N

R = 0N = M

M = R

SìNo

main {input Ninput Mif (M > N) then {

AUX = MM = NN = AUX

}Q = int(N/M)R = N - M*Qwhile (R<>0) {

N = MM = RQ = int(N/M)R = N - M*Q}

print “MCD :”, M}

Lo pseudolinguaggio



Lo pseudolinguaggio

main {input A, B, Cif (A <> 0) then {

DELTA = B*B – 4*A*Cif (DELTA >= 0) then {

RAD = 0if (DELTA > 0)

then {RAD =

SQRT(DELTA)}

X1 = (-B + RAD)/(2*A)

X2 = (-B - RAD)/(2*A)

print “le radici sono: “, X1, X2

} else{

print “non esistono radici reali”

}}

else {print “è stato inserito un polinomio non di 2°

grado”}

}




input W(I)}

input APOS = ricerca1 (W,A)if (POS > 0) then {

print “trovato in posizione ”, POS}

}

ricerca1 (V,E) {N = length(V)F = 0for I = 1 to N {

if (V(I) = E) then {F = II = N}

}return (F)}

Lo pseudolinguaggio


es. 10 : ordinamento di un vettore

Lo pseudolinguaggio


input W(I)}

W = ordina (W)for I = 1 to N {

print W(I)}

}

ordina (V) {N = length(V)for I = 1 to N-1 {

for J = I+1 to N { if (V(J) < V(I)) then {

A = V(I)V(I) = V(J)V(J) = A}

}}

return (V)}

Algoritmi e Strutture Dati

Documents

Transcript of Algoritmi e Strutture Dati