Author Archives: admin

Dal problema alla risposta – Approfondimento

I problemi

I problemi sono delle richieste che richiedono all’uomo un certo impegno fisico e/o intellettuale.
Ma tra tutti i problemi, di quali si occupa l’informatica?

Assurdi? Perché perdere tempo se la richiesta è assurda…
Impossibili? Pur interessanti, è dimostrato che non ammettono soluzione, quindi… sono PROBLEMI NON COMPUTABILI
Intrattabili? Le risorse hardware e/o il tempo necessario per ottenere la soluzione sono proibitivi, quindi… sono PROBLEMI INTRATTABILI
Banali? Esiste un dispositivo dedicato adatto allo scopo, quindi…
Interessanti? Se il problema non è assurdo, impossibile, intrattabile, banale allora… ce ne occupiamo

Un’istanza di un problema è un caso specifico, particolare del problema stesso (perché sono fissati i dati del problema).

Gli esecutori

Da sempre l’uomo desidera avere un suo sostituto che lo sollevi dalla fatica oppure che gli risparmi le lunghe attese necessarie per avere la risposta a ogni istanza di un certo problema (qualsiasi problema…)

Umanoidi Automa, androide, schiavo, macchina, robot, cyborg, ….
Dispositivi Ascensore, calcolatrice, decoder, pianola, …
Letteratura Golem, Frankenstein, …
Cinema Metropolis, Blade Runner, Terminator, Robocop, Io e Caterina, I robot, …

Computabilità

Un problema è computabile, calcolabile, se esiste un (algoritmo per un) esecutore che è capace di produrre, in tempo finito, la risposta corrispondente a qualsiasi istanza del problema.

Nel primo ‘900 sono stati proposti molti modelli astratti, formali, di esecutori che potessero calcolare la risposta per ogni istanza di un problema

Autore Sistema di calcolo
Stephen Kleene Funzioni ricorsive (parziali)
Emil Post Sistemi di riscrittura (sistemi formali)
Alonso Church Lambda calcolo
Alan Mathison Turing Macchina di Turing
John Von Neumann Macchina a registri

I primi tre esecutori sono dei sistemi di calcolo di tipo logico-matematico e permettono di calcolare la risposta applicando delle regole ad un insieme iniziale di formule logico-matematiche che rappresentano l’istanza del problema…

La macchina di Turing e la macchina a registri sono dei modelli più vicini alla realtà che hanno permesso di costruire le prime macchine calcolatrici.

Macchina universale

Se si definisce un insieme minimo di istruzioni riconosciute, ed eseguite, da una macchina allora essa diventa un sistema di calcolo universale.

Non è più necessario progettare fisicamente la macchina per un certo problema ma è sufficiente progettare un algoritmo, risolutivo per il problema, e farlo eseguire per una certa istanza.

È stato dimostrato che gli insiemi dei problemi computabili dai diversi sistemi di calcolo, finora proposti, sono equivalenti.
Quindi conviene utilizzare il sistema di calcolo più pratico perché non c’è alcun vantaggio teorico fra l’uno e l’altro.

Tesi di Church

L’insieme dei problemi computabili coincide con quello della macchina di Turing.

Si ipotizza che la macchina di Turing sia sufficiente per tutti i problemi computabili (e quindi lo sono anche gli altri sistemi di calcolo).

Equivale a: “tutti i computer, presenti e futuri, hanno e avranno la stessa capacità di calcolo”.

Algoritmo

Il concetto di algoritmo si è evoluto insieme ai sistemi di calcolo.

Un algoritmo è

  • una macchina di Turing che per ogni istanza del problema in esame restituisce, in tempo finito, le risposte attese
  • un programma per una macchina di Turing universale che …
  • un programma in forma comprensibile per una macchina programmabile che …
  • un programma in forma comprensibile per l’uomo che … (questo punto è controverso!)
Vedi le definizioni fornite da Wikipedia:Algoritmo

Un algoritmo è

  1. Un procedimento che permette di risolvere un certo problema tramite un numero finito di passi.
  2. Una sequenza ordinata e finita di passi (operazioni o istruzioni) elementari che conduce ad un ben determinato risultato in un tempo finito.

Non esiste un modello unico per rappresentare un algoritmo.
La scelta dipende dal problema, paradigma di programmazione, risolutore, esecutore, …

