Algoritmi e Principi dell’informatica (API) — Appunti TiTilda

Indice

Definizioni iniziali

Lunghezza di una stringa

La lunghezza di una stringa è il numero di simboli contenuti in una stringa (anche detta cardinalità e si indica con |x|).

La stringa vuota è la stringa che ha zero elementi (|\varepsilon| = 0).

Due stringhe sono uguali se e solo se:

Operazioni sui linguaggi

Prima di iniziare delle spiegazioni useremo le stringhe L_1 e L_2 così composte:

L_1 = \{ \varepsilon, a, b, c, bc, ca \} \\ L_2 = \{ ba, bb, bc, ca, cb, cc \}

Bene partiamo con la carrellata di operazioni.

Unione (L_1 \bigcup L_2)

L_1 \bigcup L_2 = \{ \varepsilon, a, b, c, ba, bb, bc, ca, cb, cc\} tutti gli elementi SENZA ripetizioni.

Intersezione (L_1 \bigcap L_2)

L_1 \bigcap L_2 = \{bc, ca\} SOLO elementi comuni.

Differenza (L_1 \setminus L_2 o L_1 - L_2)

L_1 \setminus L_2 = \{\varepsilon, a, b, c \} SOLO elementi NON comuni.

Complemento (L^c = A^* \setminus L)

A è l’alfabeto su cui L è definito.

* vuol dire tutte le ripetizioni possibili di quell’insieme, \varepsilon compreso.

L_1^c = tutte le stringhe su \{a, b, c\}* tranne stringhe di lunghezza 2 che iniziano con “b”, “c”.

Concatenazione (L_1 \cdot L_2 o L_1 L_2) NON è commutativa

L_1 \cdot L_2 = \{ba, bb, bc, ca, cb, cc, aba, abb, abc, aca, acb, acc, bba, bbb, bbc, bca, bcb, bcc, cba, cbb, cbc, cca, ccb, ccc, bcba, bcbb, bcbc, bcca, bccb, bccc, caba, cabb, cabc, caca, cacb, cacc\}

Potenza n-esima (L^n) concanetamento con se stesso n volte

L^i = \begin{cases} \varepsilon & i = 0 \\ L ^ {i - 1} \cdot L & i \gt 0 \end{cases}

La potenza È associativa.

Chiusura di Kleene

L^* = \bigcup_{n=0}^\infty L^n \\ \ \\ L^* = L^+ \bigcup L^0 = L^+ \bigcup \{\varepsilon\} \\ \ \\ L^+ = \bigcup_{n=1}^\infty L^n \\ \ \\ L^+ = L \cdot L^* \\ \ \\ \{\varepsilon\} \not = \emptyset \\

Automi a stati finiti

FSA (Finite State Automaton)

Un FSA ha un insieme finito di stati ovvero un numero limitato di configurazioni.

Es.

Un FSA è definito su un alfabeto (a, b, c o anche on, off, anche 1, 2, 3, insomma simboli o parole che noi definiamo come “input” anche C o Java possono essere definiti come tale).

Quando si riceve un input, il sistema cambia il suo stato (transizione).

Immagine di transizione

Gli FSA sono rappresentati tramite una tupla \lang Q, A, \delta, q_0, F \rang:

Per far sì che gli FSA riconoscano un linguaggio è necessario:

Immagine di stati finali e iniziali per dare la nostra convezione grafica

Una sequenza di mosse è di accettazione se raggiunge uno degli stati finali.

Esempio di un FSA:

Esempio di FSA preso da un esercizio

Trasduttori a stati finiti

FST (Finite State Transducer)

Sono FSA con 2 nastri.

È una tupla \lang Q, I, \delta, q_0, F, O, \eta \rang:

Esempio FST

Esempio di FST preso da un esercizio

Pumping Lemma

Se in un sistema a stati finiti si va da uno stato q_1 a q_1 (ovvero si attraversa un ciclo) vuol dire che lo si può fare n volte.

Perciò se:

x \in L e |x| \ge |Q| \implies q \in Q \land w \in I^+:

Dunque:

Conseguenze:

L = \empty se \exist x \in L \iff \exist y \in L, |y| \lt |Q|

|L| = \infty se \exist x \in L |Q| \impliedby |x| \lt 2|Q|

Problemi:

Operazioni su FSA

N.B. se un sistema è chiuso rispetto a un operazione vuol dire che il risultato è sempre parte dell’insieme.

Operazioni:

Sono operazioni CHIUSE negli FSA.

PDA (PushDown Automata)

Sono FSA con una pila.

La stringa d’ingresso x è accettata se:

Un PDA è una tupla \lang Q, I, \Gamma, \delta, q_0, Z_0, F \rang:

Esempio PDA:

Esempio di PDA preso da un esercizio

Configurazione

È una tripla \lang q, x, \gamma \rang

Le transizioni tra configurazioni (\vdash) mostra come commutare tra un PDA e un altro

Esempio

Dato \delta(q, i, A) = \lang q', \alpha \rang è definita

c = \lang q, x, \gamma \rang \vdash c'= \lang q', x', \gamma \rang

allora

Condizione di accettazione

\forall x \in I^* (x \in L \iff \exist q \exist \gamma c_0 = \lang q_0, x, Z_0 \rang \vdash^* c_f = \lang q, \varepsilon, \gamma \rang \land q \in F)

La stringa viene accettata se c’è un cammino coerente che va sallo stato iniziale a uno stato finale.

PDA VS FSA

I PDA non si fermano sempre dopo le mosse, ogni PDA si può trasformare in un PDA aciclico (si ferma sempre dopo le mosse).

PDT (PushDown Trasducer)

I PDT sono una tupla \lang Q, I, \Gamma, \delta, q_0, Z_0, F, O, \eta \rang:

Configurazione <q, x, \gamma, z>:

Condizione di accettazione:

\forall x \in I^* \forall z \in O^* (x \in L \land z = \tau(x) \iff \exist q \exist \gamma \colon c_0 = \lang q_0, x, Z_0, \varepsilon \rang \vdash^* c_f = \lang q, \varepsilon, \gamma, z \rang \land q \in F )

La traduzione è definita se e solo se x è accettata.

Esempio di PDT

Esempio di PDT preso da un esercizio

I PDT NON sono chiusi rispetto a Unione, Intersezione e Complemento.

Turing Machine (TM)

I PDA NON riconoscono a^n b^n c^n o a^n b^n \cup a^n b^{2n}.

La pila è una memoria distruttiva, letto un elemento viene eliminato.

C’è bisogno di NASTRI DI MEMORIA.

Le TM usano i nastri come memorie:

I nastri sono sequenze infinite di celle con “Blank” (segnato come “\cancel{b}”, “_” o “-”).

Mosse

Uguali a prima con aggiunta di:

Spostamento testine dichiarato con 3 movimenti:

Si esplicita SEMPRE.

Le TM sono una tupla \lang Q, I, \Gamma, \delta, q_0, Z_0, F \rang:

Esempio di TM

Esempio di TM preso da un esercizio

La Configurazione di una TM con k nastri è una (k+2)-tupla:

c = \lang q, x \uparrow iy, \alpha_1 \uparrow A_1 \beta_1, \dots, \alpha_k \uparrow A_k \beta_k \rang

