R 255 G 211 B 8 R 255 G 175 B 0 R 127 G 16 B 162 R 163 G 166 B 173 R 104 G 113 B 122 R 234 G 234 B...

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









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

4L3L

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, 6maggiorana fresca, 1 cucchiaioparmigiano grattugiato, 4 cucchiai4 cucchiai di pecorino grattugiatolatte, 1 bicchiereolio extravergine di oliva, 1 bicchieresale 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









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.


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



• 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



• 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









Le proprietà degli algoritmi


• Eseguibilità: ogni azione deve essere eseguibile dall'esecutore in un tempo finito

• Non-ambiguità: ogni azione deve essere univocamente interpretabile dall'esecutore

• Finitezza: il numero totale di azioni eseguite, per ogni insieme di dati di ingresso, deve essere finito .


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









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.


• Non esiste «un algoritmo per risolvere un algoritmo». Gli strumenti che un programmatore ha a disposizione per risolvere un algoritmo sono:

La propria intuizione

La propria esperienza

La proprie conoscenze


• 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









Le descrizione di un algoritmo

Descrizione

Come possiamo descrivere un algoritmo?

• A parole, dando una descrizione di ogni singolo passo da eseguire

Aspetti negativi: La lingua usata può essere diversa. Ci può essere ambiguità

Aspetti positivi: E’ il linguaggio a noi più vicino perché è quello che usiamo quotidianamente


Descrizione

• Con i diagrammi di flusso, ovvero «disegnando» i vari passi

Aspetti negativi: Non è compreso da un calcolatore

Aspetti positivi: E’ un linguaggio universale capito da tutti e non ambiguo, è intuitivo e semplice da capire


Descrizione

• Attraverso un linguaggio di programmazione, scrivendo i passaggi in un nuovo linguaggio non ambiguo e universale

Aspetti negativi: non è né semplice e né intuitivo

Aspetti positivi: può essere interpretato e quindi eseguito da un calcolatore


Descrizione

• Esistono diversi linguaggi di programmazione che sono più o meno adatti al contesto operativo in cui si opera

Pascal, C, per lavorare in ambito scientifico

PHP per lavorare con i database

Javascript e ASP per lavorare in ambito web


I diagrammi di flusso (flowchart)

• Utilizza figure geometriche che racchiudono le singole istruzioni

• Offre una visione globale e intuitiva del problema

• Sono collegate tra loro con freccie e simboli in modo da rendere possibile seguire la sequenza con cui devono essere eseguite le istruzioni

• Questo metodo è stato messo a punto negli Stati Uniti da Larry Constantine ed Edward Yourdon a metà degli anni ’80.

• Esso presenta, rispetto alla descrizione verbale, una maggiore concisione, una minore possibilità di ambiguità e una comprensione più immediata


Esempio di diagramma per la soluzione di ogni problema


I blocchi del diagramma a flussi

• Blocchi di esecuzione

• Blocco di ingresso-uscita

• Blocco di condizione

• Blocchi di inizio-fine

Fai qualcosa

Inizio/fine

Vero ?

Scrivi/ leggi

Indice









Definizione e tipi di iterazione

Definizione di iterazione

• Gli elementi che costituiscono un ciclo sono pertanto 2:La condizone di permanenza nel ciclo, detto anche test di controlloIl corpo del ciclo

• 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.

• 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.


I quattro tipi possibili di iterazione

• Precondizionale per vero

• A seconda delle nostre esigenze possiamo utilizzare 4 possibili tipi di iterazione:

• Precondizionale per falso

• Postcondizionale per vero

• Postcondizionale per falso


L’iterazione precondizionale per vero

• 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

• Il test di controllo viene posto prima dell’esecuzione del corpo, e prende pertanto il nome di test d’ingresso del 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


L’iterazione precondizionale per vero, diagramma a blocchi

• Il diagramma a blocchi di un ciclo precondizionale per vero avrà la forma generale presentata sotto


L’iterazione precondizionale per falso

• 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

• Il test di controllo viene posto prima dell’esecuzione del corpo, e prende pertanto il nome di test d’ingresso del 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


L’iterazione precondizionale per falso, diagramma a blocchi

• Il diagramma a blocchi di un ciclo precondizionale per falso avrà la forma generale presentata sotto


L’iterazione postcondizionale per vero

• 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

• Il test di controllo viene posto dopo l’esecuzione del corpo, e prende pertanto il nome di test di uscita dal ciclo

• Con questo titpo di iterazione, sono sicuro di eseguire il corpo del ciclo sempre almeno una volta


L’iterazione postcondizionale per vero, diagramma a blocchi

• Il diagramma a blocchi di un ciclo postcondizionale per vero avrà la forma generale presentata sotto


L’iterazione postcondizionale per falso

• 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

• Il test di controllo viene posto dopo l’esecuzione del corpo, e prende pertanto il nome di test di uscita dal ciclo

• Con questo titpo di iterazione, sono sicuro di eseguire il corpo del ciclo sempre almeno una volta


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









Le scrittura di un programma e la sua “traduzione”

La scrittura del file sorgente

• 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)

• La scrittura di un programma avviene utilizzando un linguaggio di programmazione (noi vedremo il Linguaggio C).

• 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++


La prima “traduzione” in file oggetto

• 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

• Questo file sorgente deve essere «tradotto» in un file oggetto (con estensione .o

• L’ambiente Dev C++ dispone della funzionalità di Compilazione


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.

• L’ambiente Dev C++ dispone della funzionalità di Linker

• 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


Sorgente C

Compilatore

Linker

Codice eseguibileEstensione

.exe

Sorgente C Sorgente C

Codice Oggetto Codice Oggetto Codice Oggetto

Librerie

Estensione

.o

Estensione

.c


L’ambiente Dev C++

• Per la creazione dei programmi noi utilizzeremo l’IDE Dev C++

• Un ambiente di Editor molto «user friendly»

• 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 compilatore

• Un Linker

• Un Debugger

R 255 G 211 B 8 R 255 G 175 B 0 R 127 G 16 B 162 R 163 G 166 B 173 R 104 G 113 B 122 R 234 G 234 B...

Documents

Transcript of R 255 G 211 B 8 R 255 G 175 B 0 R 127 G 16 B 162 R 163 G 166 B 173 R 104 G 113 B 122 R 234 G 234 B...