Fondazione San Benedetto
Liceo delle scienze applicate
Anno 2012-2013
Docente
Anna Carla Capodivento
Informatica vs Matematica
 Esempio: somma tra due numeri
 L’informatica è la scienza della rappresentazione e
dell’elaborazione dell’informazione
INFORmazione + autoMATICA
 Studio sistematico degli algoritmi che descrivono e trasformano
l’informazione
Algoritmi e Calcolatori
 È una descrizione completa e non ambigua di una procedura
risolutiva di un problema
 Esempio: Fare benzina alla macchina
 Computer: è un esecutore di algoritmi
 Programmi: sequenze di istruzioni in un linguaggio
 Esperto informatico: produce algoritmi e li codifica in
programmi
Problemi
 È una questione in base alla quale si devono trovare una o
più soluzioni partendo da elementi noti
 Strategia risolutiva è un insieme di passi da compiere
per giungere alla soluzione di un problema
 Soluzione: è l’obiettivo che vogliamo raggiungere
Esempio: biglietto ferroviario
Emettere un
biglietto
ferroviario
Strategia risolutiva
•
•
•
•
Dati iniziali
Stazione di partenza
Stazione di arrivo
Data e ora di partenza
Numero di persone in
partenza
Verifica dei risultati
Risultato finale
Strategia risolutiva
 Analisi del problema
Obiettivo
Stato iniziale
 Progettazione
Azioni
 Verifica della soluzione
Stato finale
Problem solving
 Indica l’insieme dei processi per individuare un metodo
per risolvere situazioni problematiche
Divide et impera
RISOLUZIONE
Stato iniziale
L’insieme dei fatti iniziali
è detto
DATI INIZIALI
NO
NO
Stato finale
Prodotto della soluzione
sono i
DATI FINALI
O
Strade scartate
Criterio di verifica
RISULTATI
Formulazione del problema
ATTENZIONE!!! Una cattiva formulazione compromette la
risoluzione
Riformulare correttamente il problema
1.
Individuare obiettivi evidenziando regole e dati impliciti
2. Eliminare i dettagli inutili e ambigui
3. Individuare il criterio di verifica
Astrazione del problema
 Astrazione è il procedimento mentale attraverso il quale
si sostituisce un insieme di oggetti con un concetto che li
descrive in base a proprietà comuni
 Esempio: insieme di automobili  concetto di
automobile
 Esempio: trovare il minimo tra 4, 8, 2  trovare il
minimo tra tre numeri A, B, C
Analisi
 Fornisce una breve descrizione di cosa si vuole fare
evidenziando:
 VINCOLI
 REQUISITI
(esempio X*Y)
 Area di interesse: (specifiche funzionali)
 Dati iniziali o Dati in ingresso  Istanza
 Dati finali o Dati in uscita
Il processo di analisi prende il nome di Problem setting
Cosa fare?
Problema 1: fare una telefonata
 Analisi del problema
Voglio chiamare un abbonato col telefono. Dopo aver composto il
numero può verificarsi che: 1. l’abbonato risponde 2. il telefono è
occupato o non risponde
 Specifiche funzionali
Dati iniziali
Numero da comporre
Dati finali
Messaggio «telefonata riuscita»
Messaggio «telefonata non riuscita»
Problema 2: trovare il maggiore tra due
numeri
 Analisi del problema
Voglio trovare il maggiore tra due numeri interi X e Y. Usiamo
una semplice sottrazione:
se X-Y > 0 il maggiore è X
se X-Y < 0 il maggiore è Y
se X-Y = 0 X e Y sono uguali
 Specifiche funzionali
Dati iniziali
Due numeri interi X e Y
Dati finali
X, se X-Y > 0
Y, se X-Y < 0
Problema 3: calcolare il prodotto tra due
numeri interi
 Analisi del problema
Voglio trovare il prodotto tra due numeri interi X e Y. Usiamo
l’addizione:
se Y = 0 il è prodotto è 0
se Y > 0 il prodotto è X + X + X + … + X (per Y volte)
 Specifiche funzionali
Dati iniziali
Due numeri interi X e Y
Dati finali
0, se Y = 0
X*Y, se Y > 0
Problema 4: trovare il massimo tra tre
numeri
 Analisi del problema
 Specifiche funzionali
Dati iniziali
Dati finali
Problema 5: cercare il numero di un
utente in un elenco telefonico
 Analisi del problema
 Specifiche funzionali
Dati iniziali
Dati finali
Modellizzazione del problema
 Modello è la rappresentazione semplificata della
situazione analizzata che evidenzi tutti gli elementi utili
alla risoluzione del problema
Realtà
Modello
interpretazione
Rappresentazione della realtà
Classificazione dei modelli
In base al loro uso:
 Descrittivi: riproducono la realtà senza presupporre l’uso
che ne verrà fatto (es. modelli grafici-tabellari)
 Predittivi: forniscono gli elementi necessari della realtà
di interesse per prevederne l’evoluzione
 Prescrittivi: impongono un comportamento particolare
in previsione dell’obiettivo da raggiungere
Classificazione dei modelli
In base alla loro natura:
 Analogici: forniscono una rappresentazione fedele della
realtà in scala ridotta (es. modellini di auto)
 Simbolici o matematici: forniscono una
rappresentazione astratta della realtà a cui si riferiscono
mediante un’equazione
 Logici: forniscono un insieme di regole logico-funzionali
