Diskreta strukturer i datavetenskap
Discrete Structures in Computer Science

EDAA40, 5.0 högskolepoäng, G1 (Grundnivå)

Gäller för: 2024/25
Fakultet: Lunds tekniska högskola
Beslutad av: Programledning C/D
Beslutsdatum: 2024-04-16
Ikraftträdande: 2024-05-08

Allmänna uppgifter

Huvudområde: Teknik Fördjupning: Grundnivå, kurs/er som inte kan klassificeras
Obligatorisk för: D1
Undervisningsspråk: Kursen ges på engelska

Syfte

Syftet med kursen är att introducera några av de mest basal formella koncepten och terminologin inom datavetenskapen och att ge ett gemensamt språkbruk, inklusive konventioner för notation och nomenklatur som senare kurser kan bygga på. Detta inkluderar en introduktion till abstrakt mängdteori, relationer, funktioner, ordnade mängder, boolesk algebra, logik och bevistekniker liksom strukturer såsom grafer och träd.

Mål

Kunskap och förståelse
För godkänd kurs skall studenten

• visa förståelse för basal notation inom mängdteori, såsom ekvivalens, kardinalitet, uppräknelighet och oändliga mängder,
• kunna karaktärisera funktioner, injektiva/surjektiva/bijektiva funktioner, partial- och totalordningar och deras egenskaper,
• förstå basala bevistekniker såsom induktion,
• vara bekant med boolesk algebra och första ordningens logik,
• förstå fundamentala strukturer som träd och grafer.

Färdighet och förmåga
För godkänd kurs skall studenten

• kunna använda notationen för mängder, relationer, funktioner och ordningar för att definiera strukturer och diskutera deras egenskaper,
• kunna använda induktion för att bevisa egenskaper hos oändliga mängder av objekt,
• kunna manipulera, transformera och förenkla booleska uttryck enligt den booleska algebrans lagar,
• kunna arbeta med träd och grafer och konstruera bevis för deras egenskaper,
• kunna implementera enkla algoritmer och test för egenskaper hos diskreta strukturer.

Värderingsförmåga och förhållningssätt
För godkänd kurs skall studenten

• kunna använda mängder, grafer och träd för att representera aspekter av verkliga problem,
• visa förmåga att ta fram en lämplig bevisstrategi för ett givet problem.

Kursinnehåll

Mängder, mängdekvivalenser, oändliga mängder, uppräkningsbarhet, funktioner, egenskaper hos funktioner (injektiva, surjectiva och bijektiva funktioner), relationer, ordningar (totala och partiella), transitivitet, (anti-) symmetri, reflexion, ekvivalensrelationer och klasser, boolesk algebra, predikatlogik, bevis, induktion, grafer, träd.

Kursens examination

Betygsskala: TH - (U, 3, 4, 5) - (Underkänd, Tre, Fyra, Fem)
Prestationsbedömning:

För godkänt betyg på kursen krävs att de obligatoriska momenten i kursen redovisats med godkänt resultat samt godkänd skriftlig tentamen. Slutbetyg i kursen bestäms av resultatet på den skriftliga tentamen.

Om så krävs för att en student med varaktig funktionsnedsättning ska ges ett likvärdigt examinationsalternativ jämfört med en student utan funktionsnedsättning, så kan examinator efter samråd med universitetets avdelning för pedagogiskt stöd fatta beslut om alternativ examinationsform för berörd student.

Moduler
Kod: 0216. Benämning: Obligatoriska moment.
Antal högskolepoäng: 2.0. Betygsskala: UG - (U, G). Prestationsbedömning: För slutbetyg på kursen krävs att de obligatoriska momenten är godkända
Kod: 0116. Benämning: Tentamen.
Antal högskolepoäng: 3.0. Betygsskala: TH - (U, 3, 4, 5). Prestationsbedömning: Resultatet på den skriftliga tentamen utgör slutbetyg i kursen. För att få slutbetyg krävs också att de obligatoriska momenten är godkända. Modulen omfattar: Skriftlig tentamen.

Antagningsuppgifter

Förkunskapskrav:

• EDAA20 Programmering och databaser eller EDAA45 Programmering, grundkurs eller EDAA50 Programmeringsteknik eller EDAA55 Programmeringsteknik eller EDAA65 Programmering eller EDAA70 Inledande programmering med Python

Kurslitteratur

• David Makinson: Sets, Logic, and Maths for Computing, 2nd ed. Springer. Boken finns också som gratis nerladdningsbar PDF/e-bok inom LTH:s nätverk: http://link.springer.com/book/10.1007%2F978-1-4471-2500-6.

Kontaktinfo

Kursansvarig: Jörn Janneck, jorn.janneck@cs.lth.se
Hemsida: https://cs.lth.se/edaa40/