Elementi di Teoria della Computazione

(ETC)

MATRICOLE DISPARI

Docente: Prof. Luisa Gargano

BENVENUTI!

Finalità: Fornire gli elementi di base delle teorie che sono di fondamento all'informatica

1. Computabilità

2. Complessità

Cosa è la ‘’Computazione’’?

Treccani • Computazione: Il computare e il modo con cui si computa; computo,

calcolo.

• Computare Calcolare, fare il conto di qualche cosa: c. il tempo necessario; metodo di c. gli anni;

Mezzi di ‘’Computazione’’

• Carta e Penna

• Abaco

• ….

• Calcolatori/programmi • … • … • …

Cosa è la ‘’Computazione’’? • Possiamo definire la computazione senza far

riferimento ad un calcolatore attuale?

Cosa è la ‘’Computazione’’? • Possiamo definire la computazione senza far

riferimento ad un calcolatore attuale?

• Possiamo definire la computazione indipendentemente dai limiti odierni della scienza (ingegneria, fisica,…)?

Cosa è la ‘’Computazione’’? • Possiamo definire la computazione senza far riferimento

ad un calcolatore attuale?

• Possiamo definire la computazione indipendentemente dai limiti odierni della scienza (ingegneria, fisica,…)?

• Possiamo definire formalmente (matematicamente) un calcolatore? Possiamo dimostrare teoremi circa ciò che può o non può essere computato?

Avendo a disposizione risorse (memoria, tempo,…) sufficienti

Avendo a disposizione risorse (memoria, tempo,…) sufficienti

• un calcolatore può risolvere qualsiasi problema?

• oppure esistono limiti fondamentali a ciò che si può computare?

Cosa è la ‘’Computazione’’?

Treccani • Computazione: Il computare e il modo con cui si computa; computo,

calcolo.

• Computare Calcolare, fare il conto di qualche cosa: c. il tempo necessario; metodo di c. gli anni;

• Computabile : Che si può computare; di cui si può o si deve tener conto • In logica matematica e in informatica teorica, detto di una

funzione (per es., l’insieme dei numeri naturali) che si può calcolare effettivamente, cioè per la quale esiste un procedimento che permette di determinarne i valori; con sign. più concreto si dicono computabili quelle funzioni che, in linea di principio, possono essere calcolate con un elaboratore adeguatamente programmato; la teoria della computabilità (o della ricorsività) studia i limiti teorici di tale possibilità.

Quali problemi possono essere computati? (con qualsiasi macchina, linguaggio, … )

Computabilità:

Esempi di problemi computazionali • Problemi numerici

• Data una stringa binaria, il numero di 1 è maggiore del numero di 0?

• Dati due numeri x e y, calcola x+y • Dato un intero, risulta x primo?

• Problemi riguardanti programmi (es. in C) • Data una sequenza di caratteri ASCII, rispetta

la sintassi del C? • Dato un programma in C, esiste un input che lo

manda in loop?

Computabilità:

Macchine a stati finiti/Automi: Quali problemi possiamo risolvere con

memoria costante?

Quali problemi possono essere computati? (con qualsiasi macchina, linguaggio, … )

Macchina a stati finiti

Distributore di bibite/snack a 50c Accetta monete da 10c e da 20c non da resto, rifiuta moneta troppo grande

E’ (semplice) macchina a stati finiti che opera in accordo all’input (monete)

Macchina a stati finiti o Automa finito

Astrazione Più semplice modello di calcolo

• Chip

• Parte di molti apparecchi elettromeccanici

• Analizzatori lessicali e sintattici di compilatori,

•…

Computabilità:

Macchine a stati finiti/Automi: Quali problemi possiamo risolvere con

memoria costante?

Quali problemi possono essere computati? (con qualsiasi macchina, linguaggio, … )

Quali problemi possono essere computati? Non tutti!!!

Computabilità:

Esempi di problemi computazionali • Problemi numerici

• Data una stringa binaria, il numero di 1 è maggiore del numero di 0?

• Dati due numeri x e y, calcola x+y • Dato un intero, risulta x primo?

