)CHEJE A 2HE?EFE @A1BH=JE?= )AIIE =IIAJJE # LA>HA

(1)

Algoritmi e Principi dell'Informatica

Alessio Massetti 15 Novembre 2011

1 Linguaggi

1.1 Tipi di linguaggi

1.1.1 Linguaggio regolare

Un linguaggio si dice regolare se è riconoscibile da un automa a stati niti come automa a potenza minima

1.1.2 Linguaggio Context-Free

Un linguaggio si dice context-free se è riconoscibile da un automa a pila non deterministico come automa a potenza minima

1.1.3 Linguaggio Context-Sensitive

Un linguaggio si dice context-sensitive se è riconoscibile da una macchina di Turing a singolo nastro come automa a potenza minima

1.1.4 Linguaggio ricorsivamente numerabile

Un linguaggio si dice ricorsivamente numerabile se è riconoscibile da una macchina di Turing come automa a potenza minima

1.2 Cheat Sheet

• I simboli che appartengono all'alfabeto di input sono solitamente minuscoli

• s.t signica s concatenato t

• r | s signica r or s

• Le parentesi forzano una precedenza di lettura

• s^∗ signica un numero arbitrario di s

• s⁺ signica almeno una s. E' equivalente a s(s)^∗

2 Automi

2.1 FSA

Composto da freccia per stato iniziale e stati nali cerchiati. Deterministico se da ogni stato esce una sola freccia per ogni possibile input. Non vengono disegnati gli stati di errore. Può essere usato come riconoscitore di linguaggi

(5)

2.1.1 Riconoscitore di linguaggi

Essenzialmente la stringa di input va riconosciuta passando da stato a stato. Ricor- darsi sempre:

• Lo stato iniziale è stato denito ed è uno solo?

• Il linguaggio in input accetta la stringa vuota?

• L'FSA può leggere altri linguaggi oltre a quello dato? (il riconoscitore di linguaggi deve riconoscere solamente quello desiderato)

2.1.2 Negazione di FSA

Si invertono stati di accettazione e non accettazione. Vanno prima disegnati gli stati di errore (che sono stati di non accettazione) e invertiti

2.1.3 Intersezione di FSA

Si fa il prodotto cartesiano degli stati dei due automi. Lo stato iniziale è quello deteterminato dal prodotto cartesiano dei due stati iniziali.

Sono invece nali tutti quegli stati prodotto dei due stati nali. Partendo dallo stato iniziale si deriva quindi la funzione δ per ogni stato.

2.1.4 Unione di FSA

E' complicato realizzarla come l'intersezione e la negazione, ovvero agendo con un algoritmo proprio sull'automa.

Si realizza sfruttando de Morgan: a ∪ b = ¬ ((¬a) ∩ (¬b)) ovvero: due comple- menti, la loro intersezione e un altro complemento in serie.

2.1.5 Traduttore

Un automa può anche essere usato come traduttore quando produce un linguaggio di output. In questo caso si può associare una stringa di output per ogni stringa di input letta. Eventualmente anche la vuota.

2.1.6 Rimozione del non determinismo

Per rimuovere il nondeterminismo in un FSA si deve partire dallo stato iniziale q0 e spostarsi seguendo le frecce sull'automa non deterministico. Quando il nondeterminismo porta a divergere su più di uno stato si indica il risultante facendo il prodotto cartesiano degli stati. Quando si riparte da questi si guarda l'input tra i due stati a quale porta facendo anche di questi il prodotto cartesiano. Uno stato così ottenuto è nale se e solo se almeno uno di quelli di partenza è nale. Per vericare che sia corretto: ogni stato deve avere tutti i possibili input in entrata e in uscita.

(6)

2.2 PDA

A dierenza dell'FSA il PDA può contare le lettere. Questo porta a considerare nondeterministico solamente il PDA che fa la stessa transizione quando legge la stessa lettera dall'input e dalla pila o quando legge la stringa vuota.