\uparrow indica la posizione della testina.

Condizione di accettazione:

\exist q \exist x' \exist i \exist y \exist \alpha_1 \exist A_1 \exist \beta_1 \dots \exist \alpha_k \exist A_k \exist \beta_k \colon c_0 = \lang q_0, \uparrow x, \uparrow Z_0, \dots, \uparrow Z_0 \rang \vdash_m^* c_F = \lang q, x'\uparrow iy, \alpha_1 \uparrow A_1 \beta_1, \dots, \alpha_k \uparrow A_k \beta_k \rang con q \in F e x = x'iy

TM VS PDA

I linguaggi accettati da TM sono detti ricorsivamente enumerabili.

TM e Macchine di Von Neumann (VNM)

La differenza sta nell’accesso alla memoria:

Il tipo di accesso NON cambia la potenza.

Le TM possono simulare le VNM.

Operazioni TM

Le TM sono chiuse rispetto a:

NON sono chiuse rispetto a:

Se esistessero TM acicliche sarebbero chiuse al complemento, il problema sta dove le computazioni non terminano.

TM Trasduttrice

Le TM trasuttrici a k nastri sono una tupla di 9 elementi \lang Q, I, \Gamma, O, \delta, \eta, q_0, Z_0, F \rang:

N.B. Le testine di uscita si muovono in 2 direzioni:

Esempio di TM traduttrice

Esempio TM traduttrice preso da un esercizio

Configurazione

c = \lang q, x \uparrow iy, \alpha_1 \uparrow A_1 \beta_1, \dots, \alpha_k \uparrow A_k \beta_k, u \uparrow o \rang

Le TM possono:

Le TM sono computer con accesso sequenziale alla memoria (Modello astratto).

Le TM possono avere nastri a n dimensioni.

N.B. Più dimensioni NON aggiungono potenza.

Modelli non deterministici

Di solito un algotimo ha una sequenza deterministica.

Il non deterministmo (ND) è un modello di computazione, utile per algoritmi di ricerca.

Esempio di ND

NFSA

Gli NFSA sono gli FSA non deterministici e sono una tupla : \lang Q, I, \delta, q_0, F \rang

\delta^* (q, \varepsilon) = \{q\} \\ \delta^* (q, y, i) = \bigcup \delta\{q', i\}

Condizione di accettazione

x \in L \iff \delta^* (q_0, x) \bigcap F \not ={\emptyset}

Basta che una vada a buon fine.

ND esistenziale

\delta^* (q_0, x) \subseteq F

DFA VS NFA

Se A_{ND} = \lang Q, I, \delta, q_0, F \rang \implies A_{D} = \lang Q_D, I, \delta_D, q_{0D}, F_D \rang

Perchè il ND ? (già è difficile di suo ora ci complichiamo la vita)

Gli NFA hanno pari potenza di DFA, ma non sono inutili (purtroppo):

Esempio di NFA

Esempio di NFA preso da un esercizio

TM non deterministici (NTM)

Per definire una NTM occorre cambiare la funzione di transizione e la funzione di traduzione.

Esempio NTM

Esempio di NTM preso da un esercizio

Condizione di accettazione

Una stringa è accettata se e solo se esiste unna computazione con uno stato di accettazione.

Che cosa è la visita dell’albero computazionale ?

Diverse modalità :

Si può costruire una DTM che visita un albero livello dopolivello ma è un processo molto lungo e noioso.

ND NON aggiunge potere alle TM

PDA non deterministici (NPDA)

L e \varepsilon-mosse avevano il seguente vincolo:

\delta(q, \varepsilon, A) \not ={\bot}\implies\delta(q, i, A) = \bot; \forall i \in I

Senza di esso i PDA sarebbero intrinsicamente ND.

Un NPDA è una tupla \lang Q, I, \Gamma, \delta, q_0, Z_0, F \rang

\mathcal{P_F} indica i sottoinsiemi finiti di Q \times \Gamma^*

Esempio di NPDA

Esempio di NPDA preso da un esercizio

Condizione di accettazione

Dato un NPDA:

\forall x \in I^* (x \in L(P) \iff \exist q \exist \gamma c_0 = \lang q_0, x, Z_0 \rang \vdash^* c_F = \lang q, \varepsilon, \gamma \rang e q \in F)

Una stringa è accettata se c’è un cammino coerente con x che va dallo stato inizio a uno di fine.

ND noi PDA aggiunge potere, riconosce \{ a^nb^n | n\ge 1\} \bigcup \{a^nb^{2n} | n \ge 1\}

I linguaggi riconoscibili dai PDA sono detti context-free.

DPDA chiusi rispetto al complemento.

NON chiusi rispetto unione, intersezione e differenza.

NPDA chiusi rispetto unione.

NON chiusi rispetto intersezione, complemento e differenza.

Schema dei poteri
Proprietà chiusura FSA DPDA NPDA TM
Unione SI NO SI SI
Intersezione SI NO NO SI
Complemento SI SI NO NO
Concanetazione SI NO SI SI
Stella di Klenee SI NO SI SI

Grammatiche

Esistono 2 tipi di modelli:

I modelli generativi producono stringhe (grammatica).

Una grammatica è un insieme di parole per costruire le frasi di un linguaggio \to tramite riscrittura (insieme di metodi).

Regole linguistiche

Le regole linguistiche descrivono un “oggetto principale” con una sequenza di componenti.

I componenti vengono dettagliati fino ad andare alla base (vuol dire che es. da staccionata si arriva a Assi, Martello, Chiodi).

Una grammatica è una tupla \lang V_N, V_T, P, S \rang

Una grammatica genera un linguaggio sull’alfabeto V_T

Produzioni

Elemento di V_N^+ \times V^* (\lang \alpha, \beta \rang | \alpha \in V_N^+, \beta \in V^*)

Si indica con \alpha \to \beta

Gerarchia Chomsky

Esistono 4 tipi di grammatiche

Tipo Nome Produzioni Macchine
3 Regolari (Destre) A \to \alpha, A \to aB (A \to \varepsilon) con A,B \in V_N, a \in V_T FSA
2 Context-free A \to B, A \in V_N NPDA
1 Context-sensitive e monotone S \to \varepsilon, \alpha A \beta \to \alpha \gamma \beta con A \in V_N, \alpha, \beta, \gamma \in V^+ (ora monotone) \alpha \to \beta con \vert \alpha \vert = \vert \beta \vert Automi lineari (NTM usano uno spazio di memoria proporzionale all’input)
0 Generali o non ristrette P \subseteq V_N^+ \times V^+ TM

Reazioni di derivazione immediata

\alpha \implies \beta (\beta è ottenuta immediatamente da \alpha)

se e solo se

\alpha = \alpha_1 \alpha_2 \alpha_3, \beta = \alpha_1 \beta_2 \alpha_3 e \alpha_2 \to \beta_2 \in P

\alpha_2 riscritta come \beta_2 nel contesto \lang \alpha_1, \alpha_3 \rang

Es. (Context-Sensitive)

V_N = \{S,A, B, C, D\}\\ V_T = \{a, b, c\}\\ S\\ P = \{S \to AB, BA \to cCD, CBS \to ab, A \to \varepsilon\}\\ aaBAS \implies aacCDS \\ bcCBSAdd \implies bcabAdd

Linguaggio generato

Data G = \lang V_N, V_T, P, S \rang

\forall x (x \in L(G) \iff x \in V_T^* \land S \implies(+) x)

Il linguaggio generato da G è l’insieme di tutte le stringhe:

ES. (Context-Free)

G_2 = \lang \{S\}, \{a, b\}, \{S \to a Sb | ab\}, S \rang \\ S \to aSb |ab = S \to aSb, S \to ab

Derivazioni

S \implies ab

$S aSb aabb $

S \implies aSb \implies aaSbb \implies aaabbb

Generalizzo L(G_2) = \{a^nb^n|n> 0\}

Regular Grammar (RG) VS FSA

Sia A un FSA, si può costruire un RG G ad esso equivalente.

G genera esattamente lo stesso linguaggio riconosciuto da A.

Le RG, FSA e espressioni regolari descrivono lo stesso linguaggio in modelli diversi.

Le context-free grammar (CFG) sono identiche alle Backus-Naus Form (BNF) usate per definire la sintassi dei linguaggi di programmazione.

Le grammatiche regolari sono anche non contestuali

I linguaggi possono essere rappresentati tramite molti modelli tra cui :

Pattern

È una tripla \lang A, V, p \rang

Il pattern genera un linguaggio che ha tutte le stringhe di A ottenute da p sostituendo ogmi variabile in p con una stringa su A.

Es. \lang \{0, 1\}, \{v_1, v_2\}, v_1v_1 \circ v_2 \rang

RE: sintassi e semantica

Definizione di un RE su un alfabeto A \colon

Siano r e s due RE, allora:

Es.

((0.(0|1)^*)|((0|1)^*.0)) è una RE su \{0, 1\}

RE e Pattern

Le RE hanno la stessa idea dei Pattern ma diverso potere.

RE \not ={Pattern}.

\{xx | x \in \{0, 1\}^*\} NO RE

Pattern corrispondente \lang \{0, 1\}, \{x\}, xx \rang

Linguaggio denotato da 0^*1^* NON ESPREMIBILE tramite Pattern.

RG e RE

RG = RE.

RE POSIX (Linux/Unix)

Caratteri meta: ( ) . [ ] ^  $ * + | { }

N.B. “.” indica qualunque carattere, NON concatenazione.

[\alpha] indica un singolo carattere \in \alpha ([abc] indica \{a, b, c\}).

[\^\ \alpha] negazione: qualunque carattere non in \alpha.

^ e $ indicano \varepsilon corrispettivamente all’inizio e alla fine della riga.

*, +, |, (, ) uguali a sempre.

 “escape” ( $ indica il simbolo $).

\alpha ? indica \alpha opzionale.

\alpha \{n\} indica \alpha^n

\alpha \{n, m\} indica \alpha^n \bigcup \alpha ^{n+1} \bigcup \dots \bigcup \alpha^m

Logica

Esistono vari linguaggi logici :

La logica è un formalismo “universale” e si applica in molti ambiti :

Gli insiemi possono essere visti come abbreviazioni di formule FOL.

Es.

\{a^nb^n | n \ge 0\} \to abbreviata di \forall x (x \in L \longleftrightarrow \exist n (n \ge 0 \land x = a^n.b^n))

x^n ?

\forall n \forall x ((n=0 \to x^n = \varepsilon) \land (n > 0 \to x^n = x^{n-1}.x))

Ora faremo un bell’ elenco di operazioni logiche, buon viaggio ; )

