Inhoudsopgave
25 relaties: AKS-test, Chinees postbodeprobleem, Chordale graaf, Clique (grafentheorie), Computationele leertheorie, Conjunctieve normaalvorm, Disjunctieve normaalvorm, Goppa-code, Kantenbedekking, Knapzakprobleem, Koppeling (grafentheorie), Maximale snede, Minor (grafentheorie), NP (complexiteitsklasse), NP-volledig, Onafhankelijke verzameling, P (complexiteitsklasse), Perfecte graaf, Priemgetal, Priemgetaltest, Pseudotoevalsgenerator, RSA (cryptografie), Steinerboomprobleem, Stephen Cook, Vervulbaarheidsprobleem.
AKS-test
De AKS-test is een priemgetaltest; een methode om te controleren of een getal een samengesteld getal of een priemgetal is.
Bekijken Polynomiale tijd en AKS-test
Chinees postbodeprobleem
Voorbeeld Het Chinese postbodeprobleem is een veelgebruikte metafoor om een bekende probleemstelling in de grafentheorie duidelijk te maken.
Bekijken Polynomiale tijd en Chinees postbodeprobleem
Chordale graaf
koorde Dit deel van een graaf is chordaal omdat de cykel twee koorden heeft. Beide koorden zijn nodig, als er een zou ontbreken zou er een cykel van lengte vier bestaan zonder koorde. Een graaf G is chordaal als voor iedere cykel C van lengte vier of meer in G er een koorde bestaat.
Bekijken Polynomiale tijd en Chordale graaf
Clique (grafentheorie)
in rood: een clique van 3 knopen In de grafentheorie is een clique of kliek een deelverzameling van de knopen van een niet-gerichte enkelvoudige graaf, waarvan de geïnduceerde deelgraaf volledig is.
Bekijken Polynomiale tijd en Clique (grafentheorie)
Computationele leertheorie
De computationele leertheorie is een onderdeel van de theoretische informatica waarin algoritmes die gebruikt worden in het machinaal leren worden geanalyseerd.
Bekijken Polynomiale tijd en Computationele leertheorie
Conjunctieve normaalvorm
In de logica is een formule in conjunctieve normaalvorm (Eng. conjunctive normal form, CNF, ook wel afgekort als CNV) als die bestaat uit een conjunctie van disjuncties met literalen (ook een conjunctie van clausules genoemd).
Bekijken Polynomiale tijd en Conjunctieve normaalvorm
Disjunctieve normaalvorm
In de logica is een formule in disjunctieve normaalvorm (Engels: disjunctive normal form, DNF) als die bestaat uit een disjunctie van conjuncties van literalen.
Bekijken Polynomiale tijd en Disjunctieve normaalvorm
Goppa-code
Een binaire goppa-code, doorgaans alleen goppa-code genoemd, is een foutcorrigerende code.
Bekijken Polynomiale tijd en Goppa-code
Kantenbedekking
In de grafentheorie is een kantenbedekking (ook wel bogenbedekking, bogenoverdekking en kantenoverdekking) (Engels: edge cover) van een graaf G een deelverzameling C van de kanten uit de graaf waarvoor geldt dat elke knoop van G het begin- of eindpunt is van minstens een kant uit de verzameling C. Men zegt dan dat C de knopen van G bedekt.
Bekijken Polynomiale tijd en Kantenbedekking
Knapzakprobleem
Voorbeeld van een knapzakprobleem. Het knapzakprobleem is een NP-volledig probleem in de wiskunde, informatica en cryptografie.
Bekijken Polynomiale tijd en Knapzakprobleem
Koppeling (grafentheorie)
Als G.
Bekijken Polynomiale tijd en Koppeling (grafentheorie)
Maximale snede
Maximale snede doorheen deze graaf. De grootte van de snede is 5. In de grafentheorie is een maximale snede een snede met maximale grootte of gewicht.
Bekijken Polynomiale tijd en Maximale snede
Minor (grafentheorie)
In de grafentheorie, een onderdeel van de wiskunde, is een minor van een graaf G een graaf die uit G kan worden voortgebracht door knopen te verwijderen, zijden te verwijderen, of zijden samen te trekken.
Bekijken Polynomiale tijd en Minor (grafentheorie)
NP (complexiteitsklasse)
Overzicht van P, NP en NP-volledig, mits P ongelijk is aan NP. NP, de aanduiding voor niet-deterministisch polynomiaal, is een complexiteitsklasse die alle beslissingsproblemen bevat die oplosbaar zijn in polynomiale tijd door een niet-deterministische turingmachine.
Bekijken Polynomiale tijd en NP (complexiteitsklasse)
NP-volledig
NP-volledigheid is een concept uit de complexiteitstheorie.
Bekijken Polynomiale tijd en NP-volledig
Onafhankelijke verzameling
In deze graaf vormen de blauwe knopen een grootste onafhankelijke verzameling. In de grafentheorie verstaat men onder onafhankelijke verzameling of stabiele verzameling (independent set in het Engels) van een graaf, een deelverzameling van de knopen van die graaf die twee aan twee niet verbonden zijn door een zijde.
Bekijken Polynomiale tijd en Onafhankelijke verzameling
P (complexiteitsklasse)
Verbanden tussen complexiteitsklassen. In de complexiteitstheorie is P, ook bekend als PTIME en DTIME(nO(1)), een complexiteitsklasse die alle beslissingsproblemen bevat die in polynomiale tijd opgelost kunnen worden door een deterministische turingmachine.
Bekijken Polynomiale tijd en P (complexiteitsklasse)
Perfecte graaf
Voorbeeld van een perfecte graaf. In vet is een geïnduceerde subgraaf aangeduid met drie knopen. Het is een clique met chromatisch getal 3. Voor elke subgraaf van deze graaf is het cliquegetal gelijk aan het chromatisch getal. Een perfecte graaf is een graaf waarvan voor elke geïnduceerde subgraaf geldt dat het cliquegetal gelijk is aan het chromatisch getal van die subgraaf.
Bekijken Polynomiale tijd en Perfecte graaf
Priemgetal
Een priemgetal is een natuurlijk getal groter dan 1 dat slechts twee natuurlijke getallen als deler heeft, namelijk 1 en zichzelf.
Bekijken Polynomiale tijd en Priemgetal
Priemgetaltest
Een priemgetaltest is een algoritme dat bepaalt of een gegeven getal al dan niet priem is.
Bekijken Polynomiale tijd en Priemgetaltest
Pseudotoevalsgenerator
Een pseudotoevalsgenerator, (Engels: pseudorandom number generator (PRNG)), is een algoritme voor het genereren van pseudotoevalsgetallen, dat wil zeggen een opeenvolging van ogenschijnlijk willekeurige getallen zonder enige samenhang.
Bekijken Polynomiale tijd en Pseudotoevalsgenerator
RSA (cryptografie)
RSA is een asymmetrisch encryptiealgoritme, dat veel gebruikt wordt bij gegevensoverdracht, bijvoorbeeld voor de beveiliging van transacties.
Bekijken Polynomiale tijd en RSA (cryptografie)
Steinerboomprobleem
Voorbeeld: de Steinerboom voor drie punten A, B en C wordt bekomen met één Steinerpunt S, dat het punt van Fermat is van de driehoek ABC. De Steinerboom voor vier punten A, B, C en D. Er zijn twee Steinerpunten gebruikt. Het (minimale) Steinerboomprobleem is een wiskundig probleem uit de grafentheorie.
Bekijken Polynomiale tijd en Steinerboomprobleem
Stephen Cook
Stephen Andrew Cook (Buffalo, 14 december 1939) is een Amerikaans theoretisch informaticus en hoogleraar aan de Universiteit van Toronto.
Bekijken Polynomiale tijd en Stephen Cook
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.
Bekijken Polynomiale tijd en Vervulbaarheidsprobleem