Er zijn aantekeningen voor het college van vorig jaar. Voor dit jaar zal er iets dergelijks komen, maar de stof zal niet precies gelijk zijn.
Er zijn binaries (executables, vertaalde programma's) voor Linux op een PC (*86, Pentium). Op het moment de volgende drie: (i) pdp8, een pdp8 simulator, en (ii) dam, een programma dat damt (niet erg sterk), (iii) xaos, een programma dat fractals vertoont. Een Linux distributie is te halen van ftp://ftp.nluug.nl/pub/os/Linux/distr .
Voor de opgaven: stuur de oplossingen, voor het volgende college, naar aeb@cwi.nl. Als een oplossing door drie mensen gezamenlijk is gevonden, stuur dan een oplossing met drie namen, en niet drie keer dezelfde oplossing. Stuur geen Word documents. Je kunt de status van ontvangen opgaven bekijken. Natuurlijk zal deze altijd enige uren achterlopen.
Inhoud: eerste, tweede, derde, vierde, vijfde, zesde, zevende, achtste, negende college.
Eerste college: 990903
Besproken: Computers,
Turing Machines,
von Neumann machines. Algoritmen, programma's, recursie.
Het Euclidisch algoritme voor de ggd (grootste gemene deler).
Dan vragen die het construeren van een Turing machine inhouden. De machine wordt beschreven door een tabel waar voor elke toestand beschreven wordt wat er gebeurt als er een 0 op de band onder de leeskop staat, en wat als het een 1 is. "Wat er gebeurt" is een paar: (actie,nieuwe toestand), waarbij actie 0, 1, L of R is. (Schrijf een 0, schrijf een 1, ga naar links of ga naar rechts.) Lege band leest als 0. De machine wordt gestart met de leeskop op de meest linkse plaats van de invoer. Toestand 1 is de starttoestand. Toestand 0 is de stoptoestand.
(ii) Schrijf een machine die kan optellen (Invoer op de band: twee getallen in het 1-tallig stelsel gescheiden door een 0. [Dus: het getal 7 wordt geschreven als 1111111.] Gewenste uitvoer: diezelfde twee getallen, gevolgd door hun som.
(iii) Schrijf een machine die kan vermenigvuldigen.
Voorbeelden: (a) Een machine die een getal uitveegt: Invoer 110111010. Uitvoer 0111010.
1: 0,0 0,2 2: R,1 *(Zie ik een 1, dan schrijf ik een 0 en ga over in toestand 2. In toestand 2 weet ik zeker dat ik een 0 zie, ik ga naar rechts en over in toestand 1. Ben ik aan het eind van de rij met enen dan stop ik.)
(b) Een machine die een getal kopieert: Invoer 11110. Uitvoer 1111011110.
1: 0,0 0,2 2: R,3 * 3: R,4 R,3 4: 1,5 R,4 5: L,6 L,5 6: 1,7 L,6 7: * R,1(Instructie 1 heeft de leeskop helemaal links op het (nog) te kopiëren getal; staat er 0 dan stoppen we. Anders schrijven we er 0 om te onthouden waar het was, gaan naar rechts voorbij de 0 (toestand 2), en alle enen van het getal (toestand 3), en één 0 (die het getal van de kopie scheidt), en voorbij alle enen in de kopie (toestand 4). Is de 0 aan het eind gevonden, schrijven we een 1, lopen weer terug langs de enen in de kopie (toestand 5), langs de 0 die getal van kopie scheidt, langs de enen van het getal (toestand 6) totdat de 0 gevonden is die we in toestand 1 neerschreven. Daar schrijven we weer een 1, gaan een stap naar rechts en herhalen de procedure.)
Merk op dat van toestand 2 alleen het 0-gedeelte en van toestand 7 alleen het 1-gedeelte gebruikt wordt. We kunnen dus toestanden 2 en 7 samenvoegen, zodat het hele programma met 6 verschillende toestanden uitkomt.
Merk op dat deze oplossing de leeskop op een slordige plaats achterlaat. Als dit een onderdeel van een grotere machine (bijvoorbeeld voor vermenigvuldigen) moet worden dan moeten we de leeskop op een welgedefinieerde plaats achterlaten, bijvoorbeeld weer aan het begin van de uitvoer:
1: 0,0 0,2 2: R,3 * 3: R,4 R,3 4: 1,5 R,4 5: L,6 L,5 6: 1,7 L,6 7: * R,8 8: L,9 0,2 9: R,0 L,9Antwoorden.
Tweede college: 990910
Besproken: Opgaven.
Rekentijd van algoritmen.
Polynomiale algoritmen. Rekentijd voor ggd en voor sorteren.
Getalsrepresentatie.
Enkele, meervoudige, onbeperkte lengte geheeltallige aritmetiek.
One's complement en two's complement voorstelling van negatieve gehele getallen.
Drijvende komma getallen met mantissa en exponent.
Interval aritmetiek.
Rood-blauw hackenbush.
Om drie verschillende getallen a,b,c op grootte te sorteren heb je drie vergelijkingen nodig: kijk of a < b, kijk of a < c, kijk of b < c. Om vier getallen a,b,c,d te sorteren hoef je niet alle (4 kies 2) = 6 vergelijkingen uit te voeren, want als a < b < c en b < d dan hoeft d niet meer met a vergeleken te worden, terwijl als d < b dan hoeft d niet meer met c vergeleken te worden. Dus voor vier getallen zijn 5 vergelijkingen voldoende. Laat zien dat vijf getallen met 7 vergelijkingen gesorteerd kunnen worden.
Derde college: 990917
Besproken: Opgave. Toepassingen van sorteren.
Het convexe omhulsel van een verzameling punten.
Vermenigvuldigen van getallen.
Vermenigvuldigen van veeltermen.
Het vinden van nulpunten via Newton-Raphson.
Meer rood-blauw Hackenbush.
(i) Op een computer en in een omgeving waarin gehele getallen in 32-bit two's complement notatie worden voorgesteld: Wat is het grootste, en wat het kleinste gehele getal? Welk geheel getal heeft geen tegengestelde?
(ii) Bereken sin(10^100) - de sinus van 10 tot de macht 100 - in twee decimalen.
(iii) Bij rood-blauw hackenbush is er een grond, en een graaf met rode en blauwe kanten, waarvan sommige knooppunten op de grond liggen (en de rest erboven). Er zijn twee spelers, Rood en Blauw, die om beurten een zet doen. Een zet bestaat uit het weghalen van een kant in de eigen kleur, benevens alles wat door het weghalen van die kant niet meer aan de grond vastzit. Wie niet kan zetten verliest.
Het is duidelijk dat blauwe kanten die aan de grond vastzitten Blauw helpen: als er zeven zulke kanten zijn, houdt hij het zeker nog zeven zetten uit. Blauwe kanten die hoog in de lucht zweven, en alleen via rode kanten aan de grond vastzitten zijn minder zeker: misschien verwijdert Rood die kanten en vallen de hoge blauwe kanten er af zonder dat Blauw er plezier van heeft gehad. Het is mogelijk om bij elk plaatje uit te rekenen hoeveel zetten voorsprong dat aan Blauw geeft (en dit aantal hoeft geen geheel getal te zijn). Op deze manier ontstaat een getalrepresentatie met plaatjes, en in sommige praktijksituaties is dit nuttig.
Nu de vragen. Elk van mijn plaatjes zal een veld met gekleurde rietstengels zijn (stengels die op de grond staan zonder vertakkingen). De achtereenvolgende kleuren worden met B en R aangegeven, zodat BBR,RBRR een veld met twee rietstengels voorstelt, de eerste van onder af blauw, blauw, rood, de tweede van onder af rood, blauw, rood, rood.
(iiia) Een veld heeft waarde 0 als degene die aan zet is verliest. Het lege veld heeft waarde 0. Laat zien dat ook het veld B,R en het veld BBRBR,RRBRB de waarde 0 hebben.
(iiib) De stengel B heeft waarde 1. De stengel RR heeft waarde -2. Laat zien dat de stengel BR de waarde 1/2 heeft door het veld BR,BR,R te bekijken.
(iiic) Laat zien dat de stengel BBRR de waarde 5/4 heeft, en de stengel BRB de waarde 3/4.
(iiid) Is er een algemene regel om de waarde van een rood-blauwe stengel te vinden?
Antwoorden.
Vierde college: 990924
Besproken: Opgave.
Nauwkeurigheid van berekeningen met Mathematica.
Zie ook
Nauwkeurigheid en stabiliteit.
Spellen en getallen.
Eerste voorbeeld van een diagonaalargument:
de verzameling van reele getallen is niet aftelbaar (Cantor).
Tweede voorbeeld van een diagonaalargument:
het stopprobleem voor Turing machines is niet beslisbaar [wordt vervolgd].
(ii) Bewijs voor getallen en spelen: (a) x >= x, (b) als x >= y en y >= z dan is x >= z. (Het ongelukkige symbool >= is het groter-of-gelijk teken.)
(iii) Blauw en Rood spelen Hackenbush met alleen maar groene kanten (een groene kant mag door elk van beide gepakt worden). Wint degene die begint of niet, in de volgende situaties: (a) Een stengel GGG. (b) Een veld G,GG,GGG. (c) Een veld GGGG,GGGGG,GGG,GG. (d) Is er een algemene regel?
(ii) Vind y zodanig dat y == 11111 (mod p) en y == 99999 (mod q),
waarbij p en q de getallen uit de eerste week zijn:
p = 106603488380168454820927220360012878679207958575989291522270608237193062808643
en q = 102639592829741105772054196573991675900716567808038066803341933521790711307779.
Vijfde college: 991001
Besproken: Opgaven. Inductie (volledig en veel vollediger,
met en liefst zonder bodem). Sturmse rijen. Hash codes. Het stopprobleem
voor Turingmachines. Primitief recursieve functies.
De Ackermann functie. Partieel recursieve functies.
Zoeken volgens Boyer-Moore.
Opgave om in te leveren
De functie van Ackermann wordt als volgt gedefinieerd:
f(0,y) = y+1
f(x+1,0) = f(x,1)
f(x+1,y+1) = f(x, f(x+1,y))
A(x) = f(x,x)
Hierbij zijn x en y niet-negatieve gehele getallen.
Bereken A(n) voor n=0,1,2,3,4,...
Bereken de laatste 4 cijfers van A(10).
Hoeveel cijfers heeft A(10) ongeveer?
Zesde college: 991015
Besproken: Opgave. Time-memory tradeoff. Getaltheorie
over congruenties. Public Key Cryptography.
Opgave om in te leveren
(i) Vind x zodanig dat x == 1 (mod 2), x == 2 (mod 3), x == 3 (mod 5),
x == 4 (mod 7), x == 5 (mod 11) en x == 6 (mod 13).
(Hier betekent == `is congruent met', normaal met drie streepjes
weergegeven. Bijvoorbeeld: 25 == 4 (mod 7) omdat 25 en 4 een verschil
hebben dat een 7-voud is.)
Zevende college: 991022
Besproken: Opgave.
Matrixvermenigvuldiging volgens Strassen.
Primaliteitscertificaat.
Waarschijnlijke priemgetallen.
Jacobisymbool.
Pokeren over de telefoon. Zero-knowledge proofs.
Opgave om in te leveren
Laat zien dat de doorsnede van de Mandelbrotverzameling
met de reele rechte precies het interval [-2, 0.25] is.
(Zie dictaat, Sectie 4.4.)
Achtste college: 991029
Besproken: Opgave. Gröbner bases.
Opgave om in te leveren
Laat zien hoe je met de hand uitrekent of 37 een kwadraat is
modulo 101. Bepaal met Mathematica of p een kwadraat is modulo q,
waarbij p en q de zeer grote priemgetallen uit eerdere opgaven zijn.
Negende college: 991105
Te bespreken: Derde
voorbeeld van een diagonaalargument:
In elk consistent systeem zijn er ware beweringen die
niet bewezen kunnen worden.
Opgave.