Kursplan för

Diskreta strukturer
Discrete Structures

EDAA75, 7,5 högskolepoäng, G1 (Grundnivå)

Gäller för: Läsåret 2022/23
Fakultet: Lunds tekniska högskola
Beslutad av: Programledning C/D
Beslutsdatum: 2022-04-07

Allmänna uppgifter

Huvudområde: Teknik.
Obligatorisk för: C1
Alternativobligatorisk för: D1
Undervisningsspråk: Kursen ges på engelska

Syfte

Syftet med kursen är att introducera några av de mest grundläggande formella koncepten och terminologin inom datavetenskapen samt 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. Dessutom diskuteras grundläggande grafalgoritmer, det ges en introduktion till kombinatorik, några bevisstrategier och grundläggande ordnade strukturer som gitter och kompletta partialordningar.

Mål

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

• visa förståelse för grundläggande 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, ekvivalensrelationer
• förstå grundläggande bevistekniker såsom induktion,
• vara bekant med boolesk algebra och första ordningens logik,
• förstå fundamentala strukturer som träd och grafer,
• förstå grunderna i att konstruera algoritmer för grafer,
• känna till grundläggande koncept inom kombinatorik (t.ex. permutationer, kombinationer),
• känna till grundläggande typer av ordnade mängder, såsom gitter och kompletta partialordningar.

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,
• känna till tekniker för att konstruera grafer och några grundläggande exempel,
• kunna arbeta med permutationer och kombinationer samt använda dem i beräkningsproblem,
• kunna använda och applicera lämpliga typer av ordnade strukturer som gitter och kompletta partialordningar.

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, surjektiva och bijektiva funktioner), relationer, ordningar (totala och partiella), transitivitet, (anti-) symmetri, reflexion, ekvivalensrelationer och klasser, kompletta partialordningar, boolesk algebra, predikatlogik, bevis, induktion, grafer, träd, grafalgoritmer, kombinatorik, bevisstrategier.

Kursens examination

Betygsskala: TH - (U,3,4,5) - (Underkänd, Tre, Fyra, Fem)
Prestationsbedömning: Skriftlig tentamen. För godkänt betyg på kursen krävs också att de obligatoriska momenten i kursen redovisats med godkänt resultat. 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.

Delmoment
Kod: 0121. Benämning: Obligatoriska moment.
Antal högskolepoäng: 3. Betygsskala: UG. Prestationsbedömning: Godkända obligatoriska moment
Kod: 0221. Benämning: Tentamen.
Antal högskolepoäng: 4,5. Betygsskala: TH. 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. Delmomentet omfattar: Skriftlig tentamen.

Antagningsuppgifter

Förkunskapskrav:

• EDAA20 Programmering och databaser eller EDAA45 Programmering, grundkurs eller EDAA50 Programmeringsteknik eller EDAA55 Programmeringsteknik eller EDAA65 Programmering

Begränsat antal platser: Nej
Kursen överlappar följande kurser: EDAF10, EDAA40

Kurslitteratur

• David Makinson: Sets, Logic, and Maths for Computing, 3rd ed. Springer. Boken finns också som gratis nerladdningsbar PDF/e-bok inom LTH:s nätverk: https://link.springer.com/book/10.1007/978-3-030-42218-9.

Kontaktinfo och övrigt

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