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 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 a 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 a 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...