Casino online

Mercato forex

Come ho spiegato nell'ultimo capitolo della sezione A della mia guida, un algoritmo è l'insieme delle operazioni e dei processi logici necessari a risolvere un problema. Tuttavia in quella sede, non ho spiegato altro oltre a questo. In questo breve articolo, esporrò qualcosa di più tecnico, ma altrettanto interessante.
Si definisce tempo di risoluzione di un algoritmo il numero di "passi" necessari a portarlo a termine. Con la parola "passi" s'intendono operazioni di assegnamento o valutazioni di valori logici (anche di letterali). Ad esempio, tutte le espressioni seguenti sono considerati passi:

'Semplice assegnamento
A = B + C
'Valutazione di un'espressione logico-booleana
If A And (B Or C) Then
'Assegnamento, un po' più complesso
A = Math.Log10(A) + (B - (C / Math.Sqrt(D)))
'Comparazione in una struttura Select Case
Case "Ciao"

Per conferire più rigore matematico all'argomento che stiamo trattando, si è soliti definire alcuni parametri e variabili:

• Dimensione dei dati (x) : con questo parametro si indica la dimensione dei dati di input. Ci si può riferire arbitrariamente a x come ad un numero (al crescere del quale l'algoritmo aumenta i tempi di elaborazione), un vettore o una matrice (indicando quindi la dimensione di tale vettore o matrice) o anche all'area di memoria occupata (riferendosi a x come a una dimensione in bytes). È ovvio che maggiori sono le dimensioni dei dati di input, maggiore sarà il numero di operazioni da compiere per eseguire l'algoritmo e quindi maggiore sarà il tempo impiegato a risolvere il problema
• Tempo di risoluzione (T) : una volta definita x come dimensione dei dati, si definisce una funzione T(x) che restituisce, a priori, il tempo di risoluzione dell'algoritmo se si introduce in esso una quantità di dati pari a x

Ovviamente, non sempre si può stabilire a priori quale sarà il valore di T: nei casi in cui non è possibile, si dice che l'algoritmo è non deterministico. In tutti gli altri casi, esso si definisce deterministico.
Prima di procedere, ecco alcuni esempi di algoritmi deterministici:

1. Public Function Sum(ByVal A As Int32, ByVal B As Int32) As Int32
       Return A + B
   End Function

   Questo semplicissimo algoritmo prende in input due numeri e li somma tra di loro. In questo caso, sia x che T(x) sono sempre gli stessi. Dato che stiamo trattando due interi a 32 bit ciascuno, x sarà sempre di 32*2 bit, ossia 8 bytes; inoltre, poiché T(x) varia in funzione di x e x è costante, lo sarà anche T. Possiamo considerare la somma come un unico passo, ma, volendo addentrarsi di più nel dettaglio, potremmo discutere di come il computer esegue le somme. La macchina non fa altro che eseguire un'operazione logica Or su ogni bit degli operandi: disponendo di due operandi da 32 bit, verranno eseguite 32 operazioni logiche, che possiamo considerare un'altra valida unità di misura per T. In realtà non si sta a guardare troppo nei particolari, e dopo vedremo perchè

2. Public Function Sum2(ParamArray Values() As Int32) As Int32
       Dim Result As Int32
       
       For I As Int16 = 0 To Values.Length - 1
           Result += Values(I)
       Next
       
       Return Result
   End Function

   In questo algoritmo, x può variare, poiché la funzione accetta un numero qualunque di parametri. Inoltre, per ognuno di questi, viene eseguita una somma mediante un'iterazione del ciclo For. Avremo quindi che il numero di operazioni semplici compiute è uguale al numero di interi immessi in input. In conclusione T(x) = x, ossia il tempo di risoluzione varia linearmente (questo significa che T(x) ha la stessa equazione di una retta, ossia un polinomio di grado 1)

3. Public Function MaxProduct(ParamArray Values() As Int32) As Int32()
       Dim A, B As Int32
       Dim Result() As Int32
       Dim Max As Int32 = 0
       
       For I As Int16 = 0 To Values.Length - 1
           A = Values(I)
           For J As Int16 = 0 To Values.Length - 1
               B = Values(J)
               If A * B > Max Then
                   Result = New Int32() {A, B}
                   Max = A * B
               End If
           Next
       Next
       
       Return Result
   End Function

   Questo algoritmo prende in input un array di interi e stabilisce quale sia la coppia che dà un prodotto maggiore. Avendo due For nidificati, verranno eseguite x operazioni del secondo al primo step del primo, x al secondo step, x al terzo, e così via, fino a che anche il primo for non abbia raggiunto il massimo. Quindi in totale saranno eseguite x * x operazioni, ossia x². I più pignoli potranno obiettare che c'è un If e al suo intero un'assegnazione semplice, ma questa parte di algoritmo non è determinabile a priori poiché dipende dalla qualità e dalla quantità del dati immessi: possiamo considerarlo come un fattore k. La funzione T(x) potrà essere scritta come T(x) = x² + k, ossia il tempo di risoluzione varia quadraticamente (questo significa che T(x) ha la stessa equazione di una parabola, ossia un polinomio di grado 2)

4. Public Sub BruteForce(ByVal Bytes() As Byte)
       Dim Buffer(Bytes.Length - 1) As Byte
       
       Do Until Buffer = Bytes
           Dim Changed As Boolean = False
           
           For I As Int16 = Bytes.Length - 2 To 0 Step -1
               If Buffer(I + 1) = 255 Then
                   Buffer(I + 1) = 0
                   Buffer(I) += 1
                   Changed = True
               End If
           Next
           
           If Not Changed Then
               Buffer(Buffer.Length - 1) += 1
           End If
       Loop
       
       MessageBox.Show("Indovinato!")
   End Sub

   Questo è una algoritmo di forza bruta: dato in input un certo qual numero di byte (numeri interi da 0 a 255), bisogna tentare di ricostruire un array esattamente uguale a quello dato, semplicemente provando tutte le combinazioni possibili. Dato che ogni posto dell'array può assumere 256 valori diversi, il numero di combinazioni possibili in un array di x posti (ammettendo byte uguali) è 256^x. Bisogna notare che questo è solo il massimo numero di operazioni possibili, poiché quasi sicuramente si raggiungerebbe un risultato dopo un numero inferiore di tentativi (a meno che, ovviamente, tutti i byte siano 255). Ma nel campo dell'algoritmica si ragiona sempre in termini di massimi o minimi e quasi mai di valori precisi. In questo caso, però possiamo ricostruire il numero massimo di passi anche tenendo conto degli If, infatti: l'ultimo byte raggiungerà il valore 255 per 256^x-1 volte, il penultimo lo assumerà 256^x-2 volte, eccetera... e il primo solo una volta (ossia 256^x-x=256⁰=1). Sapendo che per ogni If vengono eseguite 4 operazioni e che il secondo If verrà eseguito 256ⁿ volte, possiamo scrivere: T(x) = 4 * 256^x + 4 * 256^x-1 + 4 * 256^x-2 + ... + 4 * 256^x-x. Non era necessario essere così precisi, poiché si stava analizzando comunque questo e solo questo particolare algoritmo. In generale, comunque, in casi di questi tipo la funzione T(x) varia esponenzialmente (questo significa che T(x) ha la stessa equazione di un esponenziale)

Generalizzando, i primi tre casi sono esempi di algoritmi polinomiali (anche detti "risolvibili in tempo polinomiale"), ossia T(x) non è altro che un polinomio a variabile x, di grado qualsiasi. Esempi di tempi polinomiali possono essere questi:

T(x) = ax + b  [lineare, polinomio di grado 1]
T(x) = ax2 + bx + c  [quadratica, grado 2]
T(x) = ax3 + bx2 + cx + d  [cubica, grado 3]
...

L'ultimo, invece, è un algoritmo risolvibile in tempo esponenziale, ossia T(x) non è altro che un esponenziale di base qualsiasi:

T(x) = ax + b
T(x) = ax + bx - 3 / (x + 1)

In ogni campo si cerca sempre di trovare algoritmi polinomiali e di grado più basso possibile, perchè il loro tempo di elaborazione è di molto inferiore a quello degli algoritmi a tempo esponenziale. Vi faccio un piccolo esempio per chiarire meglio questo concetto.
Ammettiamo di avere una data macchina M, che possa tranquillamente fare calcoli a una "velocità" di 3GHz. Ora ammettiamo di avere due algoritmi: L₁ è risolvibile in tempo polinomiale e ha che T₁(x) = x²; L₂ è risolvibile in tempo esponenziale e ha che T₂(x) = 2^x. Data in input una certa quantità di informazione, ad esempio x = 1000, M potrà risolvere L₁ in 1000² step, ossia:

3GHz = 3 * 109 step / secondo
Tempo = T(x) / (3 * 109) = 106 / (3 * 109) = 1/3 * 10-3 = 1/3 ms

circa 0,3 millisecondi; M risolverà anche L₂ ma in 2¹⁰⁰⁰ step, ossia:

Tempo = 21000 * 3GHz = 3,57 * 10291

circa 11 300 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 anni. Mi sembra evidente che il primo sia leggermente più vantaggioso.