generalità
concetti di base
cosa significa informatica?

scienza dell’informazione


scienza dei computer (dall’inglese computer
science)


e l’informazione giornalistica?
per i progettisti di computer?
scienza per la rappresentazione e l’elaborazione
dell’informazione

e i computer?

ottobre 2002
meri esecutori
(c) Fabrizio d'Amore, 2002
2
informazione

dati di interesse


numeri, parole, simboli, testi, immagini,
suoni…
interessanti per
la consultazione
 la deduzione di novi dati (che siano deducibili…)

informatica = scienza per la rappresentazione e l’elaborazione dell’informazione
ottobre 2002
(c) Fabrizio d'Amore, 2002
3
rappresentazione dell’informazione

convenzione per
rappresentare tramite
simboli o parametri
fisici concetti astratti


simboli:
rappresentazione
digitale
parametri fisici:
rappresentazione
analogica
seven
informatica = scienza per la rappresentazione e l’elaborazione dell’informazione
ottobre 2002
(c) Fabrizio d'Amore, 2002
4
elaborazione dell’informazione

processo automatico che a partire da dati
in ingresso (input) produce dati in uscita
(output)

le regole che definiscono come costruire
l’output a partire dall’input costituiscono un
algoritmo

volto normalmente alla risoluzione di un
problema
ottobre
2002
informatica
(c) Fabrizio d'Amore, 2002
= scienza per la rappresentazione
e l’elaborazione dell’informazione5
concetto di problema

cosa è un problema?


risoluzione di un problema


descrizione di un contesto, di uno scenario
contesto + input → output
è necessario che l’output sia determinabile
(calcolabile) a partire dal contesto e
dall’input
ottobre 2002
(c) Fabrizio d'Amore, 2002
6
classe di problemi


insieme di problemi “simili”, definiti nello
stesso contesto che differiscono
essenzialmente nell’input
esempio:



contesto: “individuare su uno stradario il
percorso migliore fra due città”
input: “partenza = Roma, destinazione =
Milano”
output: “autostrada A1”
ottobre 2002
(c) Fabrizio d'Amore, 2002
7
istanze di problemi



classe di problemi + input = istanza di
problema
in genere il termine “problema” è usato in
modo ambiguo, talvolta per indicare classe
di problemi, talvolta per indicare istanza di
problema
esempio:


risoluzione di un’equazione di secondo grado
classe o istanza?
ottobre 2002
(c) Fabrizio d'Amore, 2002
8
tipi di problemi

decisionali


ammettono solamente una risposta: sì oppure no
di ottimizzazione

in un insieme di soluzioni ammissibili si vuole
individuare quale soddisfa meglio una determinata
proprietà

esempio: percorso Roma – Milano, proprietà di interesse:
distanza percorsa


ottobre 2002
una soluzione ammissibile è un qualunque percorso che
colleghi le due città
la soluzione ottimale è quella che minimizza la distanza
Roma – Milano
(c) Fabrizio d'Amore, 2002
9
sommario problemi
ottobre 2002
decisione
ottimizzazione
classe
√
√
istanza
√
√
(c) Fabrizio d'Amore, 2002
10
risoluzione dei problemi (1)

nella definizione di una classe di problemi
si specifica cosa deve essere calcolato
(una volta noto l’input)


in altre parole, data un’istanza di problema, è
perfettamente definito l’output del problema
(purché sia risolvibile e i dati siano sufficienti)
non viene invece fornito un metodo di
soluzione

dato l’input, come è possibile determinare
l’output?
ottobre 2002
(c) Fabrizio d'Amore, 2002
11
risoluzione di problemi (2)





analisi e comprensione delle specifiche
familiarità con la classe di problemi
individuazione di un insieme di strategie
ammissibili
scelta di un metodo
descrizione dettagliata del metodo
ottobre 2002
(c) Fabrizio d'Amore, 2002
12
risoluzione di problemi (3)

come mettere in pratica il metodo?


l’attuazione della procedura di risoluzione
può essere complessa
chi mette in pratica il metodo?

la descrizione dettagliata della procedura di
risoluzione non può essere indipendente
dall’attuatore
quanto è intelligente l’attuatore?
 quale grado di autonomia ha?
 sa interpretare il contesto?

ottobre 2002
(c) Fabrizio d'Amore, 2002
13
algoritmi


descrizione di una sequenza ordinata di passi
elementari che porta senza ambiguità alla
individuazione
della soluzione
di un
problema
da Ar al-Khwārazmī,
matematico
arabo
(IX
la sequenza
di passi,del
anche
se lunga,
deve
secolo) originario
Khwārazm
(Khiva)
essere
finita
che
per primo suggerì un metodo per


