Informatica di base
A.A. 2003/2004
Algoritmi e programmi
Algoritmi
Algoritmo: procedura per risolvere una classe di
problemi
Da algoritmo a programma
Caratteristiche di un algoritmo efficace:
Generale: deve funzionare per tutti i problemi
Non ambiguo: unica interpretazione dei passi
Eseguibile: i passi devono poter essere fatti in tempo
finito
2
Programmazione
Disciplina che dice come definire gli algoritmi in
modo che possano essere eseguiti da un
calcolatore
Programma: definizione di un algoritmo, scritto
secondo certe regole sintattiche
Fasi di sviluppo di un programma:
Definizione: specifica del problema + algoritmo
Realizzazione: scrittura del programma che
corrisponde all’algoritmo
Manutenzione: modifiche del programma e/o
dell’algoritmo
3
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
4
Efficienza – esempio:
somma dei primi n numeri 1, ..., n
1. Leggi n
2. Inizializza S a 0
3. Inizializza I a 1
4. Esegui S = S+I
5. Incrementa I (I=I+1)
6. Se I<n torna a 4, altrimenti se I=n esegui 7
7. Stampa S
Richiede n somme
5
Secondo algoritmo
Uso la proprieta’ S = n x (n+1) /2
1. Leggi n
2. Calcola S = n x (n+1)/2
3. Stampa S
Una sola somma, 1 prodotto, 1 divisione: solo 3
operazioni aritmetiche  piu’ efficiente
6
Sviluppo di un algoritmo
Diagrammi di flusso: rappresentazione
grafica per mostrare l’ordine logico delle
operazioni
Rettangolo: operazione da svolgere
Rombo: scelta fra due rami dell’algoritmo
(salto condizionato)
7
Strategia top-down
Suddividere il problema in sottoproblemi
indipendenti  pezzi con un punto di ingresso e
uno di uscita
Comporre i pezzi dei sottoproblemi per ottenere
l‘intero algoritmo
Vantaggi:
Scrivere i vari pezzi separatamente
Programmi leggibili
Errori localizzati e semplice trovarli
Piu’ programmatori
Pochi salti intrecciati
Programmazione strutturata
8
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), 1954
Algol, Cobol, APL, LISP (’60), Pascal, Prolog (’71),
C (’74), Ada (’79), C++ (’85), Java (’94)
9
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 programma
Semantica: significato dell’esecuzione di un
programma
10
Variabili e assegnamenti
Variabile: nome associato ad una cella di memoria
Puo’ assumere un valore (quello contenuto nella
cella)
Istruzione di assegnamento per dare un valore
ad una variabile
Valore ottenuto calcolando un’espressione (es:
A+3)
Es. (Pascal): X := Y+3
Es. (C): X = Y+3
Es. (C): X=X+1 (X da entrambe le parti!)
11
Costrutti di programmazione
Sequenza
Selezione
Iterazione
Salto incondizionato
Procedura rientrante
Funzione ricorsiva
12
Sequenza
Istruzioni eseguite in sequenza
Es: S1;S2;S3; ...; Sk;
Es. (Pascal):
S1
Begin
X:=Y+3;
Z:=X+4
End
S2
{
X=Y+3;
Z=X+4;
}
Sk
Es. (C):
13
Selezione (uno o due rami)
Se E e’ vera, esegui S1 (altrimenti esegui S2)
E espressione Booleana (vera o falsa)
Es.: A < B
E
Costrutto IF THEN ELSE
Es.: (Pascal)
S1
If a > 0 then a: a-1 else b:=a
V
If (a >0) a=a-1 else b=a
S1
Es. (C):
E
F
V
F
S2
14
Selezione (piu’ di due rami)
Condizione non Booleana  piu’ valori  piu’ rami
Costrutto CASE
Es. (Pascal):
Case veicolo of
Bicicletta: tassa:=0;
Motociclo: tassa:=30;
Auto: tassa:=100
End;
15
Iterazione - while
Per ripetere un gruppo di comandi finche’ non si verifica
una certa condizione
Costrutto WHILE: finche’ E e’ vera ripeti S
Test prima del ciclo (loop)  se E e’ falsa all’inizio, S non
viene mai eseguito
Es. (Pascal):
i:=1;
While i <= 100 do
Begin ... i:=i+1 end;
E
S1
F
V
Es. (C):
I=1;
While (i<=100) { ... I++;}
16
Iterazione -repeat
Costrutto REPEAT: ripeti S fino a che E
e’ falsa
Test dopo il loop  S viene sempre
seguito almeno una volta
Es. (Pascal):
I:=1;
Repeat
...
I:=i+1
Until i> 100;
Es. (C):
I=1;
Do
{...
I++;
} while (i<=100);
S1
F
E
V
17
Iterazione -for
Costrutto FOR: ripeti S n volte
Non c’e bisogno di una condizione, so gia’
quante volte eseguire S
Es. (Pascal):
For i:=1 to 100 do
Begin ... End
Es. (C):
For (i=1;i<=100,i++)
{ ... }
18
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!
19
Gruppi di aula informatica
Gruppo 1 (matematici):
Martedi’ 4 Novembre 14:00
Mercoledi’ 12 Novembre 14:00
Venerdi’ 21 Novembre 11:20
Venerdi’ 28 Novembre 11:20
20
Gruppi di aula informatica
Gruppo 2:
Mercoledi’ 5 Novembre 14:00
Givedi’ 13 Novembre 11:20
Giovedi’ 20 Novembre 11:20
Martedi’ 25 Novembre 14:00
21
Gruppi di aula informatica
Gruppo 3:
Giovedi’ 6 Novembre 11:20
Venerdi’ 14 Novembre 11:20
Martedi’ 18 Novembre 14:00
Mercoledi’ 26 Novembre 14:00
22
Gruppi di aula informatica
Gruppo 4:
Venerdi’ 7 Novembre 11:20
Martedi’ 11 Novembre 14:00
Mercoledi’ 19 Novembre 14:00
Giovedi’ 27 Novembre 11:20
23
Esercizio: programma per somma
(C++)
Main()
Nome funzione principale
{
Int X=10, Y=25, Zero=0;
Dichiarazioni
X=X+Y;
If (X > Zero) Y=X);
Sequenza
}
Dichiarazioni: utili per sapere quanto spazio allocare per
questi nomi
24
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
25
Struttura di un programma (C)
 Intestazione
