Riassunto teoria di FTP - Fondamenti teorici e programmazione

ALBERI RADICATI

Sono alberi liberi in cui un vertice viene designato come radice dell’albero.

I nodi sono i vertici dell’albero.

Dato un albero radicato con radice r, per un qualunque nodo u deve esistere un unico cammino da r a u (detto

“connessione”). Sia esso (r, v , v , …, v , u) si definiscono:

1 2 k

- i nodi r, v , v , …, vk sono detti antenati propri di u;

1 2

- u è un discendente proprio di r, v , v , …, v .

1 2 k

- ogni nodo è sia antenato che discendente di se stesso.

- il nodo v è detto padre di u.

k

- il nodo u è detto figlio di v .

k

- la radice dell’albero non ha antenati propri.

- i nodi figli di uno stesso nodo sono detti fratelli.

- i nodi che non hanno discendenti sono detti foglie o nodi esterni.

- i nodi che hanno discendenti sono detti nodi interni.

- il grado di un nodo è il numero dei figli del nodo.

- la lunghezza del cammino dalla radice ad un nodo u è detta profondità di u.

- l’altezza è la profondità del cammino più lungo dalla radice ad un nodo foglia.

ALBERI ORDINATI, ALBERI POSIZIONALI E ALBERI BINARI

Alberi ordinati: sono alberi in cui i figli di ciascun nodo sono ordinati: primo figlio, secondo figlio, ecc….

Alberi posizionali: sono alberi ordinati in cui ogni figlio ha una posizione specifica. Si dice “completo di dimensione k”

quando ogni nodo è un nodo foglia oppure ha k figli. I più usati sono gli alberi binari.

Alberi binari: sono alberi posizionali in cui ogni nodo ha al più due figli. Due definizioni:

- è un albero vuoto che non contiene alcun nodo;

- è una struttura che contiene un nodo radice, un sottoalbero sinistro (o figlio sinistro) e un sottoalbero destro (o

figlio destro).

ALBERO BINARIO DI RICERCA

Ad ogni nodo sono associate delle informazioni e l’operazione da compiere è la ricerca di un nodo con una data

etichetta. Le etichette appartengono ad un dominio su cui è definito un ordinamento.

Per ogni nodo valgono le seguenti condizioni:

- le etichette di tutti i nodi del sottoalbero sinistro precedono nell’ordinamento l’etichetta del nodo da inserire;

- le etichette di tutti i nodi del sottoalbero destro seguono nell’ordinamento l’etichetta del nodo da inserire.

La ricerca avviene confrontando l’etichetta (r) del nodo radice con l’etichetta (e) del nodo da inserire e riapplicando

ricorsivamente la funzione sul sottoalbero sinistro (r > e) o sul sottoalbero destro (r < e).

Le etichette devono essere tutte distinte.

- Se l’albero è bilanciato, i nodi esaminati saranno nel peggiore dei casi h = log n.

2

- Se l’albero non è bilanciato, i nodi aumentano e nel caso peggiore diventano n.

LINGUAGGI DI PROGRAMMAZIONE

Le frasi sono sequenze finite di simboli dell’alfabeto (stringhe).

Linguaggio: dato un alfabeto Ʌ, un linguaggio L è definito come un insieme anche infinito di stringhe contenenti i

simboli dell’alfabeto. Per fare in modo che l’insieme L contenga solo alcune stringhe di Ʌ*, possibilmente quelle a cui

si può attribuire un significato, si hanno a disposizione due strumenti: gli automi e le grammatiche.

Sintassi: definisce la forma delle frasi del linguaggio e la loro correttezza sintattica. Caratterizzata da:

- alfabeto: un insieme di simboli, denotato con Ʌ (lambda).

- vocaboli: semplici sequenze di simboli (non ci sono declinazioni, congiunzioni, ecc…).

- struttura: regole che permettono di comporre le frasi.

Semantica: riguarda il significato delle frasi, ovvero ciò che calcola un programma.

Pragmatica: metodologia di uso, tiene conto della comprensibilità, efficienza e riutilizzo dei programmi. Spesso

