Come ragiona il computer - Dipartimento di Informatica

Come ragiona il
computer
Problemi e algoritmi
Il problema
Abbiamo un problema quando ci poniamo
un obiettivo da raggiungere e per
raggiungerlo dobbiamo mettere a punto
una strategia
„ Per risolvere il problema individuiamo una
sequenza di istruzioni elementari che,
partendo dai dati noti, arrivi a dare la
soluzione
„
2
I problemi tipici dell’informatica
Ricerca di informazioni
„ Elaborazione
„ Decisioni
„ Ottimizzazioni
„
3
1
Ricerca di informazione
„
Trovare il numero di telefono di una
persona, individuare il numero più piccolo
di una sequenza, stabile se una parola
precede alfabeticamente un’altra
4
Problemi di elaborazione di
informazioni
„
Calcolare il costo totale di un certo numero
di prodotti, trovare perimetro e area di una
figura geometria, …
5
Problemi di decisione
„
Decidere se per andare a scuola è più
conveniente il motorino, l’autobus, andare
a piedi, farsi accompagnare da un genitore
6
2
Problemi di ottimizzazione
„
Trovare tra tutte le soluzioni possibili del
problema quella che rende minimo un
certo fattore, per esempio scegliere il
mezzo di trasporto più economico per
andare a Parigi oppure quello con il quale
si impiega meno tempo
7
Risolvere un problema
„
„
„
„
„
„
Interpretare l’enunciato
Individuare i dati noti e quelli da trovare
Costruire un modello
Descrivere il procedimento risolutivo
Eseguire le operazioni stabilite nel processo
risolutivo
Verificare se i risultati ottenuti corrispondono alla
soluzione del problema reale
8
Risolvere un problema
Verifica dei risultati
Problema
Interpretazione
Esecuzione
Modello
algoritmo
9
3
Algoritmo
„
Un algoritmo è una sequenza finita di
operazioni elementari che porta alla
soluzione del problema.
10
Algoritmo
„
Serie di prescrizioni o istruzioni che
specifica l’insieme delle azioni da
compiere per poter risolvere un problema
… [Al-Khowarizmi,
„
IX sec.]
Regole per eseguire le 4 operazioni aritmetiche sui
numeri scritti in notazione decimale
11
Algoritmi: Requisiti
„
Finitezza
… Spaziale
… Temporale
„
Generalità
… Classe
di problemi
di definizione
… Dominio
„
„
„
Completezza
Non ambiguità
Eseguibilità
12
4
Diagramma di flusso o
diagrammi a blocchi
È uno metodi più comuni usati per la
rappresentazione di algoritmi.
„ Si presenta come un insieme di figure
geometriche collegate da frecce.
„
13
Inizio
„
Inizio
Tutti i diagrammi a
blocchi cominciano
con un’ellisse che
contiene la parola
inizio
14
Dati in ingresso
„
Dati in
ingresso
I dati in ingresso sono
i dati noti del
problema, quelli che
devono essere
elaborati per arrivare
alla soluzione
15
5
Operazioni
„
Operazioni
Le operazioni da
svolgere sui dati sono
racchiuse in rettangoli
16
Scelta
„
Vero o falso?
Quando si deve fare
una scelta tra due
possibilità si usa il
rombo
17
Dati in uscita
„
Dati in
uscita
I dati in uscita sono
quelli che si vuole
conoscere e
costituiscono il
risultato
dell’elaborazione
18
6
Fine
„
fine
Ogni diagramma di
flusso si conclude con
un’ellisse che
contiene la parola fine
19
Diagrammi di Flusso
Regole di Costruzione
„
Un solo blocco iniziale e un solo blocco finale
… Ogni
… Il
„
blocco è raggiungibile da quello iniziale
blocco finale è raggiungibile da ogni blocco
I blocchi sono in numero finito
… Ogni
blocco di azione (calcolo o ingresso/uscita) ha
una freccia entrante ed una uscente
… Ogni blocco di decisione ha una freccia entrante e
due uscenti
„
Ogni freccia parte da un blocco e termina in un
blocco o su un’altra freccia
20
Problema della chiave
„
Trovare in un mazzo
di chiavi quella che
apre il lucchetto
21
7
Programmazione Strutturata
„
Uso di schemi fondamentali
… Uso
„
„
di soli diagrammi strutturati
Configurazioni standard di blocchi elementari,
comuni a molti processi della vita quotidiana
Sviluppo per raffinamenti successivi
… Ogni
schema fondamentale ha un solo punto di
ingresso ed un solo punto di uscita
„
„
Sostituibile ad un blocco di azione
Nella sostituzione, si possono omettere i blocchi di
inizio e fine dello schema che si sta inserendo
22
Programmazione Strutturata
Schemi fondamentali
„
Sequenza
„
Selezione
… Concatenazione
… Scelta
„
„
di azioni
di azioni alternative
Dipendenza da una condizione
Iterazione
… Ripetizione
„
„
di una certa azione
Dati potenzialmente diversi
Dipendenza da una condizione
23
Programmazione Strutturata
Schemi fondamentali
„
Sequenza
„
Selezione
A1
A1
C
„
…
An
A2
C
A
Iterazione
C
A
A
C
24
8