Questo sito utilizza cookie di terze parti per inviarti pubblicità in linea con le tue preferenze. Se vuoi saperne di più clicca QUI 
Chiudendo questo banner, scorrendo questa pagina, cliccando su un link o proseguendo la navigazione in altra maniera, acconsenti all'uso dei cookie. OK

Analisi e sperimentazione di algoritmi di scheduling bicriterio

L'anteprima di questa tesi è scaricabile in PDF gratuitamente.
Per scaricare il file PDF è necessario essere iscritto a Tesionline.
L'iscrizione non comporta alcun costo. Mostra/Nascondi contenuto.

6 La complessità di un problema è di solito espressa come funzione della dimensione dell’input, intesa come grandezza correlata in modo polinomiale alla lunghezza di una qualsiasi codifica naturale dell’input che sia semplice e concisa (senza ridondanze), con numeri in base maggiore o uguale a 2. Definiamo ora la nozione di complessità di un algoritmo. Definizione 1.1 Sia () A tx il tempo di esecuzione di un algoritmo A per un input x. Il tempo di esecuzione di A nel caso peggiore è: ( ) ( ) { } max | AA tn tx x n= ≤ . Quindi, un algoritmo A ha complessità: • () ( Ogn se () ( ) ( ) { } 00 (): , 0 () (), A tn Ogn fn cntaliche fn cgn nn==∃ ≤≤⋅∀≥; • () ( gnΩ se () ( ) ( ) { } (): , 0 () (), A t n g n f n c n tali che c g n f n n n=Ω = ∃ ≤ ⋅ ≤ ∀ ≥ ; • () ( gnΘ se () ( ) ( ) A tn gn=Θ cioè ( ) ( ) ( ) A tn Ogn= e ( )() ( A tn gn=Ω . Definiamo ora la nozione di complessità di un problema. Definizione 1.2 Un problema Π ha complessità: • () ( Ogn se esiste un algoritmo A che lo risolve, avente complessità ( ) ( Ogn ; • () ( gnΩ se ogni algoritmo A che lo risolve, ha complessità () ( gnΩ ; • () ( gnΘ se Π ha complessità ( ) ( ) gnΩ e ( ) ( ) Ogn .

Anteprima della Tesi di Roberto Giovannelli

Anteprima della tesi: Analisi e sperimentazione di algoritmi di scheduling bicriterio, Pagina 6

Tesi di Laurea

Facoltà: Scienze Matematiche, Fisiche e Naturali

Autore: Roberto Giovannelli Contatta »

Composta da 115 pagine.

 

Questa tesi ha raggiunto 1376 click dal 20/03/2004.

Disponibile in PDF, la consultazione è esclusivamente in formato digitale.