L_1 = a^*b^*

L_1 è il linguaggio delle stringhe su \{a, b\} con tutte le “a” all’inizio.

Più precisamente L_1 è:

Esprimibile come:

\forall x (x \in L_1 \longleftrightarrow (x = \varepsilon) \lor \exist y (x=ay \land y \in L_1) \lor \exist y (x=yb \land y \in L_1))

L_2 = a^*b^*c^*

Una stringa appartiene a L_2 se è:

In FOL:

\forall x (x \in L_2 \longleftrightarrow (x \in L_1) \lor (x \in L_3) \lor \exist y (x = ay \land (y \in L_2 \lor y \in L_3)) \lor (x=yc \land (y \in L_2) \lor y \in L_1))

Esempio

L_4 = \{x \in \{a,b\}^* |numero\ di\ 'a'\ uguale\ al\ numero\ di \ 'b'\}

In FOL: \forall x (x \in L_4 \longleftrightarrow \# (x,a)= \# (x,b))

MFO: Logica monadica del prim’ordine

MSO: Logica monadica del secondo ordine

\exist P (\forall x (\neg P(0) \land (\neg P(x) \Longleftrightarrow P(x+1))\land a(x)\land (last(x) \implies P(x))))

Per ogni FSA esiste un MSO equivalente

Da una MSO \phi è possibile costruire un FSA (Teorema di Büchi-Elgot-Trakhtenbrot)

I linguaggi definibili da formule MSO sono linguaggi regolari

Quando si programma una funzione è importante definire COSA FA.

Precondizione: indica cosa deve valere prima che la funzione sia invocata.

Postcondizione: indica cosa deve valere dopo che la funzione ha finito la propria esecuzione.

Struttura generale (notazione di Hoare)

P deve essere tale che se Pre vale prima dell’esecuzione, allora Post vale dopo l’esecuzione.

\to FOL può essere usata per questo scopo.

Abbreviazioni logiche

\forall k \in \mathbb{N}, k \ge 1 (k fissato NON si può quantificare !!!)

Vero sse Q \subseteq P \ Q contiene la I, II, V posizione di P.

Computabilità

Algoritmo di ricerca

Pre: l’array è ordinato.

Post: la variabile logica “found(un flag)” dev’essere vera sse l’elemento cercato esiste nell’array.

Pre \{\forall i (1 \le i \le n-1 \to a[i] \le a[i+1])\} \\ P \\ Post \{found \longleftrightarrow \exist i (1 \le i \le n \land a[i] = x)\}

Ordinamento

Pre: l’array NON contiene ripetizioni.

Post: l’array ottenuto è ordinato.

Formalmente

\{\neg \exist i, j (1 \le i \le n \land 1 \le j \le n \land i \not ={j} \land a[i] = a[j])\} \\ ORD \\ \{\forall i (1 \le i \le n-1 \to a[i] \le a[i+1])\}

Tesi di Church (Parte 1)

Non c’è nessun formalismoper modellare il calcolo meccanico che sia più potente della TM (o formalismi equivalenti)

Algoritmo: Procedura per risolvere problemi mediante un dispositivo di calcolo automatico.

Tesi di Church (Parte 2)

Ogni algoritmo può essere codificato mediante una TM (o formalismo equivalente)

Una TM può essere vista come un computer astratto, non programmabile, predisposto per un uso speciale.

Un insieme S può essere enumerato algoritmicamente (E) se possiamo trovare una biiezione tra S e \natnums.

Esempio

\{a,b\}^*

\varepsilon\ a\ b\ aa\ ab\ ...

0\ 1\ 2\ 3\ 4\ ...

Le TM possono essere enumerate algoritmicamente

Ipotesi:

Esempio: TM con due stati

2^2=4 stati finali possibili.

Quante funzioni f: D \to R ? \to |R|^{|D|}

Con |Q| = 2, |A|=3, (2 * 3+3+1)^{(2*3)} = 19^6 con 2 stati considerando i 2^2 scelte di stati finali, abbiamo (al più) 19^6 * 2^2 TM.

Ordiniamo TM: \{M_0,...,M_{19^6*2^2 -1} \}

Otteniamo un’enumerazione E: \{TM\} \to \natnums

E(M) è detto numero di Gödel di M e E è una Gödelizzazione

Le TM modellano computer programmabili? Si

UTM computa g(y, x)=f_y(x)

funzione calcolata dalla y-esima TM sull’ingresso x.

Possiamo codificare g(y,x) come una g^{(n)} = g(d^{-1}(n)) con n= d(y,x), (y,x) = d^{-1} (n)

Le TM computano tutte le funzioni da \natnums a \natnums?

No, ci sono funzioni che possono essere computate dalla UTM.

Esistono 2^{\alef_0} funzioni f: \natnums \to \natnums.

\alef_0 si legge “alef con zero”

Il “problema dell’arresto” (halting problem)

In termini di TM:

g(y,x) =1\ se\ f_y(x) \not ={\bot}, g(y,x)=0\ se \ f_y(x)=\bot

C’è TM che calcola g?

No

Dimostrazione per diagonalizzazione

Listiamo le funzioni calcolabili da \natnums a \natnums e i loro valori, disponendo ogni valore f_y(x) in una tabella:

Definiamo una funzione \phi: \natnums \to \natnums che differisce dalla diagonale in ogni valore.

Nessuna TM può decidere se, data una generica TM M e un generico ingresso x, M si arresta con l’ingresso x.

Lemma importante

h'(x)= se f_x(x)\not ={\bot} allora 1 altrimenti 0

Un problema non risolvibile può avere un caso particolare risolvibile.

Se un problema è risolvibile, una generalizzazione può non essere risolvibile.

Problemi di decisione

Domanda con due possibili risposte: si e no.

Semidecidibile se c’è un algoritmo che dice si se la risposta è si

Insiemi Ricorsivi

Concentriamoci sui problemi a risposta binaria:

Problema= x appartiene all’insieme S? (S \le N)

C_S(x)=\ se \ x \in S\ allora\ 1\ altrimenti\ 0

Un insieme S è ricorsivo sse la sua funzione caratteristica è computabile.

S è ricorsivamente enumerabile sse:

S=l_{g_s}=\{x|x=g_s(y),y\in \natnums\} \\ \implies \\ S=\{g_s(0), g_s(1), g_s(2),...\}

Teorema (1/2+1/2=1)

La classe di insiemi decidibili è chiusa rispetto al complemento.

Teorema del punto fisso di Klenne

Sia t una funzione totale e computabile. Allora si può sempre trovare un intero p tale che f_p=f_{t_{(p)}}

Teorema di Rice

Sia f un insieme di funzioni computabili l’insieme &S& degli indici delle TM che calcolano le funzioni di F

S=\{x|f_x \in F\}

è decidibile sse:

\to in tutti i casi non banali S non è decidibile!

Dal teorema di RIce

Implicazioni negative

Dato F=\{g\}, per Rice non è decidibile se una generica TM calcoli g o meno.

Teorema di Rice (variante)

Sia S \subseteq \mathbb{N} tale che

  1. S \not = \empty
  2. S \not = \mathbb{N}
  3. se s \in S e la TM n-esima è equivalente alla TM m-esima allora m \in S (S è l’insieme di tutte e sole le codifiche di certe TM/prog/funz. computabili)

Allora S non è decidibile.

Esempio di utilizzo

Esistano TM M e M’ tali che M è equivalente a M’

H = \{ n \in \mathbb{N} | M=\lang n \rang \ e\ M(\varepsilon) \downarrow \} è decidibile ?

  1. H \not = \empty: ci sono TM che terminano su \varepsilon
  2. H \not = \mathbb{N}: ci sono TM che NON terminano su \varepsilon
  3. se M=M' e \lang M \rang = n e \lang M' \rang = n e n \in H allora H (\varepsilon) \downarrow e poichè M=M' anche M'(\varepsilon) \downarrow e dunque n' \in H

Quindi Rice è soddisfatto e H NON è decidibile.

Riduzione di problemi

Un problema P' è ridotto a un problema P se un algoritmo per risolvere P viene usato per risolvere P'

  1. Determina una corrispondente istanza di P
  2. Costruisce algoritmicamente la soluzione dell’istanza di P' dalla soluzione dell’sistanza di P

Riduzione (Variante)

Siano A,B \subseteq \mathbb{N} e f: \mathbb{N} \to \mathbb{N}, f è una riduzione da A a B.

  1. f è TOTALE e COMPUTABILE
  2. se n \in A allora f(a) \in B
  3. se n \not \in A allora f(a) \not \in B
Teorema

Se A non è ricorsivo allora B non è ricorsivo.

Caratteristiche di alcuni linguaggi

Regolari \implies Ricorsivi

Context-free \implies Ricorsivo

Context-Sensitive \implies Ricorsivo

Ricorsivo \implies Ricorsivamente enumerabile

Ciò implica che sicuramente un linguaggio ricorsivo è R.E. ma non vuol dire che lo sia sempre anche il contrario

Complessità del calcolo

Per la tesi di Curch-Turing, un problema è calcolabile o meno indipendentemente dallo strumento usato.

Per la complessità del calcolo ?

Data la computazione c_0 \vdash c_1 \vdash c_2 \vdash ... \vdash c_r di M (a k nastri) deterministica.

La complessità temporale è T_M (x)=r se M termina in c_r

M è deterministica \implies computazione unica sull’ingresso x

Complessità spaziale

S_M(x) = \Sigma _{j=1}^k max_{i \in \{0,...,r\}} (|a_{ij}|)

Somma della quantità massime occupate

\forall x: \dfrac{S_M (x)}{k} \le T_M (x)

Notazione

\Omicron-grande : limite asintotico superiore

\Omega-grande: limite asintotico inferiore

\Theta-grande: limite asintotico sia superiore che inferiore

\Omicron-grande

Data g(n), \Omicron(g(n)) è l’insieme \Omicron(g(n))=\{f(n) | \exist c > 0, n_0 >0\ tali\ che\ \forall n>n_0, 0 \le f(n) \le c*g(n)\}

\Omega-grande

Data g(n), \Omega(g(n)) è l’insieme \Omega(g(n))=\{f(n) | \exist c > 0, n_0 >0\ tali\ che\ \forall n>n_0, 0 \le c*g(n) \le f(n) \}

\Theta-grande

Data g(n), \Theta(g(n)) è l’insieme \Theta(g(n))=\{f(n) | \exist c_1 > 0, c_2 >0, n_0 >0\ tali\ che\ \forall n>n_0, 0 \le c_1*g(n) \le f(n) \le c_2*g(n) \}

Proprità notevoli

f(n) \in \Theta(g(n)) \iff f(n) \in \Omicron(g(n)) \land f(n) \in \Omega (g(n))

Transitività

f(n) \in \Theta(g(n)) \land g(n) \in \Theta(h(n)) \implies f(n) \in \Theta (h(n))

f(n) \in \Omicron(g(n)) \land g(n) \in \Omicron(h(n)) \implies f(n) \in \Omicron(h(n))

f(n) \in \Omega(g(n)) \land g(n) \in \Omega(h(n)) \implies f(n) \in \Omega(h(n))

Riflessività

f(n) \in \Theta(f(n))

f(n) \in \Omicron(f(n))

f(n) \in \Omega(f(n))

Simmetria: f(n) \in \Theta(g(n)) \iff g(n) \in \Theta(f(n))

Simmetria trasposta: f(n) \in \Omicron(g(n)) \iff g(n) \in \Omega(f(n))

\Theta è una relazione di equivalenza.

Teorema

Se L è accettato da una TM M a k nastri in S_M (n), \forall c \in \reals^+ posso costruire una TM M' a k nastri che accetta L con S_{M'} < c*S_M(n)

