Algoritmo: differenze tra le versioni

Versione delle 10:15, 16 ott 2024

Versione delle 13:41, 13 dic 2024

Riga 101:

Due misure per sistemi di calcolo sequenziali sono i valori <math>T_a (x)</math> e <math>S_a (x)</math> che rappresentano rispettivamente il tempo e lo spazio di memoria richiesti da un algoritmo <math>a</math> su input <math>x \in X</math>. Per la sopra citata proprietà il dominio <math>X</math> deve dunque coincidere con l'insieme <math>\mathbb{N}</math>. Possiamo pertanto considerare <math>T_a (n)</math> e <math>S_a (n)</math> come funzioni intere positive che rappresentano il ''numero di operazioni'' (non il tempo di esecuzione effettivo) elementari eseguite e dal numero di celle di memoria utilizzate durante l'esecuzione di <math>a</math> sull'istante <math>x</math>.

Descrivere le funzioni <math>T_a (n)</math> e <math>S_a (n)</math> può essere molto complicato poiché la variabile <math>n</math> assume valori sull'insieme di tutti gli input. Una soluzione che fornisce buone informazioni su <math>T_a (n)</math> e <math>S_a (n)</math> consiste nell'introdurre il concetto di dimensione di un'istanza, raggruppando in tal modo gli input che hanno la stessa dimensione: la funzione dimensione associa a ogni ingresso un [[numero naturale]] che rappresenta intuitivamente la quantità di informazione contenuta nel dato considerato. Per esempio la dimensione naturale di un intero positivo <math>k</math> è <math>[1 + log_2{k}]</math>, cioè il numero di cifre necessario per rappresentare <math>k</math> in notazione binaria. Analogamente la dimensione di un vettore di elementi è solitamente costituita dal numero delle sue componenti, mentre la dimensione di un grafo è data congiuntamente dal numero dei suoi nodi e dei suoi archi. La dimensione di <math>n</math> si denota con <math>|n|</math>.

Dato un algoritmo <math>a</math> su un insieme di input <math>I</math>, può accadere che due istanze <math>i</math>, <math>i'</math> di ugual dimensione cioè <math>|i|</math>. = <math>|i'|</math>. diano luogo a tempi diversi di esecuzione per uno stesso algoritmo. Si parla dunque di complessità dell'input e se ne distinguono tre casi:

Riga 147:

sono uguali se <math>\operatorname U</math> si ottiene sostituendo le righe e le colonne di <math>\operatorname A</math> con loro combinazioni lineari e gli elementi di <math>\operatorname c</math> sono combinazioni lineari degli elementi di <math>\operatorname b</math> in base ai coefficienti di <math>\operatorname U</math>.

Il secondo è che per risolvere un sistema triangolare (dove cioè la matrice dei coefficienti gode della proprietà di triangolarità) è sufficiente utilizzare l'algoritmo di sostituzione in avanti o all'indietro (la [[Teoria della complessità computazionale|complessità computazionale]] è <math>O(n)</math>).

Si dimostra che per trasformare il sistema in triangolare occorre un algoritmo la cui complessità è <math>O(n^3)</math>. Applicando a questo sistema l'algoritmo di sostituzione diretta si trovano le soluzioni esatte del sistema, e si dimostra che la complessità totale dell'algoritmo di Gauss è sempre <math>O(n^3)</math>.