Architetture Sistemi Elaborazione

Elaborazioni ed algoritmi

Il calcolo automatico

Le basi teoriche dell'informatica si occupano in primo luogo dello stesso concetto di "calcolo automatico" da cui scaturiscono i calcolatori e le loro applicazioni. Intuitivamente, il calcolo automatico si ottiene con i seguenti componenti:

• Alcuni dati iniziali
• Un insieme di regole che costituiscono un programma
• Una macchina che esegue il programma producendo dati intermedi e dati finali (risultati)

Sul piano teorico e dei principi, il concetto stesso è "formalizzato": si introducono, cioè, uno o più modelli matematici per trattare con esattezza l'argomento. In questo capitolo si presentano i fondamenti dell'approccio teorico; essenzialmente, vengono trattati i modelli dell'informatica. In generale, un modello rappresenta l'astrazione di una realtà, effettuata allo scopo di analizzarla e studiarla o, nel caso di un prodotto dell'ingegneria, per progettarlo. Nel processo di astrazione, il modello conserva della realtà i soli tratti essenziali che interessa porre in evidenza ai fini dell'analisi o della sintesi in esame; vengono viceversa ignorati i particolari di ogni specifico esemplare del modello stesso.

L'uso di modelli in ingegneria è pratica costante: dai modelli fisici, che riproducono una realtà con parametri fisici e geometrici opportunamente modificati (modelli urbanistici, galleria del vento, vasca navale, ecc.), ai modelli matematici (studio del moto attraverso equazioni, calcolo della resistenza di manufatti, ecc.) agli stessi modelli simulati al calcolatore.

I modelli che interessano in questa sede sono i modelli matematici o modelli formali: con essi, l'oggetto fisico o il manufatto da studiare viene rappresentato da un oggetto matematico ed il suo comportamento in termini di funzioni espletate, grandezze fisiche in gioco, sua evoluzione nel tempo viene rappresentato da appositi formule, equazioni, procedimenti matematici.

In informatica, il ricorso ai modelli è fondamentale, sia per studiare gli oggetti stessi dell'informatica, quali i calcolatori, i linguaggi e in generale l'hardware e il software, sia per studiare i problemi che trovano poi soluzione attraverso l'informatica. La nostra attenzione è in questa sede rivolta allo studio degli oggetti dell'informatica e quindi ai modelli che si usano per essi: i modelli che si adoperano sono talora informali e talora costituiscono precisi modelli formali.

I modelli fondamentali dell'informatica sono alla base della disciplina stessa e forniscono astrazioni sui concetti stessi di elaborazione, algoritmi, macchina informatica. Alcuni di essi hanno inoltre importanza nella storia dello sviluppo dell'informatica.

Il concetto di elaborazione

Il concetto astratto di elaborazione è quello di trasformazione di dati; senza entrare in dettagli né teorici né applicativi, si può in generale indicare che una elaborazione è la trasformazione: Y=F(X) dove:

• X è l'insieme di dati iniziali o di "ingresso"
• Y è l'insieme di dati finali o di "uscita"
• F è una regola che fa corrispondere Y ad X

Il concetto di funzione F va qui inteso nel senso più ampio possibile del termine e della stessa concezione matematica: è elaborazione il semplice calcolo di una somma, così come la complessa risoluzione di un sistema di equazioni, l'ordinamento di un elenco o la stampa del certificato anagrafico di un cittadino, l'allestimento del bilancio di una società o la gestione di un conto corrente bancario, l'allestimento e la stampa del testo di una lettera o la comunicazione e gestione di messaggi fra gli impiegati in un ufficio e così via.

Ad esempio:

• L'elaborazione è una somma: X rappresenta gli addendi A, B ed Y la somma S: S = A+B
• L'elaborazione è "decidere se il numero X è pari": Y è allora la "risposta" al quesito: Y=si (x è pari) oppure Y=no (x non è pari)
• L'elaborazione è la risoluzione dell'equazione di secondo grado Ay² + By + C = 0: Y è la coppia di radici, X l'insieme dei coefficienti (A, B, C): (Y₁, Y₂) sono le radici di Ay² + By + C = 0
• L'elaborazione è l'ordinamento di un elenco di nomi: X è l'elenco disordinato, Y è quello ordinato: Y è l'elenco X messo in ordine alfabetico
• L'elaborazione è la ricerca dell'indirizzo del signor Rossi, incluso in un elenco assegnato: Y è l'indirizzo, X è "il signor Rossi" e l'elenco assegnato: Y è l'indirizzo del Signor Rossi
• L'elaborazione è l'allestimento di una lettera: X sono tutti i caratteri, le parole, le correzioni, le indicazioni sull'estetica della lettera (margini, tabulazioni, righi in bianco, caratteri di stampa, ecc.), Y è il testo finale: Y è il testo della lettera immessa attraverso caratteri e simboli vari X

Soltanto in casi semplici la trasformazione F si può ottenere mediante un'unica azione elaborativa (questo concetto, sarà via via precisato nel seguito): in genere, essa invece è composta da una sequenza più o meno lunga di elaborazioni intermedie.

Ad esempio:

• Per la somma, si può pensare ad un'unica azione che la esegue;
• Per la parità, si può calcolare il resto della divisione intera per 2 (è questa una nota funzione matematica) e quindi rispondere "si" se il resto è 0;
• Per l'equazione di secondo grado occorre applicare il metodo noto (calcolo del discriminante, suo confronto con 0, individuazione del tipo delle radici, loro calcolo);
• Per l'ordinamento di un elenco occorre adoperare un apposito metodo: ad esempio, prelevare l'uno dopo l'altro i nomi dati, confrontare ciascuno con l'elenco già ordinato ed inserirlo in esso;
• Per la ricerca dell'indirizzo del signor Rossi, occorre cercare "Rossi" nell'elenco dato (ad esempio con il metodo della ricerca nel dizionario) e quindi prelevarne l'indirizzo, che si suppone registrato a fianco;
• Per l'elaborazione del testo di una lettera occorre l'immissione via via delle diverse parti componente la stessa.

Dagli esempi si evince chiaramente che spesso è necessaria una sequenza di azioni elaborative per effettuare una elaborazione; lo stesso del resto accade nella pratica comune: per effettuare una operazione aritmetica "a mano" si sono imparati, nelle scuole elementari, appositi "procedimenti" che scompongono l'operazione in operazioni più elementari. La sequenza di azioni elaborative di cui sopra è detta algoritmo.

Il concetto di algoritmo

Certamente alla base dell'informatica è il concetto di algoritmo, più o meno formalizzato. Esso è preesistente l'era dell'informatica e genericamente indicava un procedimento matematico per risolvere un problema. Il concetto di algoritmo è oggi associato a quello di elaborazione e, adottando una definizione informale, può essere così definito:

L'algoritmo è una sequenza finita di azioni elaborative (o di "passi di elaborazione") che risolve automaticamente un problema. Il concetto di azione elaborativa sarà in seguito definito formalmente: per il momento, è introdotto ancora informalmente.

Un algoritmo opera su dati che sono espressi da simboli o sequenze di simboli: è un dato un numero, espresso da sequenze di cifre, così come è un dato il nome di un individuo, espresso da una sequenza di lettere, il codice di un articolo di magazzino, espresso da una combinazione di lettere e cifre, oppure una informazione che indichi il sesso di un individuo, che può essere espressa da due soli simboli distinti.

Un'azione elaborativa è una attività che produce una "semplice" trasformazione dei dati di un problema, trasportandoli da una parte ad un'altra del sistema di calcolo oppure calcolandone alcuni come funzioni di altri, dove il concetto di funzione è il più vasto possibile: la somma è funzione degli addendi, così come il nome di uno studente è funzione del suo numero di matricola, oppure l'aspetto grafico di una figura geometrica è funzione dei parametri che ne definiscono il tipo di figura e le dimensioni (per esempio: un quadrato, di lato 3 cm. e base orizzontale).

La risoluzione di un problema si può in genere decomporre in una sequenza di "passi di elaborazione": ad esempio, una moltiplicazione fra interi si potrebbe decomporre in una sequenza di addizioni oppure l'ordinamento di un elenco di nomi si può decomporre in una sequenza di scelte di nominativi in un determinato ordine. Tale sequenza costituisce, appunto, l'algoritmo.

