Riassunto esame Fondamenti d'informatica 2, Prof. Spaccamela Alberto, libro consigliato Dispense Docente, Spaccamela

F.I.2

(Modelli)

By ThePres

Complessità PT.1

Minima complessità di un programma

Efficienza → risolvere problema con poche risorse di calcolo

Tempo di calcolo

Spazio (memoria)

Non posso misurarlo

Necessità quindi di una stima generale indipendente

• FC Usato
• Linguaggio
• Dati

Uso a modello macchina V. Neumann

Analisi Costi

Ogni istr. elementare ha costo unitario

Ciclo, if, sottoprogramma vanno fatti i calcoli

^Oss

t₁ = tempo esec. istr 1

t_n = n n 2 min t_c

(t₂ & > > min) Costo costante

COSTI NOTEVOLI

Costo ricerca elem. in array con n elem → Ω(log(n))

Costo ordinamento array n elem → Ω(n log(n))

Notazione Θ

Se f(n) rappresenta sia un upper bound che un lower bound del problema, i.e.

1. Ho programma deciso con costo t(n) = O(f(n))

2. Posso dim. che compl. probl è Ω(f(n))

Il problema ha complessità Θ(f(n))

Tesi di Church-Turing

Ogni funzione che sia dimostrata calcolabile con un qualunque modello di calcolo formale è calcolabile secondo Turing.

La tesi non si può dimostrare ma sono stati ideati negli anni modelli di calcolo basati su approcci diversi e tutti erano alla fine uguali a M_T.

Quindi assumiamo che sia vera e che non esista un modello di calcolo più potente del M_T.

Random Access Machine (RAM)

Esempio di un altro modello di calcolo. Caratterizzata dall'avere un numero potenzialmente oo di registri e un contatore di programma.

Ha però poche istruzioni che la costringo.

Per la tesi è eq. a M_T.

NP-COMPLETETO

def:

• Un linguaggio L₁ è polinomialmente riducibile a L₂ se
  • una riduzione da L₁ a L₂ calcolabile in tempo, polinomiale e c. f. ogni stringa X ∈ L₁ ↔ g(x) ∈ L₂,
  • se L₁ ris. in tempo pol. lo è anche L₂. Se L₁ non lo è ≠ L₂,
• Un linguaggio L è NP-Completo se ogni altro linguaggio in NP è pol. rid. a L. L ∈ NP

OSS

• Dimostassimo di sapere risolvere un problema NP in tempo P → P=NP.
• Ma siccome non ci riusciamo, presiamo P ≠ NP

Teo (cook -lewin)

SAT è NP-COMPLETO

NP-HARD

• Un linguaggio L è NP-hard se ogni altro linguaggio in NP è polinomialmente riducibile a L. (non necessariam. NP)

(Diagramma: NP-Hard, NP-Complete, P)

Linguaggi

Linguaggio L è sottoinsieme di Σ*

Per i linguaggi di programmazione Σ=ASCII

Linguaggio formale

Insieme delle stringhe che si possono scrivere utilizzando le regole del linguaggio.

Analisi sintattica

Verificare se una stringa di simboli verifica le regole

Analisi semantica

Verificare se una stringa sintatticamente corretta ha un significato.

• Valido o operazioni insieme
• I linguaggi interessanti sono infiniti

Gerarchia di Chomsky

G. Regolari o di tipo 3:

• Produzioni lineari a dx: A → aB
• A → a¹

G. Liberi da Contesto o di tipo 2:

• Produzioni del tipo A → a

G. Contestuali o di tipo 1:

• Produzioni del tipo a → β
• |β| ≥ |a|

G. Tipo 0:

• Non esiste alcun vincolo sulla creazione delle produzioni.

Gram. Equivalenza

Due grammatiche sono equivalenti se generano lo stesso linguaggio

L(G₁) = L(G₂)

Chiusura Transitiva

Equivalenze

Automi a S.P. grammatiche di tipo 3 e regex definiscono la stessa classe di linguaggi

Conversione da Grammatiche tipo 3 a Regex

1. Trasformo la grammatica in un sistema di equazioni del tipo:

Variabile = Regex Estesa

es:

A → aB | c → A = aB + c

Quindi per prima cosa raggruppiamo in uniche produzioni:

