Complexiteit van algoritmen

Samenvattingen

Klik hier om de samenvattingen te bekijken

Informatie over het examen

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

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.