Diagramma di stato Stati e transizioni di stato: cerchi e frecce
Programma per la macchina di Turing Quintuple di simboli
Diagramma di flusso Flow-chart: rombi, rettangoli, cerchi, frecce
Istruzioni, decisioni
Programma scritto con un linguaggio di basso livello Istruzioni per la macchina a registri
Linguaggio a salti…
un linguaggio di alto livello Istruzioni interpretate/compilate
Linguaggio strutturato!
uno pseudo-linguaggio Istruzioni più vicine a formalismi già noti
Linguaggio naturale, formalismo logico-matematico …

Alcune considerazioni…

  • le istruzioni (gli stati) sono in numero finito
  • le singole istruzioni sono non ambigue per l’esecutore
  • le singole istruzioni sono eseguibili in tempo finito
  • l’intero algoritmo è eseguibile in tempo finito
  • la risposta per una certa istanza è sempre la stessa…

Dal problema alla risposta

Macchina dedicata

Una macchina progettata per svolgere un compito specifico.
La macchina riceve i dati e svolge le operazioni prestabilite per ottenere la risposta.

problema4

La maggior parte degli elettrodomestici sono macchine dedicate: calcolatrice tascabile, ascensore, lavatrice, decoder, …

Macchina onnipotente

All’estremo opposto una macchina capace di rispondere a richieste di qualsiasi tipo, di risolvere qualsiasi problema…

problema3

Macchina programmabile

Una macchina che può essere istruita, tramite un certo programma, per risolvere un certo problema.

problema31

Esempi: computer tradizionale, calcolatrice programmabile, console per videogiochi con cartucce intercambiabili, …

Algoritmo

Ogni esecutore ha un insieme diverso di istruzioni ma i problemi sono sempre gli stessi…
È utile separare la fase di risoluzione del problema dalla scrittura delle istruzioni.
In questo modo lo stesso metodo risolutivo, algoritmo, può essere tradotto in innumerevoli programmi.

problema2

Si introducono due figure: il risolutore e il programmatore

  • Il risolutore svolge il lavoro più difficile, individuare l’algoritmo per il problema….
  • Il programmatore traduce l’algoritmo in programma utilizzando un ambiente di sviluppo per un certo linguaggio di programmazione.

Compilatore

Tra il programma e l’esecutore, compaiono il file sorgente e il file oggetto.

problema1

Il programmatore utilizza

  • l’editor per scrivere il file sorgente
  • il compilatore per tradurre da alto a basso livello e produrre il file oggetto.

Il compilatore può produrre un file oggetto compatibile con una certa piattaforma.
Linguaggi di programmazione compilati: C/C++, COBOL, FORTRAN, Pascal, …

La macchina virtuale

La tecnica della macchina virtuale ha permesso la diffusione di applicazioni eseguibili su tutte le piattaforme.

problema12

Si produce un unico file oggetto (bytecode) che viene eseguito dalla macchina virtuale (plug-in, player, …) installata sulla piattaforma

Testing e debugging

Con il testing si mette alla prova il programma oggetto su diverse istanze del problema.
Utilizzando dati significativi per i quali si conosce la risposta esatta si può raggiungere una ragionevole certezza che il software funzioni.

problema11

Quando una risposta non è quella attesa sarà necessario svolgere il debugging (individuare gli errori) su sorgente, programma, algoritmoproblema (???).

Complessità: asintotica

Dopo aver analizzato la complessità in tempo di alcuni algoritmi possiamo osservare che

  1. il caso ottimo di un algoritmo è quasi sempre costante
  2. e non sarebbe significativo per la bassa probabilità che si presenti
  3. il caso pessimo e il caso medio dipendono dalla dimensione dei dati
  4. è difficile calcolare con precisione le costanti moltiplicative
  5. per n piccolo è difficile decidere tra due algoritmi
  6. mentre per n abbastanza grande la differenza di comportamento diventa evidente

Per dare una misura della complessità in tempo di un algoritmo si preferisce

  • dare una misura approssimata del calcolo del tempo di esecuzione T(n)
  • studiare il caso pessimo oppure il caso medio
  • valutare il comportamento per n sufficientemente grande…

Definizione

Si introduce la complessità asintotica e la notazione O(f(n))

una funzione g(n) è O(f(n)), e si legge g(n) è dell’ordine o grande di f(n), se esistono una costante moltiplicativa c ed un numero naturale n0 tali che g(n) ≤ c f(n), per una certa c e per ogni n ≥ n0

