SF1662 Diskret matematik 7,5 hp

Discrete Mathematics

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

  • Utbildningsnivå

    Grundnivå
  • Huvudområde

    Teknik
  • Betygsskala

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

Kurstillfällen/kursomgångar

VT19 för programstuderande

VT20 för programstuderande

Lärandemål

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.
Mer precist förväntas studenten efter genomgången kurs:

  • Förstå och kunna använda divisionsalgoritmen för heltal, polynom och gaussiska heltal.
  • Kunna använda Euklides algoritm för att beräkna den största gemensamma delaren till två tal a och b och därmed kunna lösa den diofantiska ekvationen ax+by=c.
  • Kunna använda Euklides algoritm också för polynom och gaussiska heltal
  • Behärska moduloräkning samt addition, multiplikation och division i ringarna Z/nZ.
  • Ha grundläggande kunskaper om primtal och primtalsfaktorisering, bl a aritmetikens fundamentalsats.
  • Ha kunskaper om entydig faktorisering av polynom och gaussiska heltal.
  • Kunna tillämpa Fermats lilla sats.
  • Ha grundläggande kunskaper om matematiken i RSA-kryptering.
  • Kunna använda rekursiva definitioner och induktionsprincipen för att verifiera enkla matematiska samband.
  • Behärska elementär mängdlära och veta hur man kan räkna med snitt, union, komplement, mängdskillnad och universa.
  • Kunna använda begreppen injektion, surjektion och bijektion, samt känna till sambandet mellan kardinalitet och bijektioner.
  • Ha kännedom om förekomsten av olika kardinaltal speciellt om uppräkneliga och överuppräkneliga mängder.
  • Veta hur man testar om en binär relation är en ekvivalensrelation och hur den inducerade partitionen uppstår.
  • Veta hur man testar om en binär relation är en partialordning.
  • Kunna tillämpa multiplikationsmetoden, additionsmetoden, principen om inklusion-exklusion, binomialtal, multinomialtal och Stirlingtal av andra slaget för att lösa kombinatoriska problem bl a rörande partitioner.
  • I enkla fall kunna tillämpa postfacksprincipen (the pigeonhole principle).
  • Veta hur man testar om en algebraisk struktur är en grupp resp ring.
  • Kunna beskriva och räkna med permutationer.
  • 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 grupper och deras verkan på mängder för att lösa vissa kombinatoriska problem.
  • Känna till några elementära ringar, bl.a. polynomringar.
  • Kunna elementära begrepp i grafteorin såsom: isomorfi, valens, sammanhängande, stig, cykel, hamiltoncykel och eulerkrets.
  • Ha elementära kunskaper om trädstrukturer.
  • 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.
  • Tillämpa kursens matematiska innehåll i problemlösning.
  • Som konsekvens av den matematik som gåtts igenom under kursen, ha fått 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

Kursens huvudsakliga innehåll

Aritmetik, mängdlära, funktioner och relationer, modulär aritmetik, grundläggande kombinatoriska metoder, elementär gruppteori, ringar, polynom samt grundläggande grafteori.

Behörighet

Allmän och särskild behörighet för civilingenjörsprogram.

Litteratur

K.Eriksson och H.Gavel: Diskret matematik och diskreta modeller.
K.Eriksson och H.Gavel:Diskret matematik fördjupning.
Kompletterande material distribueras under kursens gång.

Examination

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

Krav för slutbetyg

Skriftlig tentamen, eventuellt med möjlighet till kontinuerlig examination.

Ges av

SCI/Matematik

Examinator

Maurice Duits <duits@kth.se>

Versionsinformation

Kursplan gäller från och med HT2016.
Examinationsinformation gäller från och med HT2011.