Informatica di base A.A. 2003/2004 Algoritmi e programmi.

transcript

Informatica di base A.A. 2003/2004

Algoritmi e programmi

Algoritmi

Algoritmo: procedura per risolvere una classe di problemiDa algoritmo a programmaCaratteristiche di un algoritmo efficace:

Generale: deve funzionare per tutti i problemiNon ambiguo: unica interpretazione dei passiEseguibile: i passi devono poter essere fatti in tempo finito

Programmazione

Disciplina che dice come definire gli algoritmi in modo che possano essere eseguiti da un calcolatoreProgramma: definizione di un algoritmo, scritto secondo certe regole sintatticheFasi di sviluppo di un programma:

Definizione: specifica del problema + algoritmoRealizzazione: scrittura del programma che corrisponde all’algoritmoManutenzione: modifiche del programma e/o dell’algoritmo

Caratteristiche di un programma

Efficienza: risolvere un problema nel minimo tempo e con le risorse (memoria) a disposizione

Leggibilita’: scritto in modo chiaro e documentato, per agevolare la manutenzione

Modificabilita’: Facilita’ di modificarlo

Efficienza – esempio:somma dei primi n numeri 1, ..., n

1. Leggi n2. Inizializza S a 03. Inizializza I a 14. Esegui S = S+I5. Incrementa I (I=I+1)6. Se I<n torna a 4, altrimenti se I=n esegui 77. Stampa SRichiede n somme

Secondo algoritmo

Uso la proprieta’ S = n x (n+1) /21. Leggi n2. Calcola S = n x (n+1)/23. Stampa SUna sola somma, 1 prodotto, 1 divisione: solo 3 operazioni aritmetiche piu’ efficiente

Sviluppo di un algoritmo

Diagrammi di flusso: rappresentazione grafica per mostrare l’ordine logico delle operazioniRettangolo: operazione da svolgereRombo: scelta fra due rami dell’algoritmo (salto condizionato)

Strategia top-down

Suddividere il problema in sottoproblemi indipendenti pezzi con un punto di ingresso e uno di uscitaComporre i pezzi dei sottoproblemi per ottenere l‘intero algoritmoVantaggi:

Scrivere i vari pezzi separatamenteProgrammi leggibiliErrori localizzati e semplice trovarliPiu’ programmatoriPochi salti intrecciati

Programmazione strutturata

Linguaggi di programmazione

Linguaggi ad alto livello (rispetto all’Assembler)Linguaggi imperativi: rispecchiano le operazioni reali nell’architettura di Von Neumann

Scrivere un valore in una cella di memoria o in un registro

Es.: Fortran (Formula Translator), 1954Algol, Cobol, APL, LISP (’60), Pascal, Prolog (’71), C (’74), Ada (’79), C++ (’85), Java (’94)

Elementi dei linguaggi di programmazione

Alfabeto: alfabeto inglese, cifre decimali (0,1,...,9), punteggiatura (;), simboli di operazioni (+,-,*,...)Parole chiave: es. IF, THEN, WHILE, ...Operatori: aritmetici, logici (and, not, or, ...), relazionali (<, >, =, ...)Tipi di dati: interi, reali, caratteri, ...Sintassi: regole per scrivere un programmaSemantica: significato dell’esecuzione di un programma

Variabili e assegnamenti

Variabile: nome associato ad una cella di memoriaPuo’ assumere un valore (quello contenuto nella cella)Istruzione di assegnamento per dare un valore ad una variabileValore ottenuto calcolando un’espressione (es: A+3)Es. (Pascal): X := Y+3Es. (C): X = Y+3Es. (C): X=X+1 (X da entrambe le parti!)

Costrutti di programmazione

SequenzaSelezioneIterazioneSalto incondizionatoProcedura rientranteFunzione ricorsiva

Sequenza

Istruzioni eseguite in sequenzaEs: S1;S2;S3; ...; Sk;Es. (Pascal):

BeginX:=Y+3;Z:=X+4End

Es. (C):{X=Y+3;Z=X+4;}

Selezione (uno o due rami)

Se E e’ vera, esegui S1 (altrimenti esegui S2)E espressione Booleana (vera o falsa)Es.: A < BCostrutto IF THEN ELSEEs.: (Pascal)

If a > 0 then a: a-1 else b:=aEs. (C):

If (a >0) a=a-1 else b=a

Selezione (piu’ di due rami)

Condizione non Booleana piu’ valori piu’ ramiCostrutto CASEEs. (Pascal):

Case veicolo ofBicicletta: tassa:=0;Motociclo: tassa:=30;Auto: tassa:=100End;

Iterazione - while

Per ripetere un gruppo di comandi finche’ non si verifica una certa condizioneCostrutto WHILE: finche’ E e’ vera ripeti STest prima del ciclo (loop) se E e’ falsa all’inizio, S non viene mai eseguitoEs. (Pascal):

