Vai ai contenuti. | Spostati sulla navigazione | Spostati sulla ricerca | Vai al menu | Contatti | Accessibilità

logo del sistema bibliotecario dell'ateneo di padova

Santinello, Chiara (2017) Approssimazione del taglio massimo in un grafo. [Laurea triennale]

Per questo documento il full-text online non disponibile.

Abstract

La categoria di problemi decisionali, cioe' problemi le cui soluzioni consistono o nella risposta s o nella risposta no, contiene l'importante classe NP1. Ci si interroga sulla possibilita' di trovare algoritmi polinomiali (i piu' graditi) per la risoluzione di tutti i problemi appartenenti alla classe NP, nonostante sia opinione condivisa, ma non dimostrata, che tali algoritmi non esistano. Nelle prossime poche pagine, si presentera' un problema appartenente a questo incerto insieme, il MAX CUT, e verra' esposto un algoritmo d'approssimazione per risolverlo.

Item Type:Laurea triennale
Corsi di Laurea Triennale:Scuola di Scienze > Matematica
Subjects:Area 01 - Scienze matematiche e informatiche > MAT/09 Ricerca operativa
Codice ID:56548
Relatore:Di Summa, Marco
Data della tesi:22 September 2017
Biblioteca:Polo di Scienze > Biblioteca di Matematica

Solo per lo Staff dell Archivio: Modifica questo record