01 Algoritmi e Calcolatore - polimi.it
20
Daniele Loiacono Algoritmi e (cenni sul) calcolatore Fondamenti di Informatica
Transcript of 01 Algoritmi e Calcolatore - polimi.it
Daniele Loiacono
Algoritmi e (cenni sul) calcolatoreFondamenti di Informatica
Daniele Loiacono
Cos’è l’informatica?
q È la scienza che si occupa della rappresentazionedell’informazione e della sua elaborazione e gestione
Si occupa dell’informazione, che fa parte di ogni attività umana, e non riguarda solo i calcolatoriSi occupa della rappresentazione, cioè di come modellare la realtà astraendo gli aspetti importanti da quelli trascurabiliSi occupa di elaborare e gestire l’informazione, cioè di trasformarla opportunamente per raggiungere lo scopo desiderato
q È lo studio sistematico degli algoritmi che descrivono e trasformano l’informazione: la loro teoria, analisi, progetto, efficienza, realizzazione e applicazione
Daniele Loiacono
Daniele Loiacono
Cos’è un algoritmo?
q Una sequenza finita di operazioni elementari tali che:siano comprensibili ad uno specifico esecutore possano essere eseguite senza ambiguitàpermettano di risolvere uno specifico problema
q Es. istruzioni IKEApassi elementarisenza ambiguitàraggiungono lo scopo
Daniele Loiacono
Un esempio
q Come si calcola la radice quadrata di x?
q Definisce la radice quadrata ma non come si calcolaq Invece…
1. x ß radicando2. y ß (x+1)/23. Se y2 è abbastanza vicino ad x, y è la radice cercata4. Altrimenti,
y ß 0.5 * (y + x/y)5. Ricomincia dal punto 3
Daniele Loiacono
Un esempio
q Come si calcola la radice quadrata di x?
q Definisce la radice quadrata ma non come si calcolaq Invece…
1. x ß radicando2. y ß (x+1)/23. Se y2 è abbastanza vicino ad x, y è la radice cercata4. Altrimenti,
y ß 0.5 * (y + x/y)5. Ricomincia dal punto 3 VARIABILI
Daniele Loiacono
Un esempio
q Come si calcola la radice quadrata di x?
q Definisce la radice quadrata ma non come si calcolaq Invece…
1. x ß radicando2. y ß (x+1)/23. Se y2 è abbastanza vicino ad x, y è la radice cercata4. Altrimenti,
y ß 0.5 * (y + x/y)5. Ricomincia dal punto 3 OPERAZIONI
ARITMETICHE
Daniele Loiacono
Un esempio
q Come si calcola la radice quadrata di x?
q Definisce la radice quadrata ma non come si calcolaq Invece…
1. x ß radicando2. y ß (x+1)/23. Se y2 è abbastanza vicino ad x, y è la radice cercata4. Altrimenti,
y ß 0.5 * (y + x/y)5. Ricomincia dal punto 3 I/O
Daniele Loiacono
Un esempio
q Come si calcola la radice quadrata di x?
q Definisce la radice quadrata ma non come si calcolaq Invece…
1. x ß radicando2. y ß (x+1)/23. Se y2 è abbastanza vicino ad x, y è la radice cercata4. Altrimenti,
y ß 0.5 * (y + x/y)5. Ricomincia dal punto 3 DECISIONI
Daniele Loiacono
Un altro esempio
q Cercare, in una lista ordinata, il codice IATA corrispondentead un dato areoporto
q Cercare, in una lista ordinata, a che aeroporto corrispondeun certo codice IATA
IATA
Daniele Loiacono
Un ultimo esempio
q Come si contano le persone in una stanza?q Proviamo qualcosa di completamente diverso
1. Alzatevi tutti in piedi2. Ognuno di voi vale 13. Trova un compagno/a ancora in piedi
a) sommate i vostri due valori, il risultato èil vostro nuovo valore
b) uno dei due si deve sedere e l’altro deve restare in piedi4. Se al punto 3. non avete trovato un compagno, il vosto
valore non cambia e dovete restare in piedi5. Ricominciate dal punto 3, finchè non resta in piedi una sola
persona in tutta la stanza6. Il valore dell’ultima persona rimasta in piedi è il numero di
persone presenti nella stanza
Daniele Loiacono
Dal problema alla soluzione automatica
q Ci occuperemo di problemi che riguardano la gestione e l’elaborazione dell’informazione
q Vedremo come passare dalla specifica di un problema alla sua soluzione automatica attraverso l’uso di un calcolatore
La specifica è una descrizione semi-formale del problemaÈ necessario passare dalla specifica ad un algoritmo che risolve il problema datoInfine affinché l’algoritmo trovato sia eseguibile dal calcolatore dovrà essere definito in un linguaggio comprensibile al calcolatore stesso
Daniele Loiacono
Dalla specifica all’algoritmo
q Il processo che porta dalla specifica di un problema ad un algoritmo che lo risolve non è automatico e non è facile da formalizzare
La specifica spesso può essere poco chiara o ambiguaLa scrittura di un algoritmo richiede uno sforzo creativo
q Come si impara a progettare un algoritmo?Utilizzare un approccio incrementaleRealizzarlo per raffinamenti successiviFare molta pratica
q QualitàCorrettezza: risolve il problema e prende in considerazione tutti i casi possibiliEfficienza: usa con parsimonia le risorse (es. tempo)
q La correttezza è fondamentale ma difficile da verificare, l’efficienza è desiderabile e facile da misurare
Daniele Loiacono
Come si formalizza un algoritmo?
q Una buon processo di progettazione si conclude con la definizione precisa e concisa dell’algoritmo ideato
q Alcuni linguaggi semi-formali spesso usatiPseudo-codice
se A > 0 allora A = A + 1 altrimenti A = 0
Diagrammi di flusso (o schemi a blocchi)
• Blocco di input dati
• Blocchi di inizio/fine dell’esecuzione
• Blocco esecutivo
• Blocco condizionale
• Blocco di output dati
• Flusso di controllo delle operazioni
leggi…
…test…?
inizio fine
scrivi…
assegnamento
…test… ?
Daniele Loiacono
1. Leggi N ed M2. MIN = il minimo tra N ed M3. X = 1 4. MCD = 15. Fintantoché X < MIN
I. X = X + 1II. se X divide sia N che M, allora MCD = X
6. Scrivi MCD
Esempio: M.C.D. di due naturali positivi
Daniele Loiacono
Leggere i valori delle coordinate dei vertici
Triangolo degenere?
Calcolare la lunghezza dei lati
Calcolare il perimetro come somma delle lunghezze
Vuoi continuare?
sì
no
no
q Date le coordinate di tre punti, riconoscere se sono i vertici di un triangolo non degenere, e nel caso calcolarne il perimetro
sì
Scrivi: “Triangolodegenere”
INIZIO
FINE
Scrivi il valore del perimetro
Esempio: perimetro di un triangolo
Daniele Loiacono
Come è fatto un calcolatore?
Daniele Loiacono
La macchina di Von Neumann
Unità diElaborazione(CPU)
MemoriaCentrale (MM)
InterfacciaPeriferica P1
InterfacciaPeriferica P2
Bus di sistema
Esecuzione istruzioni Memoria di lavoroMemoria di massa,
stampante, terminale…
Collegamento
Daniele Loiacono
La memoria centrale (MM)
0
1
1023
Dati e
istruzioni
Indirizzo cella
Daniele Loiacono
Registro istruzionecorrente (CIR)
Registro dati (DR)Registro indirizzi
(AR)
Registro contatoredi programma (PC)
Registro di stato (SR)
Registrointerruzioni (INTR)
A
B
Unità di controllo(CU)
Clock
Unitàaritmeticologica(ALU)
Bus di sistema
CPU