Il concetto di algoritmo è un concetto astratto, in quanto rappresenta la sequenza delle azioni elaborative indipendentemente dal come esse sono espresse o comunicate al mezzo automatico (il calcolatore) che le esegue. Con esso si fissano alcuni concetti fondamentali delle elaborazioni.

1. L'algoritmo è una sequenza di azioni elaborative: il concetto di sequenzialità delle azioni è fondamentale: l'invenzione stessa dei calcolatori si è basata su tale concetto. Tuttavia, in alcuni modelli che fanno riferimento ad apparecchiature moderne particolari, la sequenzialità è sostituita in parte dal concetto di elaborazione parallela.
2. L'algoritmo è una sequenza finita di passi: non sarebbe concepibile altrimenti una realizzazione pratica di una macchina per eseguirlo.
3. L'algoritmo è deterministico: la sequenza è rigidamente fissata e non è soggetta a regole probabilistiche. Anche questa proprietà va rivista per alcune applicazioni moderne di elaborazione parallela.
4. L'algoritmo risolve automaticamente un problema: occorre quindi una "macchina" che lo esegue.

Il concetto informale di algoritmo può essere formalizzato se si definisce:

• L'insieme delle azioni elaborative possibili
• Una "macchina" in grado di eseguirle
• Un "linguaggio" attraverso il quale descrivere ciascuna delle azioni e la sequenza delle stesse

Ma il concetto di algoritmo viene matematicamente definito attraverso il modello-principe dell'informatica: la macchina di Turing.

Concetto di automa

Il modello di automa

Uno dei modelli fondamentali dell'informatica è quello di automa a stati finiti. Si tratta di un modello matematico che fornisce una prima astrazione per il concetto di macchina che esegue algoritmi; inoltre, esso introduce il concetto fondamentale di stato, che intuitivamente può vedersi come una particolare condizione di funzionamento della macchina, in conseguenza della quale la macchina reagisce con una determinata "uscita" ad un determinato "ingresso".

La teoria degli automi si è notevolmente sviluppata negli ultimi 40 anni sia da un punto di vista puramente teorico che da quello applicativo ed ha assunto diversi nomi e diversi inquadramenti, a seconda degli interessi prevalenti degli studiosi che l'hanno trattata. Da un punto di vista matematico sono stati definiti alcuni modelli, di cui si è studiata la struttura logico-matematica; il modello interessa altresì gli studiosi della teoria del controllo ed è stato anche impiegato per modellare il comportamento di organismi viventi elementari.

