Elementi di Teoria della Computazione

(ETC) Classe 2: matricole congrue a 1 (mod 3)

Docente: Prof. Luisa Gargano

BENVENUTI!

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

1. Calcolabilità

2. Complessità

Questioni principali cui vogliamo dare risposta:

1. Cosa può essere calcolato?

Cosa NON può essere calcolato?

(con qualsiasi macchina, linguaggio, … ) Dove si trova il confine tra le due?

Questioni principali cui vogliamo dare risposta:

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

Argomenti di massima:

•Macchine a stati finiti

•Macchine di Turing

•Le classi P e NP

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)

•Macchine a stati finiti o Automi finiti

Più semplice modello di calcolo

Es.

• Parte di molti apparecchi elettromeccanici

• Analizzatori lessicali e sintattici di compilatori,

• verificatori circuiti,

• …

Argomenti di massima:

•Macchine a stati finiti

•Macchine di Turing

•Le classi P e NP

• Macchine di Turing

Inventate da Alan Turing nel 1936.

Modello di calcolatore più semplice:

Nastro memoria, processore

Scopo:

formalizzare in maniera esatta (matematica) i concetti di problema e procedura (indipendentemente dalla „‟potenza di calcolo)

• Tesi di Church-Turing:

Equivalenza tra procedura effettiva e Macchina di Turing

• Limiti delle macchine di Turing

(e dei calcolatori)

Argomenti di massima:

•Macchine a stati finiti

(es Compilatori, verificatori circuiti,…)

•Macchine di Turing

•Le classi P e NP

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

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 non deterministico

(ogni qualvolta si ci trova di fronte ad una scelta si possono seguire più strade in parallelo)

Per questi problemi sono noti algoritmi che terminano in un numero di passi polinomiale rispetto alla dimensione dei dati nel caso si possa utilizzare un numero indeterminato di macchine in parallelo

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

• Calcolabilità

classificazione problemi: solubili, insolubili

• Complessità

classificazione problemi solubili: difficoltà

Informazioni Pratiche

ORARIO:

•Mercoledì: 11:00 – 13:00

•Giovedì: 11:00 – 13:00

•Venerdì: 16:00 – 18: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

• Studiare lezione per lezione

• Studiare anche 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

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 booleane AND, OR, NOT.

• Alfabeti

• Stringhe

• Linguaggi

DIMOSTRAZIONE

Metodo per stabilire una verità

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

Dimostrazione

c=cent E=Euro

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

ERRATA!!

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.

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!

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 quando 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 >0:

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 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 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 una contraddizione [cioè NOT(Q)]

possiamo concludere che sqrt(2) è irrazionale [cioè P].

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 sffermazione, 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

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.

ii 1

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

1i

i

2/)1(1

1

nnin

i

ii 1

n

i ni 1

n 1(n 1)n

2n

(n 1)n 2n

2

n(n 1)

2

ii 1

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

i 0

n

2n 1 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-1>a e b = minimo intero per cui l‟affermazione è falsa, risulta S(b-1) vera Per il Passo Induttivo, se S(b-1) è vera allora anche S(b) è vera. Abbiamo contraddizione con assunzione che S(b) falsa. Quindi ipotesi è sbagliata e non esiste intero per cui l‟affermazione è falsa.

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