Discrete Wiskunde

Ga naar: navigatie, zoeken

Samenvattingen

Klik hier om de samenvattingen te bekijken

Informatie over het examen

Dit vak wordt gegeven door professor Wim Veys. Het examen is normaalgezien volledig open boek en bestaat meestal uit vijf vragen. Het examen bestaat voornamelijk uit oefeningen en is schriftelijk, behalve één theorievraag die je mondeling bij de prof moet gaan uitleggen.

Examenvragen

Juni 2018

Examen juni 2018

Vraag 1 was mondeling te verdedigen, vraag 2 was van theoretische aard en vraag 3 en 4 waren gewoon schriftelijke oefeningen.

Juni 2011

Examen juni 2011

17 juni 2009

  1. Neem een willekeurig reeel getal en neem . Toon aan dat er een en een bestaan zodanig dat
    1. Op hieveel manieren kan men de toppen en zijvlakken van een tetraeder kleuren met 2 keer rood, 3 keer groen en 3 keer blauw?
    2. Op hoeveel manieren kan men de ribben van een tetraeder kleuren met de 3 kleuren rood, groen en blauw zodanig dat overstaande ribben telkens een andere kleur hebben?
  2. Beschouw een design met . Definieer . Toon aan dat ook een t-design is.
  3. Voor welke waarde in kan de som in gesloten vorm geschreven worden? Bereken deze gesloten vorm voor de gevonden waarde van .
    1. Leg het Massey-Omura systeem voor boodschappen uit.
    2. Stel dat je discrete logaritmes (snel) kan berekenen. Leg uit hoe je dit systeem dan kunt kraken.
    3. Op het mondeling was er een bijvraagje (compleet los van het vorige): tekening van F_5^2 gegeven, je moest alle punten aanduiden die op hammingafstand 1 van een bepaald punt liggen.

13 juni 2008

  1. Zij .
    1. Zij W een deelverzameling van V met 37 elementen. Toon aan dat er twee getallen in W zijn die 4 van elkaar verschillen.
    2. Optimaliseer de vorige opgave door 37 te vervangen door een zo klein mogelijk getal.
  2. Deze oefening gaat over de kubus. We kleuren enerzijds de zes zijvlakken en anderzijds zes toppen zodat twee overstaande toppen niet gekleurd zijn.
    1. Op hoeveel manieren kan je deze 12 objecten kleuren met de kleuren groen, blauw en rood?
    2. Op hoeveel manieren kan je deze 12 objecten kleuren zodat er 3 groene en 3 blauwe zijvlakken zijn en er 3 blauwe en 3 rode punten zijn?
    1. Zij een 2- design en een 2- design. Construeer op het Cartesiaans product een 2- design.
    2. Zij V = {A,B,C,D,E,F,G} en het 2-(7,3,1) design. Construeer op een 2-(21,3,1) design.
  3. Voor welke is de volgende uitdrukking te schrijven als de som van een (vast) aantal hypergeometrische termen in n? Bereken deze som voor de gevonden .
  4. (Mondeling) Bewijs de Gilbert-Varshamov grens.


19 juni 2007

