Algoritmi e programmazione

Algoritmi

Algoritmo = "descrizione di una successione di azioni che permettono di risolvere un problema assegnato"

Un programma, scritto in un linguaggio di programmazione come il Pascal o il C, è un esempio di algoritmo in cui il livello di precisione e di dettaglio è molto alto; una ricetta di cucina è un altro esempio, con un livello inferiore di dettaglio e precisione. In entrambi i casi, l'algoritmo si presenta come una sequenza di istruzioni (comandi che dicono cosa occorre fare).

Le azioni nei nostri algoritmi sono essenzialmente manipolazioni di dati, o strutture dati.

Normalmente, gli algoritmi sono parametrizzati dai dati, così che da essi si ottiene la soluzione di una intera classe di problemi, non solo di un particolare problema.

Esempio Supponiamo che ci venga assegnato il problema seguente: dato il libretto universitario di uno studente, trovare qual è il voto preso più di frequente (ha preso più trenta o più diciotto o più ventuno....?)

Un modo di risolvere questo problema è:

Dunque, a partire dai dati di ingresso, il testo, costruiamo una struttura dati, l'elenco dei voti; la soluzione del problema si ottiene analizzando questa struttura dati e, alla fine, estraendone la risposta voluta.

Nell'esempio si vede come il procedimento per arrivare alla soluzione, cioè l'algoritmo, sia strettamente legato all'utilizzo di una particolare struttura dati, l'elenco; questo è un fatto valido in generale.

ALGORITMI + STRUTTURE DATI = PROGRAMMI

(Niklaus Wirth, svizzero, autore del linguaggio Pascal)

Il problema a questo punto è molto semplice e l'algoritmo per arrivare alla soluzione è altrettanto semplice.

Linguaggi di programmazione

Linguaggio di programmazione = linguaggio artificiale con cui si scrive un algoritmo in modo comprensibile al calcolatore (cioè un programma).

Un programma è fisicamente contenuto in un file di testo (p.es. ASCII), detto file sorgente, in cui esso viene scritto in modo leggibile dalle persone. Successivamente, viene trattato per essere reso eseguibile dal calcolatore.

A questo scopo, i programmi (e i rispettivi linguaggi) possono essere trattati in due modi.

Possono essere compilati.

