Algoritmi - Parte 1

Soluzione di un problema

Input Output

Dati in

Dati in Elaborazione uscita

ingresso 4

Informatica Generale Maria De Marsico

Un problema semplice (?)

• riconoscere una persona tra la folla Dati in

Dati in Elaborazione uscita

ingresso SI, NO, chi

Ricerca nell’immagine

Immagine della è la persona

Confronto con dati noti

folla riconosciuta

• noi umani siamo abbastanza bravi … e il computer ?

5

Informatica Generale Maria De Marsico

Un problema “difficile”

• elaborare i dati del censimento (… in un grande

paese!) Dati in

Dati in Elaborazione uscita

ingresso Dati etnografici,

Calcoli e statistiche

Tutti i dati sociali, economici …

• noi umani siamo bravi … ma lenti! …e il computer ?

6

Informatica Generale Maria De Marsico 2

Soluzione = … … …

Attenzione!

Saper risolvere un problema non significa sempre essere

capaci di spiegare esattamente come questo avviene

Dati di

Dati di Elaborazione uscita

ingresso SI, NO, chi

Ricerca nell’immagine

Immagine della è la persona

Confronto con dati noti

folla riconosciuta

7

Informatica Generale Maria De Marsico

Il computer intelligente ?

• Perchè il computer esegua “automaticamente” un compito …

• dobbiamo esprimere i dati in maniera comprensibile al

computer (codifica!) …

• scomporre la soluzione in passi elementari che il calcolatore è

in grado di effettuare (confrontare due numeri, eseguire

semplici operazioni aritmetiche) …

• … e descriverli accuratamente con un linguaggio che il

computer è in grado di comprendere

• Attenzione! Il modo di arrivare alla soluzione dobbiamo

trovarlo noi!!

• Lo stesso vale se vogliamo far eseguire un compito a noi ben

noto ad un’altra persona non esperta … 8

Informatica Generale Maria De Marsico

Algoritmi e programmi

Algoritmo (dal nome del matematico persiano Abu

Ja’far Mohammed ibn Musà al-Khowarizmi):

• una sequenza finita di passi non ambigui

• che trasforma sempre i dati iniziali nel risultato finale

• che utilizza un insieme finito di azioni elementari che

possono essere comprese ed eseguite anche frequentemente

e ripetutamente da un opportuno esecutore

• che prevede tutte le possibili evoluzioni del procedimento

• che è in grado di risolvere tutti i problemi di un certo tipo

Programma:

• specifica di un algoritmo utilizzando un linguaggio non

ambiguo e direttamente comprensibile dal computer

9

Informatica Generale Maria De Marsico 3

Soluzione di un problema

Dati in

Dati in Algoritmo uscita

ingresso

codifica decodifica

Dati per

Dati del l’utente

problema 10

Informatica Generale Maria De Marsico

Dal problema all’algoritmo:

un esempio

• Ricerca di un libro in biblioteca

• I libri sono disposti sugli scaffali

• La posizione di ogni libro è fissata dalle due coordinate

(S,P) dove

• S è il numero dello scaffale

• P è la posizione all’interno dello scaffale

• La biblioteca ha uno schedario con una scheda per ogni

libro. Ogni scheda contiene, nell’ordine i campi:

• cognome e nome dell’autore

• titolo del libro

• numero scaffale (S) e posizione nello scaffale (P)

• Le schede sono ordinate in ordine alfabetico in base al

campo autore 11

Informatica Generale Maria De Marsico

Il problema

• Problema:

Un utente vuole prendere in prestito un libro in

biblioteca di cui conosce autore e titolo

• Vogliamo specificare un algoritmo che spieghi

all’utente della biblioteca come fare 12

Informatica Generale Maria De Marsico 4

Dal problema all’algoritmo

• Una prima versione dell’algoritmo per il prestito:

1. Decidi il libro da richiedere

2. Cerca la scheda nello schedario

3. Leggi la posizione (S,P)

4. Accedi alla posizione (S,P)

5. Preleva il libro e compila la scheda di prestito

• Non tutte le operazioni sono elementari … 13

Informatica Generale Maria De Marsico

Dal problema all’algoritmo

• … l’utente potrebbe non sapere come si effettua

la ricerca nello schedario

• ricordiamo: tutte le operazioni specificate devono

essere ‘elementari’ per chi esegue l’algoritmo

• Se non lo sono è possibile spiegarle a parte per

mezzo di un sotto-algoritmo 14

Informatica Generale Maria De Marsico

Soluzione di un problema

Dati in

Dati in Algoritmo uscita

ingresso Sotto-

Algoritmo 15

Informatica Generale Maria De Marsico 5