Algoritmi - Parte 1

Informatica Generale Maria De Marsico

Un problema semplice (?)

• Riconoscere una persona tra la folla
• Dati in ingresso: SI, NO, chi
• Ricerca nell'immagine
• Immagine della persona
• Confronto con dati noti
• Folla riconosciuta

Noi umani siamo abbastanza bravi... e il computer?

Informatica Generale Maria De Marsico

Un problema "difficile"

• Elaborare i dati del censimento (... in un grande paese!)
• Dati in ingresso: Dati etnografici
• Calcoli e statistiche
• Tutti i dati sociali, economici...

Noi umani siamo bravi... ma lenti! E il computer?

Informatica Generale Maria De Marsico 2

Soluzione = ...

Attenzione! Saper risolvere un problema non significa sempre essere capaci di spiegare esattamente come questo avviene

Dati in ingresso: SI, NO, chi

Ricerca nell'immagine

Immagine della persona

Confronto con dati noti

Folla riconosciuta

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...

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 computer9Informatica Generale Maria De Marsico 3

Soluzione di un problema

Dati inDati in Algoritmo uscitaingressocodifica decodificaDati perDati del l'utenteproblema 10Informatica 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.

• cognome e nome dell'autore
• titolo del libro
• numero scaffale (S) e posizione nello scaffale (P)

Informatica Generale

Maria De Marsico

Il 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

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...

...l'utente potrebbe non sapere come si effettua

ricerca nello schedario

• ricordiamo: tutte le operazioni specificate devono essere 'elementari' per chi esegue l'algoritmo
• Se non lo sono è possibile spiegarle a parte mediante un sotto-algoritmo

14Informatica Generale Maria De Marsico

Soluzione di un problema

Dati in

Dati in Algoritmo uscitaingresso

Sotto-Algoritmo 15Informatica Generale Maria De Marsico 5

• Sotto-algoritmo
• Soluzione di un problema che si trova di frequente come componente di problemi più complessi
• Procedura di uso frequente che può essere inclusa in altre procedure
• Meccanismo di scatole cinesi - sono scatole di diversa grandezza che possono essere chiuse le une dentro le altre: la più grande contiene quella immediatamente più piccola, che ne contiene un'altra di dimensioni ancora più ridotte e così via. Una volta che sono state messe le une nelle altre, tali scatole appaiono come un unico oggetto.
• Un algoritmo può

Sotto-algoritmo di ricerca

• Un sotto-algoritmo per "insegnare" al computer a cercare in uno schedario (in qualsiasi schedario con lo stesso tipo di schede!):
1. Apri il classificatore
2. Prendi la prima scheda
3. Confronta il campo autore e titolo con quelli cercati
4. Se sono uguali, allora la ricerca è terminata, restituisci la scheda ed esci, altrimenti prendi la scheda successiva e vai al passo 3
5. Se le schede sono finite, allora il libro cercato non esiste, restituisci un messaggio di errore ed esci

Sotto-algoritmo di ricerca

• ...4. Se sono uguali, allora la ricerca è terminata, restituisci la scheda ed esci, altrimenti prendi la scheda successiva e vai al passo 3...

Cosa succede alla fine del passo 4 se non trovo più schede e provo comunque ad andare al passo 3 ??

Generale Maria De Marsico 6

Sotto-algoritmo di ricerca

• Un sotto-algoritmo per cercare in uno schedario:
1. Apri il classificatore
2. Prendi la prima scheda
3. Confronta il campo autore e titolo con quelli cercati
4. Se sono uguali, allora la ricerca è terminata, esci, altrimenti prendi la scheda successiva e vai al passo 3
5. Se le schede sono finite, allora il libro cercato non esiste, restituisci un messaggio di errore

Informatica Generale Maria De Marsico

Sotto-algoritmo di ricerca

• Un sotto-algoritmo per cercare in uno schedario:
1. Apri il classificatore
2. Prendi la prima scheda
3. Confronta il campo autore e titolo con quelli cercati
4. Se sono uguali, allora la ricerca è terminata, esci, restituisci la scheda
5. Se le schede sono finite, allora il libro cercato non esiste, restituisci un messaggio di errore

Informatica Generale Maria De Marsico

Sotto-algoritmo di ricerca

• Un sotto-algoritmo per cercare in uno schedario:
1. Apri il classificatore
2. Prendi la prima scheda
3. Confronta il campo autore e titolo con quelli cercati
4. Se sono uguali, allora la ricerca è terminata, esci, restituisci la scheda
5. Se le schede sono finite, allora il libro cercato non esiste, restituisci un messaggio di errore

ricerca è terminata, restituisci la scheda ed esci

Se (le schede sono finite) allora il libro cercato non esiste, restituisci un messaggio di errore ed esci, altrimenti prendi la scheda successiva e vai al passo 3

Informatica Generale Maria De Marsico

Le strutture di controllo

• La struttura di controllo condizionale

1. Apri il classificatore
2. Prendi la prima scheda
3. Confronta il campo autore e titolo con quelli cercati
4. Se (sono uguali), allora la ricerca è terminata, restituisci la scheda ed esci
5. Se (le schede sono finite) allora il libro cercato non esiste, restituisci un messaggio di errore ed esci, altrimenti prendi la scheda successiva e vai al passo 3

(...) specifica una condizione o una combinazione di condizioni (ricordiamo AND, OR e NOT)

Informatica Generale Maria De Marsico 8