Esempio

Data la funzione g(n)=2n2+4n+2, scegliendo opportunamente i valori c=2.1 e n0 ≥ 41 si ha

g(41) = 3528 < 3530.1 = 2.1(41)2 = c n02

allora

g(n) < 2.1 n2, per n ≥ 41

e quindi

g(n) ∈ O(n2)

In pratica

  • le costanti moltiplicative diventano trascurabili
  • le combinazioni lineari di funzioni diventano trascurabili
  • è sufficiente individuare la funzione più pesante
  • tutte le funzioni lineari sono dell’ordine O(n)
  • tutte le funzioni quadratiche sono dell’ordine O(n2)

La complessità in tempo viene riassunta in una funzione più significativa che rappresenta la complessità in tempo asintotica.

Esempi

Le costanti sono spropositate per evidenziare l’aspetto asintotico… della complessità

  • T1(n)=2n+400log2n ∈ O(n)
  • T2(n)=2n3+400n ∈ O(n3)
  • T3(n)=20.000+log10n ∈ O(logn)
  • T4(n)=3n+400n4+100.000.000 ∈ O(2n)

Tabella

Le funzioni di complessità interessanti in ambito informatico sono relativamente poche

  • O(1), costante
  • O(log n), logaritmica
  • O(n), lineare
  • O(n log n), enne-log-enne
  • O(n2), quadratica
  • O(nk), polinomiale
  • O(2n), esponenziale

Complessità: torre di Hanoi

Dopo aver analizzato il problema decidiamo che il tempo di esecuzione dell’algoritmo è proporzionale al numero di spostamenti dei dischi

T(1)=1
T(2)=T(1)+T(1)+T(1)=3
T(3)=T(2)+T(1)+T(2)=7
T(4)=T(3)+T(1)+T(3)=15
...
T(n)=T(n-1)+T(1)+T(n-1)=2*T(n-1)+1

Numericamente si tratta della successione

1, 3, 7, 15, 31, 63, 127, ...

cioè

21-1, 22-1, 23-1, 24-1, 25-1, 26-1, 27-1, ...

quindi

T(n) = 2n-1

I tempi necessari per risolvere il problema sono

n T(n)=2n-1 1 Hz
(uomo)
1 GHz
(PC)
1 21-1=1 un secondo 10-9 s
2 22-1=3 3 secondi 3*10-9 s
10 210-1=1023 ~17 minuti ~10-6 s
20 220-1=1.048.575 ~12 giorni ~10-3 s
30 230-1=1.073.741.823 ~34 anni ~1 s
64 264-1=18.446.744.073.709.551.615 ~5*1011 anni ~500 anni

Conclusioni

  • L’algoritmo per il problema della torre di Hanoi ha complessità in tempo asintotica esponenziale, O(2n)
  • Non può esistere un algoritmo con complessità minore
  • Il problema della torre di Hanoi è un problema intrinsecamente esponenziale
  • Il problema della torre di Hanoi è un problema intrattabile!

Complessità: numeri di Fibonacci

Dopo aver analizzato il problema e individuati i 3 algoritmi discutiamo la loro complessità in tempo.

Algoritmo ricorsivo

Il tempo di attesa può essere considerato proporzionale al numero di chiamate ricorsive
  • T(1)=1
  • T(2)=1
  • T(3)=1+T(2)+T(1)=1+1+1=3 > 22-1
  • T(4)=1+T(3)+T(2)=1+3+1=5 > 22-1
  • T(5)=1+T(4)+T(3)=1+5+3=9 > 23-1
  • T(6)=1+T(5)+T(4)=1+9+5=15 > 23-1
  • T(7)=1+T(6)+T(5)=1+15+9=25 > 24-1
  • T(8)=1+T(7)+T(6)=1+25+15=41 > 24-1
  • T(n) ≥ 2n/2-1.

Il tempo di attesa è maggiore di un tempo esponenziale, anche se con esponente n/2 piuttosto che n, quindi per n molto grande

T(n) ∈ O(2n).

L’algoritmo ricorsivo per il calcolo dell’n-simo numero di Fibonacci ha complessità esponenziale!

Algoritmo iterativo

Si tratta di un algoritmo con un’iterazione semplice, senza chiamate ricorsive, quindi

T(n)=c1+c2n
T(n) ∈ O(n).

