Abilità informatiche e telematiche

Un programma è un algoritmo scritto in un linguaggio comprensibile all'esecutore

(linguaggio di programmazione).

Il linguaggio serve a descrivere in modo non ambiguo tutte e sole le operazioni che

l'esecutore è in grado di eseguire

descrive ciò che occorre sapere per formulare algoritmi che possano essere interpretati ed

eseguiti dall'esecutore.

Si può identificare l'esecutore con il suo linguaggio di programmazione, ignorando il suo

funzionamento interno.

Un calcolatore è un apparecchio elettronico progettato per eseguire automaticamente e

velocemente attività diverse. Non ha nessuna capacità decisionale o discrezionale e si limita a

compiere azioni secondo procedure prestabilite.

Il processore di un calcolatore è un esecutore che interpreta ed esegue le singole istruzioni di

un algoritmo scritto in

un prefissato linguaggio di programmazione. É un automa, cioè una macchina che esegue

algoritmi, che a partire da un opportuno insieme di dati iniziali, produce in uscita i risultati

dell'esecuzione dell'algoritmo per quei dati iniziali.

14. Automi a stati finiti

Un automa a stati finiti è un'astrazione del concetto di macchina che esegue algoritmi, basata

sul concetto di stato, cioè la particolare condizione di funzionamento in cui può trovarsi la

macchina. E' una definizione applicabile a qualsiasi sistema che evolve nel tempo per effetto di

sollecitazioni esterne. Un sistema che evolve nel tempo per effetto di sollecitazioni esterne é un

sistema che, se soggetto a sollecitazioni in ingresso, reagisce in funzione del suo stato attuale

emettendo, eventualmente, segnali di uscita. Tali sollecitazioni posso generare mutamenti nello

stato del sistema. Un sistema ha sempre uno stato iniziale di partenza da cui inizia la sua

evoluzione nel tempo. I mutamenti nello stato possono, eventualmente, terminare in uno stato

finale dopo aver attraversato una serie di stati intermedi.

Una macchina di Mealy è un automa a stati finiti i cui valori di uscita sono determinati dallo

stato attuale e dall'ingresso corrente.

Può essere definita tramite una quintupla di elementi (Q,I,U,t,w) dove:

• Q è un insieme finito di stati interni caratterizzanti l'evoluzione della macchina.

• l è un insieme finito di sollecitazioni in ingresso.

• U è un insieme finito di uscite.

• t: Qxl >Q è una funzione di transizione degli stati, che determina lo stato successivo

della macchina a partire da uno stato e da un ingresso fissati.

• W: QxI→U è una funzione di uscita, che determina l'uscita della macchina a partire da

uno stato fissato.

Una macchina di Moore è un automa a stati finiti i cui valori di uscita sono determinati dal

solo stato corrente.

Può essere definita tramite una quintupla di elementi (Q,I,U,t,w) dove:

Q è un insieme finito di stati interni caratterizzanti l'evoluzione della macchina.

• l è un insieme finito di sollecitazioni in ingresso.

• U è un insieme finito di uscite.

• t: Qxl >Q è una funzione di transizione degli stati, che determina lo stato successivo

• della macchina a partire da uno stato e da un ingresso fissati.

• W: Q→U è una funzione di uscita, che determina l'uscita della macchina a partire da uno

stato fissato.

Un Automa a stati finiti si può rappresentare graficamente tramite un grafo contenente nodi

associati agli stati del sistema, e archi orientati tra i nodi ad indicare le transizioni tra gli stati

del sistema. Ogni arco è diretto da un nodo di partenza a un nodo di arrivo, rappresentando il

passaggio da uno stato all'altro in risposta a determinati eventi o condizioni. Gli stati intermedi

sono rappresentanti tramite nodi con archi entranti ed uscenti. Il grafo può avere stato iniziale

tramite un unico nodo con nessun arco entrante. Lo stato finale se esiste è rappresentato da un

nodo senza archi uscenti.

Un Automa a stati finiti può essere rappresentato tramite una tabella contenente tante righe

quante sono gli stati del sistema, e tante colonne quante sono gli ingressi del sistema. Vanno

indicati gli stati nei quali il sistema transita per effetto delle sollecitazioni in ingresso, e le

eventuali uscita prodotta nella transizione.

Immaginiamo di voler realizzare un automa di Mealy per il controllo di un motore elettrico.

L 'automa riceve in input i segnali relativi a due pulsanti A e S

A=1 se pulsante accensione premuto, altrimenti A = 0

•

• S=1 se pulsante spegnimento premuto, altrimenti S =0

In caso di pressione simultanea, prevale il pulsante spegnimento. In uscita l'automa comanda

l'alimentazione o meno del motore.

L'automa può trovarsi in due possibili stati Q= {S , S }:

o 1

• S : motore attualmente spento;

o

• S : motore attualmente acceso.

1

L'automa dev'essere progettato per ricevere quattro possibili ingressi |={l , I , 1 , 1 ]:

0 1 2 3

• l : pulsanti A e S entrambi non premuti

o

• I : pulsante A non premuto, e pulsante S premuto

1

• I : pulsante A premuto, e pulsante S non premuto

2

• I : pulsanti AeS entrambi premuti

3