Teorema

Se L è accettato da una TM M a k nastri in S_M(n), posso costruire una TM M' a 1 nastro (non nastro singolo) che accetta L con S_{M'}(n) = S_M(n)

Teorema

Se L è accettato da una TM M a k nastri in S_M(n), \forall c \in \reals^+ posso costruire una TM M' a 1 nastro accetta L con S_{M'}(n)< c*S_M(n)

Teorema

Se L è accettato da una TM M a k nastri in T_M(n), \forall c \in \reals^+ posso costruire una TM M' a k+1 nastri accetta L con T_{M'}(n) = max (n+1, c*T_M(n))

Macchina RAM

La macchina RAM è dotata di un nastro di lettura In e uno di scrittura Out come la TM.

È dotata di una memoria con accesso a indirizzamento diretto N[n], n \in \natnums al posto dei nastri di memoria: l’accesso non necessita di scorrimento delle celle.

Le istruzioni di un programma usano normalmente come sorgente il primo operando e come destinazione N[0]

Riconoscere L=\{wcw^R\}

T_{RAM}(n) = \Theta (n)

S_{RAM}(n) = \Theta (n)

Ricerca Binaria T_{RAM}(n)=\Theta(log(n))

Ricerca di 2^{2n}

Input: una sequenza ordinata di interi ed un numero da cercare in essa.

