| Dato | Undervises av | Sted | Tema | Kommentarer / ressurser |
| 23.08.2005 | Tore Langholm? | ? | Oversikt over kurset, samt gjennomgang av 1.1 og 1.2. (Unntak: 1.1.2 er kursoriks pensum. 1.1.3 er ikke pensum. 1.2.4 er ikke pensum. 1.2.5 er kursorisk pensum.)? | Det er f?rste gang kurset foreleses etter Heins l?rebok, og den n?yaktige fremdriftsplanen kan bli endret underveis. Tall som 1.1 etc. henviser til deler av kapitler i l?reboken.Denne dagen foreleste jeg fra 1.1 (f?rste time) og 1.2 (andre time), men jeg gikk ikke gjennom alt stoffet, spesielt gikk jeg ikke gjennom bokens eksempler. Dette m? leses p? egenh?nd. Lysark fra f?rste time finnes her som henholdsvis pdf-dokument og powerpoint-presentasjon. Legg spesielt merke til lenken til slutt, gjengitt her . Trykk p? den gr? knappen merket Start Truth Table Constructor nede til h?yre p? siden du da kommer til, og pr?v deg frem ved for eksempel ? skrive inn ((A v B) => C) <=> ((A => C) ^ (B => C)) i vinduet oppe til venstre og deretter trykke OK.? |
| 25.08.2005 | ? | ? | 1.3.3? | Lysark (bare for f?rste del av forelesningen!) finnes her som henholdsvis pdf-dokument og powerpoint-presentasjon. ? |
| 30.08.2005 | ? | ? | 1.3.1, 1.3.4, 2.1.1? | Vi snakker om disse begrepene.? |
| 01.09.2005 | ? | ? | "Matematisk induksjon. Kapittel 3 til og med 3.1.1, samt utdrag fra 4.4.1? | Kapittel 3 til og med 3.1.1, samt utdrag fra 4.4.1. Rammen side 255 har dette spesialtilfellet for naturlige tall. Ta ogs? en kikk p? de to animasjonene tilgjengelige fra lenkene 1a. Principle of Mathematical Induction animation og 1b. Example of Mathematical Induction animation her? |
| 06.09.2005 | ? | ? | 6.1 og 6.2? | Gjelder hele uken. Lysark som Powerpoint eller i pdf? |
| 08.09.2005 | ? | ? | ? | ? |
| 13.09.2005 | ? | ? | 6.3? | Vi tok for oss begrepene aksiom, slutningsregel, bevis og bevis fra premisser, og gikk gjennom en del eksempler. Vi oppdaget ogs? en liten feil i boken som ikke st?r i errata-listen: I beviset side 375 slutter man fra B i linje 2 til AvB i linje 3 ved hjelp av noe som oppgis ? v?re slutningsregelen Add. Men slik denne regelen presenteres side 371, lar den oss bare slutte AvB fra den f?rste disjunkten, alts? A. For ? f? dette til ? g? i hop, m? vi derfor utvide definisjonen side 371 slik at Add ogs? tillater oss ? slutte fra B til AvB. Tilsvarende (for ? f? til overgangen fra linje 4 til linje 5 side 375) m? vi ogs? legge inn en ekstra versjon av Simp, som tillater oss ? slutte fra A&B til den andre konjunkten B.? |
| 15.09.2005 | ? | ? | 6.3 fortsatt.? | Vi s? blant annet p? beviser ved s?kalt reductio ad absurdum, det vil si beviser som bruker regelen IP.Flere av temaene vi har v?rt innom til n? er illustrert p? nettstedet Gateway to Logic (G? gjerne rett videre til lenken Server-side functions ) Her kan man skrive inn en formel og se dens sannhetsverditabell, f? den skrevet om til DNF, etc. Man kan ogs? f? den bevist hvis den er en tautologi. Da brukes et natural deduction-system som likner p? det som beskrives i v?r l?rebok. Alle bevis som returneres bruker regelen RAA, som essensielt er det samme som v?r IP. Legg merke til at bevisene ofte er un?dvendig lange og kl?nete; dette er fordi de genereres automatisk etter noks? enkle regler.? |
| 20.09.2005 | ? | ? | 6.4? | Gjelder hele uken. Lysark som powerpoint eller i pdf ? |
| 22.09.2005 | ? | ? | Se over? | Lysark som powerpoint eller i pdf ND1750 er v?r presiserte versjon av "naturlig deduksjon" fra avsnitt 6.3. Dette systemet er komplett, som vi skal se i neste ukes ?velser.? |
| 27.09.2005 | ? | ? | 7.1? | Gjelder hele uken.Vi begynner alts? p? predikatlogikk. Kikk gjerne p? denne teorembeviseren hos "Gateway to Logic". Syntaksen er tilpasset vanlig tastatur, men skulle ellers ikke v?re vanskelig ? sammenlikne med bokens. Skriv inn formler som du mener burde v?re gyldige/ikkegyldige, og se om systemet er enig.Lysark fra f?rste halvpart av forelesningen i powerpoint og pdf ? |
| 29.09.2005 | ? | ? | Se over? | Powerpoint.?PDF.? |
| 04.10.2005 | ? | ? | 7.2? | Powerpoint PDF ? |
| 06.10.2005 | ? | ? | 7.2 fortsatt. Vi begynner p? 7.3.? | Powerpoint PDF Eksempler p? oversettelse til predikatlogikk ? |
| 11.10.2005 | ? | ? | Vi fortseter med 7.3? | Notatet med rettelser har sv?rt mange referanser til avsnitt 7.3. Legg spesielt merke til at t is free to replace x in W n? (i motsetning til i boken) betyr at ingen fri forekomst av x i W st?r i skopet til en kvantor for en variabel i t. Til tross for rettelsene er bevisene som st?r etter reglene UI (7.15), EI (7.17), UG (7.18) og CP (7.19) dessverre fremdeles forvirrende, uklare og til dels gale, og utg?r derfor fra pensum.Det som er viktig ? l?re seg, er hvordan reglene side 451 i boken leses og brukes. Se lenke til rettet versjon i ruten under.? |
| 13.10.2005 | ? | ? | Vi avrunder 7.3? | Notat om premisser i bevis. ND1750PRED er v?r rettete versjon av bevissystemet i avsnitt 7.3.? |
| 18.10.2005 | ? | ? | 1.3.3, 11.1, litt av 11.2.1? | Lysark om regul?re uttrykk. (Som PDF. )Lysark om DFAer. (Som PDF. )Vi rakk ogs? ? definere NFAer.The Regex Coach finnes p? maskinene p? Hundremeterskogen, og er et nyttig hjelpemiddel til ? bli kjent med regul?re uttrykk. Tilgjengelig herfra. En annen nyttig applikasjon er JFLAP; se denne lenken for informasjon om hvordan du kan f? tak i (og kj?re) dette.? |
| 20.10.2005 | ? | ? | resten av 11.2.1, litt av 11.2.2? | Om ? lage automater fra regul?re uttrykk og omvendt. Eksemplene 11.13 og 11.14 er ikke pensum.? |
| 25.10.2005 | ? | ? | 11.2.5 og 11.3.2? | Notat of krav til DFAer i powerpoint og pdf. Endelige automater som produserer output. Konstruksjon av DFA fra NFA.? |
| 27.10.2005 | ? | ? | 11.3.3? | Konstruksjon av minimal DFA. Lysark som powerpoint og pdf. Liten og stor DFA som vi minimaliserte p? forelesningen. Dette er filer som kan leses av JFLAP; last dem ned og ?pn dem fra JFLAP. Se ogs? PDF-filer som viser minimalisering av den siste; f?rst inndeling i grupper av ekvivalente tilstander og deretter inntegning av transisjoner.? |
| 01.11.2005 | ? | ? | 11.4.2. Begynner p? 3.3.? | Siste halvpart av side 692 er ikke pensum. Siste linje side 179, side 180 og f?rste halvpart av side 181 er ikke pensum.? |
| 03.11.2005 | ? | ? | Avslutter 3.3. 11.4.1? | Lysark om kontekstfrie og regul?re grammatikker i powerpoint og PDF.?? |
| 08.11.2005 | ? | ? | Kap. 12 t.o.m. 12.2.2.? | F?lgende deler av dette er kursorisk pensum: Fra midt p? s. 704 til midt p? s. 707, og fra midt p? s. 709 til midt p? s. 711.? |
| 10.11.2005 | ? | ? | 12.4? | Repetisjon: Lysark om forholdet mellom endelige automater og regul?re gramatikker i powerpoint og PDF.Lysark om venstrerekursjon i powerpoint og PDF.Tema ellers blir eliminasjon av lambda-produksjoner, samt Chomsky og Greibach normalform.? |
| 15.11.2005 | ? | ? | Resten av 12.4. (Pumpelemma og lukningsegenskaper for kontekstfrie spr?k.) 13.1 (Innledende om turingmaskiner.)? | ? |
| 17.11.2005 | ? | ? | 13.1.2? | Eksempler p? turingmaskiner i powerpoint og PDF, og som JFLAP-kj?rbare filer: strengreversering, suksessorfunksjon med un?r og bin?r tallrepresentasjon og konverteringsfunksjoner fra un?r til bin?r og bin?r til un?r representasjon. (De fem siste b?r lastes ned f?r de kj?res, og gis navn som ender p? ".jff".)? |
| 22.11.2005 | ? | ? | 13.1.3 og 13.1.4? | Fra 2/3 ned p? side 770 til 1/3 ned p? side 773 er ikke pensum? |
| 24.11.2005 | ? | ? | 13.2 unntatt 13.2.4. 14.2? | Lysark i powerpoint og PDF. Kontekstsensitiv og ubegrenset grammatikk i JFLAP-format for spr?ket an bn cn.? |
| 29.11.2005 | ? | ? | 14.1? | Det som st?r i 14.1 etter midten av side 798 er ikke pensum.? |
| 01.12.2005 | ? | ? | Oppsummering? | Vi ser kanskje ogs? p? en gammel eksamen. Tidligere var det to eksamener i dette kurset, f?rtst en to-timers eksamen i logikkdelen (eksempel og delvis l?sningsforslag ) og s? en tre-timers eksamen som fortrinnsvis dekket beregnbarhetsdelen. (Eksempel og l?sningsforslag. ) (En til, med delvise l?sningsforslag til sp?rsm?l TO (endelig automat ), TRE (grammatikk ), og FIRE (turingmaskin ).)Vi brukte samtidig en annen l?rebok med litt annet pensum og litt andre begreper og definisjoner. Regn derfor ikke med ? forst? alt. ? |
Undervisningsplan
Publisert 30. mai 2005 16:12
- Sist endret 3. des. 2005 00:07