College Computer Algebra

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

Opgaven om in te leveren

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  *

(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

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,9

Tweede college: 990910

Opgave om in te leveren

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

Opgaven om in te leveren

(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

Opgaven om in te leveren

(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?

Antwoorden.

Vijfde college: 991001

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)

Antwoorden.

Zesde college: 991015

Opgave om in te leveren

(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.

Zevende college: 991022

Opgave om in te leveren

Antwoorden.

Achtste college: 991029

Duizend dollar probleem