TMV211 · Chalmers tekniska högskola

Inledande diskret matematik

Ny kurs

Kom igång gratis

Inga tentor än

Ladda upp dina tidigare tentor och få hjälp med att strukturera ditt studiematerial

Få dina tentauppgifter kategoriseradeBli guidad genom ditt studiematerialFå hjälp direkt med teori och tipsHåll koll på dina framsteg

Kurs info

Kurssida Kursplan

7.5

Språk

Svenska

Institution

matematiska vetenskaper

Lärandemål

Efter fullgjord kurs ska studenten kunnaanvända logikens språk för att formulera utsagor och avgöra sanningsvärdenföra enkla matematiska resonemang och bevisanvända induktion i bevisföringanvända grundläggande matematiska begrepp som mängder, funktioner och relationer för att formulera samband och lösa problemdefiniera talföljder rekursivtuttrycka och beräkna summor och produkter, speciellt aritmetiska ochgeometriska summorprimtalsfaktorisera heltal och bestämma största gemensamma delarelösa linjära diofantiska ekvationer och räkna med kongruenserlösa enkla kombinatoriska problem och motsvarande sannolikhetsproblemidentifiera olika typer av grafer och avgöra om två grafer är isomorfa

Kursinnehåll

Logik och bevisteknik: Grundläggande sats- och predikatlogik. Direkta bevis och motsägelsebevis. Induktion. Mängder, funktioner och relationer: Grundläggande mängdlära. Injektiva och surjektiva funktioner. Unära och binära operatorer. Ekvivalensrelationer. Partiella och totala ordningar. Talföljder, summor och produkter: Aritmetiska och geometriska summor. Rekursion. Heltalsaritmetik: Divisionsalgoritmen. Euklides algoritm. Aritmetikens fundamentalsats. Linjära diofantiska ekvationer. Kongruensrä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 lådprincip. Principen om inklusion och exklusion (sållprincipen). Grafteori: Grundläggande terminologi. Bipartita och fullständiga grafer. Träd. Riktade grafer. Eulervägar och Eulercykler. Hamiltonvägar och Hamiltoncykler. Isomorfa grafer.

Förutsättningar