Complexiteit van algoritmen

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.

Examen

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)

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.