Torna alla pagina di Programmazione degli Elaboratori
:: Capitolo 1: Concetti di base ::
1 Che cos'è la programmazione degli elaboratori
2 Elementi di matematica e logica per la programmazione
3 La nozione di “algoritmo”
4 I linguaggi di programmazione
6 Strumenti di modellazione della programmazione
Per poter comprendere il concetto di programmazione degli elaboratori elettronici, è prima necessario chiarire cos'è un elaboratore elettronico, e quindi cosa significa programmarlo.
Gli elaboratori elettronici sono delle macchine per elaborare informazioni, dove per macchine si intendono dispositivi - anche molto complessi - il cui scopo è sostituire o facilitare il lavoro umano nello svolgimento di compiti ripetitivi, difficili o faticosi.
Il concetto che sta alla base della programmazione è che una macchina in grado di compiere più compiti è meglio di una che ne sa svolgere uno solo, dal momento che con un unico dispositivo (e quindi un'unica spesa, trasporto, manuale, ...) otterremo qualcosa che normalmente richiederebbe l'impiego di più strumenti diversi. Gli elaboratori elettronici sono quindi programmabili per motivi economici e per versatilità.
La logica proposizionale si occupa della verità o falsità delle proposizioni, dove per proposizione si intende una frase di senso compiuto che può essere vera o falsa. Un esempio di proposizione potrebbe essere che è pomeriggio, o che il sole è freddo, o che questa? è una donna. Per comodità di manipolazione, viene spesso associato ad ogni proposizione un simbolo, così da sfruttare le più compatte ed esaustive notazioni matematiche per descrivere le interazioni dei vari eventi (ad esempio, N: “io sono nudo”).
Le proposizioni possono essere atomiche (semplici) oppure composte. Le seconde sono ottenute combinando una o più atomiche con i connettivi logici non (¬), e (∧), o (∨), implica (⊃), se e solo se (≡). Le proposizioni atomiche e quelle composte prendono anche il nome di formule ben formate o fbf.
Il valore di verità di una fbf ci dice se questa è vera o falsa, e dipende dai valori di verità delle proposizioni che la compongono. Questi ultimi cambiano a seconda del contesto in cui li caliamo, dalla loro interpretazione, ovvero dal particolare assegnamento di valori di verità dato ad ogni proposizione atomica (riprendendo l'esempio di prima, N è vero quando prendo il sole integrale ma è falso quando sono in università).
Le tabelle di verità sono tabelle (!) che indicano il valore di verità di una fbf a seconda del valore di verità delle sue “sotto-fbf”. Da notare che se una fbf è combinazione di n atomiche, la sua tabella di verità sarà formata da 2n righe. Le tabelle di verità dei connettivi logici sono:
Una fbf può essere:
Esistono in logica proposizionale alcune relazioni tra proposizioni così importanti da essere considerate leggi:
In generale una fbf Q segue logicamente da una fbf P se e solo se ogni interpretazione che soddisfa P soddisfa anche Q. In questo caso la formula P ⊃ Q si dice teorema, dove P è l'ipotesi e Q la sua tesi. La dimostrazione di un teorema è una successione di passaggi, verificabili in modo meccanico e oggettivo, che trasformano l'ipotesi nella tesi. Scrivere programmi spesso richiede la dimostrazione di teoremi.
Un insieme è una qualsiasi collezione di elementi.
Un elemento x che appartiene ad un insieme A si indica con la notazione x ∈ A.
Due insiemi si dicono uguali se e solo se contengono gli stessi elementi.
Un insieme A è sottoinsieme di B se e solo se ogni elemento di A è anche elemento di B.
L'intersezione di due insiemi A ∩ B è l'insieme di tutti gli elementi comuni ad A e B.
L'unione di due insiemi A U B è l'insieme di tutti gli elementi che appartengono ad A o a B, o ad entrambi.
Un insieme che non contiene nessun elemento si chiama insieme vuoto e si indica con Ø.
Il complemento di un insieme A è l'insieme di tutti gli elementi che non appartengono ad A.
Gli insiemi godono delle seguenti proprietà:
Dati n insiemi U1, U2, ... Un, il loro prodotto cartesiano U1 X U2 X ... X Un è l'insieme di tutte le n-uple ordinate (u1 X u2 X ... X un) dove ui ∈ Ui per i = 1, 2, ... , n.
Dati due insiemi A e B, una funzione f di dominio A e codominio B è una mappa che associa ad ogni elemento a ∈ A un elemento b = f(a) ∈ A. In formula, f: A → B.
Una funzione f si dice iniettiva se e solo se x1 ≠ x2 implica f (x1) ≠ f (x2). Una funzione si dice suriettiva se la sua immagine coincide con il suo codominio. Una corrispondenza biunivoca (o funzione biiettiva) è una funzione sia iniettiva che suriettiva.
La cardinalità di un insieme A è il numero di elementi che appartengono all'insieme A, e si denota ║A║. Dati due insiemi A e B:
La logica dei predicati è un passo avanti nel livello di astrazione della descrizione degli eventi, perché offre strumenti di descrizione molto più potenti e versatili di quelli della logica delle proposizioni. Facendo un esempio, se abbiamo dieci lampadine e dobbiamo dire se funzionano o se sono fulminate, nella logica delle proposizioni dovremo definire una proposizione per ogni lampadina. Il che può andare bene quando le lampadine sono dieci, ma quando sono diecimila? E' qui che giunge in soccorso la logica dei predicati, in grado di parametrizzare e quindi "riassumere" i vari eventi.
La logica dei predicati è costituita da:
I termini sono gli argomenti di un predicato nella logica dei predicati, e rappresentano quelle entità sulle quali è possibile costruire affermazioni. Possono essere:
Attraverso l'utilizzo dei termini diventa possibile scrivere della formule in cui ciascuna variabile può essere sostituita da una qualsiasi delle istanze.
La logica dei predicati mette inoltre a disposizione due utili elementi, i quantificatori, grazie ai quali è possibile specificare se le variabili di una data proposizione si riferiscono a tutte le loro istanze o solo ad un numero più ristretto. Ne esistono di due tipi, quello esistenziale ∃ (“esiste”) e quello universale ∀ (“per ogni”). Molto importante ricordare come i quantificatori possano essere applicati alle sole variabili libere di una formula.
L'algoritmo è una procedura passo per passo grazie alla quale un'operazione può essere svolta senza alcun esercizio di intelligenza e quindi, per esempio, da una macchina. Se il suo scopo è quello di risolvere problemi, capite bene con quanti algoritmi abbiamo a che fare tutti i giorni. Un esempio legittimo di algoritmo potrebbe essere perfino una ricetta di cucina?.
Requisiti essenziali per un algoritmo sono:
Non esiste un unico linguaggio per esprimere un algoritmo, dipende da cosa bisogna fare, come bisogna farlo e da chi farlo eseguire.
L' analisi di un algoritmo è lo studio della sua complessità computazionale, che dipende dalla quantità di risorse necessarie alla sua esecuzione, a loro volta strettamente dipendenti dalla difficoltà del problema da risolvere. Le due risorse principali sono:
Da notare che la difficoltà di un problema è misurata dalla complessità computazionale del più efficiente algoritmo che lo risolve.
Dal momento che sarebbe troppo complicato studiare la complessità di un algoritmo su una macchina reale, il suo studio avviene su un modello generico della tecnologia che verrà utilizzata per realizzarlo. Il nostro modello sarà una macchina con accesso casuale alla memoria e con un processore singolo, la random-access machine (RAM). Peculiarità della RAM è che le istruzioni vengono eseguite in sequenza, con lo stesso tempo di esecuzione e senza operazioni concorrenti. Questo significa che il tempo di esecuzione di un algoritmo su un dato ingresso è dato dal numero di passi necessari per eseguirlo moltiplicato per una costante di tempo ti. Per quanto riguarda lo spazio occupato, si considera invece la quantità massima di informazione da mantenere durante l'esecuzione.
Lo spazio e il tempo dipendono fortemente dal particolare ingresso dell'algoritmo, quindi per il loro studio non possiamo interessarci di pochi casi particolari, ma di una statistica su tutte le possibili esecuzioni. Le statistiche possibili sono tre (caso migliore, caso medio, caso peggiore), ma l'analisi degli algoritmi si concentra sul caso peggiore (maggior impiego di tempo e di spazio possibile) per tre buoni motivi:
Ciò che però realmente determina la complessità di un algoritmo non è la quantità precisa di risorse, ma l' ordine, ovvero il suo tasso di crescita (logaritmico, lineare, cubico, esponenziale, ...) al crescere delle dimensioni dell'ingresso. Ovviamente più l'ordine è basso e più l'algoritmo è semplice ed efficiente.
Facciamo due esempi:
In base al loro ordine, i problemi si possono suddividere in:
In base alla loro complessità computazionale, gli algoritmi possono essere suddivisi in classi di complessità, assegnate in base alla scelta del modello di calcolo (come la RAM o, ancora più astratto, la macchina di Turing e la macchina di Turing con oracolo) ed al concetto di riduzione del problema.
...e tanto per sapere: La macchina di Turing è un dispositivo governato da una logica interna costituita da un automa a stati finiti ed equipaggiato con una testina che legge e scrive simboli di un certo alfabeto su un nastro infinito, sul quale si può spostare di una casella alla volta. La macchina di Turing con oracolo o “non deterministica” è una macchina di Turing ideale nella quale ogni volta che l’algoritmo prevede il compimento di una scelta, lui fa sempre quella giusta.
Ultimo concetto da prendere in considerazione nell'analisi di un algoritmo è quello di riduzione o riducibilità, che permette di verificare se un certo algoritmo associato alla risoluzione di uno specifico problema può essere adoperato per risolverne anche altri.
Un linguaggio di programmazione è un linguaggio non ambiguo ed estremamente preciso, grazie al quale è possibile comunicare ad una macchina le operazioni che deve eseguire in modo del tutto meccanico e automatico.
Non esiste un unico linguaggio di programmazione, ed un buon programmatore non deve impararne uno a menadito ed usare sempre e solo quello, ma dovrà scegliere l'uno o l'altro a seconda delle necessità e di ciò che deve fare.
Un linguaggio è un repertorio di segni convenzionali e di regole per combinarli in enunciati più complessi, più altre regole che associano un significato ad ogni enunciato.
Esistono tre livelli di linguaggio:
L’insieme dei segni convenzionali (anche detti simboli o token) con i quali si possono costruire gli enunciati di un linguaggio, viene chiamato indifferentemente alfabeto o vocabolario. Una parola (in alcuni casi detta stringa o frase) è invece una sequenza di lunghezza finita di simboli dell’alfabeto. Un linguaggio è completamente definito dall'insieme delle parole che gli appartengono.
Una parola vuota è una sequenza di zero simboli, uguale per qualsiasi alfabeto e indicata con є. Se ∑ è un alfabeto, ∑* indica l’insieme di tutte le parole composte da elementi di ∑, є compresa. Per esempio se
∑ = {c,a}, ∑* = {є, c, a, ca, ac, acc, ..., acca, caca, ..., cacca, ...}.
Una definizione più formale di linguaggio potrebbe essere: un linguaggio L è un sottoinsieme delle parole costruibili su un alfabeto ∑, L ⊆ ∑*. Ne consegue che, data una parola w ∈ ∑* ci sono due possibilità:
Un modo esauriente per rappresentare il linguaggio L è definire una procedura in grado di generare tutte le sue parole. Una grammatica è proprio uno di questi sistemi generativi, quindi un insieme di regole di produzione impiegate per descrivere in modo finito linguaggi infiniti.
Più formalmente, una grammatica G è una quadrupla (N, ∑, R, S), dove:
La relazione di produzione in una grammatica G è espressa come:
⇒G ⊆ (N ∪ Σ)∗ × (N ∪ Σ)∗
ed il linguaggio generato da questa grammatica, indicato con L(G) è definito come:
L(G) = {w : w ∈ Σ∗ ∧ S ⇒∗w}
ovvero tutte le stringhe w ∈ Σ∗ che derivano dal simbolo di partenza S utilizzando le regole della grammatica.
Esistono altri tipi di notazione per definire le grammatiche, di più pratica lettura e scrittura. Ne è un esempio quella di Backus e Naur (abbreviato BNF), creata negli anni '60 per definire la sintassi del linguaggio Algol 60.
Alcune differenze rispetto alla notazione vista prima:
Un esempio di notazione in BNF potrebbe essere: <cifra> ::== '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' | '0' che associa al non terminale cifra uno dei 10 valori messi tra virgolette e separati dal metasimbolo di alternativa |.
Le carte sintattiche sono dei diagrammi che permettono di visualizzare le regole di una grammatica in forma grafica. In un diagramma i simboli non terminali vengono rappresentati da rettangoli, mentre quelli terminali da elementi rotondi o rettangolari con gli angoli smussati. I simboli sono collegati tra loro con delle frecce orientate.
Un linguaggio di programmazione può essere o direttamente comprensibile dalla macchina o più vicino al modo di ragionare di chi lo dovrà utilizzare. Nel primo caso si parla di un linguaggio di basso livello (come l'assembly o il MIXAL), nel secondo caso di alto livello (come il C++ o il Java).
Per rendere anche questi ultimi comprensibili dalla macchina, ci sarà bisogno di:
Esistono cinque fasi distinte nella scrittura di un programma:
La specifica è la fase in cui viene descritto in modo più o meno formale il problema che il programma deve risolvere, più gli eventuali vincoli e requisiti che dovrà rispettare.
Una specifica informale non è altro che un testo con la descrizione del problema da risolvere e le relazioni che si desidera mantenere tra ingressi e uscite.
Una specifica formale è una quadrupla S = <X, Y, I, U>, dove:
Esprimendo i concetti in formule, per ogni dato x ∈ X che soddisfa la formula I(x), il risultato y ∈ Y prodotto dal programma deve soddisfare la formula U(x, y).
La progettazione consiste nell'analisi del problema da risolvere e nella progettazione in modo astratto dell'algoritmo. Esistono due approcci antitetici alla progettazione:
Questi due approcci di progettazione possono essere combinati, ad esempio scomponendo un problema dall'alto e individuando quali sottorequisiti comuni e ricorrenti possono essere progettati in stile bottom-up.
Un sistema di progettazione tra i più recenti è quello ad oggetti, che consiste nell'individuare tutti gli elementi rilevanti che compaiono nella definizione del problema (gli oggetti) e quindi modellizzarli e strutturarli tra loro.
La modellazione è la fase in cui viene rappresentato l'algoritmo in maniera più formale e dettagliata, con lo scopo di renderne più evidenti i passaggi e più chiara la struttura concettuale.
È una fase molto importante e troppo spesso sottovalutata, che aiuta il programmatore a creare un programma corretto e corredato di una buona documentazione.
La codifica è il momento in cui il programma viene effettivamente scritto nel linguaggio di programmazione prescelto. Tale scelta può dipendere da vari fattori, sia interni (ad esempio, preferenze) che esterni (ad esempio, imposizioni del richiedente).
La verifica è quella fase eterna in cui viene testato il programma, un momento necessario dato che è molto improbabile che esso sia privo di errori al primo colpo. La correzione degli errori è la logica conseguenza della fase di verifica, in cui vengono corrette (!) le parti del codice segnalate dal testing.
Tutte queste attività si basano sul concetto che un programma è corretto solo quando soddisfa tutte le sue specifiche.
Esistono fondamentalmente due strumenti più o meno formali per aiutare il programmatore nella delicata fase di modellazione (quella intermedia tra l'algoritmo e il programma): i diagrammi di flusso e lo pseudocodice.
Un diagramma di flusso è la rappresentazione grafica simbolica dell'algoritmo, realizzata come sequenza di blocchi contenenti i vari passi dell'algoritmo stesso.
Ogni diagramma di flusso ha uno stato di partenza e zero o più stati finali (rappresentati come cerchietti), più altri blocchi intermedi rappresentati come rettangoli per le istruzioni e come rombi per i test. Blocchi e stati sono collegati con delle frecce, che puntano al blocco successivo da eseguire.
Un altro strumento di modellazione della programmazione è lo pseudocodice, ovvero un linguaggio fittizio che permette di descrivere un algoritmo senza utilizzare la sintassi di un linguaggio di programmazione specifico. Non può essere eseguito direttamente dal computer, ma aiuta il programmatore nella stesura del codice vero e proprio.
La documentazione di un programma è tutto quel materiale informativo prodotto per facilitare la comprensione - e quindi l'utilizzo - del programma stesso. Può essere di due tipi: interna ed esterna.
La documentazione interna di un programma è costituita principalmente dai commenti introdotti nel codice nella fase di codifica, con lo scopo di chiarire il suo funzionamento. Perfino la formattazione di un programma (indentazione, distribuzione su più righe, ...) e le asserzioni (vedi Capitolo 3) sono una forma di documentazione interna.
La documentazione esterna di un programma è costituita dai vari documenti di progetto prodotti separatamente dal programma. Sono documenti di specifica, spiegazioni scritte, manuali di riferimento, schemi e diagrammi, ... praticamente tutto il materiale prodotto nella fase di modellazione.
La documentazione non deve limitarsi alla mera fase di codifica del programma, ma anche a quella di collaudo, con la spiegazione dei sistemi di verifica applicati e dei risultati che hanno restituito.
Per quanto riguarda i manuali, consigliati per ogni programma complesso, si distinguono due tipi: il manuale utente (per l'utente comune che dovrà utilizzare il programma) e il manuale di riferimento (per l'utente avanzato o per un eventuale programmatore che potrebbe riutilizzare il programma come componente di un altro più grande).