Framdriftsplan
Tabellen under fylles ut løpende gjennom semesteret, og vil inneholde de viktigste beskjedene en bør få med seg i emnet.
Merk: Planen kan endres.
RA refererer til boken "Logiske metoder" av Roger Antonsen. Notatene som refereres til i "anbefalt lesning" vil gjøres åpent tilgjengelig på nett i god tid før temaet skal gjennomgås.
Øvingene publiseres på onsdager, kl 16, i Ovsys.
| Ukenr | (Planlagt) Tema | Anbefalt lesning | Mandag | Onsdag | Øving | Kommentarer | |
|---|---|---|---|---|---|---|---|
| 2 | Mengder og diskrete strukturer | Kap. 0,1 og 8 (opp til "Uendelighet" på s. 93) i RA | Intro-slides. Notater I tillegg til notatene drøftet vi komplement-konseptet (s. 90 i RA) | Slides. Notater i tillegg til notatene dekket vi størrelsen på endelige potensmengder, nederst på side 92 i RA. | Øving 1 | ||
| 3 | Relasjoner og funksjoner | Kap. 6,7 i RA | Vi dekket opp til ekvivalensrelasjoner i Notater uke 3, tilsvarende kapittel 6 i RA. | Vi fullførte notatene. Vi noterte også at gitt en funksjon f:A → B kaller vi A for domenet eller definisjonsområdet til f, og B kodomene eller verdiområdet til f. | Øving 2 | Merk: Når RA snakker om "binære relasjoner" er det akkurat det samme som våre relasjoner, vi bare dropper ordet "binær" foran. | |
| 4 | Utsagnslogikk 1 | Kap. 2,3 og 4 i RA | Notater kapittel 2 og 3 - det gikk litt kjapt på slutten, på onsdag tar vi en ny titt på De Morgans lov, og repeterer noe, før vi går videre. | Fullføre og repetere notatene fra mandag, før vi begynner på notatene fra kapittel 4. | Øving 3 | Merk: Øving 3 vil referere til begrepet "logisk konsekvens" som blir introdusert i kapittel 4 i RA. Vi drøfter dette begrepet i onsdagsforelesningen. | |
| 5 | Utsagnslogikk 2 og start prediaktlogikk | Kap. 4 i RA, notater | Vi fullførte utsagnslogikk. Se notater fra forrige uke. | Plan: Start predikatlogikk, uke 5. | Øving 4 | Advarsel: Vi tar en litt enklere og mer uformell tilnærming til predikatlogikk enn det som gjøres i RA. Vi anbefaler derfor å heller følge notatene og forelesningene på dette temaet enn å bruke boken. | |
| 6 | Bevisteknikker | Kap. 5 og resten av 8 i RA | Vi diskuterte bevisteknikker opp til kontrapositivt bevis. | Vi fullførte notatene. | Øving 5 | ||
| 7 | Rekursjon og induksjon 1 | Kap. 9,10 i RA | Notater, induksjon og rekursjon | Vi fikk snakket mer om induktivt definerte mengder og forklart rekursjon. Python-skript som vil drøftes: frosk_rekursjon.py | Øving 6 | Kommentar: Det var noe uklarheter rundt oppgave 4d i øving 5. Løsningen i LF er riktig. | |
| 8 | Rekursjon og induksjon 2 | Kap. 11,12 i RA | Vi reperte induktivt definerte mengder og gav en rekursiv definisjon av valuasjon av utsagnslogiske formler. Vi begynte på notatene om induksjonsbevis. | Plan: Fortsette på induksjonsbevis | Øving 7 | ||
| 9 | Kombinatorikk og rekursjon | Kap. 18 og 19 (opp til s. 217) i RA | Notater kombinatorikk: Kombinatorikk | Øving 8 | |||
| 10 | Avslutning kombinatorikk og litt mer predikatlogikk | Notater | Plan: Gå grundig gjennom oppgave 4b fra øving 7. Etter dette: Avslutning predikatlogikk | Plan: Avslutning kombinatorikk. Start Grafer og trær hvis vi får god tid. | Øving 9 | ||
| 11 | Grafteori 1 | Kap. 21 opp til og med eksempelet på side 238. Vi bruker også en del definisjoner fra kap 22. | Vi begynte på Grafer og trær. NB: Vi hoppet over definisjonen av induserte undergrafer; vi klarer oss med det generelle undergraf-begrepet. | Vi snakket om ulike typer vandringer og trær, inklusive rotfestede trær. Grafer og trær. Definisjonen av sykel som ble gitt er feil, da vi ikke vil telle lukkede vandringer av lengde 2 som sykler. En sykel skal altså være en krets som er en sti om man kutter av siste node. | Øving 10 | Kommentar: Boken diskuterer av og til såkalte pseudografer, hvor man tillater mer enn en kant mellom to noder. Vi vil ikke diskutere slike grafer, så prøv å unngå å bli forvirret av at disse av og til dukker opp i boken. | |
| 12 | Grafteori 2 | Notater og kap 22 (om Eulerkretser) | Vi beviste resultatet at en sammenhengende graf er et tre hvis og bare hvis den har én færre kanter enn noder, og introduserte Eulerkretser. | Vi fullfører notatene om Eulerkretser. | Ingen ny øving | ||
| 13 | Påske  | (Påskekrim?) | Utgår | Utgår | |||
| 14 | Formelle språk | Kap. 23 i RA | Utgår | Formelle språk | Øving 11 | Kommentar: Øvingen vil ha oppgaver om både språk og grafer. | |
| 15 | Tilstandsmaskiner | Kap. 23 i RA + Notater | Vi repterer og avslutter notatene om formelle språk, spesifikt regulære språk, og begynner på tilstandsmaskiner. | Vi fortsetter med tilstandsmaskiner og Kleenes teorem. | Øving 12 | ||
| 16 | Anvendelser + avslutning tilstandsmaskiner | Notater | Tilstandsmaskiner 2. Vi avsluttet med basis-steget i et induktivt bevis for Kleenes teorem (retning fra regulært språk til automat). Vi gikk altså ikke gjennom de siste sidene i notatene, hvor induksjonssteget drøftes litt grundigere. | Anvendelser | Øving 13 - Prøveeksamen | Øving 13 er en "ekstraøving" for å hjelpe alle å øve, men spesielt for de som ikke har rukket å få 8/12 godkjente. | |
| 17 | Repetisjon | Opptak finnes i Panopto (kan også nås i Blackboard. Her er direktelenke til først time.) | Direktelenke til opptak av første time | Pensum repiteres | |||
| 18 | Repetisjon | Plan: Gå gjennom prøveeksamen | Utgår |