Voorbeeldexamen POD II


  1. Zijn de volgende uitspraken juist of fout. Indien je “Fout” antwoordt dien je uit te leggen waarom de uitspraak fout is. (12)
    1. Bij een binaire boom mogen we de linker- en rechterdeelboom van de wortel omwisselen zonder dat de boom wijzigt. (2)
      • Fout. Bij een binaire boom wordt er altijd een ordening opgelegd aan de deelbomen.
    2. De tijdscomplexiteit van het algoritme voor het verwijderen van het kleinste element uit een binaire hoop is \(\Theta(\lg(n))\). (2)
      • Juist
    3. Veronderstel dat \(x_1\) en \(x_2\) veranderlijken zijn. Dan is de functie \(f: \mathbb {R}^2 \to \mathbb{R} : (x_1, x_2) \mapsto x_1 + 2x_1x_2 + 3x_2\) lineair in deze veranderlijken. (2)
      • False. Product van twee veranderlijken is niet lineair.
    4. Wanneer men aan een LP-probleem een extra restrictie toevoegt dan is het mogelijk dat de optimale oplossing ongewijzigd blijft. (2)
      • Juist
    5. Om geheeltallige LP-problemen steeds correct op te lossen past men eenvoudigweg het simplex-algoritme toe en rondt de oplossing af als ze niet geheel is. (2)
      • Fout. De afgeronde oplossing kan buiten de aanvaardbare gebied liggen.
    6. Een BILP, ook 0-1 LP-probleem genoemd, met drie variabelen kan hoogstens 3! = 6 aanvaardbare oplossingen hebben. (2)
      • Fout. Het kan hoogstens \(2^3 = 8\) aanvaardbare oplossingen hebben.
  2. Een nieuw computervirus dringt systemen binnen via de e-mailclient of via de browser. De waarschijnlijkheid dat het virus een systeem binnendringt via de e-mailclient is 30%, terwijl de kans dat het virus een systeem binnendringt via de browser 40% bedraagt. De kans dat het virus het systeem binnendringt zowel via de e-mailclient als via de browser is 15%.
    1. Noem A degebeurtenisdathetvirushetsysteembinnendringtviadee-mailclient en B de gebeurtenis dat het virus het systeem innendringt via de browser. De gebeurtenissen A en B zijn (duid aan wat correct is) ... ? afhankelijk ? onafhankelijk Verklaar hieronder bondig (maar toch volledig) je antwoord. (3)
      • Afhankelijk. Onafhankelijkheid: \( P(A\cap B) = P(A)P(B)\)
    2. Wat is de kans dat het virus een systeem binnendringt? (2)
      • \( P(A\cup B) = P(A) + P(B) - P(A \cap B)\) \( = 0.3 + 0.4 - 0.15 = 0.55 = 55\)%
    3. Wat is de kans dat het virus een systeem binnendringt via de browser maar niet via de e-mailclient? (2)
      • \( P(B \backslash A) = P(B) - P(A \cap B) = 0.4 - 0.15 = 0.25 \)
    4. Wat is de kans dat het virus een bepaald systeem niet binnendringt? (3)
      • \( P(\Omega\backslash(A\cup B)) = 1 - (A \cup B) = 1 - 0.55 = 0.45 \)
  3. Het aantal keren dat een individu een verkoudheid oploopt per jaar is Poisson verdeeld met parameter λ = 5. Veronderstel dat een nieuw medicijn op de markt is gebracht dat de Poisson parameter reduceert tot λ = 3 voor 75% van de bevolking, m.a.w. voor 75% van de bevolking heeft het medicijn een gunstig effect. Voor de andere 25% van de populatie heeft het nieuwe medicijn geen effect op het aantal verkoudheden.
    1. Wat is de kans dat iemand die het medicijn niet neemt méér dan 2 verkoudheden oploopt gedurende een jaar? (3)
      • X: #verkoudheden zonder medecijn, poisson verdeeld met λ = 5
        \(P(X > 2) = 1 - P(X \le 2)\)
        = 1 - poisson.verd(2;5;WAAR)
        = 0,8753 = 87,53%
    2. Wat is de kans dat iemand die het medicijn neemt gedurende een jaar juist twee verkoudheden oploopt in dat jaar? (2)
      • 0,75 * poisson.verd(2;3;ONWAAR) + 0,25 * poisson.verd(2;5;ONWAAR) = 0,189087 = 18.91%
    3. Wat is de gemiddelde tijd (in dagen) tussen twee verkoudheden voor iemand die het medicijn niet neemt? Neem aan dat een jaar 365 dagen telt. (2)
      • 365/5 = 73 dagen
    4. Als een individu het medicijn probeert gedurende een jaar en juist 2 verkoudheden oploopt in deze periode, hoe waarschijnlijk is het dan dat het medicijn gunstig is voor dit individu? (2)
      • 75 % kans dat medecijn werkt/kans dat iemand die het medecijn neemt juist 2 verkoudheden oploopt
        = 0.75 * poisson.verd(2;3;ONWAAR)/0.1891
        =0.888585 = 88.86%
    5. Wat is het gemiddeld aantal verkoudheden (per jaar) van de mensen die het nieuwe medicijn nemen? (2)
      • 0,75*3+0,25*5=3,5 verkoudheden/jaar
  4. Drie vrienden bestellen op café alledrie een op het zicht verschillend drankje. De ober keert terug met hun bestelling maar is compleet vergeten wie welk drankje heeft besteld. De ober zet de glazen dus willekeurig neer bij de vrienden. De ober voert dus (zonder dat hij dit zelf beseft) een “experiment” uit, hij zet namelijk de drie verschillende drankjes in een willekeurige volgorde op drie genummerde plaatsen.
    1. Geef de uitkomstenruimte Ω van dit experiment door opsomming. Noteer de drankjes met 1, 2 en 3. (3)
      • \(\Omega = \) {(1,2,3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)}
    2. We zeggen dat een drankje op de “juiste” plaats staat als de ober het drankje heeft geplaatst bij de vriend die het drankje effectief heeft besteld. Bijvoorbeeld, als de ober het drankje besteld door de eerste vriend op plaats 1 neerzet, dan staat dit drankje “juist”. Wanneer hij dit drankje op plaats 2 of 3 neerzet, dan staat dit drankje niet juist.
    3. Beschouw de toevalsveranderlijke X die telt hoeveel drankjes op de juiste plaats staan. Geef de toevalsveranderlijke X in tabelvorm, geef dus voor elk van de zes (tip!) elementen ω van Ω aan wat de waarde is van X. (3)
      • \(\omega\) (1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1)
        \(X(\omega)\) 31 1 0 0 1
    4. Geef de kansfunctie \(f_X\) in tabelvorm. (3)
      • X 0 1 3
        \(F_X\) 2/6 3/6 1/6
    5. Hoeveel drankjes staan er gemiddeld op hun juiste plaats? Anders gezegd, wat is \(\mu_X\) ? Antwoord exact. (2)
      • \(0 \times \dfrac{2}{6} + 1 \times \dfrac{3}{6} + 3 \times \dfrac{1}{6}\) = 1
    6. Wat is de variantie \(\sigma_X^2\) van X? Antwoord exact. (2)
      • \((0-1)^2 \times \dfrac{2}{6} + (1-1)^2 \times \dfrac{3}{6} + (3-1)^2 \times \dfrac{2}{6} = \dfrac{2}{6} + \dfrac{4}{6} = 1 \)
  5. Beschouw de binaire zoekboom in Figuur 1. Wat zijn de geldige waarden voor x en y als we aannemen dat de binaire zoekboom enkel gehele waarden bevat en dat alle waarden in de zoekboom verschillend zijn:
    1. Mogelijke waarden voor x: (2)
      • 15, 16, 17, 18, 19
    2. Mogelijke waarden voor y: (2)
      • 21, 22, 23
    3. Geef de volgorde van de toppen wanneer de boom in postorde wordt doorlopen. (3)
      • 8, 13, z, 14, 10, 20, 24, y, 28, 30, 25, x
    4. Voeg een top met waarde 11 toe aan de zoekboom in Figuur 1. Neem aan dat in de resulterende zoekboom alle toppen nog steeds een verschillende waarde hebben. (3)
    5. Teken hieronder de resulterende zoekboom wanneer de top met waarde 10 verwijderd werd uit de boom in Figuur 1. (4)
  6. Alice en Bob, een pasgetrouwd koppel, willen hun huishoudelijke taken netjes onder hun tweeën verdelen. Ze komen overeen om elk exact twee taken op zich te nemen. De efficiëntie van Alice en Bob is echter verschillend van taak tot taak, en wordt gegeven in onderstaande tabel:
    Winkelen Koken Afwassen Was en Strijk
    Alice 4.5 uur 7.8 uur 3.6 uur 2.9 uur
    Bob 4.9 uur 7.2 uur 4.3 uur 3.1 uur
    Alice en Bob willen samen zo weinig mogelijk tijd spenderen aan de huishoudelijke taken, terwijl alle taken natuurlijk wel moeten uitgevoerd worden.
    We stellen een ILP op om dit probleem op te lossen. Om de notatie te vereenvoudigen mag je de notatie ti,j (met i ∈ { 1,2 } en j ∈ { 1,2,3,4 } ) gebruiken voor de tijden die nodig zijn om de klussen uit te voeren. Zo stelt t1,3 de tijd voor die Alice nodig heeft om af te wassen.
    1. Welke beslissingsvariabelen ga je gebruiken? Geef hun betekenis. (2)
      • \(x_A = \) aantal uren Alice \(x_B = \) aantal uren Bob
    2. Geef de doelfunctie. (2)
      • \(x_A + x_B\)
    3. Ga je de doelfunctie maximaliseren of minimaliseren? (2)
      • Minimaliseren
    4. Geef hieronder alle beperkingen die beschrijven waar ze voor staan. (4)
      • \(i_{1,2}= 2\) => 2 taken/persoon
        \(j_n\) met n \( \in \{1, 2, 3, 4\} = 1\) => Elke taak uitgevoerd
        \(t_{i,j} = \) binair => niemand voert halve taken uit
    5. Noteer hieronder de optimale oplossing. (3)
      Wie neemt welke klussen voor zijn rekening?
      • Alice: \(j_2 + j_4\)
        Bob: \(j_1 + j_3\)
      Hoeveel tijd spenderen Alice en Bob samen aan deze klussen?
      • 18.4
    6. Na een aantal jaar besluiten Alice en Bob dat het niet langer noodzakelijk is om elk exact twee klussen uit te voeren. Ze willen enkel de totale tijd die wordt gespendeerd aan de klussen minimaliseren. Zal de totale tijd die ze nu spenderen aan de klussen stijgen of dalen?
      • Dalen, 18.2, Alice 3 taken
  7. Beschouw de graaf G = ( V,E ) in Figuur 2.(8)
    1. Geef de verzameling E door opsomming. (3)
      • E = {(a, b), (b, g), (c, d), (c, e), (d, b), (d, g), (e, h), (f, a), (f, b), (g, f), (h, c), (h, d)}
    2. Wanneer men de graaf G voorstelt door zijn adjacentiematrix, wat is dan het aantal “enen” in deze adjacentiematrix? (2)
      • Mijn interpretatie: Elke één op matrix Aij stelt een boog e = (i, j) van knop Vi naar Vj voor.
      • Juiste antwoord: 12
    3. Geef het aantal topologische sorteringen van deze graaf. (2)
      • 0. Bevat enkelvoudige cirkel (lus). (Geen 1 vertrek- aankomstpunt?)
    4. Wanneer men Algoritme 5.8 uit de cursus (en het formularium) toepast met als startknoop c, wat is dan de inhoud van de returnwaarde D? Neem aan dat a rangnummer 1, b rangnummer 2 heeft enz.(4)
      • Algorithm 5.8 = Kortste pad ongewogen graaf (Algoritme 5.5) in nieuwe formularium
        D[1] D[2] D[3] D[4] D[5] D[6] D[7] D[8]
        4 2 0 1 1 3 2 2
    5. Wanneer men Algoritme 5.6 uit het formularium toepast met als startknoop c, wat is dan de volgorde waarin de knopen worden ontdekt, m.a.w. wat is de volgorde van de knopen waarvoor lijn 7 uit het algoritme wordt uitgevoerd? Tip: de eerste knoop is uiteraard knoop c. Opmerking: neem aan dat op lijn 8 de buren van een knoop steeds in lexicografisch (alfabetisch) stijgende volgorde worden geretourneerd. (4)
      • Algoritme 5.6 = Recursief diepte eerst zoeken (Algoritme 5.3) in nieuwe formularium
        {c, d, b, g, f, a, e, h}

Comments