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