Algoritmi - Parte 1
Anteprima
ESTRATTO DOCUMENTO
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
I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher valeria0186 di informazioni apprese con la frequenza delle lezioni di Informatica Generale e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università La Sapienza - Uniroma1 o del prof Costa Luciano.
Acquista con carta o conto PayPal
Scarica il file tutte le volte che vuoi
Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato