Overordnede kursusmål:

Formålet med kurset er at introducere matematik, der anvendes ved analyse, design og verifikation af diskrete systemer, herunder anvendelser indenfor programmeringsprog for computersystemer.

Efter at have gennemført kurset, er den studerende i stand til at udføre følgende:
- Forstå og anvende formelle repræsentationer i diskret matematik.
- Forstå og anvende formelle repræsentationer i problemer, der løses med diskret matematik.
- Forstå metoder til løsning af problemer i diskret matematik.

- Anvende metoder til løsning af problemer i diskret matematik, herunder anvende programmeringssprog som værktøj.

Efter at have gennemført kurset, kan den studerende definere følgende begreber og anvende disse på nye problemer.

Mængder og logiske udtryk:
Definer mængde, logiske operationer, logiske udtryk og sandhedstabel for logiske udtryk; anvende reduktionsregler for logiske udtryk.

Relationer og funktioner:
Definer cartesisk produkt og ækvivalensrelation og anvende disse; definer og anvende funktioner.

Naturlige tal og induktion:
Definer naturlige tal; anvende induktion til verification af egenskaber for naturlige tal.

Division og faktorisering:
Definer primtal og anvende Euklids algoritme til faktorisering af heltal.

Grundlæggende talteori
Definere og anvende modulær aritmetik og kinesisk restklassesætning.

Regulære sprog:
Definer et regulært sprog ud fra elementer i en mængde; generere strenge fra et regulært sprog; konstruere eksempler på regulære sprog.

Endelig tilstandsmaskiner, analyse:
Definer endelig tilstandsmaskine som 6-tuple; tabel eller graf repræsentation af endelig tilstandsmaskine; minimere antal tilstande i endelig tilstandsmaskine.

Endelig tilstandsmaskiner, syntese:
Genkendelse af symbolsekvens; konstruer endelig tilstandsmaskine for given anvendelse.

Læringsmål:

En studerende, der fuldt ud har opfyldt kursets mål, vil kunne:

• Forklare og anvende mængder og logiske udtryk svarende til det specifikke kursusindhold.
• Forklare og anvende relationer og funktioner, svarende til det specifikke kursusindhold.
• Forklare og anvende naturlige tal og induktion, svarende til det specifikke kursusindhold.
• Forklare og anvende division og faktorisering, svarende til det specifikke kursusindhold.
• Forklare og anvende grundlæggende talteori, svarende til det specifikke kursusindhold.
• Forklare og anvende regulære sprog, svarende til det specifikke kursusindhold.
• Forklare og analysere endelig tilstandsmaskiner, svarende til det specifikke kursusindhold.
• Forklare og syntetisere endelig tilstandsmaskiner, svarende til det specifikke kursusindhold.

Kursusindhold:

Mængder og logiske udtryk; reduktionsregler for logiske udtryk; relationer og funktioner; ækvivalensrelationer; naturlige tal; induktion til verifikation af egenskaber ved naturlige tal; primtal og Euklids algoritme til faktorisering; modulær aritmetik og den kinesiske restklassesætning; dannelse af et sprog fra elementerne af en mængde; regulært sprog; strenge fra et regulært sprog; eksempler på regulære sprog; endelig tilstandsmaskine som 6-tuple; graf eller tabelbeskrivelse af endelig tilstandsmaskine; genkendelse af symbols strenge med endelig tilstandsmaskine; minimering af antal tilstande i endelig tilstandsmaskine; endelig tilstandsmaskine for given anvendelse.

Litteraturhenvisninger:

Open source kursusmateriale samt supplerende noter distribueres i løbet af kurset.

Bemærkninger:

Mundtlig eksamen baseret på præsentation af miniprojekt, udarbejdet I løbet af kurset og diskussion af løsning på et problem løst af den studerende. Problemerne meddeles ved starten af kurset.

Kursusansvarlig:

John Aasted Sørensen , jaas@dtu.dk