Modelli e Complessità

Analisi degli algoritmi e concetti di cardinalità

Analisi qualitativa degli algoritmi

Giovedì 24 febbraio 2022 09:00 Modelli Pagina 1
Analisi matematica degli algoritmi venerdì 25 febbraio 2022 13:00 Modelli Pagina 2
Modelli Pagina 3

Calcolo del costo di esecuzione

Giovedì 3 marzo 2022 09:00 Modelli Pagina 4
Venerdì 4 marzo 2022 13:00 Modelli Pagina 5
Modelli Pagina 6
Modelli Pagina 7

Analisi di costo degli algoritmi ricorsivi

Giovedì 10 marzo 2022 09:00 Modelli Pagina 8
Modelli Pagina 9

Analisi di upper e lower bound

Lunedì 14 marzo 2022 13:00 Modelli Pagina 10
Modelli Pagina 11

Riduzioni

Venerdì 18 marzo 2022 11:00

Concetti di cardinalità

Definizione := Due insiemi A e B si dicono equinumerosi se esiste una biiezione (o corrispondenza biunivoca) tra di essi.

Definizione := Dato un insieme finito A, la sua cardinalità |A| è così definita: |A|= 0 se A = −n se A è equinumeroso all’insieme {0, 1, ... ,n-1}, con n >= 1.

Il concetto di cardinalità può essere utilizzato per dare una definizione insiemistica del concetto di “numero cardinale”: il numero n−può infatti essere definito come la classe d’equivalenza di tutti gli insiemi equinumerosi a {0, ... ,n-1}. In particolare, il numero 0 è la classe d’equivalenza dell’insieme vuoto.

Insiemi numerabili e contabili

Definizione := Un insieme si dice numerabile se esso è equinumeroso a IN.

Definizione := Un insieme si dice contabile se esso è finito o numerabile. Mentre nel caso degli insiemi finiti la cardinalità può essere espressa dal numero cardinale corrispondente, per indicare la cardinalità degli insiemi infiniti equinumerosi ad IN si utilizza il simbolo (aleph zero).

Teorema di contabilità

Se un insieme A è equinumeroso a un insieme B, con B ⊂ C, dove C è un insieme contabile, allora anche A è contabile. L’insieme degli interi relativi risulta essere numerabile (cioè |Z| = aleph zero) poiché i suoi elementi possono essere posti in corrispondenza biunivoca con IN tramite la biiezione definita nel seguente modo.

Importante caratteristica degli insiemi infiniti: l'insieme IN è propriamente contenuto nell’insieme Z: ciononostante i due insiemi risultano equinumerosi. L’insieme delle coppie di naturali risulta essere numerabile. La corrispondenza biunivoca può essere stabilita con la seguente biiezione, frequentemente chiamata funzione coppia di Cantor.

Enumerazione e diagonalizzazione

Il procedimento di enumerazione fu originariamente introdotto da Cantor per mostrare la numerabilità dell’insieme dei numeri razionali. A tal fine dobbiamo innanzi tutto ricordare che i numeri razionali corrispondono alle classi d’equivalenza della relazione binaria R definita sull’insieme. Per tale motivo, l’insieme è dunque equinumeroso all’insieme. D’altronde poiché è contabile, anche lo è e così anche l’insieme che è equinumeroso ad un sottoinsieme proprio di . Ciò prova che è contabile.

Teorema: L’unione di una quantità contabile di insiemi contabili è ancora un insieme contabile.

Diagonalizzazione e numeri reali

L’enumerazione può essere effettuata applicando il metodo di Cantor, dove si suppone che la riga i-esima contenga gli elementi dell’i-esimo insieme.

Per mostrare l’esistenza di insiemi non numerabili si utilizza la tecnica di diagonalizzazione, introdotta da Cantor proprio per illustrare la non numerabilità dei numeri reali, e diffusamente utilizzata per provare risultati importanti nella teoria della calcolabilità.

