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.

10 () ( ) ( ) { } * ,min,|mxy mxy y Sx=∈; oppure: () ( ) ( ) { } * ,max,|mxy mxy y Sx=∈. Indichiamo con () * mx la misura di una soluzione ottima per x, ossia () ( ) ** ,mx mxy= per qualche () ** ySx∈ . 0sservazione Ad ogni problema di ottimizzazione è associato un problema di decisione soggiacente, definito nel seguente modo: 1) Si introduce nell’istanza di input un valore intero k. 2) Ci si chiede se esiste una soluzione ammissibile, la cui misura è minore o uguale a k se goal=min, oppure maggiore o uguale a k se goal=max. Risolvere un problema di ottimizzazione è difficile almeno quanto risolvere il problema di decisione soggiacente ad esso associato. Infatti, se si possiede un algoritmo efficiente che risolve il problema di ottimizzazione, allora si possiede anche un algoritmo efficiente per il problema di decisione soggiacente, che consiste semplicemente nell’eseguire il primo, e nel chiedersi se la misura della soluzione restituita è minore o uguale a k (min), oppure maggiore o uguale a k (max). Viceversa, se il problema di decisione soggiacente non è risolubile efficientemente, nemmeno il problema di ottimizzazione può esserlo. Definizione 1.11 Definiamo ora le seguenti classi di complessità per problemi di ottimizzazione: PO = Classe dei problemi di ottimizzazione il cui problema di decisione soggiacente appartiene alla classe P. NPO = Classe dei problemi di ottimizzazione il cui problema di decisione soggiacente appartiene alla classe NP. NP-Hard = Classe dei problemi di ottimizzazione il cui problema di decisione soggiacente è NP-completo.

Anteprima della Tesi di Roberto Giovannelli

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

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.