• Problemi riguardanti programmi (es. in C) • Data una sequenza di caratteri ASCII, rispetta

la sintassi del C? • Dato un programma in C, esiste un input che lo

manda in loop?

Quali problemi possono essere computati? Non tutti!!!

Computabilità:

Es. Dato un qualsiasi programma in C, possiamo stabiliure se termina su ogni input? Risposta: NO input n; while (n !=1) { if (n is even) n := n/2; else n := 3*n+1; } Termina per ogni n>1? 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

Macchine di Turing

Ideate da Alan Turing nel 1936.

Modello di calcolatore più semplice:

- macchina a stati finiti

- Nastro (lettura e scrittura) memoria, processore

Computabilità:

Modello di computazione indipendente dalla tecnologia presente?

• Macchine di Turing

Ideate da Alan Turing nel 1936.

Modello di calcolatore più semplice:

- macchina a stati finiti

- Nastro memoria, processore

Scopo:

formalizzare in maniera esatta (matematica) il concetto di computazione (indipendentemente dalla ‘’potenza di calcolo’’)

• Tesi di Church-Turing:

Equivalenza tra programmi e Macchine di Turing

• Macchine di Turing:

Concetto di Computabilità indipendente dalla tecnologia

• Tesi di Church-Turing:

Equivalenza tra programmi e Macchine di Turing

• Limiti delle macchine di Turing (e della computazione):

Problemi non computabili

Cosa può essere computato? Cosa non può esserlo? (con qualsiasi macchina, linguaggio, … ) Dove si trova il confine?

Computabilità:

Calcolabilità:

Quali sono le le risorse minime necessarie (es. tempo di calcolo e memoria) per la risoluzione di un problema?

Lista luoghi con associato il l’interesse a visitare il luogo (voto da 0 a 100) Vogliamo ordinare i luoghi in ordine di interesse

Facile!

Usando I collegamenti esistenti (metro, bus). Facile?

Prova tutti i siti

vicini non

ancora visitati

P

Algoritmi utili in pratica

Algoritmi efficienti: Utilizzano un tempo polinomiale su tutti gli input Algoritmi inefficienti: Utilizzano un tempo esponenziale su qualche input Nota. Definizione indipendente da sviluppo tecnologico Cosa rende un problema facile o meno?

Cosa rende un problema ‘’facile’’ o meno?

Le classi P e NP

Definizione (informale) della classe P:

insieme di problemi risolubili in tempo polinomiale da una macchina di Turing deterministica

Tesi Church-Turing

insieme di problemi che ammettono un’ algoritmo efficiente

Le classi P e NP

Definizione (informale) della classe NP:

insieme di problemi che ammettono un’ algoritmo efficiente di verifica di una soluzione fornita

Problemi NP-completi

• Travelling Salesman Problem,

• 3-coloring di grafi,

• Scheduling Multiprocessore,

• Folding Proteine,

• Programmazione lineare intera:

esiste soluzione intera per un sistema del tipo

Tutti risolvibili efficientemente o nessuno!

Argomenti di massima:

•Macchine a stati finiti

•Macchine di Turing

•Le classi P e NP

Finalità

Computabilità

Comprendere la nozione di di computabilità

Limiti intrinsechi della computabilità

Modelli più semplici di computazione

Risultati attesi:

Saprete

• che è impossibile dimostrare che un programma in C termina

• fornire una dimostrazione formale di ciò

• nessun calcolatore futuro può cambiare la situazione

Finalità

Computabilità

Comprendere la nozione di di computabilità

Limiti intrinsechi della computabilità

Modelli più semplici di computazione

Complessità

classificazione problemi solubili: difficoltà

riconoscere problemi ‘’difficili’’

Risultati attesi:

Saprete Come riconoscere un problema intrattabile se vi capita Es. PROTEIN FOLDING, NEURON TRAINING, AUCTION WINNER-DETERMINATION, MIN-ENERGY CONFIGURATION OF A GAS

Informazioni Pratiche

ORARIO:

•Martedì: 11:00 – 13:00

•Giovedì: 16:00 – 18:00

•Venerdì: 14:00 – 16:00

