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.

9 () 0 k k NP NTime n ∞ = = U . Le classi P e NP sono “robuste” rispetto allo schema di codifica dell’input ed al modello di calcolo utilizzati. Si presume che le due classi P e NP non coincidano, poiché nessuno fino ad oggi è riuscito a dimostrare il contrario. Definizione 1.8 (NP - Completezza) I problemi NP-Completi sono i più “difficili” in NP, e tali che se PNP≠ , allora non appartengono a P. Se si riuscisse a trovare un problema NP-completo appartenente a P, questa sarebbe la dimostrazione di P=NP. Definizione 1.9 (Riduzione polinomiale) Siano A e B due problemi in forma di decisione. AB→ , ovvero A si riduce a B, se per ogni istanza aA∈ esiste un algoritmo polinomiale che trasforma l’istanza a in un’istanza bB∈ tale che se l’istanza b è positiva, allora anche a è positiva. Lo stesso vale se l’istanza b è negativa. Un problema Π si dice NP-Completo se ,QNPQ∀ ∈→Π, dove → è la riduzione polinomiale fra problemi appena definita, cioè Π è almeno tanto difficile quanto tutti i problemi in NP. 1.3.4 Problemi di ottimizzazione Un problema di ottimizzazione è caratterizzato da una quadrupla (I , S , M , goal), dove: 1) I = Insieme delle istanze di input; 2) S = Insieme delle soluzioni ammissibili per le istanze in input; 3) M = Funzione obiettivo che associa ad ogni input x I∈ , e soluzione ammissibile () ySx∈ , un valore ( ) ,mxy N∈ ; 4) Goal = { } min, max . Definizione 1.10 () * Sx è l’insieme delle soluzioni ottime per x, ossia tali che se () ** ySx∈ , allora:

Anteprima della Tesi di Roberto Giovannelli

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

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.