Fondamenti di Programmazione
Classe 2
(matricole congrue 1 mod 3)
Docente: Prof. Luisa Gargano
Finalità: basi teoriche della programmazione
Testo: Aho, Ulman,
Foundations of Computer Science –C Edition
W.H. Freeman and Company, NY, 1994
Informazioni Pratiche
ORARIO: Martedì 16:00-18:00, Venerdì 9:00-11:00
N.B.: Tutte le lezioni sono ugualmente importanti!
SITO WEB: http://www.dia.unisa.it/professori/lg/FP.html
di riferimento per il materiale relativo al corso
- copie delle slides, esercizi,
- date delle prove,
- comunicazioni varie,
- etc.
Suggerimenti
•
Avere già le slides a disposizione a lezione
• EVITARE di lasciare accumulare il lavoro
•Studiare volta per volta
•Chiarire i dubbi di volta in volta
•Fare gli esercizi
Prove di Esame
•
Prova scritta con esercizi e teoria
(nessun materiale ammesso)
•
Eventuale prova orale
•
Requisito minimo: 40% del totale
Progamma sintetico
• Tecniche di programmazione (iterative e ricorsive)
• Efficienza di programmi
• Strutture dati elementari (liste, alberi)
• Automi finiti
ALGORITMI e PROGRAMMI
Programmazione: Lavoro che si fa per costruire sequenze di
istruzioni (operazioni) adatte a svolgere un dato calcolo
INPUT: dati iniziali
AZIONI
OUTPUT:
INPUT: x,y,z
esempio:
risultato
Somma x ed y
Somma z al risultato
OUTPUT: x+y+z
Algoritmo: Sequenza di azioni per svolgere il calcolo
Programma: Algoritmo espresso in notazione formale
(linguaggio di programmazione)
Creazione programma:
Fase 1 = algoritmo
Fase 2 = implementazione in dato linguaggio (C)
SCOPO del CORSO:
Elementi di base per semplici algoritmi e programmi
Riepilogo del linguaggio C: Espressioni
Espressione: formula (regola di calcolo) che specifica
sempre un valore
Esempio: espressione algebrica: z=x* y, (x+3)/5
Riepilogo del linguaggio C: Espressioni
Espressione: formula (regola di calcolo) che specifica
sempre un valore
Esempio: espressione algebrica: z=x* y, (x+3)/5
Espressione composta da: Operatori
Operandi (costanti, variabili,…)
Riepilogo del linguaggio C: Espressioni
Espressione: formula (regola di calcolo) che specifica
sempre un valore
Esempio: espressione algebrica: z=x* y, (x+3)/5
Espressione composta da: Operatori
Operandi (costanti, variabili,…)
Operatori Algebrici: +, -, *, /, - unario, ++, --, %
( i%j= i modulo j= resto di i diviso j)
Riepilogo del linguaggio C: Espressioni
Espressione: formula (regola di calcolo) che specifica
sempre un valore
Esempio: espressione algebrica: z=x* y, (x+3)/5
Espressione composta da: Operatori
Operandi (costanti, variabili,…)
Operatori Algebrici: +, -, *, /, - unario, ++, --, %
( i%j= i modulo j= resto di i diviso j)
Operatori Logici: AND (&&), OR (||), NOT (!),
(su variabili booleane - valore vero/falso)
x AND y VERO se e solo se x,y VERE
x OR y
FALSO se e solo se x,y FALSE
NOT x VERO se e solo se x FALSA
Espressioni
Operatori di confronto:
Uguale “==“: x==y da VERO sse x e y hanno stesso valore
Diverso “!=“: x!=y da VERO sse x e y hanno dalori diversi
Minore “<“
Minore o Uguale “<=“
Maggiore “>”
Maggiore o uguale “>=“
ISTRUZIONI
Assegnamento: x=E, Calcola il valore dell’espressione E
e lo assegna alla variabile x
Esempio: x=x+y calcola il valore di x+y e lo assegna ad x
se x vale 5 e y vale 3, x=x+y da ad x valore 8
ISTRUZIONI
Assegnamento: x=E, Calcola il valore dell’espressione E
e lo assegna alla variabile x
Esempio: x=x+y calcola il valore di x+y e lo assegna ad x
se x vale 5 e y vale 3, x=x+y da ad x valore 8
Istruzioni Strutturate:
1) Composizione di Istruzioni:
I 1;
I 2;