esistono
problemi
che non
ammettono nel
algoritmi
sommare
due numeri
rappresentati
risolutivi o che, in altre parole, non ammettono alcun
sistema numerico
Hindu
procedimento
risolutivo
che dia garanzia di
terminazione
di norma concepiti con riferimento a una classe
di problemi
ottobre 2002
(c) Fabrizio d'Amore, 2002
14
problema della capra,
del lupo e del cavolo
1.
2.
3.
4.
5.
6.
7.
porta
torna
porta
porta
porta
torna
porta
ottobre 2002
la capra sull’altra sponda
indietro
il cavolo sull’altra sponda
indietro la capra
il lupo sull’altra sponda
indietro
la capra sull’altra sponda
(c) Fabrizio d'Amore, 2002
15
qualità degli algoritmi

correttezza



output corretti in corrispondenza di input
ammissibili
quali output negli altri casi?
efficienza

uso efficace delle risorse
tempo
 spazio

ottobre 2002
(c) Fabrizio d'Amore, 2002
16
visione funzionale degli algoritmi
input
A1
A3 =
A1 + A2
output
input
A2
output
ottobre 2002
(c) Fabrizio d'Amore, 2002
A2
output
18
es: equazione
o
2
grado
ax  bx  c  0
2
 b  b  4ac
x
2a
2
ottobre 2002
(c) Fabrizio d'Amore, 2002
19
es: equazione
b
o
2
grado/2
*
b
-
√
*4
+
a
*
b
-
/
x1
c
a
ottobre 2002
(c) Fabrizio d'Amore, 2002
*2
20
ancora sulla visione funzionale

utile sia nell’approccio top-down, sia
bottom-up



top-down: decomposizione di un problema
complesso in sottoproblemi più semplici
bottom-up: riuso di soluzioni già disponibili
occorre un sistema per descrivere la
sequenza delle operazioni previste
ottobre 2002
(c) Fabrizio d'Amore, 2002
21
diagrammi o grafi di flusso
(flow charts)
start
I/O
stop
sottoprogramma
operazione
ottobre 2002
(c) Fabrizio d'Amore, 2002
test
selezione
22
diagrammi di flusso (esempio)
start
calcola
x2=(-b-r)/(2a)
output x1
input
a, b, c
calcola
x1=(-b + r)/(2a)
output x2
calcola
d = bb – 4ac
calcola
r = √d
end
ottobre 2002
se
d è d'Amore,
< 0??2002
(c) Fabrizio
23
esempio equazione 2° grado
start
calcola
x1=(-b + r)/(2a)
calcola
x2=(-b - r)/(2a)
input
a, b, c
calcola
r = √d
output
x1, x2
no
calcola
d = bb – 4ac
ottobre 2002
d<0?
sì
output
“no radici reali”
(c) Fabrizio d'Amore, 2002
end
24
descrizione di algoritmi

diagramma di flusso


pseudo-codice



quando l’algoritmo diviene complesse sono estesi e di
difficile comprensione/correzione
informale, ampiamente utillizzato
ha sostituito il diagramma di flusso negli ultimi venti
anni
codice

richiede la conoscenza di un linguaggio di
programmazione
ottobre 2002
(c) Fabrizio d'Amore, 2002
25
pseudo-codice
start
input(a, b, c)
d = bb – 4ac
if(d < 0)
output(“no radici reali”)
else
e = sqrt(d)
x1 = (-b + e) / (2a)
x2 = (-b – e) / (2a)
output(x1, x2)
stop
ottobre 2002
(c) Fabrizio d'Amore, 2002
26
radice quadrata

metodo numerico per il calcolo rapido della
radice quadrata di un reale non negativo r

metodo di Newton-Raphson

1 r
xn 1    xn 
2  xn


occorre criterio di arresto
 es., se xk 1  xk  
ottobre 2002
(c) Fabrizio d'Amore, 2002
27
radice quadrata (flow chart)
x =
(r/x + x)/2
x = 1
xprec = ∞
ε = 0.000001
xprec=x
sì
input(r)
ottobre 2002
|x-xprec|>ε?
(c) Fabrizio d'Amore, 2002
no
output x
28
radice quadrata (pseudo-codice)
start
input(r)
x=1 (ad esempio)
xprec = ∞
ε = 0.000001
while(|x-xprec| > ε)
xprec = x
x = (r/x + x)/2
output(x)
stop
ottobre 2002
(c) Fabrizio d'Amore, 2002
29