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.

8 Definizione 1.5 Un algoritmo non deterministico A risolve Π se e solo se esiste una struttura y tale per cui A risponde 1 se e solo se x Y∈ . Osservazioni 1) Un algoritmo deterministico è meno potente perché non esegue la fase 1. 2) Dato un qualsiasi algoritmo deterministico A che risolve Π , esiste un algoritmo non deterministico, avente la stessa complessità, che risolve Π nel seguente modo: Esegue la fase 1, e coincide con A nella fase 2, ignorando la struttura y. Un algoritmo non deterministico può essere definito come una procedura che, per le istanze con risposta affermativa o positive, verifica in tempo polinomiale se tale risposta è effettivamente affermativa. 1.3.3 Classi di complessità Definiamo ora le più importanti classi di complessità. Sia () ( Time f n la classe dei problemi di decisione risolubili in tempo ( ) ( ) Ofn da algoritmi deterministici. Sia inoltre () ( NTime f n la classe dei problemi di decisione risolubili in tempo ( ) ( Ofn da algoritmi non deterministici. Definizione 1.6 (Classe P) La classe P, è la classe di tutti i problemi di decisione risolubili in tempo polinomiale deterministicamente, ossia: () 0 k k PTimen ∞ = = U . Definizione 1.7 (Classe NP) La classe NP, è la classe di tutti i problemi di decisione risolubili in tempo polinomiale non deterministicamente, ossia:

Anteprima della Tesi di Roberto Giovannelli

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

Tesi di Laurea

Facoltà: Scienze Matematiche, Fisiche e Naturali

Autore: Roberto Giovannelli Contatta »

Composta da 115 pagine.

 

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

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