Im;
Esegui I1, quando e’ terminata
esegui I2, quando e’ terminata
…
esegui Im.
x=1;
y=2;
x=x+y; (x vale 3)
y=x*y (y vale 6)
ISTRUZIONI Strutturate
2) Istruzioni Condizionali:
If (C) I’ else I’’;
C condizione, I’ ed I’’ composizioni di istruzioni
Es.
Poni z=0 se x<=y; poni z=x-y se x>y
if (x<=y) z=0 else z=x-y
ISTRUZIONI Strutturate
2) Istruzioni Condizionali:
If (C) I’ else I’’;
C condizione, I’ ed I’’ composizioni di istruzioni
Es.
Poni z=0 se x<=y; poni z=x-y se x>y
if (x<=y) z=0 else x=x-y
Poni z=0 se x<=y; altrimenti lascia il valore di z inalterato
if (x<=y) z=0
If (C) I;
Istruzioni Ripetitive
for (x=1, x<=n, x++) I;
I e’ una composizione di istruzioni
Poni x=1 esegui I
Modifica x (x=2), esegui I
…
Modifica x (x=n), esegui I
x
1
2
3
…
n
y
0
1
1+2=3
1+2+3=6
…
1+2+…+n
y=0;
for (x=1, x<=n, x++) y=y+x;
x=1
x<=n
FALSO, ESCI
VERO
I
x++
while ( C ) I;
C e’ una condizione, I e’ una composizione di istruzioni
x=1; y=0;
while (x<=n) {y=y+x;
x++}
C
Falso, ESCI
Vero
x
1
2
3
…
n
y
0
1
1+2=3
1+2+3=6
…
1+2+…+n
I
do I while (C);
I
Falso, ESCI
C
Vero
n=0?
x=1;
y=0;
do y=y+x; x++ while (x<=n)
y
0
1
1+2=3
1+2+3=6
…
1+2+…+n
x
1
2
3
4
…
n+1 (>n)
Scegliere astrazione: definire un
Insieme di dati che rappresentano
la realta’ (modello di dati)
Risolvere problema
Scegliere rappresentazione della
informazione (struttura dati)
Algoritmo e programma
Es. Archivio impiegati contiene insieme di dati rilevanti
(astrazione) su ogni impiegato
Rilevanti: Nome, stipendio, mansione
Non rilevanti: altezza, peso, colore occhi, colore capelli
Tipi di dati
Variabile: e’ identificata da un nome
ha associato un tipo (intero, reale,…)
si possono conservare solo oggetti di tale tipo
Tipi Base (in C): intero (int), reale (real), carattere (char)
Definizioni di variabili
int x definisce x come variabile di tipo intero
Definizioni di Variabili
ARRAY formato da componenti dello stesso tipo
le componenti sono individuate da un indice
int A[n]
A[0]
:array di n componenti di tipo intero
A[1]
…
A[2]
A[n-1]
Si accede ad una componente alla volta specificando l’indice
int X[5]
X[0]=10;
X[1]=7;
X[2]=4;
X[3]=3;
X[4]=8;
Crea l’array di interi X:
10
7
4
3
8
Array
Es. cerca il numero di una componenti di un array
A[n] avente valore w.
idea: confronta w con A[0], A[1],… finche’ non
hai esaminato tutto l’array,
incrementa contatore ad ogni confronto positivo
int A[n]
int c=0;
for(i=0,i<n,i++) if (A[i]==w) c++;}
Assumiamo n=5 e w=3
A[0]=3
A[1]=2
c=0
A[0]=w=3 , c=1
A[2]=3
A[4]=5
A[n-1]=A[5]=2
Array
Es. cerca il numero di una componenti di un array
A[n] avente valore w.
idea: confronta w con A[0], A[1],… finche’ non
hai esaminato tutto l’array,
incrementa contatore ad ogni confronto positivo
int A[n]
int c=0;
for(i=0,i<n,i++) if (A[i]==w) c++;}
Assumiamo n=5 e w=3
A[0]=3
A[1]=2
i=1
A[1]!=3 c=1
A[2]=3
A[4]=5
A[n-1]=A[5]=2
Array
Es. cerca il numero di componenti di un array
A[n] avente valore w.
idea: confronta w con A[0], A[1],… finche’ non
hai esaminato tutto l’array,
incrementa contatore ad ogni confronto positivo
int A[n]
int c=0;
for(i=0,i<n,i++) if (A[i]==w) c++;}
Assumiamo n=5 e w=3
A[0]=3
A[1]=2
A[2]=3
A[0]=w
c=1
A[1]!=w
c=1
A[2]=w
c=2
i++
i++
i++
A[3]=5
A[3]!=w
c=2
i++
A[n-1]=A[4]=2
i=4=n-1
A[i]!=w c=2
i++, i=n, esci
STRUCT
Permette di “unire” elementi di tipi differenti.
Struct S
{T1 M1;
T2 M2;
…
Tn Mn}
Definisce una struttura con n campi
(M1, M2, …, Mn)
Di tipo T1,T2,…,Tn, rispettivamente.
Es. Vogliamo descrivere persone usando 3 campi:
(NOME, COGNOME, DATA-NASCITA)
STRUCT
Es. Vogliamo descrivere persone usando 3 campi:
(NOME, COGNOME, DATA-NASCITA)
1) typedef char alfa[10]
definisce il tipo alfa
come un array di 10 caratteri
3) Struct persona
{alfa cognome;
alfa nome;
data data-nascita}
2) Struct data
{int giorno;
int mese;
int anno}
Struct persona P
P= (Mario, Rossi,(10,3,1980))
STRUCT
La componente i-ma di nome Mi della struttura S,
S=(M1,…,Mi,…,Mn), si indica con S.Mi
Es. Struct persona
P= (Mario, Rossi,(10,03,1980))
P.nome e’ l’array contenete Mario
P.nome[1] e’ il carattere a
P.data-nascita e’ la struttura di tipo data
(10,3,1980)
P.data-nascita.mese e’ l’intero 3
E’ possibile combinare array e strutture
Es. Array di struct di tipo persona
persona A[n]
array di n componenti A[0],…,A[i],…,A[n-1]
A[i] e’ una struct di tipo persona
E’ possibile combinare array e strutture
Es. Array di struct di tipo persona
persona A[n]
array di n componenti A[0],…,A[i],…,A[n-1]
A[i] e’ una sruct di tipo persona
Cerca il numero di persone nate a maggio
{int c;
c=0;
for(i=0,i<n,i++) if (A[i].data-nascita.mese==5) c++;}
PUNTATORI
Una variabile di tipo puntatore contiene un indirizzo
di memoria
int x *p
Definisce p come un puntatore alla variabile di tipo
intero x
P
x
PUNTATORI
Una variabile di tipo puntatore contiene un indirizzo
di memoria
int x *p
definisce p come un puntatore alla variabile di tipo
intero x
P=&x assegna a p l’indirizzo di memoria di x
y=*p assegna a y il contenuto della variabile puntata
da p
Es. {p=&x; y=*p} risulta valore di x = valore di y