1

Algoritmi, linguaggi, programmazione

Di L. D’Abramo

Università dell’Aquila

A.A. 2003-2004

2

Programma : essendo il computer una macchina non intelligente ma un mero esecutore di ordini impartiti dall’esterno, necessita di una serie di istruzioni, scritte in un opportuno codice detto linguaggio di programmazione, che costituiscono appunto il programma.

La scrittura o codifica del programma necessita dei seguenti passi logici:

-analisi del problema da risolvere,

- definire gli obiettivi da raggiungere,

- individuare i dati iniziali e finali

- descrivere in modo formale i passi necessari per ottenere il risultato voluto.

3

Caratteristiche di un generico programma:

- accuratezza nella descrizione del procedimento;

- individuazione della classe di problemi che il programma può risolvere in modo indipendente dai dati iniziali (non il sigolo problema)

Tutto ciò sottende al concetto di algoritmo che è generalmente usato come sinonimo di:

• procedura effettiva

•procedimento di calcolo

metodo di risoluzione di un problema

insieme di regole per eseguire una data operazione

4

Il termine algoritmo deriva dal nome del matematico arabo Al Khwarismi, vissuto nel IX secolo, che pubblicò l’opera

Kitab Al-jabrwal Muquabala (L’arte di numerare ed ordinare le parti in tutto) da cui deriva il nome algebra.

5

Una definizione più completa:

Un algoritmo è una procedura generale, finita, completa, non ambigua ed eseguibile che lavora su dati d’ingresso fornendo alcuni dati d’uscita.

6

le proprietà della procedura

•generale: il metodo deve risolvere una classe di problemi e non un singolo problema (ad esempio deve essere in grado di calcolare l'area di tutti i triangoli e non solo quella di un particolare triangolo)

finita: le istruzioni che la compongono ed il numero di volte che ogni azione deve essere eseguita devono essere finiti

completa: deve contemplare tutti i casi possibili che può presentare il problema da risolvere

7

•non ambigua: ogni istruzione deve essere definita in modo preciso ed univoco,senza alcuna ambiguità sul significato dell’operazione

•eseguibile: deve esistere un agente di calcolo in grado di eseguire ogni istruzione in un tempo finito

Gli algoritmi possono venire classificati in:

· algoritmi deterministici

· algoritmi non deterministici

8

Algoritmo deterministico: per ogni istruzione esiste, a parità di dati d'ingresso, un solo passo successivo; in pratica esiste uno e un solo possibile percorso dell’algoritmo e quindi a fronte degli stessi dati di partenza produrrà gli stessi risultati.

9

Algoritmo non deterministico: contiene almeno una istruzione che ammette più passi successivi che hanno la possibilità di essere scelti: l'algoritmo potrà produrre risultati diversi a partire da uno stesso insieme di dati compiendo percorsi diversi; esempio:algoritmi probabilistici nei quali almeno una istruzione ammette più passi successivi, ognuno dei quali ha una certa probabilità di essere scelto:

Utilizzo nei simulatori

10

Algoritmi e Formalismi di Codifica

Dato un problema si cercherà di trovare un algoritmo che lo risolva; se tale algoritmo perviene alla soluzione del problema si dirà corretto ( o efficace), se inoltre la soluzione è raggiunta anche nel modo più breve possibile si dirà efficiente.

Esempio :

Si devono confrontare le aree di due triangoli individuando quello con l’area maggiore;

h b

:

2 A=

11

Passi procedurali

1) acquisire l’altezza del primo triangolo

2) acquisire la base del primo triangolo

3) calcolare l’ area del primo triangolo

4) acquisire l’altezza del secondo triangolo

5) acquisire la base del secondo triangolo

6) calcolare l’area del secondo triangolo

7) se l’area del primo triangolo è maggiore dell’area del secondo, comunicare che l’area del primo triangolo è maggiore dell’area del secondo triangolo

12

8) se l’area del primo triangolo è minore dell’area l’area del secondo triangolo, comunicare che l’area del secondo triangolo è maggiore dell’area del primo

Approccio al problema : scrivere un programma che calcola le aree di qualsiasi triangolo, in modo che possa essere utilizzato per tutta la classe dei problemi “calcolo delle aree dei triangoli”.

13

Si indichi con:

· h1 l’altezza del primo triangolo

