Algoritmi e Dimostrazioni Stefano Berardi

Università di Torino

http://www.di.unito.it/~stefano

E-mail: stefano@di.unito.it

Un po’ di terminologia

• Un algoritmo è un procedimento meccanico, affidabile a un calcolatore, per ottenere un certo risultato: è uno strumento di uso pratico.

• Una dimostrazione è invece un argomento rigoroso per mostrare, senza possibilità di dubbio, la verità di una certa affermazione matematica: è uno strumento concettuale.

Argomento della conferenza

• Algoritmi e dimostrazioni sono oggetti di uso molto diverso.

• Mostreremo tuttavia come, in vari casi, una dimostrazione si possa leggere come un algoritmo, e quindi essere “usata” per risolvere dei problemi pratici.

• Tale nuova lettura delle dimostrazioni matematiche, prevista dalla Logica, è stata sviluppata grazie all’Informatica.

Sommario

• Daremo esempi di dimostrazioni fatte per Induzione che si possono “usare” per risolvere dei problemi.

• 1. Le dimostrazioni per induzione.• 2. La prova di Euclide che esistono infiniti

numeri primi.• 3. Un algoritmo di ordinamento.• 4. Un risultato generale.

1. Dimostrazioni per induzione

• L’induzione è una regola per dimostrare enunciati del tipo: “ogni numero naturale ha una certa proprietà P”.

• Un esempio (facile): possiamo utilizzare la regola di induzione per dimostrare: “ogni numero naturale è pari oppure dispari”.

Regola di Induzione.

• (Passo base) Supponiamo di aver dimostrato che 0 soddisfa la proprietà P.

• (Passo Induttivo) Supponiamo di aver anche dimostrato, per ogni numero naturale n, che se n soddisfa P anche n+1 soddisfa P.

• (Conclusione) Allora ogni numero naturale soddisfa P.

Perché P vale per ogni n?

• 0 soddisfa P.• Se 0 soddisfa P, anche 1=0+1 soddisfa P. Dunque

1 soddisfa P.• Se 1 soddisfa P, anche 2=1+1 soddisfa P. Dunque

2 soddisfa P.• Se 2 soddisfa P, anche 3=2+1 soddisfa P. Dunque

3 soddisfa P.• Se 3 soddisfa P, anche 3=2+1 soddisfa P. Dunque

4 soddisfa P.• ………………… eccetera …………………

Un Esempio (facile)

• Proviamo che ogni numero naturale è pari o dispari.

• (Passo base) 0 è pari, dunque pari o dispari.

• (Passo Induttivo) Se n è pari, allora n+1 è dispari, e se n è dispari, allora n+1 è pari. Dunque: se n è pari o dispari, anche n+1 è pari o dispari.

Un Esempio (continua)

• Concludiamo, per la Regola di Induzione, che la proprietà P “essere pari o dispari” vale per ogni n.

• Lo sapevamo già, ma non importa: volevamo solo spiegare come si usa la regola.

Perché P vale per ogni n?

• 0 è pari o dispari.• Se 0 è pari o dispari, allora 1=0+1 è pari o dispari.

Dunque 1 è pari o dispari.• Se 1 è pari o dispari, allora 2=1+1 è pari o dispari.

Dunque 2 è pari o dispari.• Se 2 è pari o dispari, allora 3=2+1 è pari o dispari.

Dunque 3 è pari o dispari.• Se 3 è pari o dispari, allora 4=3+1 è pari o dispari.

Dunque 4 è pari o dispari.• ………… eccetera …………

2. La Prova di Euclide.

• Negli “Elementi di Geometria”, Euclide prova che esistono infiniti numeri primi.

• La prova contiene un algoritmo (non molto efficiente, per la verità), per generare infiniti numeri primi.

Dimostrazione per induzione

• Proveremo per Induzione che, per ogni n, esistono almeno n+1 primi (distinti tra loro).