Output: 1 se l’elemento cercato esiste nella sequenza, 0 altrimenti.

Consideriamo il caso del calcolo di 2^{2n} con una RAM

read (n);

x=2;

for (int i=0; i<n; i++)\ x=x*x;

write(x);

Complessità temporale: T_{RAM} (n)= k_1+k_2+nk_3+k_4= \Theta (n)

Servono 2^n bit per scrivere il risultato !!!

Complessità a costo logaritmico: T_{RAM} (n)= \Omicron(log(n)+n(2^{n-1}+2^{2n-2}+2^n+3log(n))+2^n)=\Omicron(n2^{2n-2})

(Tesi) di correlazione polinomiale

Sotto “ragionevoli” ipotesi di criterio di costo, se un problema è risolvibile mediante il modello M_1 con complessità c_1(n), allora è risolvibile da un qualsiasi altro modello (turing equivalente) M_2 con complessità c_2(n) \le \pi (c_1(n)), dove \pi(*) è un opportuno polinomio.

Algoritmi

Si usa pseudocodice

Esempio: Ordinamento

INSERTION-SORT(A) \\ for\ j :=2\ to \ A.length \\ key:=A[j] \\ //inserisce\ A[j]\ nella\ sequenza\ ordinata\ A[1...j-1] \\ i:=j-1 \\ while\ i>0\ and\ A[i]>key \\ A[i+1]:=A[i] \\ i:=i-1 \\ A[i+1]:=key

Visto che questa lezione si basa su scrivere codici e analizzarne solo certe parti io mi limiterò a scrivere le parti più importanti.

I paramentri sono passati per valore.

Quando un oggetto viene passato come paramentro, ciò che viene passato è il puntatore all’oggetto.

La macchina RAM esegue gli algoritmi in pseudocodice.

Si adotta il criterio di costo costante (tempo costante c_i) ci concentriamo solo sulla complessità temporale.

Algoritmo ordinamento complessità temporale

T(n)=c_1n+c_2(n-1)+c_4(n-1)+c_5\Sigma_{j=2}^n t_j+c_7\Sigma_{j=2}^n(t_j-1)+c_8(n-1)

Se l’array è già ordinato T(n)=an+b \implies T(n) = \Theta (n)

Se ordinato ma in ordine decrescente T(n)=an^2+bn+c \implies T(n)=\Theta(n^2)

Merg-Sort (del tipo “divide et impera”)

Si ordina dividendo l’array in 2 sotto-array, si ordinano e si fondono.

Complessità di un algoritmo divide et impera

Equazione di ricorrenza

\begin{cases} \Theta (1)\ se\ n<c \\ D(n) + aT(n/b)+ C(n) \end{cases}

a si divide in sottoinsiemi di dimensione 1/b ognuno.

D(n) costo di dividere il problema, C(n) costo di ricombinare i sottoproblemi e T(n) è il costo per risolvere il problema totale.

Ricorrenza per Merge-Sort

T(n)= \begin{cases} \Theta (1)\ se\ n<2 \\ 2T(n/2)+\Theta(n)\ altrimenti \end{cases} \\ a=b=c=2, D(n)= \Theta(1), C(n)=\Theta(n)

Teorema dell’esperto (master theorem) \implies NON COPRE TUTTI I CASI

(a \ge 1, b \ge 1 \ e \ n/b\ è\ o\ \lfloor n/b \rfloor\ o\ \lceil n/b \rceil)

  1. Se f(n) = \Omicron (n^{log_ba-\varepsilon}) \varepsilon >0,\ allora\ T(n) = \Theta(n^{log_ba})
  2. Se f(n) = \Theta (n^{log_ba}),\ allora\ T(n) = \Theta(n^{log_ba}log(n))
  3. Se f(n) = \Omega (n^{log_ba+\varepsilon}) \varepsilon >0,\ e\ af(n/b) \le cf(n) per qualche c<1 e per tutti gli n grandi a sufficienza, allora T(n) = \Theta (f(n))

Teorema dell’esperto MERGE-SORT

T(n) = 2 T(n/2) + \Theta (n)

a=b=2 \\ f(n)=n \\ n^{log_ba}=n'=n

Secondo caso

T_{MERGE-SORT}(n)= \Theta (nlog(n))

Caso particolare

Se f(n) è una funzione \Theta (n^k) per qualche k:

nel 3° caso la regolarità è verificata automaticamente.

Condizione di regolarità

Sia T(n) = T(n/2)+n(2-cos(n)), a=1\ b=2

f(n)=n(2-cos(n))=\Omega (n)>n^{log_ba}=\Theta (1)

HEAPSORT

È un algoritmo di ordinamento efficace (ordina in tempo \Theta (n log(n))) ma ordina sul posto.

Un heap binario è un albero quasi completo

Un max heap è un heap tale che \forall nodo x dell’albero, il valore contenuto nel padre di x è \ge del contenuto di x.

