College "T2":
ANALYSE VAN ALGORITMEN/COMPLEXITEIT (I00010)************************en
COMPLEXITEITSTHEORIE (SCHAKELCURSUS) (I00125)
Najaar 2007 - Wekelijks op maandag 13u30-15u30; zaal HG00.062 en donderdag 10u30-12u30; zaal HG00.071 .
Belangrijk: de opzet van T2 is dit jaar anders. Voor details, raadpleeg s.v.p. de cursusbeschrijving op de III-site.
week 51 - 17 dec .........bijeenkomst 26
Stof (bestudeer van tevoren): Hd 10 (STEENBOK): 10.1, 10.2.
Opgave (lever in!!!!):
RSA-priemen, deel 1.
Het aantal priemgetallen tussen 1 en x is in goede benadering (d.w.z. asymptotisch) gelijk aan x/ln x waarin ln de e-log is, e=2,718281828.... Voor RSA-doeleinden wil men priemgetallen zoeken in [10^100,2.10^100].
a. Geef een pseudocodeprogrammaatje dat gebruik maakt van een statement x:=FLIP welke een random bit oplevert in constante tijd, en dat een random getal levert tussen N en 2N (N is een natuurlijk getal). Je mag je beperken tot N een tweemacht. Doe het zo dat de looptijd lineair is.
b. Neem aan dat we een snel (polynomiaal) beslissingsalgorithme hebben voor priemgetallen dat loopt in O((#bits)^12) (dit bestaat, naar men sinds enkele jaren weet). We testen daarmee random getallen in [N,2N]. Geef een probabilistisch algorithme dat via "herhaald trekken", met kans minstens 1-epsilon een priemgetal in [N,2N] oplevert.
(wordt vervolgd)
.........
week 51 - 20 dec .........bijeenkomst 27
Stof (bestudeer van tevoren): Hd 10 (STEENBOK): 10.3 tot en met 10.3.5.
Opgaven (lever in!!!!):
RSA-priemen, deel 2.
c. Laat zien dat de benodigde looptijd in b. polynomiaal is (van graad 13). Hint: bewijs eerst dat de succeskans asymptotisch gelijk is aan 1/ln N. Neem aan dat dit exact is. Schat verder ln(1+a) met a, voor a een klein reëel getal (positief of negatief).
d. Wat is de looptijd van het algorithme in b. voor N=10^100 (bij succeskans epsilon = 10^{-4})?
.........
Het volgende college is op 7 januari. We wensen iedereen een goede Kerst en een prettige jaarwisseling! ....- Dick-Venanzio-Ken-Freek -
.........
.........
week 02 - 7 jan .........bijeenkomst 28
Stof (geen tentamenstof): Hd 10 (STEENBOK): deel van 10.3.6.
Opgaven: geen nieuwe.
.........
week 02 - 10 dec .........bijeenkomst 29
Stof (bestudeer van tevoren): geen nieuwe.
Opgaven: Alleen een bespreking van de opgaven van 20 dec.
Dit is het slot van het college. Het vierde testje is op 14 jan, gewone plaats, van 13u45 exact tot 14u45 exact; de stof is die van bijeenkomst 22 t/m 27.
Het tentamen is op de 24e, gewone plaats en tijd (10u45 exact - 12u45 exact). Het is open boek; een toelichting op de tentamenregeling is rondgemaild (je vindt de email hieronder nog eens naast de uitslag van testje 4).
Denken jullie eraan de enquête in te vullen op Blackboard?
Veel succes! Dick-Venanzio-Ken-Freek.
-----------------------------------------------------------
HERKANSING:
Donderdag 26-jun-2008 10:30-12:30 HG00.071Het tentamen is open boek en gaat over de hele stof (voor de schakelcursisten alleen het deel dat voor hen is behandeld. Hun tentamen duurt daarom 1 uur ipv 2 uur).
.
Mededelingen:
- De opgaven van bijeenkomst i worden ingeleverd op bijeenkomst i+1 en besproken op bijeenkomst i+2 (behalve voor i=28). Zie de planning (hieronder).
Uitslag testje 1.
Uitslag testje 2.
Uitslag testje 3.
Uitslag testje 4 en gemiddelden.;
email met toelichting tentamenregeling.
Uitslag tentamen 24 jan '08.
Uitslag tentamen 26 jun '08.
.
.
.
Planning (met data testjes).
Dictaat (pdf; 16.3 Mb).;
Titelblad (pdf; 496 Kb).
Docenten:
Dr. D.C. ("Dick") van Leijenhorst; kamer HG02.541;
bolke@cs.ru.nl
Dr. V. ("Venanzio") Capretta; kamer HG02.528; venanzio@cs.ru.nl
Student-assistenten:
Ken Madlener; k.madlener@student.ru.nl
Freek Verbeek; f.verbeek@student.science.ru.nl
Raadpleeg ons waar nodig!