NP compleet

W

waleedcad

Guest
Dear all:
Kan iemand mij een eenvoudige definitie voor (P, NP-compleet).

Waleed

 
Ik denk dat je vragen met betrekking tot elektronica

Voor PN Junction --
http://www.acsu.buffalo.edu/ ~ wie / applet / pnformation / pnformation.html
http://hyperphysics.phy-astr.gsu.edu/hbase/solids/pnjun.html
http://www.play-hookey.com/semiconductors/pn_junction.html

zoekopdracht op Google met "PN knooppunt" voor meer

PNP of NPN
http://www.st-andrews.ac.uk/ ~ www_pa/Scots_Guide/info/comp/active/BiPolar/page1.html

zoek op google met "bipolaire transistor" voor meer

 
Nee, ik vraag over het type van algoritmen (P, NP-compleet)

 
Hi Waleed ...

Een eenvoudige definitie minded zou zijn als dit:

Eerste wat NP staat voor: Niet-deterministische Polynoom dat is een generieke term in de manier waarop de huidige dag Turing machine computers oplossen van een bepaald probleem.

en NP compleet is een probleem dat is bewezen dat het niet kan worden opgelost met behulp van hedendaagse computers.Dit betekent dat huidige computers kan jaren duren of in sommige gevallen (afhankelijk van de input-nummers), nooit.
een voorbeeld is de reizende Saleman probleem (groot aantal van bestemming) "

Een iets andere klasse van problemen zijn NP-hard problemen.Dit zijn problemen waarvoor geen algoritme is gevonden.Maar ook zij niet bewezen als onoplosbaar.

P volledig is precies het tegenovergestelde, een probleem bleek oplosbaar en een algoritme bestaat ...

hope u got it ....voor meer informatie kunt u kijken naar boeken als "Inleiding tot de berekening" van Michael Sipser ...."Introduction to Automata Theory, Languages, and Computation" door Hopcroft-Ullman (Addison-Wesley) ..

een meer specifieke boek over NP-compleetheid wud b "Computers en weerbarstigheid: Een gids voor NP-Volledigheid" door Garey en Johnson ....dit boek heeft vele mooie voorbeelden ...

Rgds

 
Eigenlijk ..

NP-complete problemen zijn die problemen die niet kunnen worden opgelost in polynomiale tijd, die ze nodig hebben exponentieel.

NP hard problemen zijn problemen die geen polynomiale algoritme is nog niet gevonden

P gaat voor problemen opgelost in polynomiale tijd ...

Voor de NP problemen die we hebben exacte algoritmen (dagen of jaren) en heuristische algoritmes voor bijna-optimale oplossingen in microseconden (focus: ze zijn niet optima)

Manieren van programmering

Lineair Programmeren
Integer Programming
Dynamische programmering
Kwadratische

Gemengde soorten

Ga naar google en schrijf Traveling Salesman probleem en start vanaf daar ...

Sommige boeken

Vašek Chvatal: Lineair Programmeren
Lawler ..: Traveling Salesman Problem
Dimitris Bertsekas: Dynamische Programmering en optimale controle

hoop ik heb geholpen

 
Nou ...een Turing M / C is een denkbeeldige M / C die kan berekenen op basis van bepaalde stappen.Alle computers van vandaag draaien op het principe van de Turing M / C wiens idee was bedacht door de beroemde Britse wiskundige Alan Turing in de jaren 1930.

Turing probeerde te bewijzen wat een computer kan oplossen.In het algemeen als een probleem niet oplosbaar door Turing m / c, kan niet worden opgelost door computers van vandaag en dus geworden NP-complete problemen.(wat ik bedoel is dat door het oplossen van een algoritme lopen in polynomiale tijd te vinden)

In eenvoudige termen Turing machine, heeft een tape van oneindige onderverdeeld in cellen.Een header gehecht alongwith kan lezen, schrijven, naar links / rechts.Turing bewees met deze eenvoudige machine en een combinatie van deze machine, bleek hij de mogelijkheden en tekortkomingen van een computer (die nog moest worden gebouwd tijdens zijn times)

U kunt Google te vinden meer abt hen ...Rgds

 
iedereen bedanken, maar iemand heeft een beeld van Turing m / c?

 
google ..u'll krijgen een aantal beelden

<img src="http://www.edaboard.com/images/smiles/icon_smile.gif" alt="Lachten" border="0" />Rgds

 
You must log in or register to reply here.

Welcome to EDABoard.com

Sponsor

Back
Top