Kalender

Kursintroduktion

Kombinatorik

Läs kapitel 1 i Böiers. Hela kapitlet är viktigt.

Mål
att kunna redogöra för följande begrepp:

• additions- och multiplikationsprincipen
• permutation och kombination
• binomialsatsen

att kunna:

• beräkna antal urval med additions- och multiplikationsprincipen
• beräkna antal urval med och utan hänsyn till ordning
• beräkna antal urval med och utan upprepning (återläggning)

Kombinatorik

Följande problem i Böiers övningsbok behandlas:

Kapitel 1: 1.2, 1.11, 1.14, 1.21, 1.18, 1.17, 1.40

Mängdlära

Böiers kap 2 och kap 3 fram till exempel 3 på sid 52.
Hela kapitel 2 är viktigt. I kapitel 3 gäller att du ska kunna använda sats 1 i enkla fall.

Mål att kunna redogöra för följande begrepp:

• elementär mängdsyntax, t.ex.  
• potensmängd
• kardinalitet
• de vanligaste binära mängdoperationerna, t.ex.
• klassiska sannolikhetsdefinitionen
• satsen om inklusion och exklusion

att kunna:

• använda Venndiagram och mängdoperationer enlig tabell sidan 39 i Böiers
• beräkna antalet element i mängder med kombinatoriska resonemang
• beräkna sannolikheter enligt klassiska sannolikhetsdefinitionen
• använda satsen om inklusion och exklusion i enkla fall

A-uppgifter:

1. Böiers 1.9
2. Bestäm antalet lösningar till ekvationen   där  är positiva heltal.
3. Bestäm antalet delmängder till .
4. Hur många permutationer finns av ?
5. Hur många av permutatinerna innehåller följden 2,3?
   
   
   

Mängdlära

Följande problem i Böiers övningsbok behandlas:

Kapitel 2: 2.1, 2.2, 2.6, 2.10, 2.13, 2.14

Kapitel 3: 3.2, 3.5

Kombinatorik och mängdlära.

B-uppgifter, se under fliken seminarieuppgifter.

Heltal

Böiers kap 4

4.1.2 och 4.1.3 kan läsas kursivt.

Mål

att kunna redogöra för följande begrepp:

• Rekursion och induktion 
• primtal, sammansatt tal, divisionsalgoritmen
• gcd, lcm
• Aritmetikens fundamentalsats

att kunna:

• genomföra enkla induktionsbevis
• programmera en rekursiv algoritm
• beräkna gcd och lcm
• lösa enkla Diofantiska ekvationer för hand

A-uppgifter:

1. Antag att du lånar 100 pengar och årsräntan är 5%. Du amorterar 10 pengar varje år. Hur mycket pengar är du skyldig efter n år? Detta kan beskrivas som en rekursiv talföljd, med startvärde 100. Ange en rekursionsformel för talföljden.
2. Rita talföljden i uppgift 1 i Mathematica. När är skulden betald?
3. Bestäm (1820,231)
4. Bestäm [1820,231]
5. Lös den diofantiska ekvationen 1820x+231y=10000

Hela tal

Följande problem i Böiers övningsbok behandlas:

Kapitel 4: 4.2, 4.3, 4.24, 4.13, 4.34, 4.48

Relationer

Böiers kap 5
Repetition: 5.1.1-5.1.2
Kursivt: Bevis Sats 1, 5.2.2, 5.2.3, 5.3.3, exempel 44-46

Mål

att kunna redogöra för följande begrepp:

• Funktion, relation, definitionsmängd och värdemängd
• Injektiv, surjektiv eller bijektiv
• Lådprincipen
• Reflexiv, symmetrisk, antisymmetrisk eller transitiv

att kunna:

• beräkna antal injektioner och bijektioner (antal surjektioner nivå AB)
• använda lådprincipen
• avgöra om relationen är reflexiv, symmetrisk, antisymmetrisk eller transitiv
• avgöra om en relation är en ekvivalensrelation och i så fall ta fram ekvivalensklasserna

A-uppgifter:

1. Betrakta de två mängderna A={1,2,3,...,10}, och B={1,2,3,4,5,6}. Hur många funktioner fins det från A till B?
2. Hur många injektiva funktioner finns det från B till A?
3. Hur många bijektiva funktioner finns det från B till B?
4. Ge ett exempel på en injektiv funktion från B till A samt ange definitionsmängd och värdemängd.
5. Ge ett exempel på en surjektiv funktion från A till B samt ange definitionsmängd och värdemängd.

Funktioner och relationer

Följande problem i Böiers övningsbok behandlas:

Kapitel 5: 5.7, 5.12, 5.13, 5.15, 5.48

Ringar

Böiers kap 6.1-3
Tonvikt på 6.3

Kursivt: Ex 7, ex 9, ex 12, 6.2.5