che, se seguite, permettono di emulare integralmente la
realtà
Algoritmi
A quale categoria appartengono gli algoritmi?
MODELLI LOGICI
C
B
A
D
S
Studio di un problema
PROBLEMA: «studiamo una popolazione virtuale
composta da persone che vivono all’infinito»
Tempo
Ammalat
i
T0
0
T1
10
T2
20
T3
40
T4
Tempo
80
Dtn = Dt1 * 2n-1
Dtn = Dt1 * (2-0.3)n-1
Ammalati
Morti
T0
0
0
T1
10
0
T2
(10*2)-3=17
10*0.3=3
T3
(17*2)-5.1=28.9
17*0.3=5.1
T4
(28.9*2)-8.7=49.1
28.9*0.3=8.7
Somma di lunghezze
Somma le seguenti lunghezze: 3.5 km, 23 hm, 125 cm, 59 mm
1. (59+1250+2300000+3500000) mm = 5801309 mm
2. (3,5+2,3+0,00123+0,00059) km
= 5,801309 km
Strategia risolutiva
Strategia efficace  funziona
Strategia efficiente  dispendio minimo di risorse
Metodi
1.
Conoscere il tema oggetto del problema
2. Procedere per tentativi
3. Servirsi dell’esperienza e di metodi già sperimentati
4. Ripercorrere il cammino all’indietro
5. Scindere il problema in sottoproblemi
Approccio composto
L’approccio migliore è sempre quello composto!!
Divide et impera
Torta Sacher
Preparare la pasta
Preparare la
marmellata di
albicocche
Preparare le
farciture
Preparare il
cioccolato fuso
Farcire la torta
Preparare la
panna
Guarnire la torta
Risolutore ed esecutore
Risolutore: la persona che definisce e costruisce la strategia
risolutiva per un dato problema.
Esecutore: colui che esegue le azioni descritte dal risolutore
Problema
Calcolare la lunghezza della diagonale di un rettangolo conoscendo le
sue dimensioni
D?
a
b
Strategia risolutiva
• Prendere la misura della base
• Prendere la misura dell’altezza
• Calcolare il quadrato della base
• Calcolare il quadrato dell’altezza
• Sommare i due quadrati
• Calcolare la radice quadrata
• Visualizzare il risultato
Dati Iniziali
Base = 5
Altezza = 12
Esecutore
25
144
169
13
Dati Finali
13
Computer come esecutore
 Linguaggio che è in grado di interpretare
 Insieme di azioni che è in grado di compiere
 Insieme di regole che associano linguaggio e azioni
Risolutore
Programma
Prendi la base
Prendi l’altezza
….
Traduzione in linguaggio di
programmazione
Dati Iniziali
Esecutore
Verifica dei risultati
Capra, cavolo e lupo
Un contadino deve trasportare al di là del fiume il suo lupo, la sua capra e il
suo cavolo. Ha a disposizione una barca che può trasportare solo lui e uno
solo degli altri. Deve stare attento che la capra non mangi il cavolo e il lupo
la capra.
Strategia risolutiva
• Inizio strategia
• Porta la capra sull’altra sponda
• Torna indietro
• Porta il cavolo sull’altra sponda
• Porta la capra indietro
• Porta il lupo sull’altra sponda
• Torna indietro
• Porta la capra sull’altra sponda
• Fine strategia
ax + b = 0
ax + b = 0  ax = -b  x = -b/a
Strategia risolutiva
• Inizio strategia risolutiva
• Acquisisci i valori di a e b
• Calcola-b
• Dividi -b per a e assegna il risultato a x
• Visualizza il valore di x
• Fine strategia risolutiva
Azione
 Soggetto (detto esecutore)
 Oggetto
 Trasformazione
Es. Daniela mangia una mela
 Daniela prende una mela;
 Daniela sbuccia la mela;
 Daniela taglia a fette la mela;
 Daniela mastica la mela.
Le azioni devono avvenire in sequenza
Algoritmo
Istruzione è un’azione elementare in quanto non può
essere scomposta in altre azioni più semplici.
Algoritmo è un procedimento risolutivo che descrive
passo per passo il procedimento che risolve un
problema costruendo una successione ordinata e finita
di istruzioni.
Caratteristiche di un algoritmo
 Finito
 Univoco o non ambiguo o preciso
 Generale
 Completo
 Osservabile nei risultati
 Deterministico
Efficienza
Un algoritmo si dice efficiente quando:
 è corretto, cioè produce il risultato atteso;
 è veloce in termini di tempo impiegato per produrre il
risultato;
 è parsimonioso in termini di risorse allocate per produrre
il risultato.
Prelievo dal Bancomat
1. Verificare che il bancomat funzioni
correttamente
Non è in servizio
È in servizio
9. Cercare un altro bancomat
2. Introdurre la carta nel lettore
3. Digitare il codice segreto
4. Verificare che il codice sia
corretto
Non è corretto
8. Operazione terminata
È corretto
5. Digitare l’importo da prelevare
6. Prelevare le banconote
7. Ritirare la carta dal bancomat
I diagrammi a blocchi
INIZIO
CONDIZ
IONE
FINE
INPUT
AZIONE
OUTPUT
ORDINE D’ESECUZIONE
REGOLE
INIZIO
FINE
AZIONE
INPUT
CONDIZ
IONE
OUTPUT
Equazione di II grado

Maggiore tra 3 numeri
a, b, c