2.2.1 Gestione della pila

L'automa legge la cima della pila. Una volta letta può decidere se buttarla via, rimetterla al suo posto o rimetterla al suo posto insieme ad un altro simbolo. Ad ogni transizione viene quindi tolto un simbolo dalla pila e rimessi facoltativamente in pila zero, uno o due simboli compreso quello letto.

2.2.2 Cosa può leggere

Tutti i linguaggi dove è necessario contare e tutti i linguaggi riconosciuti da un FSA.

Esempi di linguaggi:

• aⁿbⁿ

• I derivati del primo che compiano operazioni matematiche sul secondo: aⁿb²ⁿ; aⁿbⁿ²

• Qualsiasi linguaggio abbia in mezzo cose numerabili: waⁿwbⁿwcon wϵ(a, ..., z)^∗ 2.2.3 Cosa non può leggere

Tutti i linguaggi dove è necessario contare più di una volta o separare il calcolo.

Alcuni esempi:

• Non è possibile leggere linguaggi che debbano contare più di due volte: aⁿbⁿcⁿ

• Non è possibile leggere linguaggi che debbano spezzare a metà uno dei due calcoli aⁿb^mc^lcon l = n + m. In quest'ultimo caso è infatti possibile creare un'automa che legga solo il linguaggio aⁿ(b + c)^m+l

2.2.4 Potenza minima

Non occorre nemmeno un PDA per leggere linguaggi che devono contare un numero

nito di cose, ad esempio: a⁴b⁵può essere riconosciuto da un FSA. In questo caso si parla di automa a potenza minima per riconoscere il linguaggio.

3 Macchina di Turing

3.1 Cosa legge

La Macchina di Turing riconosce tutti i linguaggi computabili.

(7)

3.2 Composizione

E' composta da un nastro di input, un nastro di output e uno o più nastri di memoria.

La macchina può muovere a destra a sinistra o restare ferma con la testina su ogni nastro. Tutte le macchine di Turing sono comunque equivalenti a una sola macchina di Turing con un nastro di memoria.

3.3 Funzionamento

Si usa un simbolo accessorio Z0 per indicare l'inizio del nastro. In caso non ci sia nulla sul nastro si indica con un blank. La gestione dei nastri avviene tramite un FSA

4 Reti di Petri

4.1 Cosa sono

Una rete di petri è un automa nondeterministico composto di stati e di transazioni.

Ogni transazione richiede un token in ognuno degli stati di partenza. Le transazioni vengono eseguite nondeterministicamente

4.2 Potenza di calcolo

Una rete di petri risolve tutti i problemi che è in grado di risolvere un FSA e alcuni problemi che è in grado di risolvere un PDA. La rete di Petri riesce infatti a contare più di una volta ma non riesce a ricordarsi cosa ha contato. Una RDP riconosce, ad esempio,aⁿbⁿcⁿ

4.3 Archi inibitori

Per ampliare la potenza delle RDP si possono usare gli archi inibitori, ovvero degli archi che fanno scattare la transazione collegata solamente se lo stato di partenza non contiene token. Una RDP di questo genere ha la stessa potenza di calcolo di una MT

5 Grammatiche

5.1 Cosa sono

Le grammatiche sono essenzialmente un altro formalismo per denire il linguaggio, descrivono come un linguaggio viene generato. Sono composte da un assioma, delle regole di derivazione e dei caratteri terminali e nonterminali. Per convenzione i caratteri nonterminali si scrivono con la lettera maiuscola, l'assioma viene chiamato S

(8)

5.2 Equivalenze

5.2.1 Linguaggi regolari

Una grammatica riconosce un linguaggio regolare se ha come regole di derivazione solamente A → aB | B | ε, dove A e B sono due diversi qualsiasi caratteri nonter- minali. Una grammatica di questo tipo è detta di tipo 3.

5.2.2 Linguaggio Context-Free