Complessità di MAX-HEAPIFY

T_{MAX-HEAPIFY} = \Omicron (n), n altezza albero = \Omicron(log(n)) poichè l’albero è quasi completo \implies T_{MAX-HEAPIFY}=\Omicron(log(n))

QUICKSORT (tipo “divide et impera”)

Albero di decisione (binario)

Ogni albero binario di altezza n ha un numero di foglie al più 2^n

TEOREMA

Ogni albero di decisione di ordinamento di n elementi ha altezza \Omega (nlog(n))

Ricorrenze di ordine costante

a_i intero \ge 0

T(n)= \begin{cases} \Theta (1)\ se\ n \le m \le h \\ \Sigma_{1\le i\le n} a_i T(n-i)+cn^k\ se\ n>m \end{cases} \\ a=\Sigma_{1\le i\le n} a_i

se a=1, allora T(n)= \Omicron(n^{k+1})

se a \ge 2, allora T(n) = \Omicron(a^n n^k)

Esempio T(n)=T(n-1)+\Theta(n) ottengo T(n) = \Omicron(n^2)

Versione ricorsiva di INSERTION-SORT

Conting-Sort

T= \Theta (n) \ S=\Theta (n)

Ordinamento per conteggio, NON per confronto.

Ipotesi: numeri naturali da 0 a k.

Strutture Dati

Le strutture dati sono usate per contenere oggetti.

Rappresentano collezioni di oggetti.

Spesso, ma non sempre, gli oggetti di una struttura dati hanno:

Due tipi di operazioni sulle strutture dati:

ELENCO OPERAZIONI

Pila (Stack)

Collezione di oggetti sulla quale fare le seguenti operazioni:

Si gestisce con la politica LIFO (Last In First Out).

Si può implementare come un array.

Coda (Queue)

Simile alla pila a FIFO (First In First Out)

Stesse operazioni:

N.B. DEQUEUE restituisce l’elemento tolto

Anche la coda può essere implementata tramite array.

Liste (doppiamente) concatenate

È simile a una lista dinamica in cui ogni oggetto ha 3 attributi:

Altri tipi di lista:

Dizionario: insieme dinamico che supporta solo le operazioni di INSERT,\ DELETE,\ SEARCH.

Si accede agli oggetti tramite le chiavi.

Si assume che le chiavi siano numeri naturali.

Indirizzamento Diretto

Tabelle Hash

Una tabella hash usa una memoria proporzionale al numero di chiavi effettivamente memorizzate nel dizionario.

Idea fondamentale: oggetto di chiave k è memorizzato in una cella di indice h(k), dove h è una funzione hash.

Collisioni

Problema: ho |U| possibili chiavi ed una funzione che le deve mappare su un numero m < |U| di slot o bucket della tabella

Una possibile soluzione è il concatenamento (chaining)

Chaining

Operazioni:

Analisi complessità

Nel caso pessimo, tutti gli n elementi vengono memorizzati nello stesso slot quindi la complessità è quella di cercare in una lista di n elementi, cioè \Omicron(n)

Siano:

siccome 0 \le n \le |U| avremo 0 \le \alpha \le |U|/m

Ipotesi dell’hashing uniforme semplice

Ogni chiave ha 1/m probabilità di finire in qualsiasi delle m celle di T, la lunghezza media di una lista è:

E[n_j]=\frac{1}{m} \Sigma_{i=1}^m n_i = \frac{n}{m} = \alpha

Il tempo medio per cercare una chiave k NON presente è \Theta (1+\alpha) (\Omicron (1) tempo per calcolare h(k))

\Theta (1+\alpha) è il tempo anche per trovare una chiave k presente.

\Omicron (1) per le operazioni (INSERT, etc.)

Funzioni Hash

Come si sceglie bene una funzione h ?

