Matematica III - i modelli e le macchine astratte

MODELLI E MACCHINE ASTRATTE

MODELLI FONDAMENTALI

Le basi teoriche dell’informatica si occupano in primo luogo del concetto astratto di calcolo automatico, su

cui vengono costruiti i calcolatori e le loro applicazioni. Per far questo si introducono uno o più modelli matematici per

trattare con maggior esattezza possibile l’argomento. Un modello rappresenta un’astrazione della realtà, effettuata

allo scopo di analizzarla, studiarla o di progettarla.

ELABORAZIONE E ALGORITMO

Il concetto astratto di elaborazione è da riferirsi in particolare a quello di elaborazione di dati. Per utilizzare

una notazione formale, possiamo dire che un’elaborazione è la trasformazione y = f(x), laddove il concetto di funzione

è da intendersi nel senso più vasto possibile, inclusa la sua accezione matematica. Molto spesso, affinché la

trasformazione dei dati avvenga, è necessaria una sequenza di azioni elaborative, infatti, solo in casi molto semplici, in

genere, ne è richiesta solo una. La sequenza di passi di elaborazione prende il nome di algoritmo.

L’idea di algoritmo è preesistente all’era dell’informatica, infatti esso soleva indicare un procedimento

matematico per la risoluzione di un problema. Oggi diamo un significato diverso e intendiamo per algoritmo una

sequenza di azioni elaborative, atte a fornire automaticamente la soluzione ad un problema. Tipicamente le

azioni elaborative avvengono su dati espressi sotto forma di simboli o sequenze di simboli. Dalla definizione di

algoritmo si fissano alcuni concetti fondamentali delle elaborazioni, riassumendo possiamo dire che ogni algoritmo è:

• una sequenza di azioni elaborative;

• una sequenza finita di passi;

• deterministico;

• preposto alla risoluzione automatica di un problema.

Inoltre possiamo formalizzare il concetto se, insieme ad esso, definiamo una macchina capace di eseguire le

elaborazioni e un linguaggio mediante il quale descrivere ognuna delle azioni elaborative e la sequenza delle

stesse. AUTOMI

Uno dei modelli, che si trova alla base dell’informatica, è quello dell’automa a stati finiti. È un modello

matematico, che fornisce una prima astrazione per il concetto di macchina che esegue algoritmi, inoltre esso

introduce il concetto di stato, che intuitivamente può esser visto come particolare condizione della macchina, in

conseguenza della quale essa reagisce con una determinata uscita, in risposta ad un particolare ingresso. Un automa

a stati finiti è definito dalla quintupla <Q,U,I,t,w> dove per:

• Q è l’insieme degli stati;

• I è l’insieme degli ingressi;

• U è l’insieme del