Dichiarazione variabili
Comandi (corpo) programma principale
Funzione 1
Funzione 2
...
Funzione n
26
Esempio: stampa dei numeri da 1 a 10
main()
{
Int i;
For (i=0;i<10;i++)
Printf(“%d\n,i+1);
}
27
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 diversi
Anche risultati dal sottoprogramma al programma
chiamante (funzione)
Quando lo chiamo (call), salto alla prima istruzione del
sottoprogramma e salvo l’indirizzo della prossima
istruzione
Quando finisce, ritorno al punto in cui ero (quello salvato)
28
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 : = risultato
End;
29
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);
30
Struttura delle chiamate –1
Programma
Call A
Call B
Call C
Funzione A
Fine A
Funzione B
Fine B
Funzione C
Call B
Fine C
31
Struttura delle chiamate - 2
Programma
Call A
Call A
Funzione A
Call B
Fine A
Funzione B
Call C
Fine B
Funzione C
Fine C
32
Funzioni ricorsive
Definizione ricorsiva: in termini di se’ stesso
Funzione ricorsiva: chiama se’ stessa al suo
interno
Esempio: funzione fattoriale (fatt)
0! = 1
N! = 1*2*3*4*...*n
Definizione iterativa:
If (n=0 or n=1) then fatt = 1
else {fatt = 1; for i=2 to n fatt = fatt*i}
return fatt
33
Funzioni ricorsive
Definizione ricorsiva: in termini di se’ stesso
Funzione ricorsiva: Chiama se’ stessa al suo
interno
Esempio: funzione fattoriale (fatt)
0! = 1
N! = 1*2*3*4*...*n
Definizione ricorsiva:
0! = 1
N! = n*(n-1)!
Funzione ricorsiva:
If (n=1 or n=0) then fatt = 1
Else {fatt = 1; fatt = n*fatt(n-1)}
Return fatt
34
Da linguaggio X a linguaggio macchina
Se X= Assembler  assemblatore
Se X piu’ ad alto livello  compilatore o
interprete
Fasi 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
macchina
Linker/loader: collegamento tra vari
Programmi e scelta degli indirizzi di RAM
Programma
compilatore
Codice oggetto
linker
eseguibile
loader
Programma in ling. macchina in RAM
35
Esempio
p := p + r * 60
sequenza di caratteri
Analisi lessicale:
id1 := id2 + id3 * 60
sequenza di tokens
Analisi sintattica/semantica
Generazione codice intermedio:
Temp1 := 60
Temp2 := id3*temp1
Temp3 := id2 + temp2
Id1 := temp3
Ottimizzazione codice:
Temp1 := id3 * 60
Id1 := id2 + temp1
:=
+
id1
id2
*
id3
60
Generazione codice oggetto:
MOVE id3 R2
MULT R2 60
MOVE id2 R1
ADD R1 R2
MOVE R1 id1
36
Tipi di dati
I programmi possono gestire dati di
diverso tipo:
Numerici: interi e reali
Non numerici: booleani e caratteri
Inoltre, i dati possono essere:
semplici (es. Un numero singolo o un
carattere)
strutturati (es. Ora: ore, minuti, secondi)
37
Tipi di dato strutturati
Array
Record
Coda
Pila
Lista
38
Array
V
B
V[1]
B+ixL
V[i]
L
Sequenza finite di dati omogenei
Per indicare un elemento: nome dell’intero array +
indice(i)
Indice: posizione rispetto al primo elemento
Un 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+ixL
Limiti: dimensione fissa e dati omogenei
Vantaggio: accesso diretto con tempo fisso
39
Esempio (C)
Inizializzazione a 0 degli elementi di una matrice 20x20
Macro: ogni occorrenza di Max e zero viene
#define Max 20
sostituita con 20 e 0.0 prima di iniziare a
#define zero 0.0;
compilare (pre-processore)
main()
{
int i,j;
float A[Max][Max];
for (i=0;i<Max;i++)
for j=0; j<Max; J++)
A[i][j] = zero
}
40
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)
{
Output standard (video)
if (A[i]>max)
{
max=A[i];
pos_max=i;
Funzione << di scrittura
}
i++;
}
cout<<‘’Il massimo e’:’’<<max<<‘’ in posizione:’’ <<pos_max<<endI;
}
41
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;
}
42
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);
}
43
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];
}
}
44
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)
45
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))
46
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;
}
47
Record
Composto da campi contenenti dati possibilmente di tipo
diverso
Es.: elenco del telefono, ogni riga e’ un record con
Cognome: sequenza di caratteri
Nome: sequenza di caratteri
Numero telefono: intero
Struttura dati statica
Accesso diretto
Come un array, ma con elementi di tipo diverso e indicati
con nome invece che indice. Es.: riga.cognome = Rossi
Es. (C):
struct riga
{
char cognome[20];
char nome[20];
int numero_telefono;
}
48
E1
E2
En
Lista
Struttura dinamica: oltre a leggere e scrivere elementi,
anche inserimento e cancellazione
Ogni elemento ha due parti: dato + indirizzo (puntatore)
elemento successivo  elemento successivi possono
essere in posizioni lontane di memoria
Per accedere all’elemento i-esimo: scansione sequenziale
dall’indirizzo del primo elemento  tempo variabile
Inserzione di E tra Ei e Ei+1:
Scansione fino a Ei
Link(E) = link(Ei)
Link(Ei)= ind(E)
Eliminazione di Ei:
Scansione fino a Ei-1
Link(Ei-1) = link(Ei)
49
Coda e pila
coda
pila
Dati ordinati in sequenza
Strutture dinamiche
Coda: meccanismo FIFO (first in, first out)
Inserzione in fondo
Eliminazione in cima
Pila: estrazione e inserzione dalla stessa parte (LIFO:
last in, first out)
Celle contigue di memoria
Per una coda, basta un array (se si conosce la dimensione
max.) e il puntatore al primo elemento
Per la pila, lista con inizio pila = inizio lista  no
scansione
Pila usata per gestione memoria dei sottoprogrammi 50
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?
51
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?
52
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?
53
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?
54
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?
55
Esercizio
Cosa contengono le variabili d, n, e i alla fine
dell’esecuzione del seguente programma? d=5.0, n=5, i=4
Dato un qualunque array a, cosa calcola il programma nella
variabile d?
d calcola la media degli elementi dell’array a
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;
}
56
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];
}
}
57
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;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
58