Podcast
Questions and Answers
Als f en g asymptotisch equivalent zijn, dan...
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...
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...
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...
Twee enkelvoudige grafen zijn isomorf als en slechts als...
Als P != NP, dan zijn er talen die...
Als P != NP, dan zijn er talen die...
Het aantal knopen met oneven graad in een graaf is...
Het aantal knopen met oneven graad in een graaf is...
Een graaf heeft een Euleriaans pad als en slechts als...
Een graaf heeft een Euleriaans pad als en slechts als...
De som van de graden van alle knopen in een graaf is...
De som van de graden van alle knopen in een graaf is...
Wat is de complexiteit van het algoritme van Dijkstra?
Wat is de complexiteit van het algoritme van Dijkstra?
Welke van de volgende grafen heeft een euleriaanse kring?
Welke van de volgende grafen heeft een euleriaanse kring?
Wat is een eigenschap van tweeledige grafen?
Wat is een eigenschap van tweeledige grafen?
Wat is een noodzakelijke voorwaarde voor een opspannende boom?
Wat is een noodzakelijke voorwaarde voor een opspannende boom?
Welke van de volgende stellingen is waar?
Welke van de volgende stellingen is waar?
Wat is een eigenschap van reguliere talen?
Wat is een eigenschap van reguliere talen?
Wat is de tijdcomplexiteit van het algoritme van Prim?
Wat is de tijdcomplexiteit van het algoritme van Prim?
Wat is een gevolg van de stelling van Kuratowski?
Wat is een gevolg van de stelling van Kuratowski?
Een boom met hoeveel knopen heeft steeds hoeveel bogen?
Een boom met hoeveel knopen heeft steeds hoeveel bogen?
Wat is een eigenschap van elke samenhangende graaf?
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 het algoritme van Kruskal en het algoritme van Prim?
Wat is een eigenschap van elke boom?
Wat is een eigenschap van elke boom?
Wat is een eigenschap van elke reguliere taal?
Wat is een eigenschap van elke reguliere taal?
Wat is een eigenschap van elke reguliere taal L?
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 verzameling van {(ab)^n | n element van de natuurlijke getallen}?
Wat is een eigenschap van de klasse van talen herkend door eindige toestandautomaten?
Wat is een eigenschap van de klasse van talen herkend door eindige toestandautomaten?
Welke uitspraak over reguliere talen is waar?
Welke uitspraak over reguliere talen is waar?
Wat is een eigenschap van een reguliere taal?
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 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 eigenschap van een string x ten opzichte van een automaat?
Wat is een uitspraak over niet-deterministische eindige automaten?
Wat is een uitspraak over niet-deterministische eindige automaten?
Wat is een uitspraak over Turingmachines?
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?
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?
Wanneer zijn twee grafen G en G' isomorf?
Een enkelvoudige graaf G(V,E) is tweeledig als:
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 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 reguliere talen op een gegeven alfabet £?
Wat is een eigenschap van een reguliere taal L?
Wat is een eigenschap van een reguliere taal L?
Wat is een eigenschap van een tweeledige graaf G(V,E)?
Wat is een eigenschap van een tweeledige graaf G(V,E)?
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.
Related Documents
Description
Test uw kennis over grafentheorie en reguliere talen met deze quiz. Begrijp concepten zoals bomen, samenhangende grafen en algoritmes van Kruskal en Prim.
