SF1610 Diskret matematik 7,5 hp

Discrete Mathematics

Grundläggande kurs i diskret matematik som behandlar bl.a. elementär kombinatorisk problemlösning, några algebraiska strukturer samt elementär grafteori.

  • Utbildningsnivå

    Grundnivå
  • Huvudområde

    Matematik
    Teknik
  • Betygsskala

    A, B, C, D, E, FX, F

Kurstillfällen/kursomgångar

VT18 CINTE1 för programstuderande

VT18 TCOMK1 för programstuderande

VT19 CINTE1 för programstuderande

VT19 TCOMK1 för programstuderande

Lärandemål

Det övergripande målet är att ge grundläggande kunskaper i diskret matematik, i synnerhet goda kunskaper i elementär kombinatorik, kunskaper om någon abstrakt algebraisk struktur och dess använding, samt goda kunskaper om några utvalda avsnitt i grafteori.
Efter kursen förväntas eleven ha fått en förbättrad förmåga att lära sig, använda och tillämpa matematik i allmänhet. Eftersom matematikinlärning bl a använder sig av lösning av matematiska problem som metod, förväntas eleven också generellt ha förbättrat sin problemlösningsförmåga.

Kursens huvudsakliga innehåll

Aritmetikens fundamentalsats, Euklides algoritm och diofantiska ekvationer. Modulär aritmetik, Fermat's sats och RSA-kryptering. Mängder, funktioner, oändliga mängder och kardinaltal, pigeonholeprincipen. Induktionsbevis och rekursion. Elementär gruppteori, bl a Lagranges sats och i synnerhet den symmetriska gruppen. Boolesk algebra. Felkorrigerande koder, speciellt Hamming koder. Kombinatorik, binomial- och multinomialkoefficienter, Stirlingtal, inklusion-exklusion. Elementär grafteori, Euler- och Hamiltongrafer, matchning i bipartita grafer, planära grafer

Behörighet

Elementär linjär algebra

Rekommenderade förkunskaper

Matematikkunskaper motsvarande grundläggande kurser i matematik på högskolenivå.

Litteratur

K.Eriksson och H.Gavel: Diskret matematik och diskreta modeller.

H.Gavel;K.Eriksson/Diskret matematik fördjupning.

Examination

  • TEN1 - Skriftlig tentamen, 7,5, betygsskala: A, B, C, D, E, FX, F

TEN1 - Skriftlig tentamen, 7,5 hp, betygsskala: A, B, C, D, E, FX, F

Ges av

SCI/Matematik

Examinator

Petter Brändén <pbranden@kth.se>

Versionsinformation

Kursplan gäller från och med VT2009.
Examinationsinformation gäller från och med HT2007.