MA 2301 Videregående diskret matematikk
|
02.06.2004:
|
Eksamensoppgavene med løsningsforslag er lagt ut lengere
nede på siden.
|
|---|
|
27.04.2004:
|
Pensumlisten er revidert, se endelig pensumliste.
Merk at eksamen er 4 timer.
|
|---|
|
20.04.2004:
|
Det blir repetisjon de tre siste ukene, med hovedvekt på
hvordan man løser eksamensoppgaver. Alle innspill er
velkomne.
Torsdag 22. og torsdag 29. april vil begge bli avlyst
fordi jeg er på PEDUP kurset.
|
|---|
|
26.03.2004:
|
Det har kommet et brev fra IME-fakultetet, hvor det står
at søknaden om flytting av eksamensdatoen i MA2301 er
imøtekommet.
Ny dato er 26.05.2004.
Neste uke skal vi bevege oss med stormskritt mot P, NP og
Cooks teorem.
|
|---|
|
22.03.2004:
|
På onsdag vil jeg gå gjennom eksemplet i L&A 5.6, samt noen av oppgavene fra
forrige uke. Spesielt oppgavene 5.2.2, 5.3.2 og 5.3.3.
|
|---|
|
17.03.2004:
|
Her er tre web adresser. Den første er en Turingbiografi,
den andre er 1936 artikkelen "On computable ...", og den
tredje er den berømte artikkelen fra 1950 "Computing
machinery and intelligence"
Biografi
Kortbiografi
On computable ..
Computing machinery ...
Computing machinery ...(farger invertert)
|
|---|
|
16.03.2004:
|
I morgen får vi noen flere tilhørere. En pedagog og to
andre lærere.
|
|---|
|
15.03.2004:
|
Fremdriftsplanen er litt forandret. Onsdag den 17. skal
vi gå igjennom stoppeproblemet(d.v.s. språket "Halt"), og
vise at det ikke er avgjørbart(rekursivt). Fredag 19. blir det
ingen forelesning.
|
|---|
|
25.02.2004:
|
Her ligger timeplanen for intervjuer i midtsemesteruka. Timeplan.
|
|---|
|
16.02.2004:
|
Onsdag fortsetter vi med Turingmaskiner. For de som ikke
var tilstede fredag blir det en rask repetisjon av L&P
4.1.
Her ligger et forsøk på en fremdriftsplan MA2301_plan04.html.
|
|---|
|
12.02.2004:
|
Lars Kristiansens tanker omkring Turing og Churhs teser
finner dere i notat 4 lenger ned på siden.
|
|---|
|
02.02.2004:
|
Eksamensdatoen vil ikke bli kunngjordt før 15. februar.
|
|---|
|
02.02.2004:
|
På forelesning 04.02. går vi først gjennom slutten av teorem 2.3.2. med
eksempler. Så tar vi seksjon 2.5(minimalisering) før vi tar 2.4.
|
|---|
|
02.02.2004:
|
Noen av øvingsoppgavene merket med stjerne vil bli gitt
til eksamen, så det vil lønne seg å jobbe litt ekstra med disse.
|
|---|
|
28.01.2004:
|
På forelesningen i dag skal vi se på endelige automater,
både deterministiske og ikkedeterministiske. Vi vil se
hvordan en endelig automat bestemmer et språk. Videre
skal vi se på hvordan vi til enhver endelig automat, som ikke
nødvendigvis er deterministisk, kan
assosiere en deterministisk endelig automat som bestemmer samme språk.
|
|---|
|
23.01.2004:
|
Forelesningen i dag finner dere i Notat 2. seksjon
8. Dere finner også noen løsninger på oppgavene som vi
skulle jobbe med igår. Onsdag begynner vi med endelige automater.
|
|---|
|
21.01.2004:
|
Jobber nå for å få fastsatt eksamesdatoen til onsdag
26. mai 2004.
|
|---|
|
16.01.2004:
|
Eksamesdatoen er fastsatt til 1. juni.
|
|---|
|
|
|
Generelt:
|
7.5 studiepoeng. Varighet: 1 semester (vår). Forelesninger: 3 timer pr. uke.
Øvinger: 2 time pr. uke.
|
|---|
|
|
Beskrivelse:
|
Emnet bygger på MA0301 og er i likhet med MA0301 av spesiell
interesse forinformatikkstudenter.
Emnet gir en innføring i deler av den teoretiske bakgrunnen
for informatikkfaget, og vil blant annet omhandle formelle språk,
endelige automater, Turing-maskiner og rekursive funksjoner.
Viktige begreper vi vil studere er avgjørbarhet og halvavgjørbarhetberegnbarhet,
av formelle språk, og vi vil vise at stoppeproblemet er uavgjørbart.
Vi vil definere begrepet reduksjon i polynomiell tid og studere
kompleksitetsklassene P og NP med eksempler. Vi vil gå gjennom Cooks bevis
for at tilfredsstillbarhet av formler på konjunktiv form er et NP-komplett
problem.
|
|---|
|
|
Lærebok:
|
Harry R. Lewis og Christos H. Papadimitriou,
Elements of the Theory of Computation,
2. utg., Prentice-Hall International, inc.
Boka koster kr. 750. Tapir holder på å forhandle med
forlaget. kanskje blir den noe billigere. Det er også muligheter
for å få kjøpt boka brukt på amazon.com fra USD 43.
|
|---|
|
|
Endelig pensumliste:
|
1.1-1.8, 2.1-2.3, 2.5, 3.1-3.2, 4.1-4.3, 4.5, 5.1-5.3, 5.6, 6.1-6.4, 7.1-7.2.
Til eksamen vil det bli lagt mest vekt på at man skal kunne stoffet i 2.1-2.3, 2.5, 3.1,
4.1-4.2. Man bør ha forstått teorien og kunne gjengi definisjonene av de viktigste
begrepene fra teorien også i resten av pesum, men det er ikke meningen at man skal kunne
gjengi de vanskelige bevisene i 4.3-4.4, 5.2-5.3, 7.2.
|
|---|
|
|
Eksamen:
|
26. mai 2004, skriftlig, 4 timer.
|
|---|
|
|
Forelesninger:
|
Onsdag 14:15-16 i F3
Fredag 09:15-10 i Kjel 242
|
|---|
|
|
Øvinger:
|
Torsdag 14:15 - 16. i R53.
|
|---|
|
|
|
Øving 1 (Uke 3):
|
1.1.1 - 1.1.4, 1.2.1 - 1.2.4, 1.3.2, 1.3.4,
1.3.10, 1.3.11.
|
|---|
|
Øving 2 (Uke 4):
|
1.6.8, 1.7.1, 1.7.2,
1.7.3, 1.8.1, 1.8.6 og 1.8.7(*). løsn.
|
|---|
|
Øving 3 (Uke 5):
|
2.2.1 - 2.2.6, 2.2.9, 2.2.10. løsn. 2.2.6.
|
|---|
|
Øving 4 (Uke 6):
|
2.3.2, 2.3.6(*), 2.3.7, 2.4.2(*), flere oppgaver.
|
|---|
|
Øving 5 (Uke 7):
|
2.5.1(*), 2.5.3(*), 3.1.3, 3.1.4, 3.1.10, 3.2.1(!).
Utropstegnet betyr at oppgaven er ganske utfordrende.
|
|---|
|
Øving 6 (Uke 8):
|
4.1.3, 4.1.4, 4.1.6, 4.1.7, 4.1.9, 4.1.10, 4.1.11 og 4.1.12.
|
|---|
|
Øving 7 (Uke 11):
|
4.2.1(*), 4.2.2, 4.2.3, 4.2.4, 4.3.1(*), 4.3.2(Sett k = 2)
og 4.3.3.
|
|---|
|
Øving 8 (Uke 12):
|
5.2.1, 5.2.2(Her er det mulig å bruke
teorem 2.4.1, "Pumpelemmaet".), 5.3.2 og
5.3.3. (Oppgave 5.3.2 blir mye enklere å løse med
teknikken fra seksjon 4.7, som handler om de rekursive funksjonene.)
|
|---|
|
Øving 9 (Uke 13):
|
5.6.1(*), 5.6.5, og tidligere oppgaver.
|
|---|
|
Øving 10 (Uke 14):
|
6.3.1(*), 6.3.2, 6.3.3, 5.2.2 og tidligere oppgaver.
5.2.2 og 5.3.2.
6.3.3.
|
|---|
|
|
|
Notat 1
|
Dette lille notatet om Zermelo - Fraenkels mengdeteori er skrevet
fordi jeg synes dere skal ha sett det, og fordi denne
teorien danner grunnlaget for all moderne matematikk.
Det er slett ikke meningen at dere skal kunne alt dette!
|
|---|
|
Notat 2
|
Dette er noen notater jeg skrev ifjor fordi boka ikke
var tilgjengelig på Tapir. Det er en kort oppsumering av
kapittel 1.
|
|---|
|
Notat 3
|
Kort oppsumering av en del av kapittel 2.
|
|---|
|
Notat 4
|
Detter er Lars Kristensens kompendium. Det er spesielt kapittel 2,
og om dere vil 3, som jeg vil at dere skal lese i
midtsemesterukene. Resten av stoffet faller utenfor vårt pensum.
|
|---|
|
|
|
