Logo
Unionpedia
Communicatie
Ontdek het op Google Play
Nieuw! Download Unionpedia op je Android™ toestel!
Gratis
Snellere toegang dan browser!
 

Beslissingsprobleem

Index Beslissingsprobleem

In de berekenbaarheids- en complexiteitstheorie is een beslissingsprobleem een computationeel probleem dat, afhankelijk van de gegeven invoer, met 'ja' of 'nee' beantwoord dient te worden.

16 relaties: Algoritme, Berekenbaarheid, Binair talstelsel, Computationele complexiteitstheorie, Contextvrije taal, Decimaal talstelsel, Eindigetoestandsautomaat, Entscheidungsproblem, Formele grammatica, Formele taal, Indicatorfunctie, NP-volledig, Priemgetal, Stopprobleem, Turingmachine, Vervulbaarheidsprobleem.

Algoritme

Algoritme om een willekeurig veelvlak in driehoeken op te delen (in het algemeen heeft dit probleem meerdere oplossingen, de bereikte oplossing hangt dus af van het gebruikte algoritme) Een algoritme is een stappenplan bestaande uit een set regels in vaste volgorde om tot een oplossing te komen en het einddoel te bereiken.

Nieuw!!: Beslissingsprobleem en Algoritme · Bekijk meer »

Berekenbaarheid

In de complexiteitstheorie is berekenbaarheid een eigenschap van functies.

Nieuw!!: Beslissingsprobleem en Berekenbaarheid · Bekijk meer »

Binair talstelsel

Het binaire talstelsel of tweetallig talstelsel is een positiestelsel, waarin een getal wordt voorgesteld door een rijtje van de cijfers 0 en 1.

Nieuw!!: Beslissingsprobleem en Binair talstelsel · Bekijk meer »

Computationele complexiteitstheorie

Computationele complexiteitstheorie is een tak van theoretische informatica en wiskunde die als doel heeft computationele problemen te classificeren in een aantal categorieën die de inherente moeilijkheidsgraad van deze problemen aangeven.

Nieuw!!: Beslissingsprobleem en Computationele complexiteitstheorie · Bekijk meer »

Contextvrije taal

In de theoretische informatica is een contextvrije taal een formele taal die door een contextvrije grammatica gegenereerd wordt.

Nieuw!!: Beslissingsprobleem en Contextvrije taal · Bekijk meer »

Decimaal talstelsel

Het decimale talstelsel of tientallige talstelsel is een talstelsel om getallen weer te geven met behulp van de tien cijfers 0 tot en met 9.

Nieuw!!: Beslissingsprobleem en Decimaal talstelsel · Bekijk meer »

Eindigetoestandsautomaat

Een deterministische eindige automaat Een eindigetoestandsautomaat (in het Engels: finite-state automaton, veelal afgekort tot FA, of finite-state machine, afgekort tot FSM) is een abstract, wiskundig model voor het gedrag van een systeem waarbij het model bestaat uit een eindig aantal toestanden, overgangen tussen die toestanden en acties.

Nieuw!!: Beslissingsprobleem en Eindigetoestandsautomaat · Bekijk meer »

Entscheidungsproblem

In de wiskunde en informatica is het zogeheten Entscheidungsproblem (Duits voor 'beslissingsprobleem') een uitdaging van David Hilbert in 1928.

Nieuw!!: Beslissingsprobleem en Entscheidungsproblem · Bekijk meer »

Formele grammatica

Een formele grammatica is in de informatica en theoretische taalkunde een beschrijving van een formele taal, een verzameling strings (in deze context ook zinnen genoemd) in een bepaald alfabet.

Nieuw!!: Beslissingsprobleem en Formele grammatica · Bekijk meer »

Formele taal

De term formele taal heeft ten minste drie verwante betekenissen.

Nieuw!!: Beslissingsprobleem en Formele taal · Bekijk meer »

Indicatorfunctie

0 Grafiek van de indicatorfunctie van een tweedimensionale deelverzameling van een vierkant In de verzamelingenleer, een deelgebied van de wiskunde, is de indicatorfunctie van een deelverzameling, een functie die aangeeft welke elementen tot de deelverzameling behoren en welke niet.

Nieuw!!: Beslissingsprobleem en Indicatorfunctie · Bekijk meer »

NP-volledig

NP-volledigheid is een concept uit de complexiteitstheorie.

Nieuw!!: Beslissingsprobleem en NP-volledig · Bekijk meer »

Priemgetal

Een priemgetal is een natuurlijk getal groter dan 1 dat slechts twee natuurlijke getallen als deler heeft, namelijk 1 en zichzelf.

Nieuw!!: Beslissingsprobleem en Priemgetal · Bekijk meer »

Stopprobleem

Het stopprobleem, ook bekend als het 'halting problem', is het beslissingsprobleem uit de wiskunde en informatica, om te bepalen of een algoritme bij een eindige invoer in een eindig aantal stappen eindigt of dat het eindeloos blijft doorgaan.

Nieuw!!: Beslissingsprobleem en Stopprobleem · Bekijk meer »

Turingmachine

In de informatica is de turingmachine een model van berekening en berekenbaarheid, ontwikkeld door de wiskundige Alan M. Turing in zijn beroemde artikel On computable numbers, with an application to the Entscheidungsproblem uit 1936-37.

Nieuw!!: Beslissingsprobleem en Turingmachine · Bekijk meer »

Vervulbaarheidsprobleem

In de complexiteitstheorie verwijst het vervulbaarheidsprobleem (ook bekend als SAT, van het Engelse satisfiability) naar het bepalen of een logische propositie vervuld kan worden; een propositie kan vervuld worden als er een toekenning van waar of onwaar aan de atomaire formules bestaat zodanig dat de gehele propositie waar is.

Nieuw!!: Beslissingsprobleem en Vervulbaarheidsprobleem · Bekijk meer »

UitgaandeInkomende
Hey! We zijn op Facebook nu! »