Algoritmo - Liceo Galileo Galilei

Indice
•
•
•
•
•
•
•
•
L’origine del nome e la definizione
Esempi di Agoritmo
Algoritmi e informatica
Le proprietà degli algoritmi
Differenza fra ideazione ed esecuzione di un algoritmo
La descrizione di un algoritmo
Definizione e tipi di iterazione
La scrittura di un programma e la sua “traduzione”
Algoritmo: l’ origine del nome e definizione
L’origine del nome
• Deriva dal nome del matematico Al-Khwarizmi:
nato a Baghdad nel 780 circa
• E’ un importante matematico Arabo. Tra le altre cose
ha scritto un trattato sulla numerazione Indo-Araba.
• La traduzione latina del testo Algoritmi de numero Indorum
ha dato origine alla parola algoritmo
• Il lavoro descrive il sistema numerico Hindu basato sulla notazione
posizionale dei numeri 1, 2, 3, 4, 5, 6, 7, 8, 9, e 0.
• Il primo uso dello zero come segnaposto nella notazione è
probabilmente dovuto al suo lavoro
Algoritmo: l’ origine del nome e definizione
Una prima definizione
Un algoritmo (detto anche procedura, prescrizione, processo, routine,
metodo) è un insieme di regole (dette anche direttive o istruzioni)
che, eseguite secondo un ordine prestabilito, consentono di trovare il
risultato di un problema a partire dai dati in ingresso
Indice
•
•
•
•
•
•
•
•
L’origine del nome e la definizione
Esempi di Agoritmo
Algoritmi e informatica
Le proprietà degli algoritmi
Differenza fra ideazione ed esecuzione di un algoritmo
La descrizione di un algoritmo
Definizione e tipi di iterazione
La scrittura di un programma e la sua “traduzione”
Esempi di algoritmo
Un primo esempio: il problema dei due secchi
• Sono presenti due secchi con capacità volumetrica rispettivamente
di 3 e 4 litri.
• Determinare le operazioni necessarie per far si che il primo secchio
(da 3 litri) sia riempito con 2 litri.
• Possiamo agire sui due secchi attraverso le seguenti operazioni :
 riempire completamente un secchio
 svuotarlo completamente
 travasare una certa quantità di liquido da un secchio all’altro
