Wiskunde Quiz: Grafentheorie en Reguliere Talen

Podcast Beta

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Als f en g asymptotisch equivalent zijn, dan...

is f + g asymptotisch equivalent

is f dan O(g)

is g dan O(f) (correct)

zijn f en g twee verschillende functies

Een partieel geordende verzameling met een gesloten interval [a, b] als verzameling, is een complete tralie als...

de verzameling een deel van R is

de verzameling een deel van Z is (correct)

de verzameling een deel van Q is

de verzameling een deel van N is

Een graaf heeft een Euleriaanse kring als en slechts als...

de graaf een euleriaans pad heeft

de graaf samenhangend is en hoogstens 2 knopen een oneven graad hebben

de graaf samenhangend is en elke knoop een even graad heeft (correct)

de graaf een complete graaf is

Twee enkelvoudige grafen zijn isomorf als en slechts als...

er een ordening van de knopen bestaat zodat hun buurmatrix gelijk is Signup and view all the answers

Als P != NP, dan zijn er talen die...

in polynomiale tijd door een NDTM beslist worden maar waarvoor geen DTM bestaat die de taal in polynomiale tijd beslist Signup and view all the answers

Het aantal knopen met oneven graad in een graaf is...

altijd even Signup and view all the answers

Een graaf heeft een Euleriaans pad als en slechts als...

de graaf samenhangend is en hoogstens 2 knopen een oneven graad hebben Signup and view all the answers

De som van de graden van alle knopen in een graaf is...

altijd even Signup and view all the answers

Wat is de complexiteit van het algoritme van Dijkstra?

$O(n^3)$ Signup and view all the answers

Welke van de volgende grafen heeft een euleriaanse kring?

Een samenhangende vlakke graaf Signup and view all the answers

Wat is een eigenschap van tweeledige grafen?

Ze hebben een tweekleuring Signup and view all the answers

Wat is een noodzakelijke voorwaarde voor een opspannende boom?

De graaf moet samenhangend zijn Signup and view all the answers

Welke van de volgende stellingen is waar?

Elke niet-vlakke graaf heeft een kring Signup and view all the answers

Wat is een eigenschap van reguliere talen?

Ze zijn steeds recursief Signup and view all the answers

Wat is de tijdcomplexiteit van het algoritme van Prim?

Lineair in het aantal bogen Signup and view all the answers

Wat is een gevolg van de stelling van Kuratowski?

Elke graaf zonder subgraaf isomorf met K5 of K3,3 is vlak Signup and view all the answers

Een boom met hoeveel knopen heeft steeds hoeveel bogen?

n-1 Signup and view all the answers

Wat is een eigenschap van elke samenhangende graaf?

Er is precies 1 opspannende boom Signup and view all the answers

Wat is een eigenschap van het algoritme van Kruskal en het algoritme van Prim?

Ze zijn twee verschillende manieren om hetzelfde probleem op te lossen Signup and view all the answers

Wat is een eigenschap van elke boom?

Elke boom heeft een twee-kleuring Signup and view all the answers

Wat is een eigenschap van elke reguliere taal?

Elke eindige taal is regulier Signup and view all the answers

Wat is een eigenschap van elke reguliere taal L?

als x en y een element zijn van L, dan is xy ook een element van L Signup and view all the answers

Wat is een eigenschap van de verzameling van {(ab)^n | n element van de natuurlijke getallen}?

Het is een reguliere taal Signup and view all the answers

Wat is een eigenschap van de klasse van talen herkend door eindige toestandautomaten?

Het is dezelfde als de klasse herkend door niet-deterministische eindige automaten Signup and view all the answers

Welke uitspraak over reguliere talen is waar?

Eindige talen zijn regulier Signup and view all the answers

Wat is een eigenschap van een reguliere taal?

De concatenatie van twee reguliere talen is een reguliere taal Signup and view all the answers

Wat is een relatie tussen een niet-deterministische eindige automaat en een deterministische eindige automaat?

Voor elke niet-deterministische eindige automaat is er ook een deterministische eindige automaat die dezelfde taal herkent Signup and view all the answers

Wat is een eigenschap van een string x ten opzichte van een automaat?

Als er voor een bepaalde string x een pad is van de begintoestand naar een aanvaardbare eindtoestand, dan wordt x aanvaard Signup and view all the answers

Wat is een uitspraak over niet-deterministische eindige automaten?

Er bestaan niet-deterministische eindige automaten zonder »-pijlen en zonder meer-dere pijlen vanuit dezelfde toestand met hetzelfde label, die toch geen deterministische eindige automaten zijn Signup and view all the answers

Wat is een uitspraak over Turingmachines?

Er bestaan oneindig veel Turingmachines Signup and view all the answers

Welke relatie tussen twee functies f en g is waar?

f is O(g) Ò f is O(g + h) Signup and view all the answers

Welke relatie tussen twee functies f en g is waar?

f is O(n^2) en g is ook O(n^2) Ò f g is O(n^4) Signup and view all the answers

Wanneer zijn twee grafen G en G' isomorf?

Wanneer er een ordening van de knopen en bogen bestaat waarvoor de incidentiematrices van G en G' gelijk zijn Signup and view all the answers

Een enkelvoudige graaf G(V,E) is tweeledig als:

V kan opgedeeld worden in twee deelverzamelingen V1 en V2, zo dat er enkel bogen bestaan tussen V1 en V2 Signup and view all the answers

Wat is een eigenschap van het aantal turing machines met n toestanden en m symbolen?

Het is eindig op naamgeving na Signup and view all the answers

Wat is een eigenschap van reguliere talen op een gegeven alfabet £?