i:=1;While i <= 100 doBegin ... i:=i+1 end;

Es. (C):I=1;While (i<=100) { ... I++;}

Iterazione -repeat

Costrutto REPEAT: ripeti S fino a che E e’ falsaTest dopo il loop S viene sempre seguito almeno una voltaEs. (Pascal):

I:=1;Repeat...I:=i+1Until i> 100;Es. (C): I=1;Do{...I++;} while (i<=100);

Iterazione -for

Costrutto FOR: ripeti S n volte Non c’e bisogno di una condizione, so gia’ quante volte eseguire SEs. (Pascal):

For i:=1 to 100 do

Begin ... End

Es. (C): For (i=1;i<=100,i++)

{ ... }

Salto incondizionato

Per saltare ad una qualunque istruzione che non sia la seguente

Costrutto GOTO

Contrasta con la programmazione strutturata (effetto spaghetti)

Usare solo se assolutamente necessario!

Gruppi di aula informatica

Gruppo 1 (matematici): Martedi’ 4 Novembre 14:00

Mercoledi’ 12 Novembre 14:00

Venerdi’ 21 Novembre 11:20

Gruppo 2: Mercoledi’ 5 Novembre 14:00

Givedi’ 13 Novembre 11:20

Giovedi’ 20 Novembre 11:20

Martedi’ 25 Novembre 14:00

Gruppo 3: Giovedi’ 6 Novembre 11:20

Gruppo 4: Venerdi’ 7 Novembre 11:20

Giovedi’ 27 Novembre 11:20

Esercizio: programma per somma (C++)

Main(){Int X=10, Y=25, Zero=0;X=X+Y;If (X > Zero) Y=X);}

Dichiarazioni: utili per sapere quanto spazio allocare

per questi nomi

Nome funzione principale

Dichiarazioni

Sequenza

Esercizio: minimo esponente e tale che 2 alla e superi X (C++)

Main(){ Int X=10, p=1, e=0; While (X>p) { p=p*2; esponente++; }}

Nome funzione principale

Dichiarazioni

Sequenza

Struttura di un programma (C)

Intestazione Dichiarazione variabiliComandi (corpo) programma principaleFunzione 1Funzione 2...Funzione n

Esempio: stampa dei numeri da 1 a 10

main() { Int i; For (i=0;i<10;i++) Printf(“%d\n,i+1); }

Procedura rientrante (o sottoprogramma)

Pezzo di programma con un nome e una lista di variabili (argomenti o parametri) Scritto una volta solo, ma posso ‘’chiamarlo’’ piu’ volte e con dati diversiAnche risultati dal sottoprogramma al programma chiamante (funzione)Quando lo chiamo (call), salto alla prima istruzione del sottoprogramma e salvo l’indirizzo della prossima istruzioneQuando finisce, ritorno al punto in cui ero (quello salvato)

Esempio: funzione per xy (in Pascal)

Function potenza (base: real, esponente: integer): real;Var risultato: real;begin risultato := 1; While (esponente >0) begin Risultato := risultato * base; Esponente := esponente –1; End; Potenza : = risultatoEnd;

Esempio: funzione per xy (in C)

Float potenza (float base, int esponente){ Float risultato = 1.0; While (esponente >0) { Risultato = risultato * base; Esponente = esponente –1; } Return risultato;}

Es. di chiamata: z = potenza(x,3);

Struttura delle chiamate –1

Programma

Call A

Call B

Call C

Call B

Funzione A

Fine AFunzione B

Fine B

Fine C

Funzione C

Struttura delle chiamate - 2

Programma

Call A

Funzione A

Call B

Fine C

Funzione C

Funzione B

Call C

Fine B

Fine A

Funzioni ricorsive

Definizione ricorsiva: in termini di se’ stessoFunzione ricorsiva: chiama se’ stessa al suo internoEsempio: funzione fattoriale (fatt)

0! = 1N! = 1*2*3*4*...*n

Definizione iterativa:If (n=0 or n=1) then fatt = 1else {fatt = 1; for i=2 to n fatt = fatt*i}return fatt

Funzioni ricorsive

Definizione ricorsiva: in termini di se’ stessoFunzione ricorsiva: Chiama se’ stessa al suo internoEsempio: funzione fattoriale (fatt)

0! = 1N! = 1*2*3*4*...*n

Definizione ricorsiva: 0! = 1N! = n*(n-1)!

Funzione ricorsiva:If (n=1 or n=0) then fatt = 1Else {fatt = 1; fatt = n*fatt(n-1)}Return fatt

Da linguaggio X a linguaggio macchina

