L`elaborazione dell`informazione

INFORMATICA GENERALE E BASI
DI DATI PER ARCHIVI
AUDIOVISIVI (PRIMO MODULO)
Claudio Piciarelli
A.A. 2013/2014
Lezione 4
L’elaborazione dell’informazione
Elaborazione dell’informazione
Abbiamo visto fino ad ora come rappresentare
l’informazione
Ora vogliamo studiare come elaborarla per
risolvere problemi
L’informatica consiste in larga parte in
questo: trovare soluzioni a problemi,
assicurandosi che tali soluzioni possano
essere attuate da una macchina
« Sono il signor Wolf, risolvo problemi »
Modello black box
Di fronte a molti problemi, ci limitiamo a considerare
la procedura risolutiva come una scatola chiusa, che
prende dei dati in input e restituisce degli output
Dati in
input
ELABORAZIONE
Dati in
output
(soluzione)
Noi vogliamo scoperchiare la scatola e scoprire cosa
c’è dentro!
Esempi
Due numeri
x, y
Calcolo della somma
ingredienti
Ricetta
x+y
torta
Esempio: come fare una torta di mele
Input: gli ingredienti
Output: la torta
Elaborazione: la ricetta!
Input
Output
Descrivere la fase di elaborazione
Ingredienti:
250 grammi di farina
150 grammi di zucchero
150 grammi di burro
3 uova
mezza bustina di lievito per dolci
1 bicchierino di latte
4 mele
zucchero a velo quanto basta
In un recipiente capiente montare le uova con lo zucchero con il battitore
elettrico, quindi unire la farina, il burro fuso, il bicchierino di latte e per ultimo il
lievito ed amalgamare bene. Disporre il composto in una teglia per dolci
precedentemente imburrata, sbucciare le mele, tagliarle a fettine sottili e
disporle con molta cura a raggera sopra al composto. Infornare a 180 gradi
per circa 35 minuti; lasciar raffreddare la torta e cospargerla di zucchero a
velo prima di servirla.
Istruttore ed esecutore
Abbiamo quindi un istruttore, che sa come risolvere il
problema, che esprime la sua conoscenza sotto forma
di sequenza di operazioni elementari che un
esecutore è in grado di eseguire
cuoco
Sa fare una torta
ricetta
io
So fare alcune operazioni
elementari (accendere il
forno, sbattere le uova…)
Problemi
La ricetta può essere facilmente seguita da un
essere umano, nonostante presenti numerosi
problemi…
Ambiguità della lingua italiana. Cosa vuol dire «montare le
uova»?
Misure imprecise: quanto grande è il bicchierino di latte?
Cosa significa «zucchero a velo quanto basta»?
Informazioni incomplete: che forma deve avere la teglia?
Casi non contemplati: cosa devo fare se le uova sono
marce?
Descrivere la fase di elaborazione
Descrivere la fase di elaborazione (la procedura
risolutiva del nostro problema) consiste quindi
nell’elencare una serie di operazioni elementari da
effettuare in sequenza (la ricetta)
Tuttavia siamo abituati a soluzioni incomplete e
imprecise, e dobbiamo fare ricorso alle nostre
conoscenze per colmare queste lacune
Con un computer dovremo essere più rigorosi!
Elaborazione dell’informazione
OBIETTIVO:
Esprimere la soluzione di un problema in termini di
operazioni elementari, in maniera corretta, completa
e non ambigua, affinché sia possibile automatizzarla
(farla eseguire da un computer!)
Algoritmi e programmi
ALGORITMO: Sistema di regole e procedure di
calcolo ben definite che portano alla soluzione di un
problema con un numero finito di operazioni
PROGRAMMA: descrizione di un algoritmo in un
linguaggio comprensibile dall’elaboratore
Istruttore ed esecutore / 2
Torniamo allo schema istruttore/esecutore: per
risolvere un problema all’elaboratore dobbiamo
quindi esprimere la soluzione come sequenza di
operazioni elementari eseguibili dall’elaboratore
io
programma
computer
Ma questa volta nel programma non possono esserci ambiguità
Dal problema al programma / 1
Fase 1: analisi del problema
Si studia il problema, lo si formula in maniera
chiara e rigorosa, senza ambiguità. Si identificano
gli input possibili e gli output attesi.
Dal problema al programma / 2
Fase 2: definizione dell’algoritmo
Si trova una procedura che risolva il problema e la si
descrive sotto forma di algoritmo, ovvero come
sequenza finita di operazioni elementari.
Non esiste un modo automatico per definire gli
algoritmi. Non a caso Donald Knuth ha intitolato il
suo lavoro più importante «The Art of Computer
Programming». Inventare algoritmi è un’arte che
richiede talento, ingegno, intuizione e tanta fantasia!
Dal problema al programma / 3
Fase 3: scrittura del programma
I passi identificati a livello astratto dall’algoritmo
vengono concretizzati come sequenza di istruzioni
interpretabili da un elaboratore.
Dal problema al programma
ANALISI
ALGORITMO
PROGRAMMA
Il linguaggio del computer
Ma qual è questo linguaggio compreso dal computer?
Il processore (CPU) di un computer è il suo «cervello».
E’ in grado di eseguire poche operazioni semplici (ad
es. sommare due numeri)
Ogni operazione è codificata da una sequenza di bit
Il linguaggio macchina specifica i codici (opcodes) di
ciascuna istruzione
Un programma eseguibile quindi non è altro che una lunga sequenza di bit che
identifica le operazioni da eseguire e i dati su cui vanno applicate
Linguaggio assembly
Nessuno scrive programmi direttamente in linguaggio
macchina. Si possono tuttavia assegnare dei nomi
mnemonici ai diversi codici (linguaggio assembly) per
facilitare la scrittura dei programmi. Un programma,
detto assemblatore, si occupa di tradurre i comandi
assembly negli equivalenti codici macchina
Linguaggio assembly
.data
first: .asciiz "Inserisci il numero: "
answ1: .asciiz "Fattoriale: "
.text
.globl main
main:
#calcola N! con N dato da tastiera
li $v0, 4
#4=print_string
la $a0, first
#caricamento della stringa first come parametro
syscall
#display della stringa first
li $v0, 5
#5=read_int
syscall
#lettura del valore N
move $s0, $v0
#salvataggio del valore N in $s0
li $v0, 4
#4=print_string
la $a0, answ1
#caricamento della stringa answ1 come parametro
syscall
#display della stringa answ1
li $s1, 1
#inizializzazione del risultato (0! = 1)
loop:
#ciclo di calcolo del fattoriale
beqz $s0,results
# se s0 vale 0, allora il ciclo e' finito
mul $s1, $s1, $s0
#aggiornamento del fattoriale
addi $s0, $s0, -1
#decremento della variabile da moltiplicare
b loop
#salto al loop
results:
li $v0, 1
#1=print_int
move $a0, $s1
#caricamento di N! come parametro
syscall
#display di N!
li $v0, 10
#10=exit
syscall
#uscita con successo
Calcolo del
fattoriale di un
numero nel
linguaggio
assembly del
processore MIPS
Linguaggi di alto livello
Oggigiorno è raro scrivere programmi in linguaggio
assembly
Più spesso si usa un linguaggio di alto livello, che in
seguito viene compilato (tradotto in assembly ed infine
in linguaggio macchina) mediante un programma detto
compilatore
In alternativa il linguaggio può essere interpretato (la
fase di traduzione in linguaggio macchina viene
eseguita «al volo» durante l’esecuzione del
programma)
Esistono numerosi linguaggi di alto livello: C, C++,
Pascal, Fortran, C#, Java, Python, Ruby…
Linguaggi di alto livello
#include <stdio.h>
int main(void){
int intero, fattoriale;
intero = -1; fattoriale = 1;
while (intero < 0) {
printf("Inserire un intero non negativo: ");
scanf("%d", &intero);
}
while (intero > 0) {
fattoriale = intero * fattoriale;
--intero;
}
printf("Il fattoriale è %d\n", fattoriale);
return (0);
}
Calcolo del fattoriale di un numero nel linguaggio C
Dal problema al programma
Schema aggiornato
PROGRAMMA scritto in
un linguaggio di alto
livello
compilatore
ANALISI
ALGORITMO
PROGRAMMA scritto in
linguaggio assembly
assembler
PROGRAMMA
ESEGUIBILE (sequenza di
opcodes)
Come descrivere gli algoritmi
Abbiamo dunque visto che un algoritmo è una
sequenza astratta di istruzioni per risolvere un
problema, mentre un programma è la sua
«concretizzazione» eseguibile da un computer
Come possiamo descrivere un algoritmo? Abbiamo
bisogno di:
Variabili
Un
modo per descrivere la sequenza di operazioni
Problemi vs. istanze di problemi
Distinguiamo tra problemi, generici, espressi in termini
di alcuni parametri…
…dalle singole istanze di quei problemi, in cui i
parametri sono fissati
Problema: sommare due numeri
Istanze del problema: sommare 3 e 4, 19 e 7, 21 e
1…
Variabili
Poiché un algoritmo generalmente esprime il metodo
risolutivo per un problema, e non per singole istanze
di problemi, si fa largo uso di variabili
Una variabile è un «contenitore per dati» con un
nome
Esempio:
Leggi
in input due numeri x e y
Calcola r x + y
Scrivi r
Variabili
Nell’esempio di prima, x, y ed r sono variabili
I valori contenuti nelle variabili possono essere usati in
espressioni (ad es. x + y)
Oppure è possibile assegnare un nuovo valore ad
una variabile ( r 5 )
Grazie alle variabili un algoritmo può risolvere un
problema generico, piuttosto che una sua istanza (i
parametri sono memorizzati nelle variabili)
Diagrammi di flusso
La sequenza di passi di cui si compone l’algoritmo è
espressa mediante un diagramma che evidenzia il
flusso di esecuzione (diagramma di flusso)
Componenti dei digrammi di flusso:
inizio
fine
Diagrammi di flusso
Operazioni di
input/output
Chiedono all’utente di
immettere dei dati, o
visualizzano dei dati
all’utente
Selezione a due vie
Azione
Cambia il flusso di esecuzione
dell’algoritmo a seconda che
la risposta ad una certa
domanda sia «sì» oppure
«no»
Esegui un’azione
elementare
Esempio – somma di due numeri
Es: trova il massimo tra due numeri
Pseudocodice
Un altro modo per descrivere gli algoritmi è usare uno
pseudocodice
Simile ad un linguaggio di programmazione reale, ma
astrae dai dettagli meno importanti
leggi x e y
se x > y allora
scrivi «il max è x»
altrimenti
se x = y allora
scrivi «sono uguali»
altrimenti
scrivi «il max è y»
fine
fine
Pseudocodice per trovare il
massimo tra due numeri
Correttezza degli algoritmi
Un buon algoritmo deve funzionare correttamente
su tutti gli input possibili
Esempio: cosa non va in questo codice per il calcolo
del fattoriale?
leggi n (intero non negativo)
ris n
finché n > 1 ripeti
nn-1
ris ris x n
fine
Complessità degli algoritmi
Esistono modi diversi per risolvere lo stesso problema.
Es: calcolare la somma dei primi n numeri interi
Complessità degli algoritmi
Il primo programma esegue un ciclo per un numero
di volte pari a n
Il secondo sfrutta la formula di Gauss e risolve lo
stesso problema con una sola operazione,
indipendentemente da n
Il secondo algoritmo è più efficiente (complessità
minore)
La complessità di un problema è quella
dell’algoritmo più efficiente che lo risolve
Algoritmi di ordinamento
Provate ad ordinare in modo crescente questa
sequenza di numeri …
{ 5, 2, 7, 1, 12, 4, 10, 3, 6 }
Che algoritmo avete usato?
Algoritmi di ordinamento
Probabilmente avete usato uno dei due algoritmi
più comuni per l’uomo:
Insertion sort: prendo un elemento e lo inserisco
nella posizione corretta tra i dati che ho già
ordinato. Ripeto passando all’elemento successivo
Selection sort: cerco l’elemento più piccolo e lo
sposto all’inizio. Ripeto l’operazione sui dati restanti
Insertion Sort
5,
2,
7,
1, 12,
4, 10,
3,
6
5,
2,
7,
1, 12,
4, 10,
3,
6
2,
5,
7,
1, 12,
4, 10,
3,
6
2,
5,
7,
1, 12,
4, 10,
3,
6
1,
2,
5,
7, 12,
4, 10,
3,
6
1,
2,
5,
7, 12,
4, 10,
3,
6
1,
2,
4,
5,
7, 12, 10,
3,
6
1,
2,
4,
5,
7, 10, 12,
3,
6
1,
2,
3,
4,
5,
7, 10, 12,
6
1,
2,
3,
4,
5,
6,
7, 10, 12
Selection sort
5,
2,
7,
1, 12,
4,
0,
3,
6
1,
2,
5,
7, 12,
4, 10,
3,
6
1,
2,
5,
7, 12,
4, 10,
3,
6
1,
2,
3,
5,
7, 12,
4, 10,
6
1,
2,
3,
4,
5,
7, 12, 10,
6
1,
2,
3,
4,
5,
7, 12, 10,
6
1,
2,
3,
4,
5,
6,
7, 12, 10
1,
2,
3,
4,
5,
6,
7, 12, 10
1,
2,
3,
4,
5,
6,
7, 10, 12
Vedi anche esempi visuali su http://sorting.at/
Insertion sort - flowchart
Selection sort – flowchart
Insertion sort - pseudocodice
for j 2 to length[A] do
1
2
key A[j]
3
// Insert A[j] into the sorted sequence A[1..j-1]
4
i j - 1
5
while i > 0 and A[i] > key do
6
A[i + 1] A[i]
7
i i - 1
8
A[i + 1] key
Selection sort - pseudocodice
for i 1 to length[A] do
1
2
3
4
5
6
// A[min_idx]: smallest elem. in A[ i..end ]
7
swap A[i] min_idx i
for j i + 1 to length[A] do
if A[j] < A[min_idx]
min_idx j
A[min_idx]
Insertion sort – codice C
Complessità di insertion sort
Sia n la lunghezza del nostro array
Al primo ciclo dobbiamo fare al massimo uno
spostamento…
Al secondo al massimo due…
Allo n-simo ciclo al massimo n
Numero di operazioni: al max 1 + 2 + 3 + … + n
Complessità ݊ଶ