Algoritmi - Parte 1

Informatica generale

Algoritmi

1 1

Soluzione di un problema … umana

Dati in ingresso: Descrivono il problema.

Elaborazione: Manipolazione dei dati di ingresso in modo da costruire la soluzione cercata.

Dati in uscita: Rappresentano la soluzione del problema.

2

Informatica Generale Maria De Marsico

Soluzione di un problema … con il computer

Dati di ingresso: Descrivono il problema.

Elaborazione: Manipolazione dei dati di ingresso in modo da costruire la soluzione cercata.

Dati in uscita: Rappresentano la soluzione del problema.

3

Informatica Generale Maria De Marsico 1

Soluzione di un problema

Input Output

Dati in ingresso Dati in elaborazione Dati in uscita

4

Informatica Generale Maria De Marsico

Un problema semplice (?)

• Riconoscere una persona tra la folla.

Dati in ingresso Dati in elaborazione Dati in uscita

Immagine della folla. Ricerca nell’immagine. SI, NO, chi è la persona riconosciuta. Confronto con dati noti.

• 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 ingresso Dati in elaborazione Dati in uscita

Dati etnografici, sociali, economici … Calcoli e statistiche. Tutti i dati.

• 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 ingresso Dati di elaborazione Dati di uscita

Immagine della folla. Ricerca nell’immagine. SI, NO, chi è la persona riconosciuta. Confronto con dati noti.

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