· h2 l’altezza del secondo triangolo

· b1 la base del primo triangolo

· b2 la base del secondo triangolo

· A1 l’area del primo triangolo

· A2 l’area del secondo triangolo

14

Operazioni aritmetico-logiche da eseguire:

15

Abbiamo costruito così un modello rappresentativo dell’algoritmo risolutivo; in tal modo viene risolta una classe di problemi che differiscono solo per il valore dei dati.

“I metodi per rappresentare in modo efficiente ed esaustivo gli algoritmi si chiamano formalismi di codifica poiché rappresentano l’algoritmo mediando tra il semplice linguaggio comune e il formale linguaggio matematico”.

16

Questa rappresentazione illustra le operazioni da svolgere; anche se semplice non ha le caratteristiche di unicità e non ambiguità :ciascuno potrebbe illustrare i passi in modo personale dando appunto luogo ad ambiguità.

Necessità di tecniche di rappresentazione il più possibile univoche e comprensibili:

1. I diagrammi di flusso o flow-chart

2. la pseudocodifica.

17

I diagrammi di flusso sono una forma grafica di codifica degli algoritmi; si collocano a metà strada tra i formalismi più “matematici” e quelli derivanti dalla formalizzazione del linguaggio normale (come la pseudocodifica).

In tale rappresentazione ad ogni simbolo corrisponde un tipo di operazione; è semplice da imparare ed offre una immediata percezione del flusso di esecuzione delle istruzioni.

18

19

20

Simbologia elementare ed intuitiva, adatta a :

• rappresentare algoritmi elementari

• rappresentare solo operazioni strettamente sequenziali;

• per poter rappresentare algoritmi più complessi è necessario introdurre simboli che rappresentino la selezione di due percorsi possibili e l'iterazione (cioè la ripetizione) di istruzioni o gruppi di istruzioni.

21

Istruzioni da eseguire in sequenza

22

Esempio di algoritmo più complesso:

“supponiamo di doverci rifornire ad una pompa di carburante, se la pompa è in funzione facciamo il pieno altrimenti passiamo oltre” ;

si individuano due operazioni diverse (fare il pieno, passare oltre) che sono eseguite in alternativa a seconda che una condizione sia vera

(la pompa è in funzione) oppure falsa (la pompa non è in funzione).

23

Caso della selezione tra due percorsi diversi, al verificarsi o meno di una data condizione:

24

25

L’esercizio del triangolo: il flow-chart con “strade alternative”:

la condizione da valutare è A1>A2:

• se tale condizione risulta vera (A1 è maggiore di A2) in output (video, stampante) sarà inviato il messaggio:

“La prima area è maggiore della seconda”,

•se è falsa (A1 non è maggiore di A2) in output verrà fatta apparire la scritta “La prima area è minore della seconda".

26

Dopo la selezione di una delle due "strade" possibili si possono prevedere :

• più istruzioni in sequenza oppure una sola.

• altre selezioni (selezione in cascata), iterazioni o combinazioni di tutte queste.

27

Un algoritmo più complesso : l’iterazione con controllo Esempio:

il processo (algoritmo) di "cottura della pasta", composto dai seguenti passi: prendi la pentola, riempila d'acqua, mettila sul fuoco finché l'acqua bolle, ecc., prevede un "ciclo d'attesa", nel senso che si deve rimanere in attesa controllando periodicamente se l'acqua sta bollendo finché l'acqua bolle.

28

29

Il "ciclo d'attesa" consiste quindi nella ripetizione (iterazione) di un'azione (il controllo dello stato dell' acqua) per un numero di volte che, in questo caso, non è noto a priori.

Un esempio numerico: supponiamo di dover calcolare il numero b elevato alla n , con b=3 e n=5; la procedura risolutiva consiste nel moltiplicare il numero 3 per sé stesso 5 volte, bisogna quindi ripetere, iterare una moltiplicazione.

30

31

32

•Prima sono eseguite le istruzioni che costituiscono il corpo dell’iterazione (cioè le operazioni che devono essere ripetute)

• dopo è eseguito il controllo per stabilire se ripetere il corpo dell’iterazione (se "ciclare" ancora); se la condizione di uscita dal ciclo non è verificata (è falsa) allora il ciclo viene ripetuto, altrimenti l’esecuzione prosegue con la successiva istruzione che si trova sul ramo del vero; il corpo dell’iterazione viene eseguito almeno una volta.