N.B.: Tutte le lezioni sono ugualmente importanti!

Informazioni Pratiche

SITO WEB: http://www.dia.unisa.it/professori/lg/ETC.html

di riferimento per il materiale relativo al corso

- copie delle slides, esercizi, - date delle prove, - comunicazioni varie, - etc.

Suggerimenti

(per superare facilmente l’esame)

• Seguire il corso

È più difficile imparare da soli dal libro

(ancora di più dalle slide!)

• Studiare lezione per lezione

Gli argomenti diventano più complessi

• Studiare dal libro di testo

• Fare gli esercizi

Testo

Michael Sipser, Introduction to the Theory of Computation, Course Technology.

Testo

• Jon Kleinberg, Eva Tardos, Algorithm Design, Pearson

Prove di Esame

• Prova scritta con esercizi e teoria

(nessun materiale ammesso)

• Eventuale prova orale

• Requisito minimo: 50% del totale

• Prove in Itinere

• ‘’Bonus’’

• Prossima lezione

Progamma sintetico

• Nozioni preliminari

• Automi Finiti

• Macchine di Turing

• Limiti delle macchine di Turing

• La tesi di Church-Turing

• Le classi P e NP

•

Nozioni preliminari

•Conoscenza del significato dei termini:

Definizione, Enunciato, Dimostrazione, Implicazione, Equivalenza,...

• Familiarità con i vari tipi di dimostrazioni:

per contraddizione, prova per induzione, …

• Definizioni delle operazioni logiche AND, OR, NOT.

• Alfabeti

• Stringhe

• Linguaggi

DIMOSTRAZIONE

Metodo per stabilire una verità

Differente in vari campi

• Legale: giuria – prove processuali

• Scientifica: esperimenti ripetibili

• Filosofica: persuasione basata su argomenti plausibili

Cartesio: “Cogito ergo sum,”

Deriva esistenza dal fatto di pensare sull'esistenza

PROVA Matematica

Una prova formale è una catena di deduzioni logiche che portano ad una affermazione partendo da un insieme di assunzioni

c=cent E=Euro

Assunzione 1E=100c

1 c= 0,01 E=(0,1 E)2=(10c)2=100c=1E

?

Dimostrazione

c=cent E=Euro

1 c= 0,01 E=(0,1 E)2=(10c)2=100c=1E

ERRATA!!

Affermazione

Se a e b sono due numeri reali uguali allora a = 0.

Dimostrazione

Assunzione a=b

Affermazione errata:

Se a e b sono due numeri reali uguali allora a = 0.

Dimostrazione sbagliata:

• Proposizione: affermazione che può essere vera o falsa

• Proposizioni matematiche devono riferirsi ad oggetti ben definiti matematicamente (numeri, insiemi, funzioni,...)

• Devono essere formulate in modo preciso

Es. 2 + 3 = 5.

Proposizione: può essere vera o falsa Dimostrazione: Data una proposizione, vogliamo dimostrare che essa è vera.

Es. Proposizione p(n)=n2+n+41 è numero primo per ogni n > 1.

Come facciamo?

Proviamo per qualche valore p(1)=43 primo P(2)=47 primo P(3)=53 primo … P(20)=461 primo … P(39)=1601 primo VERA?

Es. p(n)=n2+n+41 è primo per ogni n > 1.

Proviamo per qualche valore p(1)=43 primo P(2)=47 primo P(3)=53 primo … P(20)=461 primo … P(39)=1601 primo P(40)=40x40+40+41=41x41 FALSO!

Es. p(n)=n2+n+41 è primo per ogni n > 1.

Dimostrazione per esempi =

Esempio di dimostrazione sbagliata

Es. Proposizione a4 +b4 +c4 = d4 non ha soluzione con a, b, c, d interi positivi Congettura di Eulero del 1769. Dimostrata FALSA 218 anni dopo da Noam Elkies:

a = 95800; b = 217519; c = 414560; d = 422481.

Es. Proposizione 313(x3 +y3 ) = z3 non ha soluzione con x,y,z interi positivi FALSA: controesempio più piccolo ha più di 1000 digit!