Esempi di algoritmo
Un primo esempio: il problema dei due secchi
• La soluzione del problema
4L
3L
Esempi di algoritmo
Un secondo esempio: cucinare la torta pasqualina
• Dobbiamo partire da degli ingredienti.
• Dobbiamo seguire una ricetta ed eseguire delle azioni ben precise
• Possiamo agire sugli ingredienti per ottenere una buona torta
Esempi di algoritmo
La soluzione della torta pasqualina
titolo
Torta pasqualina
ingredienti
Per la pasta:
farina bianca, 400 gr. olio extravergine d'oliva, 2 cucchiai
sale, q.b.
acqua, q.b.
Per il ripieno:
bieta, 500 gr.
ricotta, 200 gr.
burro fuso, 50 gr.
uova, 6
maggiorana fresca, 1 cucchiaio
parmigiano grattugiato, 4 cucchiai
4 cucchiai di pecorino grattugiato
latte, 1 bicchiere
olio extravergine di oliva, 1 bicchiere
sale e pepe, q.b.
preparazione
-Lavorate la farina con l'olio e il sale.
-Unite man mano acqua tiepida quanto basta per ottenere un impasto omogeneo e morbido.
-Ricoprite con un panno umido.
-Fate riposare.
-Spianate 6 sfoglie sottili con un mattarello.
-Mondate la bieta.
-Sciacquatela.
-Cucinatela in una casseruola con poco sale.
-Cuocere a fiamma dolce con il coperchio, per 6 minuti.
-Terminata la cottura strizzatela bene.
-Sminuzzatela finemente e depositatela in una terina grande.
-Amalgamate la ricotta sbriciolata.
-Incorporate 2 uova intere, il parmigiano grattugiato, metà pecorino e la maggiorana.
-Allungate con del latte se l'impasto è troppo solido.
-Ricoprite con una sfoglia uno stampo apribile, unto d'olio.
-Pennellate anche la sfoglia con dell'olio.
-Sovrapporne a una a una, le altre due, oliandole sempre con olio tranne l'ultima.
-Stendere la farcia e con un cucchiaio formare 4 incavature in cui si porranno le uova intere, crude.
-Sistemare di sale.
-Insaporire con il resto del pecorino.
-Chiudere con una sfoglia di pasta.
-Sovrapporvi le altre due, sempre spennellando con il pennello la superficie tra una e l'altra.
-Sigillare il tutto con i ritagli di pasta.
-Ungere la superficie con olio e con dell'uovo intero sbattuto.
-Bucherellare la superficie con uno stuzzicadenti o una forchetta.
-Fate attenzione a non rompere le uova.
-Infornate in forno già caldo, a 200°C. per 40 minuti circa.
Indice
•
•
•
•
•
•
•
•
L’origine del nome e la definizione
Esempi di Agoritmo
Algoritmi e informatica
Le proprietà degli algoritmi
Differenza fra ideazione ed esecuzione di un algoritmo
La descrizione di un algoritmo
Definizione e tipi di iterazione
La scrittura di un programma e la sua “traduzione”
Algoritmi e informatica
Algoritmo e Informatica
• Perchè l’informatica è interessata agli algoritmi?
• Che relazione c’è fra informatica e algoritmi?
• L’informatica ci mette a disposizione macchine che sono in grado di
eseguire istruzioni
Se un algoritmo è un
insieme di istruzioni che
quando eseguite portano
alla soluzione di un
problema, e le macchine
informatiche sono in
grado
di
eseguire
istruzioni
Possiamo pensare di fare
eseguire
le
istruzioni
dell’algoritmo alle macchine
informatiche. In questo modo
possiamo pensare che se
forniamo in ingresso alla
macchina i dati del problema,
questa ci fornirà in uscita la
soluzione del problema stesso.
Algoritmi e informatica
Una seconda definizione
• Il calcolatore è un Esecutore di Azioni Elementari.
• Affinche` la risoluzione di un problema possa essere realizzata
attraverso l’uso del calcolatore, tale processo deve poter essere
definito come sequenza di azioni elementari
• Possiamo quindi ora dare una seconda definizione di algoritmo:
Un Algoritmo indica la sequenza di passi (istruzioni) elementari che
quando eseguiti da un esecutore automatico portano alla soluzione di
un qualsiasi problema computazionale di carattere generale
Algoritmi e informatica
Una seconda definizione
• una sequenza di passi: quindi non un insieme in un ordine
qualsiasi, ma una sequenza, cioè ogni istruzione deve essere nel
posto giusto, con una precisa istruzione che la precede e una che
la segue.
• elementari: il concetto di elementare va riferito rispetto all’esecutore
dell’algoritmo. Siccome per un programmatore l’esecutore di un
algoritmo è il computer, allora elementari significa istruzioni che
possono essere eseguite immediatamente dal computer (come ad
esempio fare la somma di due numeri), mentre non sono elementari
quelle istruzioni che per essere eseguite hanno bisogno di essere
scomposte in istruzioni più semplici (come ad esempio calcolare
l’area di un rettangolo)
• quando eseguiti: l’algoritmo è una descrizione statica della
soluzione, deve essere eseguito per portare a una soluzione
effettiva
Algoritmi e informatica
Una seconda definizione
• esecutore automatico: una macchina astratta capace di eseguire le
azioni specificate dall'algoritmo
• portano alla soluzione: sembra ovvio ma uno dei requisiti di un
algoritmo è che deve portare alla soluzione di un problema. Un
algoritmo che non porti alla soluzione di un problema è inutile
• di carattere generale: un algoritmo dipende dai valori in ingresso e
in questo modo può risolvere tutti i casi di un problema. Se ad
esempio avessimo l’algoritmo per il calcolo dell’area di un
rettangolo di base 3 e altezza 4 questo sarebbe utile solo nel caso
specifico in cui interessa l’area di quel particolare rettangolo,
mentre è ovviamente molto più interessante avere un algoritmo che
calcoli l’area di qualsiasi rettangolo, dati i valori della base e
dell’altezza
Indice
•
•
•
•
•
•
•
•
L’origine del nome e la definizione
Esempi di Agoritmo
Algoritmi e informatica
Le proprietà degli algoritmi
Differenza fra ideazione ed esecuzione di un algoritmo
La descrizione di un algoritmo
Definizione e tipi di iterazione
La scrittura di un programma e la sua “traduzione”
Le proprietà degli algoritmi
Le proprietà degli algoritmi
• Eseguibilità: ogni azione deve essere eseguibile dall'esecutore in
un tempo finito
• Non-ambiguità:
ogni azione
interpretabile dall'esecutore
deve
essere
univocamente
• Finitezza: il numero totale di azioni eseguite, per ogni insieme di
dati di ingresso, deve essere finito .
Le proprietà degli algoritmi
E possibilmente….
• Efficiente:
• In termini di tempo di esecuzione. Il tempo
in informatica non si misura in secondi ma in
numero di azioni (o istruzioni) che devono
esssere eseguite arrivare alla soluzione del
problema. Minori sono le istruzioni, più
efficiente è l’algoritmo.
• In termini di memoria occupata La
memoria è una risorsa importante, meno
memoria occupo (meno variabili uso, e più
piccole sono le variabili), migliore sarà
l’algoritmo
Indice
•
•
•
•
•
•
•
•
L’origine del nome e la definizione
Esempi di Agoritmo
Algoritmi e informatica
Le proprietà degli algoritmi
Differenza fra ideazione ed esecuzione di un algoritmo
La descrizione di un algoritmo
Definizione e tipi di iterazione
La scrittura di un programma e la sua “traduzione”
Differenza fra ideazione ed esecuzione di un
algoritmo
• Esiste una grandissima differenza fra ideazione ed esecuzione
di un algoritmo:
• L’ideazione di un algoritmo è compito del
programmatore. Egli deve prima analizzare i
requisiti del problema ed i dati che ha a
disposizione, e partendo da questi deve
creare l’algoritmo ottimale che porta alla
soluzione del problema.
Differenza fra ideazione ed esecuzione di un
algoritmo
• Non esiste «un algoritmo per risolvere un algoritmo». Gli strumenti
che un programmatore ha a disposizione per risolvere un algoritmo
sono:
La propria
esperienza
La proprie
conoscenze
La propria
intuizione
Differenza fra ideazione ed esecuzione di un
algoritmo
• L’esecuzione di un algoritmo invece è lasciata al calcolatore
• Il calcolatore è una macchina che non
capisce quello che sta facendo.
Esegue «bovinamente» le istruzioni in
maniera ordinata.
• Pertanto la verifica della correttezza di un algoritmo è lasciata in tutto e
per tutto al programmatore.
Indice
•
•
•
•
•
•
•
•
L’origine del nome e la definizione
Esempi di Agoritmo
Algoritmi e informatica
Le proprietà degli algoritmi
Differenza fra ideazione ed esecuzione di un algoritmo
La descrizione di un algoritmo
Definizione e tipi di iterazione
La scrittura di un programma e la sua “traduzione”
Le descrizione di un algoritmo
Descrizione
Come possiamo descrivere un algoritmo?
• A parole, dando una descrizione di ogni
singolo passo da eseguire
 Aspetti positivi: E’ il linguaggio a noi
più vicino perché è quello che usiamo
quotidianamente
 Aspetti negativi: La lingua usata può
essere diversa.
ambiguità
Ci
può
essere
Le descrizione di un algoritmo
Descrizione
• Con i diagrammi di flusso, ovvero «disegnando» i vari passi
 Aspetti positivi: E’ un linguaggio
universale capito da tutti e non
ambiguo, è intuitivo e semplice da
capire
 Aspetti negativi: Non è compreso da
un calcolatore
Le descrizione di un algoritmo
Descrizione
• Attraverso un linguaggio di programmazione, scrivendo i
passaggi in un nuovo linguaggio non ambiguo e universale
 Aspetti
positivi: può essere
interpretato e quindi eseguito da
un calcolatore
 Aspetti negativi: non è né semplice
e né intuitivo
Le descrizione di un algoritmo
Descrizione
• Esistono diversi linguaggi di programmazione che sono più o meno
adatti al contesto operativo in cui si opera
 PHP per lavorare con i database
 Pascal, C, per lavorare in ambito scientifico
 Javascript e ASP per lavorare in ambito web
Le descrizione di un algoritmo
I diagrammi di flusso (flowchart)
• Questo metodo è stato messo a punto negli Stati Uniti da Larry
Constantine ed Edward Yourdon a metà degli anni ’80.
• Utilizza figure geometriche che racchiudono le singole istruzioni
• Sono collegate tra loro con freccie e simboli in modo da rendere
possibile seguire la sequenza con cui devono essere eseguite le
istruzioni
• Offre una visione globale e intuitiva del problema
• Esso presenta, rispetto alla descrizione verbale, una maggiore
concisione, una minore possibilità di ambiguità e una comprensione
più immediata
Le descrizione di un algoritmo
Esempio di diagramma per la soluzione di ogni problema
Le descrizione di un algoritmo
I blocchi del diagramma a flussi
• Blocchi di inizio-fine
Inizio/fine
• Blocchi di esecuzione
Fai
qualcosa
• Blocco di condizione
• Blocco di ingresso-uscita
Vero ?
Scrivi/
leggi
Indice
•
•
•
•
•
•
•
•
L’origine del nome e la definizione
Esempi di Agoritmo
Algoritmi e informatica
Le proprietà degli algoritmi
Differenza fra ideazione ed esecuzione di un algoritmo
La descrizione di un algoritmo
Definizione e tipi di iterazione
La scrittura di un programma e la sua “traduzione”
Definizione e tipi di iterazione
Definizione di iterazione
• L’iterazione (o ciclo) è una particolare struttura di controllo che ci
permette di ripetere ciclicamente, o «iterare», un blocco di istruzioni
sotto il controllo di un test.
• Gli elementi che costituiscono un ciclo sono pertanto 2:
 La condizone di permanenza nel ciclo, detto anche test di controllo
 Il corpo del ciclo
• E’ fondamentale che nella costruzione di un ciclo il programmatore
stia molto attento ad impostare la condizione di permanenza.
Questa condizione deve essere posta in modo tale che prima o poi
si possa uscire dal ciclo, altrimenti si entra nel cosiddetto «loop
infinito» (ciclo infinito) e l’algoritmo non giunge mai a conclusione.
Definizione e tipi di iterazione
I quattro tipi possibili di iterazione
• A seconda delle nostre esigenze possiamo utilizzare 4 possibili tipi
di iterazione:
• Precondizionale per vero
• Precondizionale per falso
• Postcondizionale per vero
• Postcondizionale per falso
Definizione e tipi di iterazione
L’iterazione precondizionale per vero
• Il test di controllo viene posto prima dell’esecuzione del corpo, e
prende pertanto il nome di test d’ingresso del ciclo
• Si verifica prima il test di ingresso. Se la risposta è VERA allora si
entra nel ramo contenente il corpo del ciclo, se invece è FALSA si
prosegue nel ramo che NON contiene il ciclo
• Potrebbe anche succedere che il ciclo non venga MAI eseguito.
Infatti se la prima volta che eseguo il test di ingresso questo dà esito
negativo, esco subito dal ciclo senza esservi mai entrato neanche
una volta
Definizione e tipi di iterazione
L’iterazione precondizionale per vero, diagramma a blocchi
• Il diagramma a blocchi di un ciclo precondizionale per vero avrà la
forma generale presentata sotto
Definizione e tipi di iterazione
L’iterazione precondizionale per falso
• Il test di controllo viene posto prima dell’esecuzione del corpo, e
prende pertanto il nome di test d’ingresso del ciclo
• Si verifica prima il test di ingresso. Se la risposta è FALSA allora si
entra nel ramo contenente il corpo del ciclo, se invece è VERA si
prosegue nel ramo che NON contiene il ciclo
• Potrebbe anche succedere che il ciclo non venga MAI eseguito.
Infatti se la prima volta che eseguo il test di ingresso questo da esito
positivo, esco subito dal ciclo senza esservi mai entrato neanche
una volta
Definizione e tipi di iterazione
L’iterazione precondizionale per falso, diagramma a blocchi
• Il diagramma a blocchi di un ciclo precondizionale per falso avrà la
forma generale presentata sotto
Definizione e tipi di iterazione
L’iterazione postcondizionale per vero
• Il test di controllo viene posto dopo l’esecuzione del corpo, e prende
pertanto il nome di test di uscita dal ciclo
• Si esegue prima il ciclo e poi verifico il test di permanenza. Se la
risposta è VERA allora si segue il ramo che porta ad eseguire
nuovamente il corpo del ciclo, se invece è FALSA si prosegue nel
ramo che esce dal ciclo
• Con questo titpo di iterazione, sono sicuro di eseguire il corpo del
ciclo sempre almeno una volta
Definizione e tipi di iterazione
L’iterazione postcondizionale per vero, diagramma a blocchi
• Il diagramma a blocchi di un ciclo postcondizionale per vero avrà la
forma generale presentata sotto
Definizione e tipi di iterazione
L’iterazione postcondizionale per falso
• Il test di controllo viene posto dopo l’esecuzione del corpo, e prende
pertanto il nome di test di uscita dal ciclo
• Si esegue prima il ciclo e poi verifico il test di permanenza. Se la
risposta è FALSA allora si segue il ramo che porta ad eseguire
nuovamente il corpo del ciclo, se invece è VERA si prosegue nel
ramo che esce dal ciclo
• Con questo titpo di iterazione, sono sicuro di eseguire il corpo del
ciclo sempre almeno una volta
Definizione e tipi di iterazione
L’iterazione postcondizionale per falso, diagramma a blocchi
• Il diagramma a blocchi di un ciclo postcondizionale per falso avrà la
forma generale presentata sotto
Indice
•
•
•
•
•
•
•
•
L’origine del nome e la definizione
Esempi di Agoritmo
Algoritmi e informatica
Le proprietà degli algoritmi
Differenza fra ideazione ed esecuzione di un algoritmo
La descrizione di un algoritmo
Definizione e tipi di iterazione
La scrittura di un programma e la sua “traduzione”
Le scrittura di un programma e la sua “traduzione”
La scrittura del file sorgente
• La scrittura di un programma avviene utilizzando un linguaggio di
programmazione (noi vedremo il Linguaggio C).
• Il linguaggio di programmazione è un linguaggio di alto livello, che
richiama il linguaggio parlato (solitamente l’inglese) e che è
compreso e utilizzato dal programmatore ma non può essere
compreso dal computer, che invece utilizza solamente il linguaggio
macchina (formato da 0 e 1)
• Il programma originale prende il nome di «programma sorgente» nel
nostro caso con estensione .c (o .cpp)
• Per poter scrivere questo programma è sufficiente un qualsiasi
editor di testo (anche notepad o word vanno bene). Noi utilizzeremo
l’editor dell’Ambiente Dev C++
Le scrittura di un programma e la sua “traduzione”
La scrittura del file sorgente
• La scrittura di un programma avviene utilizzando un linguaggio di
programmazione (noi vedremo il Linguaggio C).
• Il linguaggio di programmazione è un linguaggio di alto livello, che
richiama il linguaggio parlato (solitamente l’inglese) e che è
compreso e utilizzato dal programmatore ma non può essere
compreso dal computer, che invece utilizza solamente il linguaggio
macchina (formato da 0 e 1)
• Il programma originale prende il nome di «programma sorgente» nel
nostro caso con estensione .c (o .cpp)
• Per poter scrivere questo programma è sufficiente un qualsiasi
editor di testo (anche notepad o word vanno bene). Noi utilizzeremo
l’editor dell’Ambiente Dev C++
Le scrittura di un programma e la sua “traduzione”
La prima “traduzione” in file oggetto
• Questo file sorgente deve essere «tradotto» in un file oggetto (con
estensione .o
• Chi effettua questa traduzione è il «Compilatore»
• I file oggetto sono la traduzione in linguaggio macchina delle
funzioni scritte in linguaggio C. In questa fase si traducono le
funzioni in linguaggio macchina e si rilevano errori sintattici
eventualmente presenti nel file sorgente. Generalmente le funzioni
codificate nel file sorgente utilizzano altre funzioni non definite nello
stesso file (perch`e le abbiamo scritte in un altro files sorgente o
perch`e fanno parte delle funzioni standard del C). I files oggetto
prodotti quindi non sono eseguibili
• L’ambiente Dev C++ dispone della funzionalità di Compilazione
Le scrittura di un programma e la sua “traduzione”
Il Linker e la creazione del file eseguibile
• Più files oggetto vengono «linkati» tra di loro per produrre il files
eseguibile, ovvero il programma vero e proprio. Compito del linker `e
(grosso modo) quello di mettere insieme il codice oggetto di tutte le
funzioni per produrre un programma. Le varie funzioni possono
essere scritte da noi oppure far parte delle «librerie» standard fornite
dal linguaggio C.
• In questa fase vengono rilevati degli errori relativi alle chiamate di
funzione: il linker si accorge se viene chiamata una funazione che
non esiste o se viene invocata una funzione con parametri diversi da
quelli che ci si attende.
• Il Linker crea quindi un file eseguibile (estensione .exe) che può
essere quindi caricato nella RAM e eseguito dal calcolatore
• L’ambiente Dev C++ dispone della funzionalità di Linker
Le scrittura di un programma e la sua “traduzione”
Estensione
.c
Sorgente C
Sorgente C
Sorgente C
Compilatore
Estensione
.o
Codice Oggetto
Codice Oggetto
Linker
Estensione
.exe
Codice eseguibile
Codice Oggetto
Librerie
Le scrittura di un programma e la sua “traduzione”
L’ambiente Dev C++
• Per la creazione dei programmi noi utilizzeremo l’IDE Dev C++
• IDE è un acronimo che sta per
Integrated
Development
Environment
• Il Dev C++ ci offre tutti gli strumenti necessari per sviluppare un
programma. Esso dispone di:
• Un ambiente di Editor molto «user friendly»
• Un compilatore
• Un Linker
• Un Debugger