CM1000 Diskret matematik 8,0 hp

Innehållet i kursen är uppdelat i obligatoriska delområden och fördjupande delområden. De obligatoriska delområdena är nödvändiga för godkänt betyg och de fördjupande delområdena ger högre betyg. Genom hela kursen finns en emfas på solid matematisk argumentation och bevisföring. Det betyder att i varje delområde av kursen sker en träning av giltiga resonemang kring begreppen i den delen av kursen. Till exempel kommer studiet av mängder att innebär studier av bevis av formler involverande mängdidentiteter.

De obligatoriska delområdena i kursen är:

• Grundläggande logik med logiska konnektiv och studier av giltig argumentation och bevismetoder.

• Inledande mängdlära med grundläggande mängdoperationer.

• Grundläggande talteori (delbarhet, kongruenser, primtal etc.).

• Funktioner, speciellt använda för att formulera isomorfibegreppet för grafer.

• Grafteori, isomorfibegreppet, träd, riktade grafer, matrisrepresentationern, eulerska kretsar och liknande begrepp. Studier av grafer för att modellera intressanta applikationer som

till exempel att I en viktad graf finna minsta uppspännande träd och kortaste vägen mellan två hörn.

• Grundläggande kombinatorik involverandes studier av multiplikationsprincipen, principen om inklusion och exklusion, binomialsatsen, permuationer och kombinationer.

De fördjupande delområdena i kursen är:

• Mer avancerade bevismetoder inom talteori såsom matematisk induktion och möjligtvis tillämpningar inom kryptering eller liknande intresseområden.

• Relationer, partiella ordningar och ekvivalensrelationer med tillämpningar och exempel från talteorin inkluderande kongruensrelationen.

• Grundläggande diskret sannolikhetslära med utfallsrum, betingad sannolikhet och oberoende händelser.

Efter godkänt betyg ska studenten kunna

* formulera grundläggande satser och definitioner av viktiga begrepp inom diskret matematik och även kunna diskutera ett urval av bevis och resulterande tillämpningar.

* tillämpa satser och metoder inom diskret matematik.

Efter kursen förväntas studenten ha en teoretisk grund för vidare studier i datateknik och

programvaruutveckling.

Kunskaper motsvarande grundläggande kurser i linjär algebra och envariabelanalys.

Bestäms inför varje kursstart

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

• RED1 - Muntlig tentamen, 3,0 hp, betygsskala: P, F
• TEN1 - Skriftlig tentamen, 5,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.

Slutbetyg A-E och det blir samma som på TEN1.

Johnny Panrike

• 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.

Ytterligare information om kursen kan hittas på kurswebben via länken nedan. Information på kurswebben kommer framöver flyttas till denna sida.