l’efficienza e la comprensibilità non si trovano assieme: un programma può essere più efficiente di un altro ma meno

comprensibile; un programma può essere più comprensibile, scritto in maniera più semplice, ma meno efficiente.

Dunque, a seconda dell’obiettivo, un programma può essere migliore di un altro.

OPERAZIONI SULLE STRINGHE

1. Concatenazione: date due stringhe s =piano e s =forte, la concatenazione di s e s , indicata con s s , calcola la

1 2 1 2 1 2

stringa che contiene tutti i simboli di s seguiti dai simboli di s , in questo caso pianoforte.

1 2

2. Lunghezza: è data dal numero dei simboli che compongono la stringa. Per calcolarla si racchiude la stringa tra

barre verticali, ad esempio |abbbb|= 5.

OPERAZIONI SUGLI INSIEMI DI STRINGHE

1. Prodotto cartesiano generalizzato: dati due insiemi di stringhe A e B, si definisce il prodotto cartesiano

generalizzato di AxB come l’insieme di tutte le stringhe che si possono ottenere concatenando un elemento di A con

un elemento di B. Formalmente: AxB = {s s |s ϵ A e s ϵ B}.

1 2 1 2

0 1 n n-1 2

2. Potenza: di un insieme di stringhe A, è A = {ε}; A = A; A = AxA . Se A = {a, b} allora A = {aa, ab, ba, bb}.

i

3. Operatore di Kleene *: indica l’unione infinita, dato A avremo che A* = U A . Ad esempio, se A = {a, b} allora

i>=0

A* = {ε, a, b, aa, ab, ba, bb, aaa, aba, abb, aab, baa, bab, bba, bbb, …}.

+ + i

4. Operatore : a differenza dell’operatore * non accetta la stringa vuota, dunque dato A avremo che A = U A . Ad

i>0

+

esempio, se A = {a, b} allora A = {a, b, aa, ab, ba, bb, aaa, aba, abb, aab, baa, bab, bba, bbb, …}.

AUTOMI

Per definire un automa bisogna definire:

1. un insieme di stati;

2. un insieme di transizioni da uno stato ad un altro al seguito di un azione.

Si definisce uno stato iniziale e uno o più stati finali.

L’automa si trova in uno stato che viene detto stato corrente.

Svolgono varie funzioni:

1. Permettono di calcolare un sottoinsieme significativo delle funzioni calcolabili.

2. Si prestano ad esprimere il riconoscimento di una frase di un linguaggio.

3. Si rappresentano usando grafi orientati etichettati, in particolare:

- stati: vertici

- transizioni: archi

- azioni: etichette degli archi

Procedimento: inizialmente l’automa si trova nello stato iniziale 0, dunque lo stato corrente corrisponde allo stato

iniziale. Se nello stato corrente viene letto dall’input un simbolo per cui esiste un arco uscente etichettato con il

simbolo letto, allora l’automa va nello stato destinazione, altrimenti si genera un fallimento perché l’automa si

arresta in uno stato che non è definito essere uno stato finale (ciò vuol dire che non si verifica alcuna transizione e

l’intera stringa non viene riconosciuta).

Un automa riconosce una stringa t se nel grafo esiste un cammino dallo stato iniziale ad uno stato finale tale che la

concatenazione dei simboli che etichettano gli archi del cammino sia uguale alla stringa t = v v …v .

0 1 k

DEFINIZIONE DI AUTOMA CHE RICONOSCE LE STRINGHE DI UN LINGUAGGIO L

Un automa è una quintupla (un oggetto formato da 5 elementi) (Ʌ, Ʃ, S, F, δ) dove:

 Ʌ (lambda): insieme di simboli (alfabeto di L).

 Ʃ (sigma): insieme degli stati dell’automa.

 S ϵ Ʃ: stato iniziale in cui si trova l’automa quando inizia il riconoscimento di una sequenza letta dall’input.

 F Ʃ: sottoinsieme di stati (finali) in cui l’automa si arresta quando ha terminato il riconoscimento.

 δ (Ʃ x Ʌ) x Ʃ: relazione di transizione.

