MA0301 Elementær diskret matematikk

Faglærer: Øyvind Bakke (e-post), Sentralbygg 2, 12. etasje, rom 1234. Telefon (735)98126.
Øvingslærere: Kristin Krogh Arnesen (e-post), Bernt Galtrud (e-post), Andreas Norling (e-post), Hans Christian Schrøder (e-post)
Referansegruppe: Runar Buvik (e-post), Henrik Goldsack (e-post), Solfrid Møllenes Haugen (e-post)

Eksamen 2010 høst

Bokmål
English

Løsningsforslag

Eksamen vår 2010

Bokmål
Nynorsk
English

Løsningsforslag

Sensur – midtsemesterprøve regnet med hvis det er til fordel for kandidaten

Meldinger

Veiledning før eksamen

Du kan stille spørsmål fra pensum til øvingslærerne. Tid og sted:

TidRomLærer
Torsdag 27. mai kl. 10–12734, 7. etasje, Sentralbygg 2Andreas
Torsdag 27. mai kl. 12–14734, 7. etasje, Sentralbygg 2Hans Chr.
Mandag 31. mai kl. 10–12734, 7. etasje, Sentralbygg 2Bernt
Mandag 31. mai kl. 12–14734, 7. etasje, Sentralbygg 2Kristin

Du kan også stille spørsmål til faglærer – muntlig eller via e-post. (18.5.2010)

Repetisjon

Det nærmer seg slutten av undervisningen. Vi tar sikte på repetisjon i siste forelesning. Send forslag til temaer eller oppgaver på e-post (seinest tirsdag). (19.4.2010)

Forskyvning av øvingsopplegget

Etter påske har fredagsgruppene øvingen før mandagsgruppen. Fredagsgruppa har øving 11 i uke 14, mandagsgruppa har den i uke 15. (27.3.2010)

Har du nok godkjente øvinger?

Du må ha minst åtte godkjente øvinger for å kunne gå opp til eksamen. Sjekk om du har nok øvinger. (27.3.2010)

Midtsemesterprøven

Bokmål
Nynorsk
Engelsk

Fasit

Resultater
Fordeling av antall rette

(15.3.2010)

Pensum for midtsemesterprøven

Pensum er det fra kapittel 1–5 som står i den foreløpige pensumlista.

Midtsemesterprøve

Det blir midtsemesterprøve tirsdag 9. mars kl. 8–10. Prøven begynner kl. 8.15, men møt opp kl. 8.00 for registrering. De som har etternavn som begynner på bokstavene A–J møter på S8, og de som har etternavn som begynner på bokstavene K–Å møter på S6. Husk legitimasjon!

Hvis det er til fordel for kandidaten, vil midtsemesterprøven telle 20 % av sluttkarakteren. Hvis ikke, eller hvis kandidaten ikke møter til midtsemesterprøven, teller eksamenskarakteren 100 %. Det vil ikke bli avholdt noen utsatt midtsemesterprøve.

Midtsemesterprøven vil være en flervalgsprøve, der svarene krysses av på oppgavearket og leveres inn etter prøven. Alle får samme oppgaver og svaralternativer, men rekkefølgen vil variere fra svarark til svarark.

Det vil bli opplyst om pensum for midtsemesterprøven seinere. Tillatte hjelpemidler er eksamenskalkulatoren.

Studenter med krav på tilrettelegging skal melde inn behov ved instituttkontoret seinest onsdag 3. mars. Ta kontakt med Berit Rau (e-post, tlf. 73591661) ved instituttkontoret (7. etasje, Sentralbygg 2). Du må søke om tilrettelegging hvis du ennå ikke har gjort det. Det gis 20 minutter for enkelt forlenget tid og 40 minutter for dobbelt forlenget tid. (15.2.2010)

Referansegruppe

Det er opprettet en referansegruppe (se toppen av sida). Ta kontakt med den hvis du har synspunkter på undervisningen. Du kan selvfølgelig også ta kontakt med faglærer eller øvingslærer. (15.2.2010)

Første forelesning

Første forelesning er tirsdag 12. januar kl. 8.15 i S8. (6.1.2010)

Om kurset

Generell informasjon

Eksamen

Eksamensdato er tirsdag 1. juni 2010 kl. 9.00. Eksamen er 4 timer skriftlig. Ingen trykte eller håndskrevne hjelpemidler er tillatt. Kalkulatoren HP 30S eller Citizen SR-270X er tillatt.