L’algoritmo iterativo per il calcolo dell’n-simo numero di Fibonacci ha complessità lineare!

Con formula

Se consideriamo costante il tempo necessario per svolgere le singole operazioni presenti nella formula allora

T(n)=c
T(n) ∈ O(1).

Se consideriamo che per n molto grande l’operazione di elevamento a potenza potrebbe dipendere dal numero di cifre e che il numero di cifre del risultato cresce proporzionalmente a n allora si ottiene di nuovo una complessità lineare.

Conclusioni

Dato un certo problema, il calcolo dell’n-esimo numero di Fibonacci, possiamo individuare diversi algoritmi con complessità diverse.

Per n abbastanza grande utilizzeremo quello con la complessità più bassa!

Complessità: problemi difficili

L’argomento viene trattato in modo molto semplificato.

Definiamo polinomiali quei problemi con

T(n) <= nc, (c > 1)

e esponenziali quelli con

T(n) <= an, (a > 1).

Esistono molti problemi che ammettono un algoritmo risolutivo esponenziale ma per i quali non si è certi che la loro complessità sia esponenziale e si spera che in futuro possano essere ricondotti nella classe dei polinomiali.

Si definiscono problemi non polinomiali (NP), insiemisticamente: P ( NP ( EXP

Tra questi problemi (commesso viaggiatore, zaino, …) esiste una relazione sorprendente: sono tutti equivalenti tra loro!

Ogni volta che è stato introdotto un nuovo problema tra gli NP è stato dimostrato che, a meno di qualche adattamento, la sua soluzione può essere ricavata a partire dalle soluzioni di un altro problema già noto come NP.

Se dovesse esistere un algoritmo polinomiale per uno qualsiasi tra essi questo potrebbe essere utilizzato anche per tutti gli altri.

Problemi intrattabili

Ci sono problemi per i quali si può dimostrare che il tempo di esecuzione del miglior algoritmo è almeno esponenziale

  • torre di Hanoi
  • permutazioni

Si dice che sono problemi intrinsecamente esponenziali.
Sono problemi intrattabili per la maggior parte delle loro istanze.

Complessità: problemi

Complessità dei problemi

Dato un problema P si possono individuare diversi algoritmi risolutivi

A1, A2, … Aq

ciascuno con la sua complessità

C1, C2, …, Cq.

Sia C* la complessità più bassa. Se si dimostra che per il problema P non può esistere un algoritmo con complessità minore di C* allora si può affermare che il problema P ha complessità C*.

Problema 1

Le possibili sequenze di lunghezza n costruite con un alfabeto di 26 caratteri sono 26: aa…a, aa…b, aa…c, …, zz…z.

Se consideriamo il tempo necessario per visualizzare le risposte e tralasciamo qualsiasi altra operazione otteniamo T(n)= 26n >> 2n. Il problema ha complessità almeno esponenziale O(2n).

Problema 2

Consideriamo le permutazioni di n elementi qualsiasi

Permutazioni Numero
1 a 1
2 ab, ba 2
3 abc, acb, bac, bca, cab, cba 6
4 abcd, abdc, acbd, acdb, bacd, badc, bcad, bcda
cabd, cadb, cbad, cbda, dabc, dacb, dbac, dbca
24
5 120
n n!

Come prima si ottiene T(n)=n! >> 2e quindi il problema ha complessità almeno esponenziale O(2n).

Problema 3

Nel prodotto tra matrici di dimensioni nxn, C=AxB, è richiesto almeno il tempo

  • T1(n)=n2, per scrivere i risultati in C
  • T2(n)=2*n2, per leggere i dati in A e B

Non può esistere un algoritmo con complessità inferiore a quella necessaria per esaminare l’input oppure per generare l’output e quindi si parte comunque da una complessità quadratica.

L’algoritmo tradizionale che calcola il singolo elemento Cij tramite il prodotto scalare

Cij = Ai*Bj = Ai1*B1j+Ai2*B2j+…+Ain*Bnj

richiede n moltiplicazioni per ogni prodotto scalare e quindi richiede T3(n) = n*n2 = nper calcolare tutti i prodotti.

Questo algoritmo potrebbe non essere il migliore (…) ma ci permette di stabilire un limite superiore per la complessità del problema.

In conclusione

T1(n) < T2(n) <= T(n) <= T3(n)
n2 <= T(n) <= n3

Il problema del prodotto matriciale ha una complessità compresa tra O(n2) e O(n3).

Problema 4

Per il problema dell’ordinamento esistono molti algoritmi con complessità diverse

O(n2) Ingenui selection sort, bubble sort, shaker sort, insertion sort
O(n~1.2) Intermedi shell sort
O(nlogn) Evoluti merge sort, quick sort, heap sort

Si può dimostrare che non possono esistere algoritmi con complessità più bassa di O(n log n), quindi il problema dell’ordinamento ha complessità O(n log n).

Complessità degli ordinamenti

Confrontiamo la complessità in tempo degli algoritmi di ordinamento ingenui con quella degli algoritmi evoluti, al variare della dimensione del problema

n n2 (ingenuo) nlog2n (evoluto) evoluto / ingenuo
103 106 ~104 10-2
106 1012 ~2*107 2*10-5
109 1018 ~3*1010 3*10-8
1010 1020 ~3,3*1011 3,3*10-9

Moltiplicando per 103 il numero di elementi nel vettore, si moltiplica per 106 il numero di operazioni dell’algoritmo ingenuo (per ~104 il numero di operazioni dell’algoritmo evoluto…).

Se un calcolatore svolge 106 operazioni elementari al secondo allora i tempi di attesa sono

n n2 nlog2n
103 ~1 sec ~0.01 sec
106 ~11,5 giorni ~20 sec
109 ~30 mila anni ~8 ore
1010 ~3 milioni di anni ~4 giorni

Se un calcolatore svolgerà, fra qualche anno, 109 operazioni elementari al secondo allora i tempi di attesa saranno

n n2 nlog2n
103 ~0.001 sec ~0.00001 sec
106 ~17 min ~0.02 sec
109 ~30 anni ~30 sec
1010 ~3000 anni ~5,5 min

Complessità: ricerca binaria

Analizziamo il codice

Utilizzando la tecnica di calcolo della complessità in tempo possiamo concludere che

T(x) = c1+c2x

con x il numero di volte che viene eseguito il ciclo.

I calcoli approssimati per T danno

  • vettore vuoto: ~7
  • elemento trovato al 1° passo (in mezzo): c1+c2*1
  • elemento trovato al 2° passo: c1+c2*2
  • elemento trovato all’ultimo passo: c1+c2*(m-1)
  • elemento non presente: c1+c2*m

Supponiamo pessimisticamente di dover aspettare sempre fino all’ultimo passo, allora

T(n)=c1+c2*m.

Quanto vale m?

La dimensione del vettore sul quale si effettua la ricerca passo-passo è

  • n
  • ~n/2
  • ~n/4
  • ~n/8
  • ...
  • 2
  • 1
  • 0

Quando il valore della potenza di 2 a denominatore raggiunge n il ciclo termina sicuramente, cioè per

2= n

quindi, nel caso pessimo

T(n) = c1+c2m = c1+c2log2n

Esempi numerici

n m
24 16 4
28 256 8
210 1.024 10
216 65.536 16
220 1.048.576 20
230 1.073.741.824 30

L’algoritmo di ricerca binaria applicato a un vettore con un miliardo di elementi garantisce una risposta dopo appena 30 passi!

Complessità delle ricerche

Per semplificare i calcoli e per rendere più evidente il confronto tra i due algoritmi ipotizziamo che i coefficienti numerici delle funzioni di complessità in tempo siano molto sfavorevoli per la ricerca binaria, per esempio

  • Tseq(n)=5+5*n
  • Tbin(n)=100+100*log2n

calcoliamo i tempi di attesa al variare di n

n Tseq(n) Tbin(n)
16 5+5*16=85 100+100*4 = 500
256 5+5*256=1285 100+100*8 = 900
1.024 5+5*1.024=5125 100+100*10 = 1.100
65.536 ~105 100+100*16 = 1.700
1.048.576 ~107 100+100*20 = 2.100
1.073.741.824 ~1010 100+100*30 = 3.100

Anche in questa situazione di svantaggio ipotetico l’algoritmo di ricerca binaria si comporta meglio se applicato ad appena 200 elementi!

comp_b2

Utilizzando la terminologia della complessità asintotica in tempo si può concludere che

la complessità dell’algoritmo di ricerca binaria, O(log n), è profondamente diversa da quella dell’algoritmo di ricerca sequenziale, O(n).