In sostanza, un automa definisce un grafo etichettato sull’albero del linguaggio, con i vertici che rappresentano gli

stati dell’automa e gli archi che rappresentano le transizioni di stato. Dunque, gli stati e le transizioni costituiscono

un grafo etichettato. Ʌ

Simbolo letto di

TABELLA DI TRANSIZIONE

Rappresenta le transizioni di stato dell’automa (ovvero gli archi del grafo). a c i o

Ha una riga per ogni stato e una colonna per ogni simbolo di Ʌ. 0 0 1 0 0

Dato che Ʌ è un insieme finito, la tabella può essere sempre costruita. 1 0 1 2 0

Stato corrente

Ad esempio, la tabella per l’automa che riconosce “ciao” in cui Ʌ = {a, c, i, o} è: 2 3 1 0 0

3 0 1 0 4

4 4 4 4 4

DIFFERENZA TRA AUTOMI DETERMINISTICI E AUTOMI NON DETERMINISTICI

Automi deterministici: hanno sempre relazioni di transizione per cui per un dato elemento del dominio coppia (s, v),

dove s è lo stato (sorgente) e v è un simbolo, esiste una sola coppia e quindi un solo elemento del codominio, vale a

dire un unico stato corrispondente (destinazione). Sono:

- più semplici da comprendere;

- più semplici da implementare: per ogni sequenza esiste un solo cammino.

Automi non deterministici: la condizione sopra descritta non è verificata. Ci possono essere più cammini che

ricostruiscono la stringa, a differenza degli automi deterministici in cui il cammino è uno solo. Sono:

- più compatti;

- richiedono un minor numero di stati;

- hanno una maggiore espressività;

- più difficili da implementare: bisogna prima trasformarli in automi deterministici equivalenti.

EQUIVALENZA DI AUTOMI

Due automi G e G sono equivalenti se riconoscono lo stesso linguaggio, ovvero se L(G ) = L(G ).

1 2 1 2

Tutte le stringhe che sono riconosciute da G devono essere riconosciute da G . Ciò non implica che il cammino (o i

1 2

cammini) per cui una stringa è riconosciuta in un automa debba essere lo stesso cammino per cui la stringa è

riconosciuta nell’altro automa.

DAL NON DETERMINISMO AL DETERMINISMO

E’ sempre possibile, dato un automa non deterministico, costruire un automa deterministico equivalente.

Il metodo di costruzione dell’automa deterministico si chiama “per sottoinsiemi”.

Sia N = (Ʌ, Ʃ, S , F, δ) l’automa non deterministico da trasformare.

0

L’automa deterministico equivalente è D = (Ʌ, Ʃ , S , F , δ ) dove:

D D D D

 Ʃ P(Ʃ ): l’insieme potenza dell’insieme degli stati di N.

D N

 Stato Nome a N b N

S = {S }: lo stato iniziale di D è lo stato insieme singoletto

D 0 ∅ ∅ ∅

A A A

che contiene il solo stato iniziale di N. {0} B {0,1} E {0} B

 ∩ ≠ ∅}

F = {s|s ϵ P(Ʃ ) Ʌ s F

D N ∅

{1} C A {2} D

 ∪

δ (S, a) = δ (p, a) per ogni S ϵ P(Ʃ ) e per ogni a ϵ Ʌ.

D p ϵ S N N ∅ ∅

{2} D A A

{0,1} E {0,1} E {0,2} F

Automa non deterministico: Automa deterministico: {0,2} F {0,1} E {0} B

3

Ʌ = {a, b}; formato da 3 stati 2 = 8 stati ∅

{1,2} G A {2} D

Stato a b {0,1,2} H {0,1} E {0,2} F

0 {0,1} {0}

∅

1 {2} Gli unici stati significativi sono quelli raggiungibili

∅ ∅

2 dallo stato iniziale B {0}, dunque B, E, F.

GRAMMATICHE

Una grammatica è una quadrupla (Ʌ, V, s, P):