Se X= Assembler assemblatoreSe X piu’ ad alto livello compilatore o interpreteFasi di un compilatore:

Analisi lessicale: da caratteri a nomi, operatori, parole chiave, ... (tokens)Analisi sintattica/semantica: da tokens a costrutti (if then else, while, ...)

Generazione codice oggetto in linguaggio macchinaLinker/loader: collegamento tra vari Programmi e scelta degli indirizzi di RAM

Codice oggetto

eseguibile

compilatore

linker

loader

Programma

Programma in ling. macchina in RAM

Esempio

p := p + r * 60 sequenza di caratteriAnalisi lessicale: id1 := id2 + id3 * 60 sequenza di tokensAnalisi sintattica/semanticaGenerazione codice intermedio:

Temp1 := 60Temp2 := id3*temp1Temp3 := id2 + temp2Id1 := temp3

Ottimizzazione codice:Temp1 := id3 * 60Id1 := id2 + temp1

Generazione codice oggetto:MOVE id3 R2MULT R2 60MOVE id2 R1ADD R1 R2MOVE R1 id1

id3 60

Tipi di dati

I programmi possono gestire dati di diverso tipo:

Numerici: interi e realiNon numerici: booleani e caratteri

Inoltre, i dati possono essere:semplici (es. Un numero singolo o un carattere) strutturati (es. Ora: ore, minuti, secondi)

Tipi di dato strutturati

ArrayRecordCodaPilaLista

Sequenza finite di dati omogeneiPer indicare un elemento: nome dell’intero array + indice(i)

Indice: posizione rispetto al primo elementoUn indice vettore (array monodimensionale). Es.: V[3]Due o piu’ indici matrice. Es.: V[3,2]

Dichiarazione di un array: nome + numero dimensioni + tipo elementi + numero elementi in ogni dimensione. Es.: int V[100];In memoria: celle contigue a partire da B, N elementi, ognuno lungo L indirizzo elemento i: B+ixLLimiti: dimensione fissa e dati omogeneiVantaggio: accesso diretto con tempo fisso

Esempio (C)

Inizializzazione a 0 degli elementi di una matrice 20x20#define Max 20#define zero 0.0;main(){ int i,j; float A[Max][Max]; for (i=0;i<Max;i++) for j=0; j<Max; J++) A[i][j] = zero}

Macro: ogni occorrenza di Max e zero viene sostituita con 20 e 0.0 prima di iniziare a compilare (pre-processore)

Esempio (C++): determinare la posizione del massimo in un array di interi (while)

#include <iostream> il pre-processore include la libreria di funzioni iostream main(){ int a[]={10,0,5,-12,45,-9,23}; int i=1, max=A[0], pos_max=0; while (i<7) { if (A[i]>max) { max=A[i]; pos_max=i; } i++; } cout<<‘’Il massimo e’:’’<<max<<‘’ in posizione:’’ <<pos_max<<endI;}

Output standard (video)

Funzione << di scrittura

Esempio (C++): determinare la posizione del massimo in un array di interi (for)

#include <iostream>main(){ int a[]={10,0,5,-12,45,-9,23}; int max=A[0], pos_max=0; for (int i=1;i<7;i++) if (A[i]>max) { max=A[i]; pos_max=i; } cout<<‘’Il massimo e’:’’<<max<<‘’ in posizione:’’ <<pos_max<< endI;}

Esempio (C): prodotto degli elementi di un vettore di interi

main(){ int num[100]={10,0,5,-12,45,-9,23, ...}; float prod = 1.0; for (i=0;i<100;i++) prod= prod*num[i]; printf(“il Prodotto e’”,prod);}

Esempio (C): minimo e massimo di un vettore

main(){ int V[10]={10,0,5,-12,45,-9,23,8,10,9}; int min=max=V[0]; for (i=1;i<10;i++) { if (V[i]<min) min=V[i]; if (V[i]>max) max=V[i]; }}

Esempio (C): trovare la posizione di un elemento in un vettore

main(){ int val = 45, pos, i, T[10]={10,0,5,-12,45,-9,23,8,10,9}; pos=-1; i=0; do { if (val ==T[i]) pos=i; i++; }}

Numero di confronti O(n): 1 nel caso migliore, n nel caso pessimo (val non e’ contenuto in T)

Esempio (C): trovare la posizione di un elemento in un vettore ordinato – metodo dicotomico

main(){ int sn, dx, ct, N=10, val = 45, pos, i, T[10]={10,0,5,-12,45, 9,23,8,10,9}; pos=-1; sn = 0; dx = N-1; do { ct = (sn+dx+1)/2; if (val ==T[ct]) pos = ct; if (val < T[ct]) dx = ct-1 else sn=ct+1; } while (sn<=dx);}

Numero di confronti O(log2(n))

