Diskret matematik
Discrete Mathematics

FMA091F, 7,5 högskolepoäng

Gäller från och med: Höstterminen 2021
Beslutad av: FN1/Anders Gustafsson
Datum för fastställande: 2013-11-15

Allmänna uppgifter

Avdelning: Matematik (LTH)
Kurstyp: Gemensam kurs, avancerad nivå och forskarnivå
Kursen ges även på avancerad nivå med kurskod: FMA091
Undervisningsspråk: Engelska

Syfte

Syftet med kursen är att behandla några grundläggande delar av den diskreta matematiken, av betydelse inom datavetenskap, informationsteori, signalbehandling, fysik och många andra tekniska och naturvetenskapliga ämnen. Syftet är vidare att utveckla studenternas förmåga att lösa problem och att tillgodogöra sig matematisk text. Kursen ska också ge matematisk allmänbildning.

Mål

Kunskap och förståelse

För godkänd kurs skall doktoranden

• kunna förstå och med egna ord tydligt definiera de centrala begreppen inom kombinatorik, talteori, grafteori, funktioner och relationer, samt teorin för ändliga kroppar.
• kunna med egna ord beskriva de logiska sammanhangen mellan förekommande begrepp (satser och bevis).
• med säkerhet kunna utföra standardmässiga beräkningar inom kursens ram.
• i praktiska situationer med säkerhet kunna identifiera olika kombinatoriska urvalssätt: med/utan återläggning, med/utan hänsyn till ordning.
• förstå hur resultat för ändliga kroppar och linjär algebra kan användas inom kodning.

Färdighet och förmåga

För godkänd kurs skall doktoranden

• kunna visa förmåga att identifiera problem som kan lösas med metoder från diskret matematik och välja lämplig metod.
• i samband med problemlösning kunna visa förmåga att integrera kunskaper från de olika delarna i kursen.
• med adekvat terminologi, lämpliga beteckningar, väl strukturerat och logiskt sammanhängande kunna redogöra för lösningen till ett problem.
• kunna använda grundläggande satser inom grafteori för att dra slutsatser om en given graf (av måttlig storlek).

Kursinnehåll

Talteori: Delbarhet. Primtal. Euklides algoritm. Kinesiska restsatsen. Modulär aritmetik. Mängder, funktioner och relationer: Injektiv, surjektiv och bijektiv funktion. Invers funktion. Ekvivalensrelationer. Kombinatorik: De fyra fallen dragning med/utan återläggning, med/utan hänsyn till ordning. Binomialkoefficienter. Principen om inklusion och exklusion. Metoden med genererande funktion. Rekursion: Rekursionsformler och differensekvationer. Ringar och kroppar: Definition. Tillämpningar på kodningsteori. Grafteori: Terminologi och grundläggande begrepp. Euler- och Hamilton-grafer. Kombinatorik: De fyra fallen dragning med/utan återläggning, med/utan hänsyn till ordning. Binomialkoefficienter. Principen om inklusion och exklusion. Metoden med genererande funktion. Grafteori: Terminologi och grundläggande begrepp. Euler- och Hamilton-grafer. Tillämpningar i kodningsteori.

Kurslitteratur

• Grimaldi, Ralph P.: Discrete and Combinatorial Mathematics: Pearson New International Edition. 2013. ISBN 9781292022796.
• Andersson, K.: Finite Fields and Error-Correcting Codes.. Matematikcentrum, 2015.

Tillgänglig som pdf-fil på nätet. 54 sidor.

Kursens undervisningsformer

Undervisningsformer: Föreläsningar, seminarier, övningar

Kursens examination

Examinationsformer: Skriftlig tentamen, muntlig tentamen
Betygsskala: Underkänd, godkänd
Examinator:

Antagningsuppgifter

Förutsatta förkunskaper: FMAB65 Endimensionell analys och FMAB20 Linjär algebra

Kurstillfällesinformation

Kontaktinformation och övrigt

Kursansvariga:
Hemsida: http://www.maths.lth.se/utbildning/matematiklth/