Discrete Wiskunde en Programmeren, najaar 2003

Voor de kwartalen 5 en 6 (het derde semester) ziet het rooster er zo uit:

• section 1.1: Exercises 23 and 53
• section 1.2: Exercise 45 (niet alleen Ja of Nee, ook een reden geven)
• section 1.3: Exercises 59 and 70
• section 1.4: Exercise 24
• section 1.5: Exercise 5

• section 2.1: Exercise 78
• section 2.3: Exercise 49
• section 2.4: Exercise 35
• section 2.5: Exercise 41
• section 2.8: Exercise 77
• Verzin een formule voor de uitkomst als functie van het natuurlijke getal n van de som over 1/P(S), waar de som loopt over alle niet-lege deelverzamelingen van {1,2,3,..,n} en waar P(S) het product van de elementen van S aangeeft.

1. Opwarmertje.
   Een natuurlijk getal N is een driehoeksgetal wanneer je het kunt verkrijgen als het aantal punten in een driehoekje dat ontstaat door op de eerste rij 1 punt te plaatsen, op de tweede rij 2, enzovoorts.
   1. Maak in magma op drie verschillende wijzen de verzameling van alle driehoeksgetallen onder de 500.
   2. Maak in magma op twee manieren de verzameling van getallen n onder de 500 waarvoor n^2 - 1 een produkt van twee priemgetallen is.
   3. Bepaal of de doorsnede van de in onderdelen a en b genoemde verzamelingen leeg is of niet.
2. IsPrime(n) is een functie in magma die kan bepalen of een getal n een priemgetal is. Hiermee is de verzameling van alle priemgetallen die kleiner zijn dan 1000 te maken. Bijvoorbeeld:
   
       P := { p : p in [1..1000] | IsPrime(p) };
   
   
   1. Maak in magma de verzameling van alle priemgetallen die kleiner zijn dan 1000 door de Zeef van Eratosthenes te gebruiken. (Hint: zie opgave 82 blz 63.)
   2. Implementeer in magma een functie die gegeven een grens N alle priemgetallen kleiner dan N geeft (met de Zeef).
3. In hoofdstuk 3 paragraaf 3 wordt het Euclidische algoritme gegeven. Vorig jaar is behandeld dat er een uitgebreid Euclidisch algoritme is dat bij geven gehele getallen a en b, ook gehele getallen s en t vindt zodat
   
       s·a + t·b = ggd(a,b).
   
   Implementeer het uitgebreide Euclidische algoritme in magma.
4. De machtsverzameling (oftewel powerset) van een verzameling U is de collectie van alle deelverzamelingen van U. Voorbeeld: als U = {1,2,3} dan is
   
       { {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} }
   
   de machtsverzameling van U.
   1. Implementeer in magma een functie die met behulp van recursie de machtsverzameling van een gegeven verzameling geeft. Noem deze functie rpowerset.
   2. Implementeer in magma een functie die ZONDER recursie de machtsverzameling van een gegeven verzameling geeft. Noem deze functie ipowerset. (i staat voor inductief.)
5. Bekijk de verzameling W van strings die alleen maar bestaan uit de karakters "a" en "b". (Merk op dat de ``lege'' string "" ook in W zit.) De verzameling W heeft met de operatie concatenatie een structuur die lijkt op die van een groep:
   1. Voor ieder element w uit W geldt
      
          w cat "" = "" cat w = w.
      
      
   2. Als u en v in W dan geldt
      
          u cat v
      
      in W.
   Het enige dat je niet kunt is een inverse van een string nemen in W. (Dat wil zeggen: niet voor elk element u uit W bestaat er een v uit W zodat u cat v = v cat u = "".) We gaan nu "aa" als de `inverse' van "b" nemen. Als een element w van W ergens de substring "aab" of "baa" heeft dan mogen we die weglaten. Laat bijvoorbeeld w = "aaababbba" dan mogen we herschrijven w = "bba". We zeggen dat w van normaalvorm is als in w de substring "aab" en "baa" niet voorkomen.
   1. Implementeer in magma een functie die van een gegeven string w uit W de normaalvorm geeft.
   2. Implementeer in magma een functie die een rechtsinverse van een string uit W geeft als we "aa" zien als de inverse van "b".

• section 4.1: Exercise 58
• section 4.2: Exercise 72
• section 4.6: Exercises 23 en 29
• section 4.7: Exercise 15, 28 (vind een alternatieve methode!), en 29
• section 4.8: Exercise 27

• Implementeer in Magma: Algoritme 4.3.9 (blz. 189)
• Implementeer in Magma: Algoritme 4.3.14 (blz. 190)
• section 4.3: Exercise 22 (in magma)

• Bedenk een algoritme voor het betegelen van een door een rechthoekig polygoon begrensd tegeloppervlak door een gegeven (verzameling) rechthoekige tegel(s). .

• section 6.1: Exercise 45 (maar let op: in sommige edities van het boek ontbreekt een deel van het plaatje boven Exercise 43, namelijk rode horizontale lijntjes).
• section 6.1: Exercise 48
• section 6.2: Beantwoord de volgende vragen (in de stijl van Exercises 10--18). Teken een graph met de volgende eigenschappen, of laat zien dat deze niet bestaat:
  • Een enkelvoudige (=simpele) graph met 5 punten, waarvan de graden 2,2,4,4,4 zijn;
  • Een enkelvoudige (=simpele) graph met 5 punten, waarvan de graden 2,3,4,4,4 zijn;
  • Een enkelvoudige (=simpele) graph met 5 punten, waarvan de graden 2,3,3,4,4 zijn;
  • Een samenhangende (=verbonden) graph met 5 punten, waarvan de graden 2,2,4,4,4 zijn;
  • Een samenhangende (=verbonden) graph met 5 punten, waarvan de graden 2,3,4,4,4 zijn;
  • Een samenhangende (=verbonden) graph met 5 punten, waarvan de graden 2,3,3,4,4 zijn.
• section 6.2: Exercise 58
• section 6.2: Exercise 59
• section 6.2: Exercise 60
• section 6.3: Exercise 11

• section 6.3: Exercise 35
• section 6.4: Exercise 5
• section 6.5: Exercises 12, 14, 21, 25

• Maak met het graph-datatype van Magma de graph op blz 293 van het boek. (Gebruik eventueel `labelled graphs'.)
• Implementeer Dijkstra's algoritme 6.4.1 in Magma (voor graphs als in het vorige onderdeel) en vind er het kortste pad van a naar z in de graph op blz 293 mee.

• section 6.6: Exercises 3, 5, 17, 22, 28
• section 6.7: Exercise 2