Es. Congettura di Goldbach (1742) Proposizione P(n): n si può scrivere come somma di due primi per ogni n>2 ?

Non possimo stabilire VERO provando per un numero finito di valori! Servono altri metodi!

Es. Congettura di Goldbach (1742) Proposizione P(n): n si può scrivere come somma di due primi per ogni n>2 ?

Proposizione: affermazione che può essere può essere vera o falsa Dimostrazione: Data una proposizione, vogliamo dimostrare che essa è vera.

Proposizione P: vera (T) o falsa (F) Operazioni Logiche: NOT, OR, AND Tavole di verità:

Implicazioni: Deduzioni logiche per provare nuove proposizioni a partire da altre note (vere)

• P Q (P implica Q: se P è vera allora Q è vera )

Es. “Se gli asini volano, allora voi capirete questa lezione.” E’ un insulto? Nel linguaggio comune: Si Matematicamente è un affermazione vera!

PQ è vera ogni volta che P è falsa o Q è vera

Deduzioni logiche: per provare nuove proposizioni a partire da altre note (vere)

• (P vera, P Q) ALLORA Q vera

• (P Q; Q falsa) ALLORA P Falsa

Deduzioni logiche • NOT(Q) NOT(P)

Equivalente a PQ

• NOTA NOT(P) NOT(Q) ALLORA P Q: ERRATA

Come dimostrare che P Q: 1. “Assumiamo P.”

2. mostriamo che Q segue

Es. Se 0 < x < 2, allora -x3 + 4x + 1 > 0. Dim. Assumiamo 0 < x < 2 Scriviamo -x3 + 4x = x(2 - x)(2 + x) Sappiamo che x, 2 - x, e 2 + x nonnegativi ( >0 ). Allora il loro prodotto è nonnegativo (>0). Sommando 1 abbiamo numero positivo (>0):

-x3 + 4x+1= x(2 - x)(2 + x) + 1 > 0.

“P IFF Q”

equivale a

“P Q” AND “Q P”.

“P IFF Q”

equivale a

“P Q” AND “Q P”.

Provare “iff” :

1. “Proviamo che P implica Q e vice-versa.”

2.“Per prima cosa, mostriamo che

P implica Q.” (Come prima)

3. “Secondo passo, mostriamo che Q

implica P.” (Come prima)

ES.

Dimostrazione per contraddizione

per dimostrare P

Schema:

1.Assumiamo che l’ipotesi P è falsa

2.Dimostriamo che NOT(P) NOT(Q) per qualche Q che sappiamo essere vera

3.A questo punto abbiamo una contraddizione e possiamo concludere che P deve essere vera

Teorema. La radice quadrata di 2 è un numero irrazionale.

Dim.

Assumiamo che l’ipotesi P è falsa, cioè

sqrt(2)=m/n (m,n interi primi fra loro)

Dimostriamo NOT(P) NOT(Q) [Q: m, n primi tra loro]

m2 =(n sqrt(2))2=n22 m2=2n2 m2 pari m pari,

Poniamo m=2k

Allora 2n2= m2= 4k2 n2=2k2 n pari

Abbiamo che n,m entrambi pari m,n hanno fattore comune 2

A questo punto abbiamo NOT(Q)

possiamo dedurre che P è falsa (cioè sqrt(2) è irrazionale)

Teorema.

La radice quadrata di 2 è un numero irrazionale.

Dim.

Assumiamo che l’ipotesi è falsa, possiamo scrivere

a) sqrt(2)=m/n

b) con m,n interi primi fra loro

Abbiamo

• m2 =(n sqrt(2))2=n22 m2=2n2 m2 pari m pari,

• Ponendo m=2k si ha 2n2= m2= 4k2 n2=2k2 n pari

Quindi n,m entrambi pari m,n hanno fattore comune 2

che contraddice punto b)

possiamo concludere che sqrt(2) è irrazionale.

Dimostrazioni Corrette in Pratica • Definire il metodo che si vuole seguire es. “Usiamo un distinzione di casi” o “Ragioniamo per assurdo.” • Una dimostrazione e` un “saggio” non un calcolo

Approccio errato: sequenza di espressioni senza commenti

Una dimostrazione comprensibile e` un “saggio” inframmezzato da calcoli