Esempio (C++): numero di elementi <0 in un array

main(){ int num=0,T[10]={10,0,5,-12,45, 9,23,8,10,9}; for (i=0;i<10;i++) if (T[i] < 0) num=num+1;}

Record

Composto da campi contenenti dati possibilmente di tipo diversoEs.: elenco del telefono, ogni riga e’ un record con

Cognome: sequenza di caratteriNome: sequenza di caratteriNumero telefono: intero

Struttura dati staticaAccesso direttoCome un array, ma con elementi di tipo diverso e indicati con nome invece che indice. Es.: riga.cognome = RossiEs. (C):

struct riga{

char cognome[20];char nome[20];int numero_telefono;

Struttura dinamica: oltre a leggere e scrivere elementi, anche inserimento e cancellazioneOgni elemento ha due parti: dato + indirizzo (puntatore) elemento successivo elemento successivi possono essere in posizioni lontane di memoriaPer accedere all’elemento i-esimo: scansione sequenziale dall’indirizzo del primo elemento tempo variabileInserzione di E tra Ei e Ei+1:

Scansione fino a EiLink(E) = link(Ei)Link(Ei)= ind(E)

Eliminazione di Ei:Scansione fino a Ei-1Link(Ei-1) = link(Ei)

E1 E2 En

Coda e pila

Dati ordinati in sequenzaStrutture dinamiche Coda: meccanismo FIFO (first in, first out)

Inserzione in fondoEliminazione in cima

Pila: estrazione e inserzione dalla stessa parte (LIFO: last in, first out)Celle contigue di memoriaPer una coda, basta un array (se si conosce la dimensione max.) e il puntatore al primo elementoPer la pila, lista con inizio pila = inizio lista no scansionePila usata per gestione memoria dei sottoprogrammi

coda pila

Domande – algoritmi e programmi

Cos’e’ un algoritmo?

Che differenza c’e’ tra un algoritmo e un programma?

Come si misura l’efficienza di un algoritmo?

Un algoritmo che ha complessita’ O(n) e’ piu’ o meno efficiente di uno che ha complessita’ O(logn)? E di uno che e’ O(n2) o O(2n)?

Cosa sono le parole chiave di un linguaggio di programmazione?

Domande – linguaggi

Cos’e’ la sintassi di un linguaggio di programmazione? E la semantica?

Cosa si intende per linguaggi imperativi?

Cos’e’ una variabile?

Cos’e’ un’espressione Booleana?

Cos’e’ un assegnamento?

Domande – costrutti e sottoprogrammi

Descrivere il costrutto di selezione a uno, due o piu’ rami

Descrivere i tre costrutti per l’iterazione, specificando le loro differenze

A cosa servono le dichiarazioni in un programma?

Cos’e’ un sottoprogramma?

Che differenza c’e’ tra una procedura e una funzione?

Cosa succede quando viene chiamato un sottoprogramma?

Cosa si intende per sottoprogramma ricorsivo?

Domande – compilatori e tipi di dato

Qual e’ la funzione di un compilatore?

Cosa succede durante la fase di analisi lessicale?

E quella di analisi sintattica?

Fare degli esempi di tipi di dati semplici

Cosa sono i tipi di dati strutturati? Fare degli esempi

Quali sono le principali caratteristiche di un array?

Cosa contiene la dichiarazione di un array?

Quali sono le principali differenze tra array e record?

Domande - liste

Quali sono le principali caratteristiche delle liste, e le differenze con gli array?

A parita’ di dati memorizzati, occupa piu’ spazio un array o una lista?

Quali sono le operazioni necessarie per inserire un nuovo elemento in una lista?

E per cancellare un elemento?

Cosa contengono le variabili d, n, e i alla fine dell’esecuzione del seguente programma?

Dato un qualunque array a, cosa calcola il programma nella variabile d? main();{ int n=0, a[] = {11, 3, 2, 4, 5}; float d = 0.0; for (i=0;i<5;i++) { d = d+a[i]; n=n+1; } d=d/n;}

Esercizio

d=5.0, n=5, i=4

d calcola la media degli elementi dell’array a

Esercizio: trovare il minimo e il massimo di una matrice

main(){ int V[10][20]={10,0,5, ...}; int min=max=V[0][0]; for (i=0;i<10;i++) for (j=0;j<20;j++) { if (V[i][j]<min) min=V[i][j]; if (V[i][j]>max) max=V[i][j]; }}

Esercizio: inizializzare una matrice a righe crescenti

main(){ int V[4][4]; for (i=0;i<4;i++) for (j=0;j<4;j++) { V[i][j] = j +1 + i*4; }}

9 10 11 12

5 6 7 8

1 2 3 4

13 14 15 16

Informatica di base A.A. 2003/2004 Algoritmi e programmi.

Documents