Elementi di Informatica Claudia Raibulet
raibulet@disco.unimib.it
Elementi di Informatica Claudia Raibulet
raibulet@disco.unimib.it
Rappresentazione di un algoritmo Diagrammi di flusso
Sono grafici che permettono di esprimere un algoritmo in modo schematico e intuitivo
Per rappresentare un algoritmo occorre rappresentare:
Passi necessari
Loro corretta sequenza
I diagrammi di flusso sono una descrizione piu’ efficace e meno ambigua di una descrizione a parole
Diagrammi di flusso
Sottoalgoritmo I blocchi base vengono collegati tramite “frecce” che collegano un’azione alla successiva all’interno dell’algoritmo Operazione I/0 Trasferimento di informazioni Azione (istruz.) Esecuzione di calcoli Cond. Si No Assunzione di decisioni START STOP Si costruiscono a partire da un certo numero di blocchi base che rappresentano le operazioni elementari ed i costrutti di controllo
Rappresentazione di un algoritmo
Istruzione 4 Istruzione 1 Istruzione 2 Sequenza Selezione condizione falsa Iterazione condizione vera condizione Istruzione 3 SE condizione allora altrimenti Istruzione 5 Istruzione 6 START STOP
Diagrammi di flusso
Realizzare i diagrammi di flusso per i seguenti algoritmi:
Trovare il massimo fra 2 numeri interi positivi x e y
Trovare il massimo fra 3 numeri interi positivi x, y e z
Trovare il massimo fra N numeri interi positivi
Massimo fra due numeri interi positivi X e Y
START STOP Leggi i valori di X e Y D = X - Y D > 0 Si No Scrivi massimo e’ X Scrivi massimo e’ Y
Massimo fra N numeri interi positivi
START STOP Leggi il valore di K K > 0 Si k > 1 Si No Leggi i primi due
numeri in X e Y M = MAX (X,Y) K = K-2 No Leggi un altro numero in X Non e’ possibile
calcolare il massimo k == 0 Si No Leggi il valore di X Il massimo e’ X M = MAX (X,Y) K = K-1 No No Il massimo e’ M
Esercizio
Si chiede di realizzare il diagramma di flusso dell’algoritmo che risolve il prodotto di due numeri col metodo delle addizioni successive.
Soluzione
Si chiami X il valore del moltiplicando ed Y il valore del moltiplicatore e sia M il risultato.
Si inizializza il valore M a 0
Si ripetono le seguenti operazioni fintanto che Y e’ diverso da 0:
Si sommi il valore di X al valore di M e si chiami ancora il risultato M (M=M+X)
Si sottraga 1 dal valore di Y, e si chiami Y ancora il risultato (Y=Y-1)
Sia M il risultato del prodotto
Esercizio
Si chiede di rappresentare con un diagramma di flusso l’algoritmo che effettua la somma di N numeri interi.
Origine della parola “algoritmo”
Da Muhammad ibn Muza, detto al-Khowarizmi, un matematico arabo-persiano (825 d.c.) a cui è attribuita l’invenzione di un insieme di precise regole di calcolo per le quattro operazioni.
In latino Algorismus: una procedura per risolvere un problema matematico in un numero finito di passi che implicano frequenti ripetizioni di un'operazione.
Concetto di algoritmo
Algoritmo = sequenza di passi, definiti con precisione, che portano alla realizzazione di un compito.
In mathematics and computing, an algorithm is a procedure (a finite set of well-defined instructions) for accomplishing some task which, given an initial state, will terminate in a defined end-state [Wikipedia].
Calcolatori – esecutori di algoritmi
Caratteristiche di un algoritmo
Un insieme finito di prescrizioni (istruzioni) che da’ luogo ad una sequenza finita di operazioni
Termina dopo un numero finito di passi
Opera su input ammissibili per il problema considerato
Produce output desiderati che abbiamo una relazione con gli input specificati (siano funzione degli input)
Tutte le operazioni dell’algoritmo devono essere elementari (comprensibili all’esecutore) e poter essere eseguite in un tempo finito
Osservazione: il concetto di azione elementare e’ relativo all’esecutore!
Concetto di algoritmo: requisiti fondamentali
Univocita’
La descrizione è effettuata in un linguaggio comprensibile all’esecutore e mediante un insieme finito di operazioni elementari, note all’esecutore
Completezza
Tiene conto di tutte le possibili condizioni che si possono verificare durante la sua esecuzione
Finitezza
In un numero finito di passi il compito viene portato a termine
Determinismo
Risultati non dipendenti dalla esecuzione
Efficienza
Minimo di operazioni
Concetto di programma
Un linguaggio di programmazione consente di stabilire un dialogo (di comunicare) con lélaboratore.
Un lingiaggio di programmazione e’ un linguaggio comprensibile ad un elaboratore, per mezzo del quale si possono esprimere gli algoritmi.
Un programma e’la rappresentazione formale di un algoritmo mediante un lingiaggio di programmazione
Le istruzioni specificate in un programma possono richiedere dati comunicati dall’utente (dati di input - ingresso) e producono altri dati (dati di output - uscita)
Concetto di programma
Il linguaggio macchina e’il linguaggio che l’elaboratore e’ in grado di comprendere
Linguaggi di programmazione di alto livello:
Piu’ facili da usare, in quanto piu’ comprensibili
I programmi scritti in un linguaggio di alto livello sono tradotti da altri programmi in linguaggio macchina
Esempi di linguaggi di alto livello:
ForTran (Formula Translator)
Cobol (Common business oriented language)
Pascal
C
Java
…
Comments