Data una lista di oggetti, la tecnica di diagonalizzazione consiste nel creare un controesempio, cioè un oggetto non appartenente alla lista, mediante un procedimento che deliberatamente lo costruisce garantendo che esso sia diverso da tutti gli altri oggetti appartenenti alla lista; tale oggetto è detto oggetto diagonale.

L’insieme IR dei reali non è numerabile. Innanzi tutto osserviamo che l’insieme aperto (0, 1) e l’insieme IR sono equinumerosi. Basta dunque mostrare che l’insieme dei reali in (0, 1) non è numerabile. A tal fine, consideriamo dapprima l’insieme delle sequenze infinite di cifre decimali che rappresentano la mantissa dei reali in (0, 1) e mostriamo che tale insieme non è numerabile. Per farlo si supponga per assurdo di aver trovato una qualsiasi corrispondenza tra i naturali e le sequenze. Dopo aver supposto per assurdo di poter enumerare tutte le rappresentazioni decimali di reali nell’intervallo (0, 1), è stato possibile costruire per diagonalizzazione un’ulteriore rappresentazione che, seppure relativa ad un reale in (0, 1), non appartiene all’enumerazione, il che contrasta con l’ipotesi che l’insieme delle rappresentazioni dei reali sia numerabile. La non numerabilità dei reali in (0, 1) deriva da quanto detto ed osservando inoltre che ogni numero reale ha al più due rappresentazioni distinte.

L'insieme delle parti di IN

L’insieme delle parti di IN, P(IN), non è numerabile. Supponiamo per assurdo che P(IN) sia numerabile e sia una sua enumerazione. A ciascun i, con i = 0, 1, 2, ..., associamo una sequenza ..., dove Costruiamo ora l’insieme diagonale P. La sequenza associata a P è dove per i = 0, 1, 2, .... L’insieme P è perfettamente definito dalla sequenza, ma differisce da ciascuno degli insiemi poiché, per costruzione, . Avendo dunque supposto che sia possibile enumerare gli elementi di P(IN), si è riusciti a costruire un insieme P ∈ P(IN) che non fa parte della enumerazione, il che falsifica tale ipotesi. Chiaramente il risultato di non numerabilità trovato non vale solo per l’insieme delle parti di IN, ma per l’insieme delle parti di ogni insieme di cardinalità.

Definizione := Si definisce funzione caratteristica di un insieme S ⊂ IN la funzione totale.

Teorema

L’insieme delle funzioni caratteristiche non è numerabile. Si supponga per assurdo di avere una corrispondenza tra l’insieme delle funzioni caratteristiche e i naturali. A partire dalle funzioni di questa enumerazione, si può costruire una nuova funzione, definita come di seguito: Questa assume ovviamente solo valori in {0, 1}. La funzione così costruita è evidentemente diversa da tutte quelle enumerate per almeno un valore dell’argomento, il che dimostra l’asserto. Dato un insieme A numerabile, e quindi di cardinalità aleph zero, si dice che l’insieme P(A) ha cardinalità 2^{aleph zero}. Gli insiemi aventi cardinalità 2^{aleph zero} vengono detti insiemi continui.

• È un problema di decisione (output: sì/no)
• Halting Problem (HP): dato un programma sorgente S, scritto in un linguaggio di programmazione (ad es., C), dato un possibile input x per il programma S vogliamo stabilire se S termina la computazione sull'input x
• Vorremmo risolvere (decidere) HP, ovvero progettare un algoritmo che, letta la codifica di un programma S (stringa) e letta una stringa x, decida se S termina la sua computazione quando l'input è x.

Decidibilità e Halting Problem

sourceCode è una stringa che codifica un programma input è stringa da dare in input al programma codificato da sourceCode. La funzione itHalts() deve restituire 1 se il programma descritto dalla stringa sourceCode termina quando il suo input è la stringa x; 0 se non termina. Halting Problem è indecidibile (non esiste un algoritmo di decisione), quindi non è possibile scrivere la funzione itHalts().

Costruzione di una funzione diagonale

