Wiskunde Quiz: Grafentheorie en Reguliere Talen
38 Questions
0 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to lesson

Podcast

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...

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

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

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

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

    <p>altijd even</p> Signup and view all the answers

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

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

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

    <p>altijd even</p> Signup and view all the answers

    Wat is de complexiteit van het algoritme van Dijkstra?

    <p>$O(n^3)$</p> Signup and view all the answers

    Welke van de volgende grafen heeft een euleriaanse kring?

    <p>Een samenhangende vlakke graaf</p> Signup and view all the answers

    Wat is een eigenschap van tweeledige grafen?

    <p>Ze hebben een tweekleuring</p> Signup and view all the answers

    Wat is een noodzakelijke voorwaarde voor een opspannende boom?

    <p>De graaf moet samenhangend zijn</p> Signup and view all the answers

    Welke van de volgende stellingen is waar?

    <p>Elke niet-vlakke graaf heeft een kring</p> Signup and view all the answers

    Wat is een eigenschap van reguliere talen?

    <p>Ze zijn steeds recursief</p> Signup and view all the answers

    Wat is de tijdcomplexiteit van het algoritme van Prim?

    <p>Lineair in het aantal bogen</p> Signup and view all the answers

    Wat is een gevolg van de stelling van Kuratowski?

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

    Een boom met hoeveel knopen heeft steeds hoeveel bogen?

    <p>n-1</p> Signup and view all the answers

    Wat is een eigenschap van elke samenhangende graaf?

    <p>Er is precies 1 opspannende boom</p> Signup and view all the answers

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

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

    Wat is een eigenschap van elke boom?

    <p>Elke boom heeft een twee-kleuring</p> Signup and view all the answers

    Wat is een eigenschap van elke reguliere taal?

    <p>Elke eindige taal is regulier</p> Signup and view all the answers

    Wat is een eigenschap van elke reguliere taal L?

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

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

    <p>Het is een reguliere taal</p> Signup and view all the answers

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

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

    Welke uitspraak over reguliere talen is waar?

    <p>Eindige talen zijn regulier</p> Signup and view all the answers

    Wat is een eigenschap van een reguliere taal?

    <p>De concatenatie van twee reguliere talen is een reguliere taal</p> Signup and view all the answers

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

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

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

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

    Wat is een uitspraak over niet-deterministische eindige automaten?

    <p>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</p> Signup and view all the answers

    Wat is een uitspraak over Turingmachines?

    <p>Er bestaan oneindig veel Turingmachines</p> Signup and view all the answers

    Welke relatie tussen twee functies f en g is waar?

    <p>f is O(g) Ò f is O(g + h)</p> Signup and view all the answers

    Welke relatie tussen twee functies f en g is waar?

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

    Wanneer zijn twee grafen G en G' isomorf?

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

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

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

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

    <p>Het is eindig op naamgeving na</p> Signup and view all the answers

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

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

    Wat is een eigenschap van een reguliere taal L?

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

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

    <p>V kan opgedeeld worden in twee deelverzamelingen V1 en V2, zo dat er enkel bogen bestaan tussen V1 en V2</p> 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.

    Quiz Team

    Related Documents

    Fundamenten Meerkeuze PDF

    Description

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

    More Like This

    Use Quizgecko on...
    Browser
    Open
    Browser
    Browser