Schemi teoria Fondamenti di informatica

Automa limitato linearmente (LBA)

È una macchina di Turing non deterministica con limite sulla dimensione del nastro, l'automa limitato linearmente (LBA). Il nastro è limitato alle sole celle contenenti l'input. Questi automi riconoscono tutti e soli i linguaggi contestuali di tipo 1.

Riconoscimento dei linguaggi

Linguaggi di tipo 3 (produzioni regolari)

Sono riconosciuti da macchine a stati finiti (FSM).

Linguaggi di tipo 2 (produzioni non contestuali)

Sono riconosciuti da automi a pila non deterministici (NPDA).

Linguaggi di tipo 1 (produzioni contestuali)

Automi limitati liberamente (LBA).

Linguaggi di tipo 0 (produzioni di tipo generale)

Sono riconosciuti da macchine di Turing (TM). Questi linguaggi sono i più liberi e quindi l'unica cosa che una TM può fare è, data una stringa appartenente al linguaggio, dire se questa stringa appartiene. In tutti gli altri casi potrebbe andare in un loop infinito.

Macchina di Turing

È un automa con una testina di scrittura/lettura su nastro bidirezionale “illimitato”. A ogni passo si trova in un certo stato e legge il simbolo sul nastro, in base alla forma di transizione deterministica scrive un simbolo sul nastro, sposta la testina di una posizione e cambia stato.

• Σ è l'alfabeto del nastro.
• Q è un insieme finito di valori.
• q_0 è lo stato iniziale.
• F è l'insieme di stati finali.
• δ è la funzione di transizione.

Un automa è una macchina astratta che realizza un certo algoritmo secondo un modello di calcolo.

TM deterministica

Queste macchine passano da uno stato all'altro a seconda dell'input e dell'output.

• Σ è l'alfabeto di input.
• Q è l'insieme, non vuoto, di stati.
• δ è la funzione di transizione che in base allo stato attuale e al simbolo di input attuale mi determina lo stato successivo.
• q0 è lo stato iniziale.
• F è l'insieme di stati finali.

Automi e calcolo

TM non deterministica

La macchina non deterministica ha la stessa potenza computazionale di quella deterministica, però quella deterministica deve fare una singola elaborazione alla volta e quindi ci mette molto più tempo rispetto a una non deterministica.

In forma non deterministica permette di riconoscere i linguaggi non contestuali.

In forma deterministica permette di riconoscere i linguaggi non contestuali deterministici.

Macchina a stati finiti (FSM)

Sono simili a FSM ma dotati di memoria infinita, organizzata a pila.

Questo comporta che si può accedere solo alla cima della pila, che si può leggere il simbolo in cima e che è possibile la sostituzione del simbolo in cima con una nuova stringa.

• Σ è l'alfabeto di input.
• Γ è l'insieme di simboli della pila.
• z_0 è il simbolo di pila iniziale.
• Q è l'insieme finito non vuoto di stati.
• q_0 stato iniziale.
• F insieme di stati finiti.
• δ è la funzione di transizione. In base allo stato, al simbolo di input, al simbolo in cima alla pila, determina lo stato successivo e i simboli inseriti nella pila. Per rimuovere il simbolo in cima alla pila si scrive ε.

Automi a pila

Definizione di PDA

La rappresentazione della funzione di transizione si può fare in due modi.

In particolare questa è la rappresentazione della macchina con la tabella di transizione.

Con il diagramma degli stati.

Es. δ: ho due transizioni.

• Esempio 1. Simbolo A in cima alla pila sostituito da BA, stato interno q.
• Esempio 2. Simbolo A eliminato, sostituito da ε, nuovo stato interno r.

FSM non deterministica

Ci sono delle macchine non deterministiche in cui, dato lo stato attuale e un certo simbolo di input, la macchina può fare delle transizioni. Quindi, dato uno stato attuale e un simbolo di input, produce un insieme di stati successivi, ma non si sa in quale vada. Dobbiamo immaginare che la macchina generi tutti gli stati successivi.

δ_n è la funzione di transizione.

PDA non deterministico (NPDA)

La NPDA ha maggiore potere computazionale di PDA.

Per ogni stato/ingresso vengono definiti stati successivi.

Il non determinismo aggiunge potere computazionale.

Equivalenza FSM/NFSM

FSM è un caso particolare di NFSM.

Classi di complessità

Costante: il numero di operazioni non dipende da n.

Sotto-lineare.

Lineare: il numero di operazioni è proporzionale a n, ricerca lineare.

Sovra-lineare.

Un algoritmo è efficiente fino alla classe polinomiale, un problema è trattabile se esiste un algoritmo efficiente.

• Complessità polinomiale.
• Complessità esponenziale.
• Esponenziale.
• Super-esponenziale.

Problemi P e NP

Problemi P

Esiste un algoritmo deterministico polinomiale.

Problemi NP

Non esiste un algoritmo deterministico polinomiale. Sulle macchine deterministiche non è noto un algoritmo polinomiale per la ricerca di una soluzione, ma un algoritmo polinomiale per la verifica della soluzione.

Linguaggio di programmazione

Sistemi di garbage collection

Restituiscono automaticamente la memoria per gli oggetti/dati che non servono più. I vantaggi sono che si libera sistematicamente della memoria, non si rimuovono dati ancora utili e che i dati vengono rilocati per compattare la memoria. Gli svantaggi sono la maggiore occupazione del processore e della memoria.

È una notazione formale e non ambigua per definire algoritmi, un algoritmo è una sequenza di istruzioni per risolvere un dato problema.

Sintassi

È l'insieme di regole formali per scrivere frasi ben formate. Spesso la sintassi opera a due livelli.

• Lessico.
• Struttura.

Ogni linguaggio è caratterizzato da sintassi e semantica.

Semantica

Attribuisce un significato alle frasi costruite nel linguaggio.

Compilatori

Compilatore

Traduzione del linguaggio in linguaggio macchina.

Collegamento con librerie di supporto.

Front-end

Analisi del linguaggio di alto livello.

• Lessicale.
• Grammaticale.
• Contestuale.

Linker statico

Libreria inclusa nel file oggetto, eseguibile stand-alone.

Dimensioni maggiori, ma possibile includere solo funzionalità utilizzate.

Architettura del compilatore

Collega i diversi moduli oggetti e il compilatore.

Rappresentazione intermedia AST (Annotated Syntax Tree).

Il codice oggetto non è ancora eseguibile, un collegamento può essere statico o dinamico.

Esecuzione dei programmi

Librerie condivise da diverse applicazioni.

Programma ad alto livello ha bisogno di per i progra.