In questo caso esiste un programma (il compilatore) che legge il file sorgente e scrive un file eseguibile. (In windows, i file eseguibili si riconoscono per l'estensione .exe , cioè executable)

Oppure possono essere interpretati.

In questo caso esiste un programma (l'interprete) che legge il file sorgente e non scrive alcun file eseguibile, bensì esegue direttamente le istruzioni dell'algoritmo.

La compilazione si fa una volta per tutte. L'interpretazione si fa ad ogni esecuzione.

 

Esempi di linguaggi celebri

Interpretati

BASIC

Significato del nome: Beginner's All-purpose Symbolic Instruction Code

Nascita: Metà anni 60 (John Kemeney, Thomas Kurtz)

Descrizione: Semplice e di uso generale (cioè non specifico per qualche tipo di problema). È il più celebre linguaggio interpretato, diffuso su tutti i piccolissimi calcolatori fin dai tempi della nascita dello home computer (fine anni 70: Apple II) e in ambito didattico.

Matlab

Significato del nome: Matrix Laboratory

Nascita: Metà anni 80 (The Mathworks, Inc.)

Descrizione: Programma di calcolo numerico che tratta matrici e vettori. Le procedure di calcolo si scrivono in un suo linguaggio di programmazione, molto diffuso perché potente e sintetico.

Macrolinguaggi

Significato del nome: una Macroistruzione è una istruzione composta di più istruzioni elementari.

Nascita: Fine anni 70

Descrizione: I programmi applicativi possono essere programmati per svolgere operazioni ripetitive. In questi casi, il programma applicativo fa da interprete.

In Microsoft Office, per esempio, il linguaggio di macroprogrammazione è una versione estesa del BASIC.

Compilati

Fortran

Significato del nome: Formula Translator

Nascita: 1957 (John Bakus)

Descrizione: Uno dei più antichi linguaggi di programmazione e tutt'ora uno dei più usati in ambito scientifico e tecnico (ingegneria).

Specializzato per eseguire calcoli numerici (come Matlab, ma più antico e più veloce).

Pascal

Significato del nome: scelto in omaggio a Blaise Pascal, che costruì nel XVII sec. una macchina da calcolo.

Nascita: Fine anni 60 (Niklaus Wirth).

Descrizione: Linguaggio di uso generale. Semplice, ma pensato in modo da invitare il programmatore a dare al programma un ordine e una struttura per ottenere programmi puliti, leggibili e quindi facilmente controllabili. Molto usato in ambito didattico.

C

Significato del nome: il linguaggio è derivato dal precedente BCPL. Un primo derivato si chiamava linguaggio B (1a lettera del nome); il linguaggio C è il secondo linguaggio derivato (quindi la 2a lettera).

Nascita: Anni 70 (Brian W. Kernighan, Dennis Ritchie)

Descrizione: Linguaggio di uso generale, che fornisce istruzioni di alto livello e istruzioni di basso livello (simili all'Assembler). Molto potente e usatissimo, permette di fare con facilità molte cose che in altri linguaggi sono più complesse (inlusi potenziali pasticci).

Una via di mezzo

Java

Significato del nome: Probabilmente studiato da uffici marketing per il suo effetto, come il nome delle automobili. Non risulta alcun significato. Java è un caffè.

Nascita: 1995 (riciclato da un precedente linguaggio OAK; Sun Microsystems Inc.)

Descrizione: Java viene compilato in una versione non eseguibile, chiamata byte code. A sua volta, il byte code viene interpretato da un interprete chiamato Java Virtual Machine.

Essendo una macchina virtuale, se ne può fare una versione identica per ogni possibile architettura di calcolatore, quindi Java è indipendente dall'architettura e dal sistema operativo e funziona su tutte le macchine per cui esiste una virtual machine.

Per questi motivi Java è un linguaggio per programmi diffusi in Internet.

 

 

Dati e tipi di dati

 

Sappiamo che il calcolatore può trattare dati codificati in determinati modi. Abbiamo visto le codifiche per:

Questi sono tipi di dati. Un tipo di dati rappresenta (per me) la natura delle informazioni memorizzate, oppure (per il calcolatore) il modo in cui si interpretano le informazioni memorizzate.

Questi sono tipi di dati primitivi. I linguaggi di programmazione possono offrire altri tipi di dati, non supportati direttamente dalla macchina ma "capiti" dal compilatore o dall'interprete. Essi possono essere:

Esempio di algoritmo

Vediamo con un esempio pratico come si passa dal problema all'algoritmo e dall'algoritmo al programma, specificando tutto ciò che serve per ottenere un programma realmente funzionante.

Il problema: quello citato all'inizio.

Supponiamo che un corso di laurea preveda 26 esami con voti da 18 a 30 e lode (che sono 14 punteggi possibili). Facciamo finta che 30 e lode si scriva 31.

Essendoci più esami che punteggi, ha senso chiedersi quale sia il punteggio ottenuto più di frequente da un determinato studente.

L'algoritmo:

Supponiamo che sia data in ingresso l'elenco degli esami superati, cioè il contenuto del libretto universitario.

Non vogliamo complicarci la vita, in questo momento. Supponiamo che sia dato in una forma che non ci crea troppi problemi per il programma, cioè che sia facile da leggere con istruzioni semplici. Potrebbe essere un file ASCII con i voti scritti p.es. uno per riga:

28

31

29

30

...eccetera...

Questo formato è facile da leggere in un programma. P.es. se avessimo il libretto in forma cartacea da passare allo scanner, il discorso sarebbe ben più complicato.

Il nostro algoritmo avrà una forma piuttosto comune:

 

La fase di input sarà:

  1. Leggere l'elenco dei 26 voti conseguiti: Per ogni voto incontrato,
  2. incrementare la sua frequenza osservata (cioè il conteggio di quante volte è comparso)

La fase di elaborazione sarà:

  1. Scorrere l'elenco delle frequenze: Per ogni frequenza,
  2. se essa è superiore a quella massima incontrata finora,
  3. ricordarsela

La fase di output sarà:

  1. Scrivere il voto a frequenza massima.

Questo è l'algoritmo, scritto in un modo un po' più dettagliato di prima.

Dall'algoritmo osserviamo che ci sono vari tipi di istruzioni, per realizzare le quali i linguaggi di programmazione mettono a disposizione strumenti appositi.

Dall'algoritmo osserviamo anche che avremo bisogno di varie strutture dati.Anche per realizzare le strutture dati i linguaggi di programmazione prevedono strumenti appositi.

Elementi di un linguaggio di programmazione

Iterazione

Costrutto per eseguire una istruzione in modo ripetitivo. Per esempio:

  • Un numero predeterminato di volte
  • Finché non si verifica una condizione di arresto specificata

Esecuzione condizionale

Costrutto per eseguire una istruzione solo se si verifica una data condizione. Per esempio:

  • SE condizione ALLORA esegui istruzione
  • SE condizione ALLORA esegui istruzione1
    ALTRIMENTI esegui istruzione2

Un esempio di struttura dati: l'ARRAY

È una struttura dati aggregata. Molto usata. Vediamo che dati rappresenta e come è organizzata nella memoria del calcolatore.

Che dati rappresenta?

Un array in inglese è una sequenza di oggetti allineati.

Quindi l'array rappresenta sequenze indicizzate di dati omogenei.

L'array è indicizzato perché un array di dimensione N possiede N posizioni numerate. Alla posizione i-esima si accede fornendogli l'indice i, che è un numero intero compreso tra 1 e N.

I dati dell'array sono omogenei perché l'array è organizzato per contenere in ogni sua posizione lo stesso tipo di dato. Questo può essere un tipo elementare o, a sua volta, un tipo strutturato.

In matematica, l'equivalente dell'array può essere il vettore N-dimensionale. Infatti in informatica usiamo dire indifferentemente array o vettore.

Anche in questo caso, naturalmente, c'è una differenza: in matematica si trattano di solito vettori a valori numerici, mentre l'array può avere valori di qualunque altro tipo.

Per rappresentare la componente i-esima del vettore v in matematica si usa il pedicevi .

Poiché i programmi sono scritti in file ASCII, che non prevedono la codifica dei pedici, in informatica agli elementi degli array si accede attraverso l'uso delle parentesi: v[i] , oppure v(i) (linguaggi diversi hanno usanze diverse).

Come è organizzato in memoria?

La memoria è essa stessa una sequenza lineare di parole, indicizzata attraverso gli indirizzi di memoria. Perciò un array sarà semplicemente un segmento di memoria.

Per esempio: Un array di 8 elementi grandi ciascuno una parola di memoria sarà organizzato così:

MEMORIA

IL MIO ARRAY

0

1

2

3

4

5

6

7

Per esempio: Un array di 5 elementi grandi ciascuno due parole di memoria sarà organizzato così:

MEMORIA

IL MIO ARRAY

0

1

2

3

4

Le caselle sono le parole della memoria. Quelle evidenziate sono usate per contenere l'array.

I numeri indicati sotto sono gli indici di ciascun elemento. L'indice è il numero di elementi da contare oltre il primo per arrivare a quello voluto. Per esempio, l'indice del primo elemento è 0, perché occorre spostarsi di zero posizioni dal primo elemento per arrivare al primo elemento. L'indice del terzo elemento è 2, perché occorre spostarsi di 2 posizioni oltre il primo elemento per raggiungere il terzo.

Questo è il calcolo che viene fatto internamente dal calcolatore. Alcuni linguaggi di programmazione mi permettono di indicare un array con indici arbitrari (p.es. da 1 a 8, o da -7 a 7), e poi si occupano loro di fare i calcoli corretti come scritto sopra. Fra questi linguaggi non è compreso il C, che quindi rispetta rigorosamente questa rappresentazione (indici con partenza da zero).

ATTENZIONE: Si noti che stiamo parlando di contare gli elementi dell'array, e non le caselle di memoria (parole). Nel primo esempio un elemento sta in una parola, ma nel secondo un elemento sta in due parole. Spostarsi di un elemento equivale a spostarsi di due parole in questo secondo caso.

Il nostro programma

Prima scriviamo il programma che realizza l'algoritmo del nostro esempio. Poi lo commentiamo, cercando al suo interno gli elementi che abbiamo descritto in teoria.

Scriviamo il programma in linguaggio C perché è molto diffuso: così diffuso che molti altri linguaggi (C++, Java, Matlab) sono stati progettati per assomigliargli.

  1. #include <stdio.h>
  2. main()
  3. {
  4. int i;
  5. int max;
  6. int voto;
  7. int vfreq[14];
  8. for (i=0; i<14; i++)
  9. vfreq[i]=0;
  10. for (i=0; i<26; i++) {
  11. scanf("%i",&voto);
  12. vfreq[voto-18]++;
  13. }
  14. max = 0;
  15. for (voto=0; voto<14; voto++) {
  16. if (vfreq[max]<vfreq[i])
  17. max = i;
  18. }
  19. printf("Il voto piu' preso e' %i (%i volte)\n",max+18, vfreq[max]);
  20. }

Le righe sono numerate in questo esempio, così commentarle è più facile. Però i numeri non fanno parte del file sorgente: sono solo per nostra comodità. NON DOBBIAMO INSERIRLI NEL FILE.

Inoltre il modo in cui è disposto il testo del file sorgente non conta. Di solito si usa questo stile per mettere in evidenza le varie parti. Però probabilmente funzionerebbe anche se (p.es.) scrivessi tutto su un'unica riga.

Per prima cosa lasciamo stare le righe 1, 13 e 21. Quelle sono istruzioni di ingresso e uscita. Sono molto legate al caso specifico, cioè ai dettagli di come è memorizzato l'ingresso e di come si vuole l'uscita, quindi non dicono molto su come si trasforma un algoritmo in un programma. Faremo un cenno più oltre.

La riga 3 indica dove inizia il programma. In C non ci sono procedure, però ci sono le funzioni. In C è considerato una funzione speciale anche il programma principale stesso. Il programma è una funzione che si chiama main (="principale") e che, in questo esempio, non ha argomenti (vedi le parentesi tonde vuote) né restituisce un valore.

Però deve essere ugualmente una funzione, e deve chiamarsi main.

Le righe 4 e 22 contengono le parentesi graffe più esterne, che delimitano il corpo del programma. In altri linguaggi, le parentesi graffe sono sostituite da indicazioni esplicite: { si indica con begin, } si indica con end. Quello che sta fra le parentesi è ciò che deve fare la funzione main, cioè il programma.

Le righe da 5 a 8 sono dichiarazioni. In C, la dichiarazione di una variabile intera si fa così:

int nomevariabile;

dove int è una parola-chiave predefinita, che in C ha un determinato significato (quello di indicare il tipo di dato integer, cioè intero). Invece nomevariabile è il nome della variabile che stiamo dichiarando, ed è un nome che decido io. Basta che inizi per una lettera e contenga solo lettere, cifre e il carattere _ .

Il punto e virgola è obbligatorio alla fine di ogni istruzione. Se non c'è un punto e virgola alla fine di una riga (come per esempio alla riga 10), significa che l'istruzione non è finita e continua sulla riga seguente.

Quindi con le righe 5, 6, 7 ho dichiarato rispettivamente che esistono le variabili i, max e voto e che sono variabili di tipo numerico intero.

(Useremo i come indice generico per scorrere l'array, voto come variabile contenente il voto letto in ingresso, e max come indice del voto a frequenza massima.)

La riga 8 è una dichiarazione di un dato strutturato. È la dichiarazione di un array.

In linguaggio C, le cose spesso sono indicate in modo molto sintetico (vedi { per begin, int per integer, ecc). Anche nella dichiarazione dell'array il C è molto sintetico. Anziché scrivere esplicitamente "la variabile vfreq è un array di interi", in C scrivo che vfreq è "un intero a 14 posizioni". Quindi, scrivo int vfreq[14]; che è uguale alla dichiarazione di una variabile intera, però seguita dal numero di elementi.

ATTENZIONE: Ricordiamo che in C l'indice è il numero di posizioni da contare, oltre la prima, per arrivare all'elemento voluto. Quindi il primo elemento avrà indice 0, mentre l'ultimo elemento avrà indice 13. L'indice 14 non deve mai comparire. Il fatto che esso debba invece comparire nella dichiarazione è origine di confusione. Nel resto del programma, l'indice non potrà mai valere 14, altrimenti succederà un errore.

L'array vfreq sarà usato per contenere le frequenze di ciascun voto. Ogni elemento corrisponderà a un possibile voto, dall'elemento 0 (voto minimo, cioè 18) all'elemento massimo (14, che sta per 31 ossia 30 e lode). Ogni elemento partirà dal valore zero e verrà incrementato ogni volta che incontreremo il voto corrispondente.

(Notiamo che i voti vanno da 18 a 31, mentre gli indici vanno da 0 a 13, quindi voto reale = indice + 18.)

Le righe 10, 12 e 17 contengono il costrutto di controllo for. Il costrutto for equivale al "per ogni..." che abbiamo scritto nel nostro algoritmo. Quindi è un modo per scrivere un ciclo.

Il costrutto for è scritto in questo modo:

for ( inizializzazione ; condizione ; aggiornamento )

istruzione ;

L'inizializzazione è un'istruzione che impone le condizioni di inizio del ciclo. Nella riga 10, p.es., impone che l'indice i inizi da zero con l'istruzione i = 0.

La condizione è una espressione logica. Il ciclo si ferma quando tale espressione smette di avere valore VERO e assume valore FALSO. Nella riga 10, p.es., la condizione è che l'indice i sia minore del massimo consentito, cioè i < 14 .

L'aggiornamento serve a passare da una iterazione alla successiva. Nell'esempio della riga 10, ogni iterazione è caratterizzata da un diverso valore dell'indice i (ricordiamoci che questo costrutto traduce il per ogni elemento, cioè per ogni valore dell'indice dell'array). Quindi in questo caso l'aggiornamento consiste nell'incrementare i con l'istruzione i++.

Infine, l'istruzione è l'istruzione che viene iterata. Nel caso della riga 10, l'istruzione da iterare è scritta alla riga 11.

Le righe 10 e 11 costituiscono un ciclo di inizializzazione dell'array. La riga 11 è una istruzione di assegnazione (ATTENZIONE: il simbolo = si legge così: "assegna alla variabile a primo membro, che deve essere proprio una variabile, il valore del secondo membro, che può essere un'espressione qualunque").

La riga 11 impone che alla variabile vfreq[i], cioè all'elemento i-esimo dell'array vfreq, sia assegnato il valore 0. Questo viene fatto per (for) ogni valore valido dell'indice i, da 0 a 13.

Anche l'inizializzazione in riga 10 è una istruzione di assegnazione. Anche in tale assegnazione viene imposto ad una variabile (l'indice i) di contenere il valore zero.

Quindi, si inizia con tutte le frequenze nulle.

Il ciclo alla riga 12 ha come istruzione una sequenza di istruzioni comprese fra parentesi graffe.

Più istruzioni fra graffe equivalgono, secondo le "regole grammaticali" del linguaggio C, ad una unica istruzione. Quindi le righe 13 e 14 sono le componenti di una istruzione composta.

La riga 13 è una istruzione di ingresso. Non ci interessa sapere niente, tranne che essa mette nella variabile voto il prossimo voto letto dall'ingresso.

Subito dopo, nella riga 14, c'è una istruzione di incremento. Questa volta viene incrementato il valore dell'elemento dell'array vfreq corrispondente al voto letto. (Si applica la trasformazione da voto reale a indice, che consiste nel sottrarre 18 in modo che 18 diventi 0, 19 diventi 1, ... 31 diventi 13. Quindi l'indice corrispondente a voto è dato dall'espressione voto - 18.)

Quindi l'elemento da incrementare è vfreq[voto-18] e il comando di incremento è ++ .

A questo punto, usciti dal ciclo di lettura (che viene iterato 26 volte), possiamo scandire tutto l'array e cercare la frequenza massima. Per memorizzare la frequenza massima, useremo la variabile max, indice del voto a frequenza massima. Il voto a frequenza massima sarà quindi max+18 e la sua frequenza sarà vfreq[max].

Cominciamo a inizializzare max (riga 16). Imponiamo che, prima di qualunque analisi, il primo voto che incontriamo nella scansione (che corrisponde all'indice 0 ed è il voto 18) sia quello a frequenza massima. Perciò imponiamo max = 0 .

Se poi ci saranno altri voti a frequenza più alta, aggiorneremo via via max. Alla fine avremo l'indice del massimo incontrato in tutta la scansione dell'array.

Il ciclo in riga 17 impone di scandire tutto l'array vfreq per ogni indice i fra 0 e 13.

Per ogni valore dell'indice, eseguiamo un'istruzione di aggiornamento max = i . Tale aggiornamento va fatto però solo se troviamo un voto a frequenza maggiore del massimo incontrato finora.

Il costrutto if , che si trova alla riga 18, equivale al SE... che abbiamo scritto nel nostro algoritmo. Quindi è un modo per imporre un'esecuzione condizionale.

Il costrutto if è scritto in questo modo:

if ( condizione )

istruzione ;

La condizione è un'espressione logica come già descritto per il for, e anche per l'istruzione vale quanto già detto in quel caso, compreso il discorso sulle istruzioni composte. L'istruzione del costrutto if viene eseguita solo se la condizione ha valore logico VERO.

(Per parlare onestamente, in C le espressioni logiche non esistono. Il C ha pochi tipi di dato, tra cui non è compreso il tipo logico o booleano. In C le espressioni logiche sono espressioni numeriche intere in cui FALSO è il valore 0 e VERO è qualunque valore non zero.)

La frequenza incontrata in una data iterazione è vfreq[i]. La frequenza massima incontrata è vfreq[max]. Quindi la condizione che dobbiamo verificare perché sia richiesto di aggiornare max è vfreq[max]<vfreq[i] .

Alla fine del ciclo, l'istruzione di uscita scriverà sullo schermo due informazioni: qual è il voto a frequenza massima e qual è tale frequenza. Per esempio:

Il voto piu' preso e' 29 (8 volte)

Infine, per completezza, la riga 1. L'istruzione #include indica al compilatore che, per poter funzionare, questo programma ha bisogno di un altro file che contiene le definizioni delle funzioni di ingresso e uscita che intendiamo usare, e quindi gli indica il nome di tale file, che va incluso nel mio sorgente. Tale operazione avviene automaticamente a cura del compilatore.