Kursplan för Inledande diskret matematik

Kursplan fastställd 2021-02-26 av programansvarig (eller motsvarande).

Kursöversikt

  • Engelskt namnIntroduction to discrete mathematics
  • KurskodTMV211
  • Omfattning7,5 Högskolepoäng
  • ÄgareTKDAT
  • UtbildningsnivåGrundnivå
  • HuvudområdeMatematik
  • InstitutionMATEMATISKA VETENSKAPER
  • BetygsskalaTH - Mycket väl godkänd (5), Väl godkänd (4), Godkänd (3), Underkänd

Kurstillfälle 1

  • Undervisningsspråk Svenska
  • Anmälningskod 49113
  • Sökbar för utbytesstudenterNej
  • Endast studenter med kurstillfället i programplan.

Poängfördelning

0120 Tentamen 7,5 hp
Betygsskala: TH		7,5 hp
  • 21 Okt 2023 em J
  • 04 Jan 2024 fm J
  • 30 Aug 2024 em J

I program

Examinator

Gå till kurshemsidan (Öppnas i ny flik)

Behörighet

Grundläggande behörighet för grundnivå
Sökande med en programregistrering på ett program där kursen ingår i programplanen undantas från ovan krav.

Särskild behörighet

Samma behörighet som det kursägande programmet.
Sökande med en programregistrering på ett program där kursen ingår i programplanen undantas från ovan krav.

Syfte

Kursen ger grundläggande kunskaper om diskreta matematiska strukturer som behövs för högskolestudier, främst sådana som har anknytning till datorer och programering.

Lärandemål (efter fullgjord kurs ska studenten kunna)

Efter fullgjord kurs ska studenten kunna

  • använda logikens språk för att formulera utsagor och avgöra sanningsvärden
  • föra enkla matematiska resonemang och bevis
  • använda induktion i bevisföring
  • använda grundläggande matematiska begrepp som mängder, funktioner och relationer för att formulera samband och lösa problem
  • definiera talföljder rekursivt
  • uttrycka och beräkna summor och produkter, speciellt aritmetiska och
    geometriska summor
  • primtalsfaktorisera heltal och bestämma största gemensamma delare
  • lösa linjära diofantiska ekvationer och räkna med kongruenser
  • lösa enkla kombinatoriska problem och motsvarande sannolikhetsproblem
  • identifiera olika typer av grafer och avgöra om två grafer är isomorfa

Innehåll

- Logik och bevisteknik: Grundläggande sats- och predikatlogik. Direkta bevis och motsägelsebevis. Induktion.
- Mängder, funktioner och relationer: Grundläggande mängdlära. Injektiva och surjektiva funktioner. Unära och binära operatorer. Ekvivalensrelationer. Partiella och totala ordningar.
- Talföljder, summor och produkter: Aritmetiska och geometriska summor. Rekursion.
- Heltalsaritmetik: Divisionsalgoritmen. Euklides algoritm. Aritmetikens fundamentalsats. Linjära diofantiska ekvationer. Kongruensräkning. Kinesiska restsatsen. Eulers sats och Fermats lilla sats. RSA-kryptering.
- Kombinatorik: Additions- och multiplikationsprinciperna. Permutationer. Ordnade och oordnade urval (kombinationer). Binomialkoefficienter och binomialsatsen. Multinomialkoefficienter. Dirichlets lådprincip. Principen om inklusion och exklusion (sållprincipen).
- Grafteori: Grundläggande terminologi. Bipartita och fullständiga grafer. Träd. Riktade grafer. Eulervägar och Eulercykler. Hamiltonvägar och Hamiltoncykler. Isomorfa grafer.

Organisation

Undervisningen bedrivs i form av föreläsningar och övningspass. Studenterna förväntas också arbeta självständigt (individuellt eller i grupp).

Litteratur

Kurslitteratur meddelas via kurshemsidan senast två veckor före kursstart.

Examination inklusive obligatoriska moment

Kursen examineras genom skriftlig tentamen. Duggor och redovisningsuppgifter som ger bonuspoäng kan förekomma.

Kursens examinator får examinera enstaka studenter på annat sätt än vad som anges ovan om särskilda skäl föreligger, till exempel om en student har ett beslut från Chalmers om pedagogiskt stöd på grund av funktionsnedsättning.