De klasse van de reguliere talen op £ valt samen met de klasse van de reguliere verzamelingen Signup and view all the answers

Wat is een eigenschap van een reguliere taal L?

Er bestaat een n, zo dat, voor elke string s element van L met |s| >= n, het volgende geldt: er bestaan strings x, y, z zo dat s = xyz met |y| > 0 Signup and view all the answers

Wat is een eigenschap van een tweeledige graaf G(V,E)?

V kan opgedeeld worden in twee deelverzamelingen V1 en V2, zo dat er enkel bogen bestaan tussen V1 en V2 Signup and view all the answers

Study Notes

Grafentheorie

Een boom met n knopen heeft steeds n-1 bogen.
Elke samenhangende graaf heeft precies 1 opspannende boom.
Een graaf met een euleriaanse kring heeft nooit knopen met oneven graad.
Elke samenhangende vlakke graaf heeft een euleriaanse kring.
Een tweeledige graaf heeft een twee-kleuring.
Elke vlakke graaf heeft een vierkleuring.

Reguliere talen

Elke eindige taal is regulier.
Voor elke reguliere taal L bestaat er een eindige automaat die die taal herkent.
De klasse van talen herkend door eindige toestandautomaten is dezelfde als de klasse herkend door niet-deterministische eindige automaten.
Voor elke reguliere taal L en voor elke string s kan in tijd O(n) beslist worden of s is element van L, met n de lengte van s.
De concatenatie van twee reguliere talen is een reguliere taal.
Elke deelverzameling van een taal is een taal.

Algoritmes

Het algoritme van Kruskal en het algoritme van Prim zijn twee verschillende manieren om hetzelfde probleem op te lossen.
Het algoritme van Dijkstra kan door een deterministische TM uitgevoerd worden.
De tijdscomplexiteit van het algoritme van Prim is linear in het aantal knopen.

Turingmachines

Voor elk java-programma bestaat er een Turingmachine die voor eender welke input dezelfde output geeft als dat programma.
Voor elke functie f: N -> N bestaat er een Turingmachine die f berekent.
Er bestaan oneindig veel Turingmachines.
Het aantal Turingmachines met n toestanden en m symbolen is eindig (op naamgeving na).

Complexeitstheorie

Uit de stelling van Cook volgt dat SAT is een element van NPC.
Er zijn talen die in polynomiale tijd door een NDTM beslist worden maar waarvoor geen DTM bestaat die de taal in polynomiale tijd beslist (als P != NP).

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Description

Test uw kennis over grafentheorie en reguliere talen met deze quiz. Begrijp concepten zoals bomen, samenhangende grafen en algoritmes van Kruskal en Prim.

Wiskunde Quiz: Grafentheorie en Reguliere Talen

Podcast Beta

Questions and Answers

Als f en g asymptotisch equivalent zijn, dan...

Een partieel geordende verzameling met een gesloten interval [a, b] als verzameling, is een complete tralie als...

Een graaf heeft een Euleriaanse kring als en slechts als...

Twee enkelvoudige grafen zijn isomorf als en slechts als...

Als P != NP, dan zijn er talen die...

Het aantal knopen met oneven graad in een graaf is...

Een graaf heeft een Euleriaans pad als en slechts als...

De som van de graden van alle knopen in een graaf is...

Wat is de complexiteit van het algoritme van Dijkstra?

Welke van de volgende grafen heeft een euleriaanse kring?

Wat is een eigenschap van tweeledige grafen?

Wat is een noodzakelijke voorwaarde voor een opspannende boom?

Welke van de volgende stellingen is waar?

Wat is een eigenschap van reguliere talen?

Wat is de tijdcomplexiteit van het algoritme van Prim?

Wat is een gevolg van de stelling van Kuratowski?

Een boom met hoeveel knopen heeft steeds hoeveel bogen?

Wat is een eigenschap van elke samenhangende graaf?

Wat is een eigenschap van het algoritme van Kruskal en het algoritme van Prim?

Wat is een eigenschap van elke boom?

Wat is een eigenschap van elke reguliere taal?

Wat is een eigenschap van elke reguliere taal L?

Wat is een eigenschap van de verzameling van {(ab)^n | n element van de natuurlijke getallen}?

Wat is een eigenschap van de klasse van talen herkend door eindige toestandautomaten?

Welke uitspraak over reguliere talen is waar?

Wat is een eigenschap van een reguliere taal?

Wat is een relatie tussen een niet-deterministische eindige automaat en een deterministische eindige automaat?

Wat is een eigenschap van een string x ten opzichte van een automaat?

Wat is een uitspraak over niet-deterministische eindige automaten?

Wat is een uitspraak over Turingmachines?

Welke relatie tussen twee functies f en g is waar?

Welke relatie tussen twee functies f en g is waar?

Wanneer zijn twee grafen G en G' isomorf?

Een enkelvoudige graaf G(V,E) is tweeledig als:

Wat is een eigenschap van het aantal turing machines met n toestanden en m symbolen?

Wat is een eigenschap van reguliere talen op een gegeven alfabet £?

Wat is een eigenschap van een reguliere taal L?

Wat is een eigenschap van een tweeledige graaf G(V,E)?

Study Notes

Grafentheorie

Reguliere talen

Algoritmes

Turingmachines

Complexeitstheorie

Studying That Suits You

Related Documents

Description

More Quizzes Like This

Exploring Graph Theory

Graph Theory Quiz: Test Your Knowledge with Our Free Online Quiz

Graph Theory Quiz: Test Your Knowledge with Graphing Quiz

Graph Theory Problems