Costruiamo una funzione diagonale. Supponiamo per assurdo che itHalts(char*, char*) esista e costruiamo una nuova funzione diag(char*) che la sfrutta: Costruiamo la contraddizione.

• Costruiamo la stringa s_diag = "void diag(char *sourceCode) { if(itHalts(sourceCode, sourceCode) while(1); else return; }" che è il codice sorgente di diag
• diag(s_diag) ◦ non termina (while(1)) se s_diag (se stessa) termina
• termina (return) se s_diag (se stessa) non termina
• impossibile!
• Poiché tutti i passi del ragionamento sono semplici e costruttivi, il fatto che un assunto X implichi una conseguenza impossibile denota l'impossibilità stessa di X
• In altre parole: non esiste un algoritmo che esegue quanto descritto per la funzione itHalts(), ovvero: Halting Problem è indecidibile
• La tecnica di dimostrazione utilizzata si basa sulle tradizionali prove "per assurdo" ed è basata sulla costruzione di un esemplare (di funzione) diagonale, ovvero che non è inclusa nell'insieme delle funzioni effettivamente realizzabili (e quindi esistenti)
• L'uso del termine diagonale si riferisce a una nota evidenza visuale che occorre nella prova di non numerabilità dell'insieme (insieme delle parti dei naturali N, oggetto di studio)

Teoria dei linguaggi

Lunedì 21 marzo 2022 13:00 Modelli Pagina 17
Modelli Pagina 18
Modelli Pagina 19

Specifiche sulle grammatiche

Giovedì 24 marzo 2022 09:00 Modelli Pagina 20
Modelli Pagina 21
Modelli Pagina 22

Venerdì 25 marzo 2022 13:00 Modelli Pagina 23
Modelli Pagina 24
Modelli Pagina 25

Definizione alternativa di linguaggio riconosciuto

Lunedì 28 marzo 2022 13:00 Modelli Pagina 26
Modelli Pagina 27
Modelli Pagina 28

Giovedì 31 marzo 2022 09:00 Modelli Pagina 29
Modelli Pagina 30
Modelli Pagina 31

Operazioni chiuse sui linguaggi regolari

Venerdì 1 aprile 2022 13:00 Modelli Pagina 32
Modelli Pagina 33

Automi equivalenti

Lunedì 4 aprile 2022 13:00 Modelli Pagina 34
Modelli Pagina 35
Modelli Pagina 36

Specifiche sui linguaggi Context Free (CFL)

Giovedì 7 aprile 2022 09:00 Modelli Pagina 37
Modelli Pagina 38
Modelli Pagina 39

Analisi sintattica

Venerdì 8 aprile 2022 13:00 Modelli Pagina 40
Modelli Pagina 41
Modelli Pagina 42

Fasi di compilazione

Giovedì 21 aprile 2022 09:00

• Un token è una porzione di input, categorizzata
• Input = stringa su alfabeto Unicode
• Alfabeto Java Unicode
• Scanning = riconoscimento (tramite ASFD) di un token
• Tokenization = suddivisione dell'input in token
• Le grammatiche di tipo 2 permettono di rappresentare la struttura gerarchica dei programmi
• Sono più semplici delle grammatiche di tipo 1 e questo permette di avere parser efficienti
• INPUT: Sequenza di tokens
• OUTPUT: Albero di derivazione
• Riporta errori di sintassi ed effettua una diagnostica degli errori
• Crea tabella dei simboli, che contiene i diversi identificatori usati nel programma

Modelli Pagina 43
Per ogni sequenza di token iniziale (prefisso) t1, t2, ..., tk che l’analisi individua come legale o accettabile (cioè che potrebbe fornire una stringa del linguaggio) devono esistere tokens tk+1, tk+2, ..., tn tali che la stringa t1, ..., tn è un programma sintatticamente corretto. Se consideriamo un token come un singolo carattere, per ogni "parola prefisso" x che l’analisi considera legale esiste suffisso w tale che x·w è un programma sintatticamente corretto. Trovato un prefisso ci possono essere varie continuazioni, ma almeno una è un suffisso e lo completa.