Realizzazione software•Due fasi:

(1)

1

Elementi di Informatica 1

Realizzazione software

• Due fasi:

1. Specifica del programma 1.a Definizione dei dati

1.b Definizione della modalità della loro elaborazione

2. Realizzazione algoritmo con un particolare linguaggio (traduzione)

Algoritmi

• Risolvere un problema significa individuare un procedimento che permetta di arrivare al risultato partendo dai dati

• Il procedimento (chiamato algoritmo) è composto da passi elementari

• Il modo di esprimere la sequenza dei passi elementari deve essere standardizzato

Proprietà degli algoritmi

• L'algoritmo è caratterizzato da:

– finitezza: composto da un numero finito di passi elementari; le operazioni sono eseguite un numero finito di volte – non ambiguità: i risultati non variano in

funzione della macchina/persona che esegue l'algoritmo (deterministico) – realizzabilità: deve essere eseguibile con

le risorse a disposizione

Algoritmo

• Per definire un algoritmo è necessario:

– condurre un'attenta analisi del problema – individuare i possibili ingressi

– precisare le uscite

– definire completamente e dettagliatamente la sequenza dei passi che portano alla soluzione

è conveniente suddividere il problema in piccoli sottoproblemi

Rappresentazione degli algoritmi

• Si fa riferimento ai diagrammi di flusso (flow chart)

• Sono rappresentazioni grafiche dei passi elementari; visione globale del problema

• Strumento efficace per descrivere un algoritmo (più della descrizione a parole, troppo generica o appesantita da troppi dettagli)

• Le operazioni base sono 4

Operazioni base

• Le operazioni primarie sono:

– Trasferimento di informazioni

lettura dati, scrittura risultati, visualizzazione dati intermedi – Esecuzione di calcoli

– Assunzione di decisioni – Esecuzione di iterazioni

ripetizione di sequenze di operazioni

• Sono rappresentate da forme geometriche diverse

(2)

2 Simboli convenzionali

ingresso/uscita

elaborazione

elab. predefinita

decisione

inizializzazione

inizio/fine

connessioni

documento

input manuale

disco

mem. sequenziale Elementi di Informatica 8

Esempi

• Diagramma di flusso per:

– somma di N dati – media di N dati – calcolo del fattoriale

– calcolo della radice quadrata approssimata – calcolo dei primi N numeri primi

– inserimento/ricerca di un elemento in un albero binario

Tecniche di programmazione

• Programmazione top-down:

– scomposizione iterativa del problema in sottoproblemi

– i sottoproblemi devono essere indipendenti ed avere interfacce ben definite

– visibilità dei dettagli di ogni sottoproblema

• Programmazione strutturata

Programmazione strutturata

• Teoria nata nel 1965

• Basata su eliminazione dei salti incondizionati e -più generalmente- sulla definizione di restrizioni

• Rendono la scrittura dei programmi e la loro manutenzione più semplici

• Migliorano la leggibilità dei programmi

Teorema di Jacopini-Bohm

• Per costruire un programma sono necessari 3 soli blocchi:

1. blocco di elaborazione

è assimilabile ad una sola istruzione o un solo blocco con un ingresso e una uscita 2. meccanismo di ripetizione (o loop) 3. meccanismo di decisione binaria

• While-Do

I

O

I

O

Strutture per il controllo di flusso

(3)

3

• Repeat-Until

I

O

I

O

Strutture per il controllo di flusso

• If-Then-Else

I

O

I

O

Strutture per il controllo di flusso

Teorema di Jacopini-Bohm

• All'interno di ogni blocco si nasconde un ciclo o una biforcazione

• Il programma risulta quindi composto da una sequenza di blocchi, senza controlli di flusso

• Simile alla programmazione top-down dove, però, i blocchi non devono essere indipendenti e omogenei

Scelta dell'algoritmo

• Non esistono strutture (dati e di controllo) preferite: la loro scelta dipende dal tipo di linguaggio in cui si codifica l'algoritmo

• La scelta dell'algoritmo ottimo dipende dal linguaggio a disposizione: occorre

conoscere bene il linguaggio e le primitive che esso offre