Het examen was volledig open boek. Vraag 5 was mondeling te verdedigen bij Veys, de rest was schriftelijk.

  1. Toon aan dat er een getal bestaat van de vorm 20062006...2006, dat deelbaar is door 2007.
  2. Het kaartspel 'Set!' (Veys had zo'n kaartspel mee om te tonen op het examen) bestaat uit 81 kaarten, waarbij op elke kaart een aantal (1,2 of 3) gekleurde ( rood, groen of paars ) figuren (ruiten, ovalen of krullen) met een bepaalde opvulling ( vol, gearceerd of leeg ) zijn getekend en waarbij elke mogelijke samenstelling van de vier kenmerken voorkomt. We noemen 3 kaarten een 'set' als elk van de vier kenmerken ofwel hetzelfde is ofwel helemaal verschillend ( de 3 mogelijkheden komen voor ) op de drie kaarten. Noteer door V de verzameling kaarten en door B de verzameling 'sets'.
    • Voor welke t is (V,B) een t-(81,3,lambda)-design ? Bepaal de maximale waarde van t en bereken b = |B|.
    • met welk bekend design is dit design isomorf? Geef een isomorfisme. Met welk blok komt de set bestaande uit 2 paarse volle krullen, 3 paarse volle ruiten en 1 paarse volle ovaal overeen ?
    • Op hoeveel verschillende manieren kan men de hoekpunten en zijvlakken van een octaëder kleuren met rood, geel en zwart, zodat in totaal 2 zijvlakken of hoekpunten rood, 3 geel en 9 zwart zijn ?
    • Op hoeveel manieren kan dit als we bovendien eisen dat 2 overstaande hoekpunten rood moeten zijn ?
  3. Voor welke a in de natuurlijke getallen > 0 is te schrijven als een som van hypergeometrische termen in n ? Geef en bewijs voor al deze a deze som.
  4. Leg het protocol van Fiat-Shamir uit. Waarom moet de geheime sleutel inverteerbaar zijn ? (mondeling)

24 juni 2005

  1. Bewijs dat in een verzameling met 3n+1 elementen in het vlak waarvan elke 4 elementen er minumum 2 maximum op 1 afstand liggen er minimum n+1 elementen zijn die binnen een gesloten cirkel met straal 1 liggen.
  2. Hoeveel verschillende manieren bestaan er bij een vijfvlak (twee driehoeken met drie vlakken tussen) de toppen en de vlakken te kleuren met rood, geel en blauw zo dat:
    • er minimum 5 toppen rood zijn
    • de twee driehoeken in verschillende kleuren zijn
  3. Neem een 2-(v,k,lam)-design (V,B). Neem dan (V,B_) waarbij B_ = {b_ = V\b|b el. van B_}. Toon aan dat dit een 2-(v,v-k,lam_) design is en bepaal lam_
  4. Toon aan dat f(n) = sum over k=1..n (2^k*lam^k) te schrijven valt als de som van twee hypergeometrische reeksen en voor welke lambda
  5. Bewijs dat voor een gegeven controle-veelterm van een (n,k)-cyclische code h=h_0+..+h_kX^k de matrix H zoals in boek pag. 312 welk degelijk de pariteitscontrole matrix is.

juni 2000

  1. Toon aan dat er in een groep van 28 personen 4 verschillende personen a,b,c,d bestaan zodat b evenveel dagen verjaart na a als dat d verjaart na c.
  2. Beschouw een icosaëder. Op hoeveel verschillende manieren kan je de zijvlakken kleuren met 8 keer rood, 2 keer blauw en 6 keer wit zodat 2 overstaande zijvlakken dezelfde kleur hebben?
  3. Gegeven een design. Construeer het afgeleide design . Leg voor een gegeven voorbeeld uit wat het afgeleide design is en met welk bekend design het overeenkomt.
  4. Mondeling
    1. DSA: leg uit waarom . Waar gebruik je dat q priem is?
    2. Waarom is het discrete logaritmeprobleem in met generator g niet geschikt voor cryptische toepassingen?

augustus 2000

  1. Zoek de grootste n zodat waar is: uit elke verzameling van 100 getallen kan je n getallen kiezen zodat het verschil tussen gelijk welke getallen uit n deelbaar is door 7.
  2. mama bakt taart die ze in 12 gelijke stukken verdeelt. Ze maakt 5 stukken met appel, 4 met banaan, 3 met aardbei. Ook zet ze op elk stuk een kaars, namelijk 7 gele kaarsen, 3 rode en 2 witte. Op hoeveel verschillende manieren kan dit?
  3. Voor welke is de volgende uitdrukking te schrijven als de som van een (vast) aantal hypergeometrische termen in n? Bereken deze som voor een gevonden .
  4. Leg Fiat-Shamir uit. (mondeling)
  5. Ook mondeling:
    1. Zij C een lineaire code met voortbrengende matrix G. Bewijs dat G de pariteitscontrolematrix is van .
    2. Zij C een repetitiecoce over . Bewijs dat C perfect is als en slechts als C een oneven lengte heeft.

11 juni 2001

  1. Oefening
    1. Zij V een deelverzameling van {1,2,3,...,99,100} met 36 elementen die geen opeenvolgende getallen bevat. Bewijs dat er in V twee getallen zijn die 6 of 7 van elkaar verschillen.
    2. Geef een deelverzameling van {1,2,3,...,99,100} met 32 elementen die geen opeenvolgende getallen bevat en waarin geen twee getallen zijn die 6 of 7 van elkaar verschillen.
    3. Zelfde als (a) met 36 vervangen door 33.
  2. Oefening
    1. Op hoeveel manieren kan je de zijvlakken van een octaëder kleuren zodat er 3 rood, 3 blauw en 2 wit zijn?
    2. Op hoeveel manieren kan je de zijvlakken van een octaëder kleuren met de kleuren rood, blauw en wit zodat er tegenover rood en blauw steeds wit ligt?
  3. Zij en de P_i zijn onderling verschillend en . Voor welke is een design? Bewijs uw antwoord.
  4. Bewijs dat er juist één bestaat waarvoor te schrijven is als som van hypergeometrische termen in n, en doe dit dan ook voor de gevonden q.
  5. Bewijs de Gilbert-Varshamov grens. (mondeling)


Lang geleden

  1. Oefening
    1. Construeer het lichaam met 16 elementen.
    2. Met welke standaardgroep is isomorf?
    3. Met welke standaardgroep is isomorf?
  2. Een land geeft nummerplaten uit bestaande uit zes getallen uit . Twee nummerplaten moeten op ten minste drie plaatsen verschillen. Gegeven is . Hoeveel nummerplaten kan het land maximaal uitgeven?
  3. Zij D een design met . Bewijs dat