SF1631 Diskret matematik 12,0 hp

Bijektioner, injektioner, surjektioner. Principer för räkning. Pascals triangel. Linjär rekursion. Partitioner, ekvivalensrelationer. Modulär aritmetik. Kryptografi. Boolesk algebra. Grafer. Grundläggande gruppteori. Kinesiska restsatsen. Ringar, kroppar, polynom. Ändliga kroppar. Felrättande koder. Fördjupning inom något område av grafteori.

Kursens övergripande mål är att ge grundläggande kunskaper i diskret matematik: speciellt ökad förmåga i elementär kombinatorisk problemlösning, kännedom om några algebraiska strukturer samt kunskaper i elementär grafteori. I kursen övas också förmågan att föra stringenta matematiska resonemang.

Efter genomgången kurs skall man speciellt:

- Kunna tillämpa multiplikationsmetoden, additionsmetoden, principen om inklusion-exklusion, binomialkoefficienter, multinomialkoefficienter och Stirlingtal av andra slaget för att lösa kombinatoriska problem bl a rörande partitioner.

- I enkla fall kunna tillämpa pigeon hole principen (postfacks-principen).

- Kunna lösa linjära rekursionsekvationer med konstanta koefficienter samt känna till den s.k. Master satsen.

- Behärska begreppen surjektiv, injektiv och bijektiv funktion.

- Kunna beskriva och räkna med permutationer.

- Ha kännedom om förekomsten av olika kardinaltal speciellt om uppräkneliga och överuppräkneliga mängder.

- Veta hur man testar om en relation är en ekvivalensrelation och hur den inducerade partitionen uppstår.

- Kunna beräkna den största gemensamma delaren D till två tal a och b med hjälp av Euklides algoritm och därmed kunna lösa den diofantiska ekvationen ax+by=D.

- Ha grundläggande kunskaper om primtal och primtalsfaktorisering, bl a aritmetikens fundamentalsats.

- Behärska moduloräkning samt addition, multiplikation och division i ringarna Z/nZ. Kunna använda kinesiska restsatsen i samband med snabb aritmetik.

- Kunna tillämpa Fermats lilla sats och Eulers sats samt Eulers fi-funktion.

- Ha grundläggande kunskaper om matematiken i RSA-kryptering.

- Veta hur man testar om en algebraisk struktur är en grupp, ring resp kropp.

- Behärska Lagranges sats för grupper och begreppen delgrupp, sidoklass och ordning av element.

- Känna till och kunna räkna i cykliska grupper och i den symmetriska gruppen.

- Kunna använda Burnsides lemma.

- Känna till några elementära ringteoretiska begrepp som enhet, integritetsområde och nolldelare, samt kunna räkna några ringar som t ex polynomringar.

- Kunna konstruera ändliga kroppar och kunna räkna i dessa.

- Kunna konstruera felkorrigerande koder med hjälp av parity-check matriser och förstå innebörden av minimiavstånd och linjär kod.

- Kunna elementära begrepp i grafteorin såsom: isomorfi, valens, sammanhängande, stig, cykel, Hamiltongraf och Eulerväg.

- Ha elementära kunskaper om trädstrukturer.

- Ha kännedom om olika typer av färgläggningsproblem.

- Veta vad som menas med en planär graf och kunna Eulers polyederformel och Kuratowskis sats.

- Behärska Halls bröllopssats och begreppen maximal matchning och alternerande stig.

Dessutom skall eleven ha fördjupat sig i något specialområde inom främst grafteori och i samband med denna fördjupning tillämpa dessa nya insikter på något praktiskt problem. En skriftlig redovisning innehållande 2000-3000 ord med gott språk, snygg presentation och god matematik skall också presteras av eleven.

Till slut och som konsekvens av den matematik som gåtts igenom under kursen, få en ökad allmänmatematisk bildning och en ökad förståelse för styrkan i ett matematiskt tänkesätt i samband med strukturering av lösning av problem.

SF1604 Linjär algebra II.

Biggs: Discrete Mathematics, 2:nd ed.

När kurs inte längre ges har student möjlighet att examineras under ytterligare två läsår.

• LAB1 - Uppsats, 3,0 hp, betygsskala: A, B, C, D, E, FX, F
• TENA - Tentamen, 6,0 hp, betygsskala: A, B, C, D, E, FX, F
• TENB - Tentamen, 3,0 hp, betygsskala: A, B, C, D, E, FX, F

Examinator beslutar, baserat på rekommendation från KTH:s handläggare av stöd till studenter med funktionsnedsättning, om eventuell anpassad examination för studenter med dokumenterad, varaktig funktionsnedsättning.

Examinator får medge annan examinationsform vid omexamination av enstaka studenter.

Två skriftliga tentamina, TENA 6 hp och TENB 3 hp, eventuellt med möjlighet till kontinuerlig examination, samt en skriftlig uppsats, LAB1 3 hp.

Bengt Ek

• Vid grupparbete har alla i gruppen ansvar för gruppens arbete.
• Vid examination ska varje student ärligt redovisa hjälp som erhållits och källor som använts.
• Vid muntlig examination ska varje student kunna redogöra för hela uppgiften och hela lösningen.