33

Occorre controllare sempre che esista una condizione – prevista dal programma- che permetta di uscire dal ciclo (loop finito)

Facendo riferimento all'esempio precedente: se non si incrementa n questi rimane sempre a 1, la condizione è sempre falsa ed il ciclo dura all' infinito (si verifica un loop infinito).

Segue esempio del triangolo

34

35

36

37

Pseudocodifica

Formalismo di codifica più legato al linguaggio naturale scritto, rispetto ai diagrammi di flusso

Si utilizza un linguaggio speciale che descrive le istruzioni con frasi rigorose anziché con i simboli grafici; si usano parole chiave, scritte in maiuscolo ed operatori (? , +, *, -, /); si usa inoltre l’identazione, una tecnica che prevede il rientro dei gruppi di istruzioni riferite a cicli o a strutture di scelta.

38

Esempi: pseudocodifica dei problemi precedenti

La sequenza si rappresenta in questo modo :

INIZIO

Istruzione 1

Istruzione 2

..

Istruzione n

FINE

39

Algoritmo “Fare la pasta”

INIZIO

prendi la pentola

riempila d'acqua.

mettila sul fuoco finché l'acqua bolle

assaggia l'acqua

se l'acqua non è salata sala l'acqua,

altrimenti metti la pasta

.

.scola la pasta

FINE

Da svolgere ulteriormente

Da svolgere ulteriormente

40

Pseudocodifica della iterazione( metti l’acqua sul fuoco finchè bolle) :

RIPETI

<corpo dell’iterazione>

FINCHE’ <condizione>

pseudocodifica per l'istruzione "mettila sul fuoco finché l'acqua bolle“:

RIPETI

controlla se l'acqua bolle

FINCHE’ l'acqua bolle

41

Pseudodifica della selezione (istruzione " se l'acqua non è salata, sala l'acqua, altrimenti metti la pasta “:

SE l'acqua non è salata

ALLORA sala l'acqua

ALTRIMENTI metti la pasta

Pseudocodifica dell'esempio del rifornimento di benzina:

SE la pompa è in funzione

ALLORA fare il pieno

ALTRIMENTI passare oltre

42

Esempio sul calcolo e confronto delle aree dei triangoli:

SE A1>A2

ALLORA scrivi “La prima area è maggiore della seconda”,

ALTRIMENTI scrivi “La prima area è minore della seconda“

In generale si avrà:

SE condizione

ALLORA <istruzione 1>

ALTRIMENTI <istruzione 2>

43

Pseudocodifica del programma di confronto delle aree dei triangoli:

INIZIO

Leggi(h1)

Leggi(b1)

A1= b1* h1/2

Leggi(h2)

Leggi(b2)

A2= b2* h2/2

SE A1> A2

ALLORA Scrivi(“l’area del primo triangolo è maggiore dell’area del secondo triangolo”)

ALTRIMENTI Scrivi(“l’area del secondo triangolo è maggiore dell’area del primo triangolo”)

FINE

44

Vantaggio della pseudocodifica: passaggio molto semplice dalla pseudocodifica di un algoritmo al programma vero e proprio

Per contro: nella pseudocodifica il percorso dei dati risulta meno chiaro che nei diagrammi di flusso.

45

Linguaggi e programmi : i passi logici :

-I problema da risolvere-Analisi concettuale e ricerca dell’algoritmo risolutivo-Formalizzazione (linguaggio naturale o formale)-Traduzione in un linguaggio comprensibile dall’elaboratore- Esecuzione- Risultati

46

Considerazioni :

•Il linguaggio “macchina” è molto lontano dal modo di pensare dell'uomo e molto vicino alla struttura fisica del computer.

• I dati su cui operare e le istruzioni da eseguire sono stringhe binarie (sequenze di 0 e 1),

•Di conseguenza la "traduzione" degli algoritmi in tale linguaggio è un compito per esperti che conoscono la struttura dell’elaboratore.

47

•Necessità di disporre di una serie di comandi il più possibile “vicini” al linguaggio naturale, che siano “comprensibili” dall’elaboratore

•I linguaggi di programmazione :

linguaggi formali costituiti da parole il più possibile facili da ricordare (grammatica del linguaggio), combinate secondo rigide regole grammaticali (sintassi del linguaggio).

48

Per utilizzare un linguaggio di programmazione bisogna conoscere quindi la sua sintassi, la sua grammatica e la sua semantica.

Definizione di programma:

traduzione di un algoritmo in un linguaggio di programmazione.

49

Evoluzione e tipologia dei linguaggi

-inizi degli anni ’50 : I PROGRAMMI SONO SCRITTI IN LINGUAGGI “VICINI ALLA MACCHINA” QUINDI DIVERSI TRA ELABORATORE ED ELABORATORE: il programmatore DEVE conoscere come opera la macchina

-Anni 60-70: Nascita dei linguaggi simbolici: consentono l’uso di un gruppo di parole, dette parole chiave, che possono essere combinate secondo una determinata sintassi.

- anni 80 : evoluzione dei linguaggi in senso della vicinanza al linguaggio naturale e quindi sempre più vicini al modo di rappresentare il problema : ci si allontana sempre più dal linguaggio macchina.

50

Rimane da risolvere il problema della traduzione dal linguaggio simbolico (programma sorgente) al linguaggio macchina (programma oggetto) : l’unico eseguibile dall’elaboratore

Vengono ideati a tale scopo i programmi traduttori (uno per tipologia di elaboratore) suddivisi in:

· compilatori e linker

· interpreti

51

Classificazione dei linguaggi di programmazione :

1) linguaggi macchina