For å kunne gå opp til eksamen, må du ha fått godkjent minst 8 øvinger. Minst 12 øvinger vil bli gitt.

Midtsemesterprøve vil bli avholdt. Midtsemesterprøven teller 20 % av sluttkarakteren (eksamen teller 80 %), men bare hvis dette er til fordel for kandidaten. Hvis en ikke møter til midtsemesterprøven, teller bare eksamen.

Lærebok

Ralph P. Grimaldi: Discrete and combinatorial mathematics, 5. utgave, 2004.

Pensumliste

1. Fundamental principles of counting. 1.1–4
2. Fundamentals of logic. 2.1–4
3. Set theory. 3.1–3
4. Properties of the integers: mathematical induction. 4.1–2
5. Relations and functions. 5.1–3, 5.5
6. Languages: finite state machines. 6.1–3
7. Relations: the second time around. 7.1–2, 7.4
11. An introduction to graph theory. 11.1–5
12. Trees. 12.1–2
13. Optimization and matching. 13.1–2

Øvingene er også en del av pensum.

Undervisning

Forelesninger

Det er forelesninger tirsdager 8.15–10.00 i S8 og torsdager 14.15–16.00 i R5. Første forelesning er tirsdag 12. januar.

Øvinger

Øvingene starter i uke 3 (som starter mandag 18. januar).

Dere vil bli delt inn i grupper på ca. 20 studenter, med øvingsveiledning én gang i uka. Regn flest mulig av oppgavene på forhånd. Oppgavene blir lagt ut nedenfor.

Det ser foreløpig ut til at det blir satt opp fire øvingsgrupper:

GruppeTidRomProgramØvingslærer
1mandag 11.15–12.00S23MBIOT5Hans Christian Schrøder
2mandag 13.15–14.00S22BMATAndreas Norling
3fredag 12.15–13.00S22BITKristin Krogh Arnesen
4fredag 13.15–14.00S22MLREALBernt Galtrud

Hvis dere ønsker å bytte gruppe, eller enkelte uker ønsker å møte opp til en annen gruppe enn den dere har meldt dere på, så kan dere gjøre det uten formaliteter. Men lever øvingene til øvingslæreren i gruppa du vanligvis møter til. I tabellen er det angitt studieprogram for hver gruppe, men dette er bare en anbefaling. Inndeling i grupper blir gjort på de første forelesningene.

Øvingsbesvarelsene leveres inn og blir rettet av øvingslærer. Du må ha fått godkjent minst 8 øvinger for å få gå opp til eksamen. Det anbefales innlevering av alle øvingene. Minst 12 øvinger vil bli gitt. Ta godt vare på de godkjente øvingene i tilfelle feil ved registreringen av godkjenningen.

Fristen for innlevering er tirsdag for mandagsgruppene og mandag for fredagsgruppene. Besvarelsen leveres i hylle i Nordre lavblokk, 3. etasje, Sentralbygg 2. Utlevering skjer samme sted eller på øvingsgruppa. Merk besvarelsene med MA0301, øvingsnummer, navn og gruppenummer! Det siste er viktig, da mange besvarelser blir lagt i feil hylle.

Registrerte poststudenter (fjernstudenter) sender besvarelsen til NTNU, Institutt for matematiske fag, 7491 Trondheim. Merk konvolutten MA0301. Konvolutten må være poststemplet seinest fredag samme uka som øvingen. Husk å skrive MA0301, øvingsnummer, navn, adresse og e-post-adresse på besvarelsen. Besvarelsen kan også sendes som telefaks, nr. 73593524, eller på e-post, etter avtale med øvingslærer.

Ta kontakt med Inger Seehuus (e-post), tlf. 73591880, for å registrere deg som poststudent.

Foreløpig undervisningsplan

Undervisningsplanen vil bli ajourført etter hvert.

UkeØving nr.DatoForelesning nr.Kapittel/avsnitt
  2 12.1   11.1–2
14.1   21.2–3
  3  1 19.1   31.3–4
21.1   42.1–2
  4  2 26.1   52.2–3
28.1   62.3–4
  5  3   2.2   72.4, 3.1
  4.2   83.1–2
  6  4   9.2   93.2
11.2 103.3, 4.1
  7  5 16.2 114.2, 5.1–2