Buone dimostrazioni <=> Buoni programmi Stesso rigore necessario per scrivere

programmi funzionanti • Programma che ''sembra funzionare'' può

causare molti problemi • Es. Therac 25: macchina per radioterapia

che ''ogni tanto'' ha ucciso i pazienti per eccesso di radiazioni (problema software)

• Es. (Agosto 2004) problema software usato

da United e American Airlines ha messo a terra l'intera flotta delle due compagnie

INDUZIONE

Data una affermazione, vogliamo dimostrare che essa vale per ogni intero n>a.

Es. La somma dei primi n interi vale n(n+1)/2 per ogni n > 1.

INDUZIONE

Vogliamo dimostrare che un certo predicato è vero. • Formaliziamo con affermazione S(n) • dimostriamo per induzione che S(n) vera (per ogni intero n>a). Una dimostrazione per induzione consiste di 2 fasi 1. BASE INDUTTIVA. Si dimostra che l’affermazione è

vera per il primo valore, cioè S(a) è vera. 1. PASSO INDUTTIVO. Assumiamo che S(n-1) è vera e

dimostriamo che allora anche S(n) è vera.

INDUZIONE

2

)1()...21(

1

nnni

n

i

Formalizzazione S(n): Si vuole dimostrare per induzione che S(n) vale per ogni n > 1.

Es. La somma dei primi n interi vale n(n+1)/2 per ogni n > 1.

ii1

n

(1 ... n) n(n 1)

2

INDUZIONE

1. BASE INDUTTIVA. S(a) è vera. 2. PASSO INDUTTIVO. S(n-1) implica S(n) vera.

Es. S(n): Si vuole dimostrare che S(n) vale per ogni n > 1. Base. S(1) è vera perché Passo. Ipotesi induttiva S(n-1): Si ha Quindi S(n) è vera.

2/)11(111

1

i

i

2/)1(1

1

nnin

i

ii1

n

i ni1

n1

(n 1)n

2 n

(n 1)n 2n

2n(n 1)

2

ii1

n

(1 ... n) n(n 1)

2

INDUZIONE

Esercizio. Dimostrare per induzione che la seguente affermazione S(n) è vera per ogni intero n>0. S(n):

2i

i0

n

2n1 1

INDUZIONE

Es. Se x≥4, allora 2x ≥x2 •Affermazione S(x): 2x ≥x2 •Mostriamo per induzione che S(x) vera per ogni x≥4. Base: x = 4 ⇒ 2x = 24 = 16 e x2 = 42 = 16 Passo I.: Supponiamo che 2x ≥x2 per x ≥ 4 Dobbiamo dimostrare che 2x +1 ≥ (x + 1)2

Abbiamo: 2x +1 = 2 2x ≥ 2 x2 (dalla ipotesi induttiva) Dimostriamo adesso che 2x2 ≥ (x + 1)2=x2+1+2x Semplificando: x2-2x ≥ 1 Se x ≥ 4, x(x-2) ≥ 8>1

VALIDITA’ delle dimostrazioni per INDUZIONE

Dim. per induzione S(n) vera, ogni n>a Base: S(a) vera Passo induttivo

Minimo controesempio. IPOTESI: S(n) falsa per qualche n. Sia b il più piccolo intero tale che S(b) falsa. DEDUCIAMO: Se b=a contraddiciamo la base. Quindi b>a. Essendo b = minimo intero per cui l’affermazione è falsa, risulta S(b-1) vera (nota b-1 > a). Per il Passo Induttivo, S(b-1) S(b). Allora S(b) vera: contraddizione con assunzione che S(b) falsa. Quindi ipotesi è sbagliata, Cioè non esiste intero per cui l’affermazione è falsa Cioè S(n) vera per ogni intero

Teorema. Tutti i cavalli hanno lo stesso colore

Dim. Sia P(n): ''in ogni insieme di n cavalli, tutti i cavalli hanno lo stesso colore.'' Mostriamo per induzione che P(n) vera per ogni n ≥ 1. Base : P (1) vera. Passo. Assumiamo P (n) vera, n>1. Consideriamo insieme di n + 1 cavalli: h1 , h2 , . . . , hn , hn+1 Per I.I. I primi n cavalli h1 , h2 , . . . , hn hanno stesso colore, Per I.I. Gli ultimi n cavalli h2 , h3 , . . . , hn+1 hanno stesso colore, Quindi h1 , h2 , . . . , hn+1 hanno stesso colore, e P(n+1) vera Poiche` P (n) P (n + 1), allora P(n) vera per ogni n ≥ 1.

Teorema. Tutti i cavalli hanno lo stesso colore

Dim. Per induzione su n. Sia P(n): ''in ogni insieme di n cavalli, tutti i cavalli hanno lo stesso colore.''

Conseguenza: se n=(numero cavalli nel mondo) allora tutti cavalli hanno lo stesso colore. Abbiamo provato una cosa FALSA!

ERRORE?

Abbiamo provato: P (1) P (2) P (3), P (3) P (4), etc. NON P (1) P (2)

INDUZIONE COMPLETA

Vogliamo dimostrare che P(n) vale per ogni intero n>a. Dimostrazione per induzione completa: 1. BASE INDUTTIVA. Si dimostra che l’affermazione è

vera per il primo valore, cioè P(a) è vera.

2. PASSO INDUTTIVO. Assumiamo che P(a), P(a+1),…, P(n-1) sono tutte vere e dimostriamo che anche P(n) è vera.

Definizioni Induttive

; Una definizione per induzione (o induttiva o ricorsiva) di un insieme di oggetti consiste di una base e di un passo induttivo. BASE definisce uno o più oggetti elementari. Passo Induttivo definisce la regola che permette di costruire oggetti più complessi in termini di quelli già definiti

Definizioni Induttive

; BASE definisce uno o più oggetti elementari. Passo Induttivo definisce la regola che permette di costruire oggetti più complessi in termini di quelli già definiti Es. Definizione induttiva di n! (prodotto primi n interi) BASE 1! P.I. n!=n (n-1)! Per ogni n>1

Definizioni Induttive

; BASE definisce uno o più oggetti elementari. Passo Induttivo definisce la regola che permette di costruire oggetti più complessi in termini di quelli già definiti Es. Definizione dei numeri di fibonacci BASE f(0)=f(1)=1 P.I. f(n)=f(n-1)+f(n-2), per ogni n>1

Teorema. Ogni intero maggiore di 1 è un prodotto di primi Dim. Stabiliamo affermazione P(n): l’intero n è un prodotto di primi Vogliamo dimostrare per induzione completa che p(n) vera per ogni n>1. Base. P(2) vera, poichè 2 è primo Passo. II: p(2),…,p(n-1) vere Proviamo che P(n) è vera. Se n è primo, ok Se n non è primo allora n=km per qualche k e m II ci dice che P(k), p(m) vere, Cioè k ed m sono prodotti di primi Quindi anche il loro prodotto n=km è un prodotto di primi.

Definizioni Induttive

; Una definizione per induzione (o induttiva o ricorsiva) di un insieme di oggetti consiste di una base e di un passo induttivo. BASE definisce uno o più oggetti elementari. Passo Induttivo definisce la regola che permette di costruire oggetti più complessi in termini di quelli già definiti

Definizioni Induttive

; BASE definisce uno o più oggetti elementari. Passo Induttivo definisce la regola che permette di costruire oggetti più complessi in termini di quelli già definiti Es. Definizione induttiva di n! (prodotto primi n interi) BASE 1! P.I. n!=n (n-1)! Per ogni n>1

Definizioni Induttive

; BASE definisce uno o più oggetti elementari. Passo Induttivo definisce la regola che permette di costruire oggetti più complessi in termini di quelli già definiti Es. Definizione dei numeri di fibonacci BASE f(0)=f(1)=1 P.I. f(n)=f(n-1)+f(n-2), per ogni n>1

Definizioni Induttive e Dimostrazioni Induttive

; Es. Mostrare che il numero di fibonacci f(n) soddisfa f(n)<2n, per ogni n>0