LMA100. Läsanvisningar i Diskret matematik

Kapitel 1

Detta kapitel är mest av introduktionskaraktär och läses huvudsakligen kursivt.

1.1

Något bör man väl fascineras av talmanipulation. Talet 142857 fick jag faktiskt Annika Lantz att roa sig med i Morgonpasset 2000-02-02.

1.2

En introduktion till binära tal - ser du det?

1.3

Delbarhetstester var nog mera välkända före miniräknarnas intåg; jag lärde mig dessa, utom den för 7, av min mor (som inte är matematiker) redan i småskoleåldern. Jag betraktar inte detta som onyttig kunskap eftersom det har starka samband med positionssystemet. Kan du formulera liknande kriterier för tal skrivna i bas 8, t.ex.?

1.4

Detta ligger väl utanför den diskreta matematiken. Dock skall man förstås kunna lösa andragradsekvationer, och det är en liten besvikelse att han inte härleder den formel han ger på s. 19 vilket ju görs genom kvadratkomplettering, som man ju bör känna till. Övning 1.26 visar ett sätt att beräkna kvadratrötter approximativt som vi återkommer till i kapitel 5.

Kapitel I

Kapitel 2

Kapitel 3

Detta är ett av huvudnumren i kursen. Kombinatorik handlar om att svara på frågan "Hur många?" i olika sammanhang och inte minst om att visa identiteter genom att räkna samma sak på olika sätt.

3.1

Här presenteras Multiplikationsprincipen och Additionsprincipen samt permutationer och kombinationer vilket handlar om val med resp. utan hänsyn till ordningen.
Dessvärre finns ett feltryck i Stirlings formel s. 129: (n/e) skall höjas till n, inte bara till 2!
Fakulteter n! växer väldigt snabbt, och formeln (3.8) är sällan särskilt lämplig för beräkningar, utan man bör använda (3.9) efter att först utnyttjat (3.10) så att man kan välja det mindre av talen r och n - r. Märk att (3.8) inte bör betraktas som definition av C(n, r) utan som ett sätt att beräkna den; definitionen gavs ovan apropå kapitel I.
Egenskaperna (3.10) och (3.11) liksom att summan av C(n, r) då r går från 0 till n är lika med 2ⁿ (se övn. 3.54 s. 145) bör visas kombinatoriskt.

3.2

Ger den viktiga binomialsatsen med bevis och sättet att organisera binomialkoefficienterna i Pascals triangel samt några av dennas egenskaper. Bevisa (3.21) kombinatoriskt.

3.3

Lådprincipen hänförs mycket riktigt ofta till Dirichlet, som dock inte var fransman utan tysk. I all sin enkelhet är denna princip mycket användbar; som de många exemplen visar, gäller det att vara uppmärksam på möjligheterna att använda den, och det är det, inte principen själv, som är det svåra!

3.4

Principen om inklusion-exklusion handlar om hur man räknar antalet element i en union av två (eller flera) mängder; vad det gäller är att elementen i snittet räknas två gånger om man bara adderar antalet element i var och en av de två mångderna. För fler än två mängder kan räkna genom att använda tvåmängdsprincipen upprepade gånger eller genom att gå direkt på formler som (3.27) och (3.29) eller deras alternativa former (3.28) och (3.30).
Den mest avancerade användningen av principen ser vi i ex. 3.21 och 3.22 s. 166-168; ordboken översätter derangement med oordning, men här bör vi nog använda en teknisk term, så jag föreslår derangemang även på svenska. I formeln i övn. 3.99 s. 169 är uttrycket inom parentes mycket nära 1/e; se övn. 3.102 s. 170.

3.5

Idéerna i detta avsnitt ligger mycket nära vad vi redan sett i kap. 3; det räcker om du läser 3.5.1. Sannolikhetslära återkommer i en delkurs i LMA200.

Kapitel 4

Tar upp (felupptäckande och felrättande) koder och kryptering, vilka båda har viktiga tillämpningar när det gäller överföring av information; koderna för att se till att informationen kommer fram rätt och krypteringen för att inte obehöriga skall komma åt den.

4.1

Vi skall bara intressera oss för binära koder, så det räcker att du läser t.o.m. ex. 4.3 s. 200-202. Avsnitt 4.1.3 kan läsas kursivt för allmänbildningens skull.

4.2

Ger de grundläggande idéerna kring upptäckande och rättning av fel.

4.3

Här introduceras matriser som ett praktiskt beteckningssätt; mer om matriser kommer i delkursen Geometri och linjär algebra.
Linjära koder eller gruppkoder är sådana där summan av två kodord alltid är ett kodord och vi får här se hur avkodning av mottagna ord är särskilt enkel för sådana koder. Avsnitt 4.3.5 kan du hoppa över, även om ex. 4.22 (d) ger precis den kod som används för att lösa tipsproblemet: hur kan man vara säker på att få 12 rätt på tips genom att tippa 3¹⁰ välvalda rader?

4.4

Kan läsas kursivt som allmänbildning.

4.5

Hoppar vi över.

4.6

Mer om kryptering finns i Juliusz' stencil Restaritmetiker. Jag kommer också att dela ut ett kapitel ur samlingen Välj specialarbete i matematik, utgiven av Institut Mittag-Leffler och redigerad av Dan Laksov.

Kapitel 5

Iteration och rekusion är två mycket viktiga idéer, inte minst i datorsammanhang, eftersom datorn är unikt lämpad för det tradiga arbetet att upprepa samma procedur många gånger.

5.1

Newton-Raphsons metod är en välkänd iterativ metod och leder bl.a. till ett sätt att beräkna kvadratrötter som var känt för babylonierna för 4000 år sedan och som används i dagens miniräknare.
Övningar: 5.1 samt:
Använd den babyloniska metoden längst ned på s. 272 för att beräkna närmevärden på kvadratroten ur 2. Använd startvärdet x₀ = 1 och räkna exakt, dvs. skriv x_n som ett bråk a_n/b_n, åtminstone för n < 4. Visa också att a_n² - 2b_n² = 1, dvs. att (a_n, b_n) satisfierar Pells ekvation x² - 2y² = +1. Försök också att finna fler heltalslösningar till den ekvationen.

5.2

Givet ett rekursivt samband (eller differensekvation) är det alltid möjligt att beräkna x_n genom att börja med x₀ och räkna sig fram till x_n men ofta vill man kunna få en direkt formel för x_n utan att behöva gå igenom denna procedur. Detta avsnitt behandlar första ordningens differensekvationer med bankkonton som ett typiskt exempel; andra exempel är populationstillväxt och radioaktivt sönderfall. I samtliga fall gäller exponentiellt växande (eller avtagande).
Övningar: 5.5, 6, 7, 8, 11, 14, 19, 22

5.3

Här behandlas andra ordningens linjära differensekvationer med konstanta koefficienter med Fibonaccitalen som det främsta exemplet. Som synes av exempel och övningar dyker Fibonaccitalen upp i en mängd olika sammanhang.
Övningar: 5.33, 34, 39, 42, 45, 46

5.4

Tar vi inte upp nu; det kan du återvända till i samband med delkursen Geometri och linjär algebra 2 i LMA200.