Mål

att kunna redogöra för följande begrepp:

• Grupp, ring, kropp
• Kongruens modulo n
• Ringen Zn, ange kongruensklasser
• Eulers fi-funktion

att kunna:

• gemomföra räkning i Zn
• beräkna invers i Zn
• beräkna antalet inverterbara element i Zn

A-uppgifter:

1. Vad innebär att en ring är nolldelarfri?
2. Vad menas med multiplikativ invers?
3. Vad är skillanden mellan en ring och en kropp?
4. Bestäm fi(2011).
5. Bestäm fi(20x11).

Mer talteori, ringar

Följande problem i Böiers övningsbok behandlas:

Kapitel 6: 6.1, 6.11, 6.12, 6.13, 6.14, 6.15, 6.25, 6.30

Heltal och relationer.

B-uppgifter, se under fliken seminarieuppgifter.

Eulers sats

Böiers kap 6.4, 6.6

Tonvikt 6.4 och exempel 35

Mål

att kunna redogöra för följande begrepp:

• Eulers sats
• RSA
• Kinesiska restsatsen

att kunna:

• gemomföra förenkling med Eulers (Fermats) sats i Zn
• Kryptera enligt RSA

A-uppgifter:

1. Vad blir 123^2010 mod 2011
2. Vad blir 13^20111111 mod 19
3. Vad är ett primitivt element?
4. Vad menas med ordningen av ett element i Zp?
5. Vad blir 13^20111111 mod 18?

Eulers och Fermats satser

Följande problem i Böiers övningsbok behandlas:

Kapitel 6: 6.37, 6.38, 6.57, 6.63, 6.39, 6.58, 6.61, 6.64

Grafteori

Böiers 9.1

Exempel 5 kan läsas kursivt

Mål

att kunna redogöra för grundläggande terminologi och definitioner i grafteori, såsom:

• G=(V,E)
• riktad, viktad graf, multigraf
• väg, cykel, grad
• kompletta grafen, komplementgraf
• sammanhängande
• isomorfa grafer
• incidensmatris, grannmatris

 att kunna

• tillämpa dessa begrepp vid problemlösning
• avgöra om två grafer är isomorfa (ankla fall)

A-uppgifter:

Med graf menas ej multigraf.

1. Kur många bågar har den kompletta grafen med 10 noder?
2. Vad menas med att två grafer är isomorfa?
3. En öglefri sammanhängande graf har 12 kanter. Hur många hörn har grafen om alla hörn har samma grad? Vilken är denna grad?
4. Bestäm incidensmatrisen till grafen på sidan 264.
5. Bestäm grannmatrisen till grafen på sidan 264.

Grafteori

Följande problem i Böiers övningsbok behandlas:

Kapitel 9: 9.14, 9.20, 9.24, 9.12, 9.21, 9.59, 9.60, 9.70, 9.79

Heltal, relationer, algebra.

B-uppgifter, se under fliken seminarieuppgifter.

Eulergrafer, Hamiltongrafer, planära grafer

Böiers 9.2, 9.3, 9.4

Mål

att kunna redogöra och tillämpa för följande begrepp:

• Eulergraf, Eulercykel, Eulerväg
• Hamiltongraf, Hamiltoncykel, Hamiltonväg
• planär graf
• Eulers polyederformel
• homeomorfa grafer

att kunna

• tillämpa ovanstående begrepp i problemlösning

A-uppgifter:

1. Vad menas med Eulergraf, Hamiltongraf, Planär graf?
2. Vilka av graferna i uppgift 9.22 är Eulergrafer?
3. Ge exempel på en graf med minst fem hörn som har en Hamiltonväg men ingen Eulerväg?
4. En öglefri sammanhängande planär graf med 16 kanter. Om alla hörn har grad 4, hur många delytor avgränsas av grafen?
5. Vad menas med att två grafer är homeomorfa?

Grafteori, forts.

Följande problem i Böiers övningsbok behandlas:

Kapitel 9: 9.31, 9.37, 9.75, 9.76, 9.81, 9.84

Träd, färgning

Böiers kap 9.5

Mål

att kunna redogöra för följande begrepp:

• träd, uppspännande träd
• kromatiskt tal, kromatiskt polynom
• kontraktion
• fyrfärgssatsen

att kunna:

• använda Kruskal's algoritm
• använda Dijkstra's algoritm
• bestämma kromatiskt tal
• bestämma kromatiskt polynom
• tillämpa färgning i enkla fall

A-uppgifter:

1. Vad menas med kromatiskt tal och kromatiskt polynom?
2. Vad menas med en kontraktion?
3. Vad innebär fyrfärgsproblemet? Vad är lösningen?
4. Vad är kromatiska talen för graferna på sidan 256?
5. Nämn ett praktiskt problem där färgning kan tillämpas?

Repetition