Complexiteit van algoritmen

Ga naar: navigatie, zoeken

Samenvattingen

Klik hier om de samenvattingen te bekijken

Informatie over het examen

Tegenwoordig: Gegeven aan studenten computerwetenschappen en wiskunde. Prof: Bart Demoen en Jon Sneyers

Tot 2007: Keuzevak licenties informatica, ook gegeven aan licentie wiskunde. Prof: Walter Van Assche, walter@wis.kuleuven.ac.be Assistent: tom.claeys@wis.kuleuven.be

Er staat een voorbeeldexamen op het blackboard.

Examenvragen

Tegenwoordig

Het examen is mondeling met ongeveer 1 uur schriftelijke voorbereiding. Je mag de hele cursus (en zelfs extra cursussen) meenemen en gebruiken. Hierna word je door beide proffen apart ondervraagd. Jon focust vooral op grote verbanden, Bart kiest een aspect uit de cursus en gaat er heel diep op in. Beide proffen stellen 2 vragen: in totaal 2 over de cursus, 1 over je paper en 1 over de paper van een medestudent die je op voorhand gekozen hebt.

Belangrijk: Enkel wat je zegt is belangrijk, achteraf wordt er niet naar je voorbereiding gekeken.

juni 2015

Demoen:

  • Op p 112 wordt gedefinieerd wat een Turing machine met advies is. Leg die definitie uit in woorden. Vergelijk de notie van advies met die van certificaat. Leg daarna stelling 6.18 uit.
  • Vraag over eigen paper.

Sneyers:

  • Wat is er mis met volgend "bewijs" dat P = NP?

Uit het ongerijmde. Stel P = NP
Als P = NP, dan is PA = NPA voor alle A.
Maar dat is niet wegens stelling 3.7. Dus veronderstelling is fout. en dus is P niet gelijk aan NP.
QED.

  • Vraag over paper van een medestudent.

Tot 2007

Het examen is mondeling met schriftelijke voorbereiding. Er zullen drie vragen zijn:

  • vraag 1 (5 punten): een theorievraag over een onderwerp uit de cursus. Vaak één of ander aspect dat in meerdere hoofdstukken terugkomt.
  • vraag 2 (5 punten): een (variant van een) oefening uit de cursustekst, aan het einde van elk hoofdstuk.
  • vraag 3 (5 punten): vijf kortere oefeningen zoals diegene die je hebt gezien tijdens de oefeningenzittingen.

De twee practica in de loop van het semester tellen mee voor 5 punten (samen).

Kleine tip: leer de complexiteit van de geziene algoritmes vanbuiten ! (klinkt logisch gezien de vaknaam, maar vorig jaar hebben we er met veel ons laten door vangen)

2007-06

  1. Bespreek de 3 verschillende manieren om 2 getallen met elkaar te vermenigvuldigen
  2. PROP is de eigenschap of een formule een tautologie is. Bewijs dat niet-PROP in NPC zit
    • Bijvraag: schema van de verzamelingen (NP, co-NP, P, NPC) tekenen
  3. 5 oefeningen
    1. 3 vergelijkingen telkens module een ander getal (onderling ondeelbaar) oplossen
    2. Zoek in Z_17 een curve met p(1) = 1, p(3) = 0, p(4) = 0, p(weet niet meer) = -1
    3. + nog 3 andere oefeningen die mij niet meer te binnen schieten

2006-06

     1. Bespreek 3 verschillende manieren om 2 getallen met elkaar te vermenigvuldigen.
     2. Oef 9 Hfst 5
     3.  a) FFT via zo'n tabel
         b) Merkle Hellman: superstijgende rij vinden
         c) + d)  Oefening op ondergrens voor T(n)
         e) Als je twee 4*4 matrices kan vermenigvuldigen in q stappen, hoe snel kan je dan
         2 n*n matrices vermenigvuldigen? (n is een macht van 4)

2006-06

1. Geef een algoritme om het middelste element van een rij te zoeken en geef de   complexiteit.
2. Een transformatie van Knapzak probleem naar iets anders(iemand?).
3.-Positief opgerolde convolutie
  -een oefening met de chinese reststelling
  -Een oefening zoals in de eerste oefenzitting
  -Hoeveel vergelijkingen zijn minstens nodig om (a,b,c,d,e) te ordenen
  -nog eentje(iemand?)

2004-06-17

On 17-06-2004 15:35:24 +0000, Reinaert Albrecht wrote:
> Ter nog meerdere eer en glorie van het nageslacht:
>  
> 1. - Wat is het verschil tussen een priemtest en een ontbinding in
> priemfactoren
> - Beschrijf de priemtest van Miller
> - Hoe ga je daarmee praktisch te werk
> - Geef de bitsgewijze tijdscomplexiteit
>  
> 2. Schrijf een algoritme dat controleert of n een macht is van een
> bepaald getal, dus n = a^b. Bewijs dat dit kan in bitsgewijze
>  tijdscomplexiteit O(log^4 n loglog n)
>  
> 3. - los x^2 = 81 mod 145 op
>  - bepaal met fft de negatief opgerolde convolutie in Z_17 van twee
>    rijen van 4 lang
>  - geef een scherpe ondergrens voor T(n) <= 2^n + 2^-n sum(k=1..n-1) 2^kT(k)
>  - nog twee dingen
 
Die twee andere dingen waren dan

- is TS => KS en TS => SAT? motiveer (stel u bij => het tekentje polynoomtransformeerbaarheid voor )
- gegeven een grote rij getallen, allemaal door elkaar, gevraagd of er een mogelijkheid bestaat om met die getallen het getal x te bepalen (waarbij x dan een gegeven getal van 5 cijfers was wat ik mij
 uiteraard niet meer herinner) De rij getallen was een superstijgende rij bij nader inzien behalve dat er twee getalletjes dubbel inzaten, maar dat was niet echt een hindernis.