Infine, l'automa deve produrre in output due possibili uscite U={U , U }

0 1

• U : non alimentare motore

0

• U : alimenta motore.

1

Fissati gli insiemi l, Q e U, si può passare a definire il grafo e la tabella di transizione degli stati

che descrivono il comportamento del sistema in termini di cambiamento di stato e uscita

prodotta quando si riceve in ingresso un particolare valore tra quelli previsti.

Se viene premuto il pulsante di accensione e quello di spegnimento resta non premuto, se

attualmente il motore è spento, l'automa cambia stato e viene alimentato il motore.

Se viene premuto sia il pulsante di accensione che quello di spegnimento, se attualmente il

motore è acceso, l'automa cambia stato e viene tolta l'alimentazione al motore.

Se viene premuto il pulsante di spegnimento e quello di accensione resta non premuto, se

attualmente il motore è acceso, l'automa cambia stato e viene tolta l'alimentazione al motore.

La macchina di Turing è un modello teorico dell'informatica ed è spesso utilizzato per

raggiungere risultati teorici sulla calcolabilità e sulla complessità degli algoritmi. È composta da

una memoria infinita divisa in celle, una testina di lettura/scrittura mobile e un dispositivo di

controllo che modifica lo stato e le azioni in base ai simboli letti.

Tale macchina è definita dalla quintupla (A, S,fm, fs, fd)

A è l'insieme finito dei simboli di ingresso e uscita

• S è l'insieme finito degli stati (di cui uno è quello di terminazione)

•

• f è la funzione di macchina AxS→A che determina i simboli da scrivere

m

fs, è la funzione di stato AxS→S

•

• f è la funzione di direzione AxS→D={Sinistra, Destra, Nessuna)

d

La macchina è capace di:

• leggere un simbolo dal nastro

scrivere sul nastro il simbolo specificato dalla funzione di macchina

• transitare in un nuovo stato interno specificato dalla funzione di stato

• spostarsi sul nastro di una posizione in base alla funzione di direzione

•

La macchina si ferma quando raggiunge lo stato di terminazione.

Una macchina di Turing è un dispositivo di controllo che è capace di leggere da un nastro anche

la descrizione dell'algoritmo. E’ una macchina universale capace di simulare il lavoro compiuto

da un'altra macchina qualsiasi. La macchina di Turing Universale è l'interprete di un linguaggio.

Non esiste alcun formalismo, per modellare una determinata computazione meccanica, che sia

più potente della Macchina di Turing e dei formalismi ad essi equivalenti. Ogni algoritmo può

essere codificato in termini di Macchina di Turing. Un problema è non risolubile

algoritmicamente se nessuna Macchina di Turing è in grado di fornire la soluzione al problema

in tempo finito.

• Problemi decidibili → sono meccanicamente risolvibili da una macchina di Turing.

• Problemi indecidibili →non sono meccanicamente risolvibili da una macchina di Turing.

Se un problema è calcolabile, allora esisterà una macchina di Turing in grado di risolverlo. La

classe delle funzioni calcolabili coincide con quella delle funzioni calcolabili da una macchina di

Turing. Un algoritmo risolvente un dato problema calcolabile è indipendente dal sistema per

esso esiste una macchina di Turing in grado di risolverlo. Un algoritmo è indipendente dal

linguaggio usato per descriverlo per ogni linguaggio si può sempre definire una macchina di

Turing universale.

15. La descrizione degli algoritmi

Per algoritmo si intende una sequenza finita di passi che portano alla realizzazione di un

compito; è un insieme finito di istruzioni che, eseguite secondo un ordine prestabilito,

permettono di giungere alla soluzione di un problema. Un algoritmo risolutivo deve essere

espresso in un linguaggio comprensibile all'esecutore a cui è rivolto. L'esecutore di un

algoritmo risolutivo di un problema è l'entità che ha il compito di interpretare ed eseguire i

passi dell'algoritmo in modo da giungere alla soluzione del problema.

Nella definizione di un algoritmo, è essenziale considerare alcuni aspetti fondamentali:

1. deve essere composto da un insieme finito di passi

2. i passi devono essere eseguiti in una sequenza precisa

3. i dati di input devono essere elaborati per giungere alla soluzione del problema

4. i dati di output devono essere prodotti come soluzione del problema stesso

Un programma è un algoritmo scritto in un linguaggio di programmazione comprensibile

all'esecutore. Il linguaggio utilizzato dev’essere tale da descrivere in modo non ambiguo tutte e

sole le operazioni che l'esecutore è in grado di eseguire, fornendo così le istruzioni necessarie

per formulare algoritmi interpretabili ed eseguibili. In sostanza, si può considerare l'esecutore

come il linguaggio di programmazione stesso, ignorando il suo funzionamento interno.

In un programma, tipicamente, si possono individuare due classi fondamentali di frasi del

linguaggio:

• le istruzioni, che descrivono l’esecuzione di determinate operazioni.

• le strutture di controllo, che indicano all'esecutore l'ordine in cui tali operazioni

devono essere eseguite.

Le istruzioni comprendono azioni specifiche che il computer deve eseguire, come calcoli,

manipolazione di dati o interazioni con l'utente. Le strutture di controllo sono utilizzate per

dirigere il flusso