Una grammatica riconosce un linguaggio context-free se ha come regole di derivazione oltre a quelle dei linguaggi regolari almeno una regola A → ABC dove A, B, C sono tre diversi qualsiasi caratteri nonterminali. Una grammatica di questo tipo è detta di tipo 2.

5.2.3 Linguaggio Context-Sensitive

Una grammatica riconosce un linguaggio context-sensitive se ha come regole di derivazione oltre a quelle dei linguaggi context free almeno una regola α → β con|α| ≤ |β| dove α e β sono un insieme qualsiasi di caratteri terminali nonterminali mischiati a piacere (in una maniera ovviamente non compresa nei linguaggi regolari e context free, esempio: ABC → aBCc. Una grammatica di questo tipo è detta di tipo 1.

5.2.4 Linguaggio ricorsivamente numerabile

Una grammatica riconosce un linguaggio context-sensitive se ha come regole di derivazione oltre a quelle dei linguaggi context free almeno una regola α → β dove α e β sono un insieme qualsiasi di caratteri terminali nonterminali mischiati a piacere (in una maniera ovviamente non compresa nei linguaggi regolari e context free, esempio: ABC → aB. Una grammatica di questo tipo è detta di tipo 0.

5.3 Tecniche di costruzione

5.3.1 Coppia ordinata

Per costruire una coppia ordinata si usa la tecnica dei linguaggi ben parentesizzati.

Esempio: aⁿbⁿ S→ aAb A→ aAb | ε

5.3.2 Più di una coppia ordinata

Analogamente al punto precedente proviamo a costruire aⁿc^md^mbⁿ. In questo esempio costruisco prima le coppie di nonterminali, li permuto e successivamente li trasformo in terminali.

S→ XS | S → SY

X → ABX

(9)

Y → Y CD

DC → CD

BA→ AB BC→ CB

BD→ DB

A→ a B→ b C→ c D→ d

5.3.3 Palindromi

E' possibile dimostrare che se un linguaggio è palindromo allora esiste una grammatica che lo genera.

6 Decidibilità

6.1 Denizioni

La decidibilità signica che eseguendo un dato algoritmo dopo un numero nito di passi ottengo una risposta (so che il programma termina o non termina). Non si tiene conto della complessità del codice che può essere arbitrariamente elevata ma non innita.

6.2 Semidecidibilità

La semidecidibilità è una condizione più debole: ovvero implica che dopo un certo numero di passi ottengo una risposta in condizioni nite, ma non posso dire nulla facendo un ulteriore passo. La terminazione è garantita quindi per un certo numero di input ma non per tutti gli input.

6.3 Provare la decidibilità

Se c'è un algoritmo che risolve il problema (e che termina in tempo nito), il problema è decidibile. Siccome non è quasi mai possibile individuare un algoritmo in tempo nito, abbiamo delle soluzioni alternative per provare se un problema è decidibile o meno:

6.3.1 Riduzione

Il problema si riduce ad un problema conosciuto universalmente come decidibile, semidecidibile o non decidibile. Esempio: Sapere se una macchina di Turing termina non è un problema decidibile.

(10)

Altri problemi noti non decidibili:

• Sapere se due programmi computano la stessa funzione (è una generaliz- zazione del problema non decidibile riguardante il programma che computa una determinata funzione)

• Sapere se due programmi computano la stessa funzione sapendo che termi- nano per ogni input (non decidibile perché il dominio di input è nito) Altri problemi noti decidibili:

• Sapere se due programmi computano la stessa funzione sapendo che termi- nano per ogni input e che il dominio di input è nito

Altri problemi noti semidecidibili:

• Sapere se due programmi che terminano per ogni input computano funzioni dierenti

• Sapere se due funzioni denite sullo stesso dominio sono dierenti 6.3.2 Tecnica di enumerazione diagonale

Si enumerano il numero di istruzioni e il numero di stati ai lati di un quadrato e si procede enumerando seguendo la diagonale. Se è possibile fare ciò il problema è semidecidibile, ovvero nchè funzioni e passi sono niti se la risposta esiste prima o poi la trovo.

6.3.3 Dimostrazione per assurdo

Nego la tesi e cerco di arrivare ad un assurdo con l'ipotesi

6.4 Teorema di Rice

Data una qualunque enumerazione ricorsiva di un insieme di funzioni e chiamato F il set di numeri di Godel contenuto in esso, F è decidibile se e solo se

• F è vuoto

• F è tutto l'insieme di funzioni

In poche parole non è possibile stabilire se un sottoinsieme di funzioni ricorsive termina solamente partendo da una determinata proprietà.

(11)

6.5 Cheat Table

Problema Complemento Decidibile Decidibile Semidecidibile Non decidibile Non decidibile Semidecidibile Non decidibile Non decidibile

Cosa ci dice questa tabella? Che se non possiamo sapere al volo se un problema è decidibile possiamo guardare il suo complemento: se il complemento è decidibile il problema è decidibile. Se il complemento è semidecidibile sappiamo già che il problema è non decidibile.

7 Complessità

7.1 Teoria della Complessità

La complessità riguarda la dimensione del calcolo sulle MT che terminano la com- putazione. La complessità viene scritta in relazione alla dimensione dei dati in ingresso n. In generale non è però valida l'equazione tra numero di dati in ingresso e complessità - ovvero algoritmi con lo stesso numero di dati in ingresso possono avere complessità dierenti. Nei nostri esempi prenderemo per motivi ingegneristici sempre il caso pessimo.

7.2 Relazioni Asintotiche

7.2.1 Notazione O-grande

La notazione O-grande indica il limite asintotico superiore della complessità - ovvero un valore sicuramente più grande del reale valore della complessità della funzione all'innito. Questo è il caso pessimo che verrà analizzato.

7.2.2 Notazione Omega-grande

La notazione O-grande indica il limite asintotico inferiore della complessità - ovvero un valore sicuramente più piccolo del reale valore della complessità della funzione all'innito. E' solitamente indicato come il valore da cui non si può prescindere in base alla struttura dati a disposizione - esempio: se l'algoritmo prevede la lettura di un vettore lungo n la complessità sarà sicuramente almeno Ω (n) se prevede una lettura di una matrice n ∗ n sarà sicuramente almeno Ω(

n²) , ecc..

7.2.3 Notazione Teta-grande

La notazione Teta-grande indica il limite asintotico esatto della complessità, ovvero - per il noto teorema del confronto di analisi 1 - il limite esatto, quando è possibile calcolarlo, della complessità della funzione. Ovvero quel limite in cui convergono i valori di Ω e O. Ad esempio dopo aver calcolato un algoritmo riguardante la lettura

(12)

asintotico superiore della complessità è O (n) è possibile scrivere che la notazione asintotica esatta di quell'algoritmo è Θ (n)

7.3 Proprietà delle relazioni asintotiche

7.3.1 Transitività

Se f (n) = Θ, Ω, Θ (g (n)) e g (n) = Θ, Ω, Θ (h (n)) allora f (n) = Θ, Ω, Θ (h (n)) 7.3.2 Riessività

f (n) = Θ, Ω, Θ (f (n)) 7.3.3 Simmetria

f (n) = Θ (g (n))⇐⇒ g (n) = Θ (f (n)) 7.3.4 Simmetria trasposta

f (n) = O (g (n))⇐⇒ g (n) = Ω (f (n))

7.4 Calcolo della complessità

Per semplicare si assegna un costo costante e pari a 1 a tutte le istruzioni. Il calcolo viene fatto quindi in base ai dati e alle funzioni dipendenti da n. Qui di seguito alcuni esempi in pseudocodice

for i = 1 to n i++;

Viene eseguito n volte in ogni caso. La complessità esatta è quindi Θ (n) while(i > n)

i = 2 * i;

Il contatore in questo caso viene incrementato come 2ⁿ. La complessità esatta è quindi Θ (Log2(n))

while(i > n) i = i * i;

Il contatore in questo caso viene incrementato in maniera esponenziale 2²ⁿ. La complessità esatta è quindi Θ (Log2Log2(n))

7.4.1 Note Utili

Il logaritmo iterato Log^∗equivale all'applicazione di cinque logaritmi, riduce il costo a 1 ed è quindi uguale a 5.

(13)

7.4.2 Calcolo della ricorsione

Può capitare nella risoluzione dei problemi di doversi trovare di fronte a casi di ricorsione. In questo caso vi sono tre vie possibili:

• Sostituzione

Si sviluppa la ricorsione di un passo e si cerca di minorare tutta la com- plessità di c ∗ n dove c è una costante.

• Albero di ricorsione

Vedi slide (WIP)

• Master Theorem

 Applicabile solamente alle ricorrenze: T (n) = aT(_n

b

)+f (n)con a, b >

1

 Possono vericarsi tre casi a seconda del valore k di una f (n) costante:

∗ k < logba→ T (n) = Θ( n^log^b^a)

∗ k = logba→ T (n) = Θ(

n^k∗ log (n))

∗ k > logba→ T (n) = Θ( n^k)

8 Gra e Alberi

8.1 Denizione

Un grafo è una coppia (V,E) in cui V è un insieme nito di nodi ed E è un insieme di relazioni che possono essere orientate o non orientate. Un grafo è orientato se i suoi archi lo sono, non orientato altrimenti

8.2 Cammino

Un cammino è una sequenza di nodi tali che tra ogni coppia c'è un arco. La lunghezza del cammino è uguale al numero di nodi meno uno. (Regola delle strette di mano in una stanza). Un grafo non orientato è connesso se tra ogni coppia di vertici esiste un cammino.

8.3 Alberi

Un albero è un caso particolare: è infatti un grafo connesso, aciclico non orientato.

Chiamiamo radice il primo nodo e fogli i nodi raggiungibili col cammino più lungo.

Ogni nodo ha un padre e uno o più gli (a parte le foglie).

(14)

8.3.1 Denizioni

• nodi interni: tutti i nodi dei cammini tra la radice e le foglie

• profondità (di un nodo N): la distanza di N dalla radice

• altezza (dell'albero): la distanza massima tra la radice e una foglia

• antenato (di un nodo N): ogni nodo che precede N sul cammino dalla radice a N

• padre (di un nodo N): il nodo che immediatamente precede N lungo il cam- mino dalla radice a N

• glio (di un nodo N): ogni nodo di cui N è padre

• fratelli (di un nodo N): i nodi che hanno lo stesso padre di N

• albero binario: albero in cui un nodo N ha al più due gli

Un vettore più essere trasformato in un albero binario di ricerca tramite l'algoritmo di Heapsort che viene eseguito in Θ (n ∗ Log (n))

9 Strutture dati

9.1 Pila

Struttura di oggetti su cui è possibile fare le seguenti operazioni:

• Controllare se è vuota

• Inserire un elemento in testa (push)

• Cancellare l'elemento in testa (pop)

La pila è quindi gestita con la politica LIFO. Se la pila contiene al massimo n elementi è implementabile come un array di lunghezza n.

9.2 Coda

E' simile alla pila, salvo la scelta della politica FIFO. Anche la coda se contiene al massimo n elementi è implementabile come un array di lunghezza n. Bisogna però tenere conto di due indici, ovvero l'indice dell'elemento da eliminare e quello dell'elemento dove inserire.

9.3 Liste doppiamente concatenate

A dierenza di pile e code qui gli elementi si puntano a vicenda. Ogni elemento contiene quindi l'informazione del precedente e del successivo. Se un oggetto non ha successore (puntatore a NULL) è l'ultimo elemento della lista, se invece non ha predecessore è il il primo elemento. E' possibile quindi scorrere la lista da entrambi i lati

(15)

9.3.1 Altre liste

• Concatenate in modo singolo: gli elementi non hanno il puntatore al prece- dente.

• Ordinate: l'ordinamento degli elementi nella lista è quello delle chiavi. Il primo elemento ha la chiave minima, l'ultimo la massima.

• Non Ordinate

• Circolari: il puntatore dell'ultimo elemento punta alla testa della lista (e vicev- ersa)

9.4 Dizionari a indirizzamento diretto

Si accede ai puntatori delle liste tramite le loro chiavi. La cardinalità dell'insieme delle chiavi possibili è ragionevolmente piccola dato che l'accesso deve essere veloce.

La maniera più veloce è quindi tramite un array a n elementi.

9.4.1 Tabella Hash

Una tabella Hash usa quindi eettivamente un numero di chiavi eettivamente memorizzate, tramite una funzione di hash. Problema: avrò necessariamente casi in cui k (h1) = k (h2), ovvero casi di collisione

1. I casi di collisione possono essere memorizzati in una lista concatenata 2. I casi di collisione possono essere memorizzati nella prima cella disponibile

immediatamente vuota.

9.5 Alberi Binari

9.5.1 Denizione

Un albero Binario è fatto di tre elementi: La radice, il sottoalbero sinistro e il sottoalbero destro. Tipicamente le strutture sono concatenate, ovvero ogni glio punta al padre e ai propri due gli.

9.5.2 Algoritmi di attraversamento dell'albero binario

• Inorder tree Walk: gli elementi vengono restituiti in ordine INORDER-TREE-WALK(x)

if x ̸= NIL

INORDER-TREE-WALK(x.left) print x.key

INORDER-TREE-WALK(x.right)

(16)

• Postorder tree Walk: la radice viene restituita dopo i sottoalberi. E' l'implementazione per eseguire operazioni con automi a pila. (2+5)*(3+7) viene infatti restituito 25+37+*

9.5.3 BST

Possiamo utilizzare l'albero binario per le operazioni di ricerca. In questo caso l'algoritmo avrà complessità nel caso pessimo O (h) dove h è l'altezza dell'albero.

L'altezza e quindi la complessità è minima nell'albero completo, ovvero quell'albero dove se x è un nodo ox ha due gli, o x è una foglia. Se l'albero è completo, la complessità diventa Θ (Log (n))

9.5.4 Alberi Rossoneri

Gli alberi rossoneri sono alberi bilanciati, ovvero alberi in cui l'altezza è costante h = O (Log (n)). Il bilanciamento consiste nel non avere mai un ramo lungo più del doppio di un altro. Un RB tree soddisfa le seguenti 5 proprietà

1. Ogni nodo o è rosso o è nero 2. La radice è nera

3. Le foglie sono nere

4. I gli di un nodo rosso sono entrambi neri

5. Per ogni nodo x l'altezza nera è uguale. N.b. l'altezza nera è il conteggio dei nodi neri escludendo il nodo x.

9.5.5 Operazioni sui Red and Black Tree

Inserimento: quando inserisco un nodo lo inserisco sempre come nodo rosso. Rista- bilisco quindi eventualmente colorando gli altri nodi la condizione 5. Attenzione alla radice - se alla ne del procedimento arrivo infatti ad avere una radice rossa, posso ristabilire la 2 colorandola di nero senza avere alcun problema.

9.6 Grafo come struttura dati

9.6.1 Algoritmi di visita del Grafo

1. Breadth-First Search. Visito i nodi in base alla loro profondità dal nodo di rifer- imento, il cui indirizzo è il valore che viene passato in esecuzione all'algoritmo.

2. Depth-First Search. Visito i nodi in profondità. Ovvero preso il nodo x, guardo la stella uscente e visito il primo glio. Se il nodo non ha gli torno al precedente.

)CHEJE A 2HE?EFE @A1BH=JE?= )AIIE =IIAJJE # LA>HA