L'interesse dell'informatica nel modello è da un lato di tipo teorico, dall'altro applicativo: il modello è adoperato nello studio di alcuni algoritmi fondamentali, nella teoria e nella progettazione dei linguaggi di programmazione, nello studio dell'architettura dei sistemi di calcolo, nella progettazione di circuiti elettronici componenti le apparecchiature (l'automa viene allora anche detto macchina sequenziale) e così via. In particolare, il comportamento di un calcolatore o di una sua parte potrebbe essere descritto mediante un automa.

Il modello di automa è così definito su un piano formale. Un automa M (a stati finiti) è una quintupla di enti (Q, I, U, t, w):

• Q è un insieme finito di stati interni q, q ∈ Q
• I è un insieme finito di ingressi i, i ∈ I
• U è un insieme finito di uscite u, u ∈ U (o un suo sottoinsieme)
• t è la funzione di transizione che trasforma il prodotto cartesiano
• w è la funzione di uscita che trasforma QxI (o un suo sottoinsieme) in U

Se i sottoinsiemi coincidono entrambi con , l'automa è detto completo, altrimenti incompleto.

Un automa è dunque caratterizzato da un insieme di stati, di ingressi e di uscite, nonché da alcune relazioni tra essi, espresse mediante le funzioni t, w. Gli stati vengono detti stati interni, poiché rappresentano una particolare condizione interna della macchina, a causa della quale essa "risponde" in uscita in un modo piuttosto che in un altro ad una determinata sollecitazione agli ingressi.

Il modello presentato esibisce un comportamento terminale (secondo il quale ad una sequenza di ingressi risponde con una sequenza di uscite) regolato e determinato dagli stati interni che via via assume. Il modello è anche detto di macchina sequenziale. Al modello matematico corrisponde un modello concettuale, secondo il quale un automa schematizza una macchina (fig. 4.1) con un insieme di ingressi I, uscite U e stati interni Q; la macchina consta di due componenti: una calcola le funzioni t e w definendo l'uscita u ∈ U e lo stato seguente q' ∈ Q in funzione dell'ingresso i ∈ I e dello stato attuale q ∈ Q, l'altra è un elemento di ritardo che ripropone all'ingresso della macchina il nuovo stato così calcolato. In questo modo, la macchina "risponde" ad una sequenza di ingressi con una sequenza di uscite che è funzione dello stato iniziale della stessa.

Il modello presentato è in realtà uno dei modelli di automa, in particolare quello di Mealy; un altro, altrettanto diffuso, è quello di Moore, nel quale le uscite, piuttosto che essere funzione di stati ed ingressi, sono funzione solo degli stati:

È stata dimostrata l'equivalenza concettuale fra i due modelli e la possibilità di trasformare un automa di Mealy in uno di Moore, caratterizzato dal medesimo comportamento terminale e viceversa. Invero, a seconda dei casi conviene trattare con l'uno o con l'altro modello.

Le uscite, gli ingressi e gli stati sono altrettanti elementi degli insiemi U, I, Q di natura imprecisata; le funzioni t e w si possono esprimere, essendo gli insiemi finiti, in forma tabellare: per la t, ad ogni coppia (q, i) per la quale è definita, la tabella fa corrispondere una q ed analogamente per la w. Una tabella di Mealy è abbozzata in tab. 4.1, ove gli elementi di I, U, O sono indicati con le lettere corrispondenti ed un pedice. Più immediatamente visiva è una rappresentazione mediante un grafo, detto diagramma degli stati: ciascun nodo rappresenta uno stato ed archi orientati indicano le possibili transizioni fra di essi; su ciascun arco viene segnato l'ingresso che causa la relativa transizione e, separata dal simbolo " / ", la conseguente uscita che, se non specificata, può essere indicata con il simbolo " - ". In figura 4.2 è mostrato il grafo corrispondente alla tabella 4.1: dallo stato Q₁ con l'ingresso I₁ si transita nello stato Q₁ fornendo uscita U₁; sempre da Q₁ con l'ingresso I₂ si resta in Q₁ fornendo uscita U₂ e così via.

Tabella 4.1 Tabella di stato per un automa di Mealy

Il diagramma degli stati per una macchina aderente al modello di Moore si presenta in forma analoga, solo che le uscite sono segnate in corrispondenza dei nodi del grafo piuttosto che sugli archi. Analogamente, nella tabella le uscite sono indicate a livello di ciascuna riga.

Figura 4.2 Diagramma di stato equivalente alla tabella 4.1

Per fissare le idee, si mostrano alcuni esempi.

Esempio 4.1: complementatore di un numero

Come è noto, dato un numero (decimale) N di n cifre, il suo complemento C a 10 (C=10ⁿ - N) si ottiene con il semplice algoritmo che segue:

• Tutte le cifre di "coda" uguali a 0 restano inalterate;
• La prima cifra (dalla destra) diversa da 0 si cambia nel suo complemento a 10;
• Tutte le altre cifre si cambiano nel loro complemento a 9.

In fig. 4.3 è mostrato un automa di Mealy che riceve in ingresso le cifre di N in sequenza, a partire da quella meno significativa; si suppone inoltre che la sequenza di cifre sia preceduta e seguita da due caratteri speciali: "*", che indica l'inizio della sequenza e "!" che ne indica la fine. L'automa opera in tre stati interni: di "riposo", di "coda", nel quale esamina le cifre di coda del numero, lasciando inalterati gli zeri e complementando a 10 la prima cifra diversa da zero, e quello di "testa", ove complementa a 9 le cifre.

Figura 4.3 Esempio di automa complementatore

Esempio 4.2: automa contatore

[Descrizione dell'automa contatore non fornita nel testo originale]