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

Metaeuristiche per la costruzione degli orari dei corsi universitari

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.

Capitolo 1. Denizione del problema 10Denizione 1.2 LaclasseNP è la classe dei problemi di decisione che pos-sono essere risolti da un algoritmo non-deterministico in tempopolinomiale.Un problema di decisione che può essere risolto da un algoritmo determi-nistico in tempo polinomiale può essere risolto anche da un algoritmo non-deterministico in tempo polinomiale: pertanto, P  NP. Probabilmenteuna delle più importanti questioni aperte in informatica teorica è decidere seP =NP. È largamente diusa l'opinione che P 6=NP, nonostante non siastata fornita ancora alcuna provaperquesta congettura.Poiché non è possibile mostrare che NPnP è non vuoto, a meno che siafornita una prova per P 6= NP, la teoria della NP-completezza forniscerisultati in una forma debole, sotto l'ipotesi di P 6=NP.Denizione 1.3 Un problema  è riducibile in tempo polinomiale al proble-ma 0, se esiste un algoritmo che trasforma ogni istanza di  in un'istanza di0 in tempo polinomiale e che, per ogni istanza di , risponde a tale istanzasi se e solo se la risposta della corrispondente istanza di 0 è si.In modo informale questa denizione dice che se  può essere ridotto a0 in tempo polinomiale, allora il problema 0 è almeno altrettanto di-cile da risolvere quanto il problema . Usando la nozione di riducibilitàin tempo polinomiale possiamo procedere a denire la classe dei problemiNP-completi.Denizione 1.4 Un problema  è NP-completo se e solo se  2NPe 80 2NP vale che 0 è riducibile in tempo polinomiale a .La classe dei problemiNP-completi è in un certo senso la classe dei problemipiù dicili appartenenti a NP. Se un problema NP-completo può essererisolto da un algoritmo in tempo polinomiale, allora tutti i problemi in NP

Anteprima della Tesi di Max Manfrin

Anteprima della tesi: Metaeuristiche per la costruzione degli orari dei corsi universitari, Pagina 10

Tesi di Laurea

Facoltà: Scienze Matematiche, Fisiche e Naturali

Autore: Max Manfrin Contatta »

Composta da 181 pagine.

 

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

Disponibile solo in CD-ROM.