• Dobbiamo provare che esiste almeno un numero primo, e che se ne esistono almeno n+1, allora ne esistono almeno (n+1)+1=n+2 (almeno uno in più).

Dimostrazione per Induzione: passo base

• Esiste almeno un numero primo, il numero 2.

Dimostrazione per Induzione: passo induttivo• Supponiamo che esistano n+1 primi:

p1, p2, p3, …, pn+1

• Sia X = (p1p2p3…pn+1 + 1). X diviso pi fa (p1…pi-1pi+1…pn+1), con resto 1.

• Dunque nessun pi divide esattamente X, cioè nessun pi è fattore primo di X.

Dimostrazione per Induzione: passo induttivo (segue)

• Segue che ogni fattore primo di X è distinto da p1, p2, p3, …, pn+1.

• Sia pn+2 il minimo fattore primo di X. Allora p1, p2, p3, …, pn+1 , pn+2 sono n+2 primi distinti.

L’algoritmo nascosto nella prova di Euclide.• Partiamo con una lista di un solo primo, p1

= 2.

• Sia X = (prodotto del solo 2) + 1 = 2+1=3. Il minimo fattore primo di X, cioè 3, è il secondo primo nella nostra lista.

• Sia X =2.3+1=7. Il minimo fattore primo di X, cioè 7, è il terzo primo della nostra lista.

L’algoritmo nascosto nella prova di Euclide (segue)

• La lista dei primi prosegue con:• X= 2.3.7+1 = 43, p4= 43• X= 2.3.7.43+1 = 1807 = 13.139 p5= 13• X= 2.3.7.43.13+1= 23479 = 53.443 p6= 53

• Il procedimento trova dunque infiniti numeri primi (non trova però tutti i numeri primi, ma solo alcuni, disposti per di più in modo bizzarro).

3.Un algoritmo di ordinamento (ottenuto da una dimostrazione)

• Daremo un esempio di una prova per induzione corrispondente ad un algoritmo di ordinamento.

• Per la cronaca, l’algoritmo di ordinamento che otterremo porta il nome di InsertSort.

Cos’è un algoritmo di ordinamento

• Un algoritmo di ordinamento prende una lista di oggetti (per esempio, una lista di nomi), e la dispone seguendo un certo ordine (per esempio, quello alfabetico), senza aggiungere né togliere elementi.

• Si tratta di un procedimento che viene ampiamente usato in Informatica.

Un Esempio.

• Sia L una lista di nomi:

Gabriele, Eloisa, Emanuele, Federico

• Una versione ordinata L’ di L è:

Eloisa, Emanuele, Federico, Gabriele

Dimostrazione: una lista può sempre essere ordinata.

• Proviamo per induzione che, per ogni n, ogni lista L di n+1 elementi ha una versione ordinata L’.

• Dobbiamo provare che una lista di 1 elemento ha una versione ordinata, e che se le liste di n+1 elementi hanno versioni ordinate, allora anche le liste di (n+1)+1=n+2 elementi hanno versioni ordinate.

Passo base.

• Una lista L di 1 elemento è già ordinata.

• Infatti L non ha due elementi, e dunque, a maggior ragione, non ha due elementi in ordine errato (l’argomento può apparire paradossale, ma è logicamente corretto).

Passo Induttivo.

• Sia L = a1, a2, a3, …, an+1 una lista di n+1 elementi, M = L, an+2 una lista di n+2 elementi.

• Supponiamo che L abbia una versione ordinata L’= b1, b2, b3, …, bn+1. Dobbiamo definire una versione ordinata M’ della lista M.

Passo Induttivo (segue)

• Inseriamo an+2 entro L’, dopo tutti gli elementi b1, …, bi, che precedono an+2 nell’ordine, ma prima di tutti gli elementi bi+1, …, bn+1 che seguono an+2 .

• Sia M’ = b1, …, bi, an+2 , bi+1, …, bn+1

• M’ è una versione ordinata di M. Infatti in M’ vengono prima gli elementi di L precedenti an+2, nel loro ordine, poi an+2 stesso, poi gli elementi di L che seguono an+2, sempre nel loro ordine.

