Problemi facili, problemi difficili

Un rappresentante di commercio…

…deve recarsi a Cagliari, Carbonia, Muravera, Oristano e Sanluri (non importa in quale ordine).

Più chilometri percorre, più aumentano i costi (in tempo e in denaro).

Quale percorso gli Quale percorso gli conviene fare?conviene fare?

Cos’è un algoritmo?

E’ una procedura:• formulata mediante un numero finito di

istruzioni esatte, ciascuna delle quali contiene un numero finito di simboli;

• se eseguita correttamente, produce il risultato desiderato in un numero finito di passi;

• deve poter essere eseguita (in linea di principio) con carta e matita da un essere umano non aiutato da una macchina;

• Non deve richiedere l’uso di creatività o ingegno.

Esempi

Addizioni e moltiplicazioni in colonna;

Estrazione della radice quadrata; Conversione di numeri decimali

periodici in frazione; Tavole di verità.

Quand’è che un algoritmo è efficiente?

Prima proposta: Quando produce la soluzione desiderata in un tempo “rapido”

DIFETTI: la velocità di calcolo dipende dal computer su cui l’algoritmo è implementato e dal linguaggio di programmazione usato

Si vuole una definizione di efficienza che non dipende da questi fattori accidentali

Macchina di Turing

E’ un modello matematico astratto dell’attività di esecuzione di algoritmi. Si compone di:

un alfabeto finito un nastro potenzialmente

infinito in entrambe le direzioni, diviso in celle (ognuna può contenere al più un simbolo)

un lettore che può osservare solo una cella per volta

Una memoria capace di un numero finito di stati, detti stati interni

UNA MACCHINA DI TURING SI IDENTIFICA ASTRATTAMENTE CON LA SUA TAVOLA DELLE ISTRUZIONI

Macchina di Turing per l’operazione di addizione

1 0 0 S 1

1 1 0 S 2

2 0 1 S 3

2 1 1 S 2

3 0 0 D 4

3 1 1 S 3

4 0 0 H 4

4 1 0 H 4

Se eseguo un algoritmo A su una (qualsiasi) macchina di Turing:

La lunghezza dell’input è il numero di “1” presenti sul nastro all’inizio del calcolo

La lunghezza del calcolo è il numero di passi necessari alla macchina per terminare l’esecuzione dell’algoritmo

QUESTE NOZIONI NON DIPENDONO DALLA MACCHINA DI TURING SU CUI L’ALGORITMO E’ IMPLEMENTATO

Algoritmi efficienti

Un algoritmo A è polinomiale (P) quando la lunghezza del calcolo è data da una funzione polinomiale della lunghezza dell’input

N = lunghezza del calcolo

n = lunghezza dell’input A è polinomiale sse

esistono k, C t.c. per ogni n

N < Cnk

Algoritmi inefficienti

Un algoritmo A è esponenziale quando la lunghezza del calcolo è data da una funzione esponenziale della lunghezza dell’input

Esempio:N = 2n

Perché polinomiale = efficiente, esponenziale = inefficiente?

Aumento della lunghezza del calcolo in funzione della lunghezza dell’input:

1 2 3 5 10

N = n2 1 4 9 25 100

N = 2n 2 4 8 32 1024

Torniamo al nostro rappresentante…

Se deve visitare n località, i percorsi possibili sono n!

La funzione fattoriale cresce più rapidamente di 2n

L’ALGORITMO DELLA RICERCA ESAUSTIVA E’ TIPICAMENTE INEFFICIENTE!!!

Inzà, ‘ta faeusu?

Fortunatamente, per casi specifici del problema, si danno algoritmi efficienti:

Programmazione dinamica (Held e Karp 1962): n = 13

Branch and bound (Crowder e Padberg 1979): n = 318

Problemi decisionali

Variante decisionale del problema del commesso viaggiatore:

“Dato un insieme di località e un numero B, esiste un percorso che tocchi tutti i luoghi e abbia una lunghezza al massimo pari a B”?

Macchina di Turing non deterministica

Esistono istruzioni ambigue: ad esempio

Quando si trova di fronte a più istruzioni contrastanti, la macchina sceglie quella che massimizza la rapidità del calcolo

4 0 1 S 5

4 0 0 D 4

Algoritmi NP

Un algoritmo A è NP quando la lunghezza del calcolo su una macchina di Turing non deterministica è data da una funzione polinomiale della lunghezza dell’input

Esiste un algoritmo NP per il nostro rappresentante di commercio?

Sì: 1) Sceglie a caso il primo

luogo da visitare, poi il secondo, poi il terzo…;

2) Calcola il percorso totale; 3) Lo confronta col numero

assegnato B

Supponendo che a ogni stadio si “indovini” la località successiva, il risultato corretto sarà calcolato in tempo polinomiale

La probabilità che ciò si verifichi nella realtà è 1/n!

Problemi NP-completi

Un problema è NP-completo se una sua eventuale soluzione implica una soluzione di ogni altro problema NP

TEOREMA DI COOK: Determinare se una formula logica è una

tautologia mediante le tavole di verità è un problema NP-completo

(Anche il commesso viaggiatore, e molti altri problemi, lo sono)

P = NP?

E’ convinzione generale che i problemi NP non siano P…

…ma nessuno è mai riuscito a dimostrarlo

PROVATECI: se ci riuscite avrete gloria imperitura…

…e 1.000.000 di dollari in contanti (Clay Institute)

Programmazione lineare

Algoritmi inefficienti in teoria possono funzionare bene con dati semplici (ossia nella maggior parte dei problemi pratici).

ESEMPIO: programmazione lineare, che funziona nei problemi di ottimizzazione

Esempio dell’industria tessile (1)

Un’industria produce due tessuti, A e B, usando lana rossa, verde e gialla

In magazzino ci sono: 1400 kg lana rossa 1800 kg lana verde 1800 kg lana gialla

Esempio dell’industria tessile (2)

Il profitto dell’azienda è 12 Euro per ogni pezza di tessuto A e 8 Euro per ogni pezza di tessuto B

La lana occorrente per ciascuna pezza è:

Tess. A

Tess. B

rossa 4 kg 4 kg

verde 6 kg 3 kg

gialla 2 kg 6 kg

Esempio dell’industria tessile (3)

Come dobbiamo usare la lana in modo da massimizzare il profitto?

X = numero di unità di tessuto A Y = numero di unità di tessuto B P = 12X + 8Y 4X + 4Y <= 1400 6X + 3Y <= 1800 2X + 6Y <= 1800 0 <= X; 0 <= Y

Altri metodi usati

Metodo del simplesso (Dantzig 1947) esponenziale ma in pratica funziona

(calcolo teorico dell’efficienza fatto sul caso più sfavorevole)

Metodo ellissoidale (Shor 1970) polinomiale ma non funziona bene in

pratica Metodo di Karmarkar (1984) polinomiale e funziona bene in pratica

(non si va da un vertice all’altro di un politopo, ma ci si muove al suo interno)