18.2 125.2–3
  8  6 23.2 135.3, 5.5, 6.1
25.2 146.1–2
  9  7   2.3 156.2–3
  4.3 166.3, 7.1
10  8   9.3 Midtsemesterprøve
11.3Ingen forelesning
11  9 16.3 17Gjennomgang av midtsemesterpøve
18.3 187.1–2, 7.4
1210 23.3 1911.1–2
25.3 2011.2–3
13Ingen øving Ingen forelesningerPåskeferie
1411   6.4Ingen forelesning Påskeferie
  8.4 2111.3–4
1511/12 13.4 2211.4–5, 12.1
15.4 2312.1–2
1612/13 20.4 2412.2, 13.1–2
22.4 25Repetisjon
1713

Øvingsoppgaver

De nummererte oppgavene er fra læreboka. Ellers kan det bli gitt gamle eksamensoppgaver.

Alle svar skal begrunnes!

Øving 1, uke 3

1.1–2: 5, 10, 14, 21
1.3: 1, 3, 7, 16–17, 25, 30
2006V: 2
2009V (bokmål, nynorsk, engelsk): 1

Øving 2, uke 4

1.4: 1–2, 8, 12
1. supplementary: 6, 24
2.1: 4, 8–9
2003H: 1
2004V: 2

Øving 3, uke 5

2.2: 6, 20
2.3: 1a, 10bf, 11a, 12ac
2004V 2006V: 1
2004V 2008V: 2
2009V (bokmål, nynorsk, engelsk): 2

Øving 4, uke 6

2.4: 3, 9, 12, 21
3.1: 1, 4–5, 8–9, 12
2003H: 4

Øving 5, uke 7

3.1: 18
3.2: 1–2, 8, 14, 16, 19
2004V: 1
2008V: 3

Øving 6, uke 8

3.3: 1, 4
4.1: 2, 14
4.2: 16
5.1: 1, 12
2004V 2006V: 5
2008V: 8

Oppgave: Finn feilen i dette beviset for at alle jenter er blonde:

La S(n) være det åpne utsagnet at alle jenter i en mengde av n jenter har samme hårfarge.

S(1) er åpenbart sann. Anta at S(k) er sann. Ta ut én jente fra en mengde av k+1 jenter. Da har alle de gjenværende jentene samme hårfarge, siden vi antar at S(k) er sann. Sett inn igjen jenta, og ta ut en annen. Igjen har alle de gjenværende k jentene samme hårfarge. Siden de to mengdene overlapper, har alle k+1 samme hårfarge, og vi har vist S(k+1).

Så vi har vist ved induksjon at alle jenter har samme hårfarge. Minst én er blond, så alle er blonde.

Øving 7, uke 9

5.2: 1, 4, 15–16, 21
5.3: 1–2, 8
5.5: 3, 7
6.1: 1, 3, 5, 7, 10

Øving 8, uke 10

6.2: 1, 3, 5
6.3: 1, 3
2006V: 3
2008V: 4
2009V (bokmål, nynorsk, engelsk): 3

Øving 9, uke 11

Mest repetisjon denne gangen:

1. supplementary: 17–18
2. supplementary: 13
3. supplementary: 3
4. supplementary: 3
5. supplementary: 10
6.3: 7–8

Øving 10, uke 12

7.1: 1–2, 5–6
7.2: 1

2003H: 2
2004V: 3
2008V: 5

Øving 11, uke 14–15

7.2: 8, 17(i)–(ii), 18(b)
7.4: 3–4, 7
11.1: 2–3, 5, 10
11.2: 1, 3, 9

2006V: 6

Øving 12, uke 15–16

11.3: 1–2, 5, 20–21, 23
11.4: 2, 4, 14
11.5: 1, 3

2003H: 3, 5
2004V: 4
2008V: 7, 10

Øving 13, uke 16–17

12.1: 8, 13
12.2: 1, 6–7
13.1: 2

2008V: 6
2009V (bokmål, nynorsk, engelsk): 4

Gamle eksamensoppgaver og midtsemesterprøver

Eksamener

2003H, løsning
2004V
2006V, løsning
2007V med løsning
2008V, løsning
2009V (bokmål, nynorsk, engelsk), løsning

Midtsemesterprøver

2003H, løsning
2006V med løsning
2008V med fasit