A → a₁B₁ a₂B₂ […] a_nB_m

E ci associamo l'eq.

1. Eliminazione RicorsioneDevo Risolvere Sistema

S = aS + bB → a* + bB → S = a* + b(b*c)

T = bTB + c → b*c

1. Semplificazioni

Semplificare fino a che rimanga una sola eq. relativa all’assioma a alla fine il membro dx è la regex

Parsing

Per costruire l'albero di derivazione l'analizzatore produce una seq. di produzioni.

Inoltre riporta gli errori di sintassi e crea la tabella dei simboli che contiene ı identificatori

usati nel programma.

Posso ottenere l'ordine di produzioni o espandendo da dx a sx.

Parser Top-Down

• Espande sempre il non terminale più a sx.
• Ripetutamente scelgo un simbolo non terminale a dell'albero finora ottenuto e applico produzione ad a.
• Termina con succ. quando le foglie dell'albero rappres. la stringa di input.
• Albero visitato in preordine.

Sono più semplici da implementare di quelli passo per motivi di efficienza è deterministico, comodo un algoritmo ricorsivo.

Se ho A → a | β

1. Uso A → a ricorsivamente, se fine succ.
2. x → β o @ succ.

fail.

ALGORITMO LL(1) PARSER

1. COSTRUIRE INSIEMI FIRST E FOLLOW
2. SE GRAMMATICA NON È LL(1) DAI ERRORI
3. PROCEDI COSTRUENDO UN PARSER PREDITTIVO A DISCESA RICORSIVA

• UN METODO PER CIASCUN NON TERMINALE A
• PER OGNI TOKEN t IN FIRST(α) USA LA REGOLA A→α

COSTRUZIONE TABELLA DEL PARSER PREDITTIVO

(CONSIDERO UN NON-TERMINALE A, LA PRODUZIONE A→α E UN TOKEN t)INSERIAMO NELLA TABELLA T[A,t]=α IN 2 POSSIBILI CASI:

• SE A→a ... → Β => t ∈ FIRST(A) PERCHÉ CI POSSO ARRIVARE
• SE A→a ... → ε => t ∈ FOLLOW(A) PERCHÉ NON CI POSSO ARRIVARE DIRETTA. DEVO ELIMINARE A DERIVANDO A→a ... → ε

QUINDI, ESAMINA TUTTE LE PROD. X→ΒPER TUTTI I TERMINALI a IN FIRST(Β) PONGO table[X,a]=ΒSE FIRST(Β) INCLUDE λ → ∀ a ∈ FOLLOW(X)table[X,a]=ε

Approcci al Parsing

Top-Down

Obiettivo: fissata una grammatica non contestuale G, data una stringa x in input costruire un albero di derivazione di x a partire dalla radice usando produzioni di G.

Metodi:

• analisi di discesa ricorsiva (exp)
• analisi predittiva (lineare, basato su grammatica LL(k))

Bottom-Up

Obiettivo: Fissata una grammatica non contestuale G, data una stringa x in input costruire un albero di derivazione di x a partire dalle foglie usando le produzioni di G.

Metodi:

• analisi SHIFT-REDUCE
• lineare
• analisi predittiva (basato su gramm. LR(k))

Algoritmo costruzione tavole

1. Costruire insieme di stan
2. Inizia con lo stato iniziale, prendi le produzioni dello assumo e costruemmo la sua chiusura
3. Determina il prossimo stato esaminando le possibili produzioni, esegui la chiusura e determina un nuovo insieme
4. Itera il passo precedente fino ad aver esaminato tutte le transizioni
5. Costruisci tabelle Action e Goto

Grammatica LR(0)

Una grammatica è LR(0) se per ciascun dogli stem:

• È presente al più una sola produzione con il punto finale (assenza di conflitti riduce-riduce)
• Non sono contemporaneamente presenti una produzione con il punto finale e un'altra con il punto non finale (assenza di conflitti shift-riduce)

La decisione di shift-riduce viene presa senza guardare alcun look unidigest.Vanno levamente shift-riduce, riduce-riduce.

Guardando in input è possibile effettuare LR parsing su molte più grammatiche. Tutti i linguaggi context-free deterministica ammettono una grammatica context LR(1).