L’algoritmo nascosto nella prova di ordinamento.

• Sia L = Gabriele, Eloisa, Emanuele, Federico, una lista di nomi.

• Utilizzeremo la prova di ordinamento come algoritmo per ordinare L (in ordine alfabetico).

L’algoritmo di ordinamento (passo 1)

• La lista di 1 elemento L1 = Gabriele viene lasciata com’è.

L’algoritmo di ordinamento (passo 2)

• Sia L2 = L1, Eloisa = Gabriele, Eloisa • Si inizia col dividere L1 in due parti: i nomi che

precedono Eloisa nell’ordine alfabetico (la lista vuota), e i nomi che seguono Eloisa (il solo Gabriele).

• Quindi si forma la lista ordinata

L’2 = Eloisa, Gabriele• ponendo prima i nomi precedenti Eloisa, poi

Eloisa stessa, infine i nomi che seguono Eloisa.

L’algoritmo di ordinamento (passo 3)

• Sia L3 = L’2, Emanuele = Eloisa, Gabriele, Emanuele.

• Si inizia col dividere L’2 in due parti: i nomi che precedono Emanuele nell’ordine alfabetico (la sola Eloisa), e i nomi che seguono Emanuele (il solo Gabriele).

L’algoritmo di ordinamento (segue passo 3)

• Quindi si forma la lista ordinata

L’3 = Eloisa, Emanuele, Gabriele

• ponendo prima i nomi precedenti Emanuele, poi Emanuele stesso, infine i nomi che seguono Emanuele

L’algoritmo di ordinamento (passo 4)

• Sia L4 = L’3, Federico = Eloisa, Emanuele, Gabriele, Federico.

• Si inizia col dividere L’3 in due parti: i nomi che precedono Federico nell’ordine alfabetico (Eloisa e Emanuele), e i nomi che seguono Federico (il solo Gabriele).

L’algoritmo di ordinamento (passo 4 e fine)

• Quindi si forma la lista ordinata

L’4 = Eloisa, Emanuele, Federico, Gabriele

• ponendo prima i nomi precedenti Federico, poi Federico stesso, infine i nomi che seguono Federico.

4. Un risultato generale

• Un logico, G. Kreisel, ha provato nel 1960 che ogni dimostrazione matematica dell’esistenza di un oggetto con proprietà decidibili (=verificabili mediante un procedimento meccanico) può essere letta come un algoritmo.

• Tale algoritmo utilizza effettivamente le idee contenute nella dimostrazione stessa.

Un esempio di applicazione del Teorema di Kreisel• L’enunciato “esiste una versione ordinata

L’ di una lista L data” afferma l’esistenza di un oggetto, L’, con una proprietà “decidibile”, essere ordinata.

• Dunque ogni prova per induzione di tale proprietà, contiene, per il per il Teorema di Kreisel, un metodo per costruire tale versione ordinata L’ di L.

Conclusioni

• In questa conferenza abbiamo visto come la regola di Induzione abbia una “lettura” come algoritmo abbastanza intuitiva.

• Il Teorema di Kreisel, però, ci dice che la stessa “lettura” è possibile per tutte le dimostrazioni dell’esistenza di un oggetto con proprietà decidibili, anche per quelle che utilizzano ragionamenti per assurdo, in cui la lettura come algoritmo non è affatto evidente (pero c’è).

Uno Slogan

Dimostrazioni di esistenza di un x avente una proprietà P

=

un algoritmo che trova tale x

+

una prova che x soddisfa P

(purché la proprietà P sia decidibile).

Estrazione di Programmi da Prove

• Esistono vari sistemi di sviluppo di dimostrazione al calcolatore, come il francese Coq.

• Essi consentono di scrivere una dimostrazione al calcolatore, quindi di controllarne la correttezza logica, infine di produrre automaticamente l’algoritmo associato alla prova stessa.