l'accesso più veloce di browser!
21 relazioni: Algoritmo di approssimazione, Cardinalità, Classi di complessità P e NP, Glossario di teoria dei grafi, Grafo, Grafo bipartito, Grafo duale, Grafo planare, Inclusione, Informatica teorica, Insieme complemento, NP (complessità), NP-completo, NP-difficile, Problema decisionale, Problema del postino cinese, Problema di ottimizzazione, Schema di approssimazione in tempo polinomiale, Taglio (teoria dei grafi), Valore atteso, 21 problemi NP-completi di Karp.
Algoritmo di approssimazione
Nell'informatica e nella ricerca operativa, un algoritmo di approssimazione è un algoritmo usato per trovare soluzioni approssimate a problemi di ottimizzazione.
Nuovo!!: Taglio massimo e Algoritmo di approssimazione · Mostra di più »
Cardinalità
In teoria degli insiemi per cardinalità (o numerosità o potenza) di un insieme finito si intende il numero dei suoi elementi.
Nuovo!!: Taglio massimo e Cardinalità · Mostra di più »
Classi di complessità P e NP
Il problema delle classi P e NP è un problema tuttora aperto nella teoria della complessità computazionale.
Nuovo!!: Taglio massimo e Classi di complessità P e NP · Mostra di più »
Glossario di teoria dei grafi
Un grafo G è una coppia (V, E) dove V è un insieme e E ⊆ V × V è un sottoinsieme del prodotto cartesiano di V per se stesso.
Nuovo!!: Taglio massimo e Glossario di teoria dei grafi · Mostra di più »
Grafo
Grafo (non orientato) con 6 nodi e 5 archi I grafi sono strutture matematiche discrete che rivestono interesse sia per la matematica che per un'ampia gamma di campi applicativi.
Nuovo!!: Taglio massimo e Grafo · Mostra di più »
Grafo bipartito
Nella teoria dei grafi, un grafo bipartito è un grafo tale che l'insieme dei suoi vertici si può partizionare in due sottoinsiemi tali che ogni vertice di una di queste due parti è collegato solo a vertici dell'altra.
Nuovo!!: Taglio massimo e Grafo bipartito · Mostra di più »
Grafo duale
Nella teoria dei grafi il grafo duale di un grafo planare (o in generale di un grafo raffigurato su una varietà) G è un nuovo grafo G′ che ha un nodo per ogni regione di G ed un arco per ogni arco di G (due nodi di G′ sono connessi da un arco se e solo se le due corrispondenti regioni di G sono separate da un arco).
Nuovo!!: Taglio massimo e Grafo duale · Mostra di più »
Grafo planare
Nella teoria dei grafi si definisce grafo planare un grafo che può essere raffigurato in un piano in modo che non si abbiano archi che si intersecano.
Nuovo!!: Taglio massimo e Grafo planare · Mostra di più »
Inclusione
In matematica, e in particolare in teoria degli insiemi, l'inclusione, indicata con \subseteq, è una relazione binaria tra insiemi definita nel seguente modo: "l'insieme B è contenuto o incluso nell'insieme A se e solo se, per ogni elemento x, se x appartiene a B allora x appartiene ad A".
Nuovo!!: Taglio massimo e Inclusione · Mostra di più »
Informatica teorica
L'informatica teorica è una branca dell'informatica che riguarda gli aspetti più astratti e matematici della computazione, come la teoria della computazione, la semantica della programmazione e la teoria della complessità computazionale.
Nuovo!!: Taglio massimo e Informatica teorica · Mostra di più »
Insieme complemento
Nella teoria degli insiemi e in altri campi della matematica, esistono due tipi di insieme complemento: il complemento relativo (detto anche insieme differenza) e il complemento assoluto.
Nuovo!!: Taglio massimo e Insieme complemento · Mostra di più »
NP (complessità)
La classe di problemi NP comprende tutti quei problemi decisionali che, per trovare una soluzione su una macchina di Turing non deterministica, impiegano un tempo polinomiale.
Nuovo!!: Taglio massimo e NP (complessità) · Mostra di più »
NP-completo
Nella teoria della complessità computazionale i problemi NP-completi sono i più difficili problemi nella classe NP ("problemi non deterministici in tempo polinomiale") nel senso che, se si trovasse un algoritmo in grado di risolvere "velocemente" (nel senso di utilizzare tempo polinomiale) un qualsiasi problema NP-completo, allora si potrebbe usarlo per risolvere "velocemente" ogni problema in NP.
Nuovo!!: Taglio massimo e NP-completo · Mostra di più »
NP-difficile
In teoria della complessità, i problemi NP-difficili o NP-ardui (in inglese NP-hard, da nondetermistic polynomial-time hard problem, "problema difficile non deterministico in tempo polinomiale") sono una classe di problemi che può essere definita informalmente come la classe dei problemi almeno difficili come i più difficili problemi delle classi di complessità P e NP.
Nuovo!!: Taglio massimo e NP-difficile · Mostra di più »
Problema decisionale
Un problema decisionale nell'ambito della matematica riguarda un problema di scelta in cui si deve prendere una decisione tra un elevato numero di soluzioni (ammissibili) alternative, sulla base di uno o più criteri.
Nuovo!!: Taglio massimo e Problema decisionale · Mostra di più »
Problema del postino cinese
Il problema del postino cinese è un problema della teoria dei grafi formulato dal matematico cinese Mei-Ku Kwan (o Kuan) nel 1962.
Nuovo!!: Taglio massimo e Problema del postino cinese · Mostra di più »
Problema di ottimizzazione
In matematica e in informatica, un problema di ottimizzazione è il problema di trovare la migliore soluzione fra tutte le soluzioni fattibili.
Nuovo!!: Taglio massimo e Problema di ottimizzazione · Mostra di più »
Schema di approssimazione in tempo polinomiale
In informatica, uno schema di approssimazione in tempo polinomiale (in inglese polynomial-time approximation scheme o PTAS) è un tipo di algoritmo di approssimazione per problemi di ottimizzazione (molto spesso, problemi di ottimizzazione NP-difficili).
Nuovo!!: Taglio massimo e Schema di approssimazione in tempo polinomiale · Mostra di più »
Taglio (teoria dei grafi)
Nella teoria dei grafi, un taglio è una partizione dei vertici di un grafo in due sottoinsiemi disgiunti.
Nuovo!!: Taglio massimo e Taglio (teoria dei grafi) · Mostra di più »
Valore atteso
In teoria della probabilità il valore atteso (chiamato anche media, speranza o speranza matematica) di una variabile casuale X, è un numero indicato con \mathbb (da expected value o expectation in inglese o dal francese espérance) che formalizza l'idea euristica di valore medio di un fenomeno aleatorio.
Nuovo!!: Taglio massimo e Valore atteso · Mostra di più »
21 problemi NP-completi di Karp
Nella teoria della complessità computazionale, i 21 problemi NP-completi di Karp sono un insieme di problemi computazionali che si presentano NP-completi.
Nuovo!!: Taglio massimo e 21 problemi NP-completi di Karp · Mostra di più »
Riorienta qui:
Max-cut, Problema del taglio massimo.