Ne dovrei prendere una che soddisfa l’ipotesi di hashing uniforme semplice, per farlo devo sapere la distribuzione di probabilità (NON ANCHE QUIIIIIIII :( ) delle chiavi da inserire.

Assunzione: la chiave k è un intero non-negativo.

Metodo di divisione

h(k) = k\ mod\ m

Ovvero prendo solo il resto della divisione.

Facile da realizzare e veloce

Evitare valori di m come:

di solito ad m si assegna un numero primo lontano da una potenza di 2.

Esempio

h(k) = k\ mod\ m \\ m=5 \\ Inseriamo:\ 38,12,18 \\ \frac{38}{5}=3\ hash(38)= 3 \\ si\ ha\ h(38)=3, h(12)=2, h(18)=3 \\ T=[NIL,NIL,lista(12),lista(18,38),NIL]

Metodo di moltiplicazione

Moltiplichiamo k per una costante A reale tale che 0 < A < 1, quindi prendiamo solo la parte ffrazionaria di kA, lo moltiplichiamo per m e prendiamo la parte intera.

cioè h(k)=\lfloor m(kA\ mod\ 1)\rfloor di cui x\ mod\ 1 = x - \lfloor x \rfloor è la parte frazionaria di x.

m può essere valore di A

È meglio prendere un valore di A che sia della forma s/2^w con w dimensione della parola di memoria del calcolatore.

Un valore di A proposto (da Knuth) è:

A=(\sqrt{5}-1)/2

Inveso sezione aurea

Esempio

h(k)=\lfloor m(kA\ mod\ 1)\rfloor \\ A=(\sqrt{5}-1)/2 \\ m=5 \\ 38,18,12 \\ \lfloor 38*A \rfloor =0,484 \\ \lfloor m*(38*A) \rfloor=2 \\ h(38)=2,h(12)=2,h(18)=0 \\ T=[lista(18),NIL,lista(12,38),NIL,NIL]

Indirizzamento aperto

Altro metodo per evitare collisioni

La tabella contiene tutte le chiavi, senza memoria aggiuntiva.

L’idea è quella di calcolare lo slot in cui va memorizzato l’oggetto.

h ora diventa:

h:U \times \{0,1,...,m-1\} \to \{0,1,...,m-1\}

la sequenza di ispezione deve essere una permutazione \lang 0,...,m-1 \rang

Analisi di complessità indirizzamento aperto

Ricordiamo che è necessario fare una permutazione m! per ogni \lang 0,...,m-1 \rang.

L’analisi viene fatta con fattore \alpha = n/m,n\le m,0 \le \alpha \le 1

Il numero medio di ispezioni necessarie per effettuare l’inserimento del nuovo oggetto nella tabella è m se \alpha=1, e non più di \frac{1}{(1-\alpha)} se \alpha < 1

Numero medio ispezioni per trovare un elemento presente è (m+1)/2 se \alpha =1, non più di \frac{1}{\alpha} *log(1/(1-\alpha)) se \alpha<1

Tre tecniche di ispezione

Queste tre tecniche fanno uso di una funzione hash ausiliara

h':U \to \{0,1,...,m-1\}

Ispezione lineare

h(k,i)=(h'(k)+i)\ mod\ m

si parte da h'(k) e poi h'(k)+1, fino a m-1

genera solo m sequenze di ispezioni distinte.

Soffre del fenomeno dell’addensamento(clustering) primario - lunghe celle occupate consecutivamente che aumentano il tempo medio di ricerca

Esempio h(k,i)=(h'(k)+i)\ mod\ m \\ m=5 \\ h'(k)=k\ mod\ m \\ 38,12,18 \\ h(38,0)=3, h(12,0)=2, h(18,0)=3\ occupato!! \\ allora\ h(18,1)=4 \\ T=[NIL, NIL, 12, 38, 18] \\ Cancelliamo\ 38 : T=[NIL,NIL,12,DEL,18] \\ Inseriamo\ 43\ h(43,0)=3 \to T=[NIL,NIL,12,43,18]

Ispezione quadratica

h(k,i)=(h'(k)+c_1i+c_2i^2)\ mod\ m

Hashing doppio

h(k,i)=(h_1(k)+ih_2(k))\ mod\ m

Alberi e grafi

Alberi Binari

Gli alberi binari si rappresentano mediante strutture dati concatenate, ogni noda ha:

Ogni albero T ha un attributo, T.root, che è il puntatore alla radice dell’albero.

x.p=NIL sse è la radice.

s.left=NIL se sottoalbero sinistro del nodo è vuoto.

s.right=NIL se è quello destro.

Nodo ed albero

Ogni padre ha al massimo 2 figli.

Binary Search Tree

È un albero che soddisfa la seguente proprietà:

per tutti i nodi x del BST, se l è un nodo nel sottoalbero sinistro, allora l.key \le x.key, se r è un nodo del sottoalbero destro, allora x.key \le r.key

Proprietà degli alberi binari di ricerca
Esempio BST

Operazione tipica: attraversamento(walk through)

Scopo: produrre gli elementi dell’albero.

Attraversamento simmetrico (inorder tree walk):

Algoritmo ricorsivo

Altre stratege di attraversamento

Operazioni sui BST

Ricerca (algoritmo intuitivo)

Tempo di esecuzione \Omicron(h), h altezza albero.

Massimo e minimo

Anche qui è intuitivo soprattutto se si ricorda la priprietà del BST.

Tempo \Omicron(h)

Successore e Predecessore

Il successore (predecessore) di un oggetto x in un BST è l’elemento y del BST tale che y.key è la più piccola (grande) tra le chiavi che sono più grandi (piccole) di x.key.

Tempo \Omicron(h)

Esempio di successore e predecessore

Inserimento

Idea banale con confronto si trova il posto dell’elemento e si inserisce.

Cancellazione

Idea banale ma con 3 casistiche ovvero l’elemneto z da cancellare:

Primo caso semplice si mette a NIL il puntatore del padre.

Primo caso cancellazione

Secondo caso si sposta tutto il sottoalbero all’insù di un livello.

Secondo caso cancellazione

Terzo caso si trova il successore dell’elemento da cancellare e si sostituisce con l’elemento cancellato spostando il sottoalbero.

Terzo caso cancellazione

Tempo \Omicron(h)

Tutte le operazioni sui BST hanno tempo \Omicron (h)

Altezza BST

Per un albero completo h=\Theta (log(n))

Caso pessimo (in linea), h=\Theta(n)

Caso pessimo

Alberi bilanciati

\Theta (log(n)) anche nel caso di alberi bilanciati.

Un albero è bilanciato sse non ci sono 2 foglie nell’albero tali che una è “molto più lontana” dalla radice, banalmente devono essere alla stessa altezza o al massimo avere una differenza di altezza di 1.

Diverse tecniche per mantenere un albero bilanciato:

L’altezza attesa di un albero costruito inserendo le chiavi in ordine casuale con distribuzione uniforme è \Omicron(log(n))

Alberi R-B

Altezza \Omicron (log(n))

Operazioni più importanti in tempo \Omicron(log(n))

È un albero bilanciato.

Idea:

Ogni nodo ha 5 attributi:

Un BST è un RB se soddisfa queste 5 proprietà:

  1. Ogni nodo è o nero o rosso.
  2. La radice è nera.
  3. Le foglie (NIL) sono tutte nere
  4. I figli di un nodo rosso sono entrambi neri.
  5. Per ogni nodo x tutti i cammini da x alle foglie sue discendenti contengono lo stesso numero bh(x) di nodi neri.
    • bh (black height)
    • il nodo x non è contato
Esempio albero RB

Un albero RB con n nodi interni ha altezza h \le 2log_2(n+1).

Il numero di nodi interni di un sottoalbero con radice x è \ge 2^{bh(x)}-1.

Per la 4^a priprietà almeno metà dei nodi dalla radice x ad una foglia sono neri, quindi bh(x) \ge h/2, e n \ge 2^{h/2}-1, da cui si discende h \le 2log_2(n+1)

Come conseguenza le operazioni richiedono tempo \Omicron(log(n))

INSERT e DELETE funzionano come prima ma con una modifica per mantenere la 5^a proprietà, ovvero una rotazione a destra (RIGHT-ROTATE) o sinistra (LEFT-ROTATE)

ROtazioni

Inserimento

Uguale a BST ma ruotando per ristabilire le proprietà se necessario, si chiama INSERT-FIXUP.

RB-INSERT-FIXUP sempre su un nodo z tale che z.color=RED.

L’inserimento può dare vita ha 3 casistiche:

Primo caso: y rosso

Primo caso inserimento RB

Secondo caso: y nero e z figlio destro di x

Secondo caso inserimento RB

Terzo caso: y nero e z figlio sinistro di x

Terzo caso inserimento RB

Può essere invocato \Omicron(h) volte, cioè \Omicron(log(n))

Funzionamento di RB-DELETE

Uguale al DELETE ma con T.nil al posto di NIL.

Se viene cancellato un nodo rosso non c’è problema.

Per com’è fatto viene eliminato un nodo (y) con al più un figlio diverso da T.nil, e se y.color=RED il nodo x che prende il posto di y è perforza nero.

Se invece y è nero si può aver violato delle proprietà:

5 casistiche:

Caso 0: x è un nodo rosso, oppure è la radice (ricordo che viene eliminato y)

Caso zero

Caso 1: x è un nodo nero, il suo fratello destro w è rosso, e di conseguenza il padre x.p è nero.

Caso primo

Caso 2: x è nero, suo fraltello destro è nero con figli entrambi neri.

Caso secondo

Caso 3: x è nero, suo fratello destro w è nero con figlio sinistro rosso e figlio destro nero.

Caso terzo

Caso 4: x è nero, suo fratello destro w è nero con figlio destro rosso.

Caso quarto

Grafi

Richiamo ai grafi

Un grafo è una coppia G=(V,E) in cui:

Un arco è una connessione tra 2 vertici

Ci sono 2 tipi di grafi: orientati e non orientati.

Grafo NON orientato
Grafo orientato

Rappresentazione di grafi in memoria

2 tecniche principali:

graph TD;
    A-->D;
    A-->B;
    D-->A;
    B-->E;
    C-->E;
    E-->D;
    E-->E;
Matrice di adiacenza e Lista di adiacenza per l garfo orientato qui sopra

DIiensione delle rappresentazioni dei grafi

Nel caso di liste di adiacenza abbaimo un array di liste:

Nella matrice di adiacenza M, l’elemento m_{ij} è 1 se c’è un arco dal nodo i al j, 0 altrimenti.

In entrambi i casi, dato un nodo u in un grafo G, l’attributo u.Adj rappresenta l’insieme di vertici adiacenti a u.

Liste di Adiacenza:

Matrice di Adiacenza:

Liste migliori quando |E| \not ={\Theta (|V|^2)}, cioè grafo sparso, si ricorda |E| \le |V|^2 cioè |E|=\Omicron (|V|^2).

Se grafo completo (o quasi), tanto vale usare la matrice.

Un grafo è completo quando per ogni coppia di nodi u e v, sia l’arco (u,v) che l’arco (v,u) sono in E.

Rappresentazione di grafi non orientati

L’arco (u,v) non orientato come 2 archi orientati uno da u a v e uno da v a u.

Matrice e Lista di adiacenza di un grafo NON orientato

Matrice di adiacenza simmetrica, quindi basta guardare la diagonale superiore principale.

Problema:

Algoritmo Breadth-First Search

Idea: prima visitiamo i nodi che distano 1 da s, poi 2, poi 3, etc.

Qunado si visita un nodo, si tiene traccia della distanza da s in un attributo u.dist.

Mentre si visitano i nodi si colorano:

Complessità di BFS \Omicron (|V| + |E|)

BFS politica FIFO

DFS invece LIFO

Idea: ogni volta che mettiamo un nodo in cima allo stack, si comincia subito a visitare i nodi adiacenti.

Problema risolto dall’algoritmo DFS

DFS usato spesso come sottoalgoritmo, stessa colorazione di BFS.

Complessità di DFS è \Theta (|V| + |E|).

Grafo Orientato Aciclico

Supponiamodi avere un grafo orientato aciclico (directed acyclic grafh, DAG) che rappresenta le precedenze tra gli eventi.

Esempio

graph TD;
   Orologio;
   Mutande-->Pantaloni;
   Mutande-->Scarpe;
   Calze-->Scarpe;
   Pantaloni-->Scarpe;
   Pantaloni-->Cintura;
   Cintura-->Giacca;
   Camicia-->Cintura;
   Camicia-->Cravatta;
   Cravatta-->Giacca;

Ordinamento Topologico

Un ordinamento topologico di un DAG è un ordinamento lineare dei nodi del grafo tale che, se nel DAG c’è un arco (u,v), allora nodo u precede v.

Esempio con il grafo sopra:

Ordinamento Topologico

Idea:

Tempo: \Theta (|V|+|E|).

Argomenti Avanzati (NON presenti nell’esame)

Cammini Minimi

Si vuole avere il cammino minimo tra due nodi.

Ingresso: G=(V,E) orientato, funzione di peso W:E\to R

Peso cammino

p= \lang v_0, v_1,...,v_k\rang \\ W(p)=\Sigma_{i=1}^k w(v_{i-1},v_i)

Peso cammino minimo tra u e v:

\delta (u,v)=\begin{cases} min\{w(p):u \to^p v\}\ se\ esiste\ cammino\ p\ da\ u\ a\ v \\ \infty\ altrimenti \end{cases}

Non sono ammessi cicli negativi.

Calcoliamo i cammini minimi da nodo fissato s.

Uscita:\forall v \in V: d[v]=\delta (s,v)

Programmazione dinamica

Come divide-et-impera, si scompone il problema, si risolvono i sotto-problemi e si ricompone.

Spesso usata per l’ottimizzazione.

Problema:Taglio delle aste

Esempio tabella

Se asta lunga 4 posso vederlo: [4](9);[1,3](9);[2,2](10);[3,1](9);[1,1,2](7);[1,2,1](7);[2,1,1](7);[1,1,1](4)

taglio ottimale:[2,2]

Data lunghezza n, ci sono 2^{n-1} modi di taglio.

r_n ricavo massimo.

r_4=10,r_{10}=30(venduta intera).

r_n è della forma r_i+r_{n-1}

In altre parole:

r_n=max(p_n,r_1+r_{n-1},...,r_{n-1}+r_1) \implies r_n = max_{1\le i\le n}(p_i+r_{n-i}).

Procedura ricorsiva di questa espressione ha costo temporale: T(n)=c+\Sigma_{j=0}^{n-1} T(j)

Algoritmi golosi

A volte non serve provare tutte le soluzioni basta dimostrare che sia una quella ottimale, ciò è chiamato algoritmo goloso (greedy).

In generale gli algoritmi golosi si muovono per ottimi locali (soluzioni).

Spesso in problemi difficili però l’ottimo locale rappresenta una buona approsimazione dell’ottimo globale.

n attivita a_1,a_2,...,a_n usano stessa risorsa.

Ogni a_i ha un tempo di inizio s_i ed un tempo di fine f_i con s_i <f_i.

a_i occupa la risorsa nell’intervallo temporale [s_i,f_i).

a_i e a_j compatibili se [s_i,f_i) e [s_j,f_j) disgiunti.

Esempio

Insieme di attività computabili : \{a_3, a_9, a_{11}\}.

Max numero attività computabili: 4

Esempio: \{a_2, a_4, a_9, a_{11}\}.

Definiamo s_{ij} l’insieme delle attività che iniziano dopo la fine di a_i e terminano prima dell’inizio di a_j.

A_{ij} insieme massimo attività computabili in S_{ij}.

Mettiamo in una tabella c, c[i,j]=|A_{ij}|

\implies c[i,j]=c[i,k]+c[k,j]+1.

Per risolvere il problema di ottimizzazione basta ogni volta scegliere l’attività che finisce prima, quindi ripetere l’operazione sulle attività che iniziano dopo quella scelta.

Complessità \Theta(n).

Complessità e non determinismo

Data funzione T(n), indichiamo con DTIME(T) l’insieme dei problemi tali che esiste un algorirmo che li risolve in tempo T(n).

DTIME(T) classe dei linguaggi riconducibili in tempo T mediante macchine di Turing deterministiche a k nastri di memoria, idem DSPACE(T).

NTIME(T) e NSPACE(T) uguali ma macchine Turing non deterministiche.

Fondamentale classe di problemi:

P=U_{i\ge 1} DTIME(O(n^i)), chiamati trattabili.

NP=U_{i \ge 1} NTIME(O(n^i))

P=NP? Probabilmente no, ma non si è ancora dimostrato.

\mathcal{L} classe di linguaggi, diciamo che un linguaggio L è \mathcal{L}-difficile rispetto alle riduzioni in tempo polinomiale sse, \forall L' \in \mathcal{L}, è riducibile in tempo polinomiale a L.

L è \mathcal{L}-completo se è \mathcal{L}-difficile ed è in \mathcal{L}.

Computer quantistici

Qubit può non solo trovarsi a 0 e 1, ma anche in sovrapposizione tra i due stati.

Supremazia quantistica: risolve problemi difficili molto più efficiente che con i computer classici.

I computer quantistici possono risolvere efficientemente i problemi NP-difficili? No.

Algoritmi

Qui sono presenti tutti gli algoritmi presentati in pseudo-codice

Insertion-Sort
Merge Sort
Merge
Counting-sort
Heap Family
Quick Family
Ultima modifica:
Scritto da: Niccolò Papini   Andrea Oggioni