2) linguaggi assemblativi

3) linguaggi procedurali

4) linguaggi non procedurali

1)linguaggi macchina (nascono insieme ai primi computer): primo livello, molto vicino al computer, complesso per il programmatore

2) i linguaggi assemblativi, di secondo livello, presentano una struttura elementare ; le istruzioni si identificano mediante sigle che fanno riferimento a componenti fisiche dell’elaboratore.

52

- (segue) Linguaggi assemblativi, linguaggi simbolici ancora molto vicini al linguaggio macchina

Esempio il linguaggio Assembler( diverso da elaboratore ed elaboratore)

ISTRUZIONI TIPO :

MOV A, 7 (scrive 7 nella variabile A),

ADD A, 4 (somma 4 alla variabileA);

INC A (incrementa A di 1) ecc.

53

I linguaggi procedurali (di terza e di quarta generazione) : linguaggi di tipo più evoluto (alto livello), semantica più vicina alla descrizione del problema in linguaggio naturale ( fine anni ’50)

Poiché i problemi possono essere complessi sono state costruite tecniche di programmazione strutturata, (es. Warnier) che limitano la possibilità di errori di logica : la tecnica fa uso uso sistematico della sequenza della selezione e dell' iterazione.

54

Principali linguaggi procedurali evoluti, tutt’oggi in uso, sono:

· FORTRAN (FORmula TRANslator): nato nel 1956 ed usato per scopi scientifici ed ingegneristici è stato il primo linguaggio ad alto livello

· COBOL (COmmon Business Oriented Language): nato nel 1960, ancora in uso per la sua semplicità ed elasticità, per applicazioni commerciali e gestionali

55

Segue…….. Linguaggi procedurali

• Pascal: nato nel 1971 in ambiente prettamente scientifico, molto usato anche dal punto di vista didattico per l’uso coerente dei principi della programmazione strutturata

· C: nato nel 1974 sempre in ambito scientifico, con struttura aderente ai principi della programmazione strutturata, è molto diffuso e permette di scrivere programmi per risolvere problemi molto complessi.

56

Altri linguaggi procedurali ,oggi in disuso : il LISP, il Prolog, e l’ADA, anche questi sviluppati dal ’60 alla fine degli anni ’70.

57

Linguaggi evoluti, non procedurali, nati a partire dagli anni ’70: linguaggi non strutturati: il flusso delle istruzioni non può essere rappresentato per mezzo delle codifiche sopraesposte; (es. Natural);una singola istruzione è in grado di operare diversi passi logici su un gruppo di dati (es. ricercare un dato con una chiave , leggere il dato e inviarlo a video….)

58

Successiva evoluzione in :

-programmazione ad oggetti ( es. Power Builder linguaggio C++, Turbo Pascal versione 5.5 in poi) e programmazione ad eventi (Visual Basic): il flusso delle informazioni non è “rigido”, “prevedibile” ma varia a seconda degli eventi generati dall’azione dell’utente sugli oggetti.

