Nessun titolo diapositiva - Dipartimento di Informatica · Congettura di Eulero del 1769....
Transcript of Nessun titolo diapositiva - Dipartimento di Informatica · Congettura di Eulero del 1769....
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