59

Ciclo di vita del software

La costruzione dei prodotti informatici non può essere un procedimento casuale, ma deve prevedere delle fasi che costituiscono quello che viene definito il ciclo di vita del software; tale

ciclo si sviluppa dall’esame del problema, continua nella fase di scrittura del software per arrivare, come passo estremo, alla sua definitiva eliminazione dal sistema.

60

Si individuano sette fasi fondamentali:

· lo studio di fattibilità

· l’analisi e la specifica dei requisiti

· il progetto dell’architettura del sistema (logica)

· la realizzazione dei singoli moduli

· l’integrazione del sistema

· l’installazione del prodotto

· la manutenzione del prodotto

61

A monte della realizzazione di un progetto, anche non interamente informatico, devono essere stimati i costi di sviluppo derivanti dalla realizzazione del prodotto stesso;

tali costi devono essere poi confrontati con i benefici ricavabili (studio di fattibilità).

Problematiche tipiche dello sviluppo di un sistema: errori dei programmatori che potrebbero rallentarne lo sviluppo, reale stima della complessità del problema, non chiarezza del committente e conseguente difficoltà di capirne le reali esigenze

62

Analisi e specifica dei requisiti :

-Definizione delle proprietà richieste al Sistema Informativo e degli obiettivi che si vogliono conseguire.

-Formalizzazione delle funzioni e delle strutture dati per risolvere il problema.

63

Progetto dell’architettura logica del sistema

-Scomposizione del problema generale in problemi più semplici (metodo top-down); vengono quindi realizzati separatamente, in un qualsiasi linguaggio, i vari moduli

- Per ogni programma o insieme di programmi (procedura) controllo e verifica per garantire il rispetto delle specifiche richieste.

64

-Integrazione del sistema : assemblaggio dei singoli moduli per ottenere l’insieme completo dei programmi/ procedure; particolare cura nei collegamenti (interfacce) tra i vari moduli

-Test di sistema: verifica dell’intero sistema tramite controlli effettuati dal produttore (alfa-test) ed eventualmente da terze parti (beta-test).

-Installazione : messa in opera; l’insieme dei programmi viene portato dall’ambiente di sviluppo del produttore nell’ambiente di esercizio, dove verrà utilizzato dal cliente.

65

manutenzione :servizio che va dalla consegna del prodotto fino alla sua dismissione per fornire al cliente assistenza sia per la correzione degli eventuali errori, sia per modifiche che tengano conto delle mutate esigenze dello stesso

66

•Tipi di manutenzione

•Ordinaria: correzione degli errori non individuati nella fase di test,

• Straordinaria : modifiche necessarie per intervenute modifiche nei requisiti (ad es per modifiche nella normativa di riferimento),

•Evolutiva: sviluppo di nuove funzioni automatizzate, integrate con le precedenti,

• Migliorativa : miglioramento delle prestazioni, delle presentazioni all’utente ecc)

67

Strumenti di sviluppo

Programmi di utilità e di servizio che costituiscono l’ambiente ospite dei linguaggi di programmazione ( ambiente di sviluppo); comprendono:

-L’ insieme di programmi che agevolano la scrittura di programmi applicativi e la verifica della loro correttezza (sintattica e strutturale, non logica).

-Un programma di editor per scrivere il programma sorgente, che costituisce il prodotto della codifica nel linguaggio scelto del programma stesso ( le istruzioni non sono ancora comprensibili dall’elaboratore)

- un compilatore che traduce il programma sorgente in programma oggetto, formato da istruzioni intellegibili dall’elaboratore.

68

Strumenti di sviluppo (segue)

-Il programma di LINK :il programma oggetto non può ancora essere eseguito, necessita di “legare” i vari moduli tra di loro e di richiamare eventuali programmi esterni : questa funzione è svolta dal “linker” che permette di ottenere il programma eseguibile.

69

70

-In alcuni linguaggi più elementari, (esempio basic e sue evoluzioni) al posto del compilatore e del linker è presente un particolare programma detto interprete che traduce ciascuna istruzione del programma sorgente in una istruzione-macchina e la esegue(linguaggi interpretati).

- Il debugger serve ad analizzare la correttezza del programma nel corso della sua esecuzione verificando passo per passo il risultato delle singole istruzioni.