Beskjeder - Side 2

Vi hopper over kap 6 - Advanced topics in computability theory. Det er likevel tillatt å ta en titt på det. Lars Kristiansen starter tirsdag med kompleksitet.

FOREDRAG 7 mars

LOGID gruppa vil holde en rekke populære foredrag på torsdager 16-18 i lokalene i femte etasje i OJD. Det blir først foredrag og deretter noe å spise (pizza). Første gang 7 mars. Første side av foredraget er lagt ut som Foredrag 0703. Foredragene er åpne og temaene skulle passe for dere.

Se på web for andre foredrag. Lagt ved et eksempel Foredrag Virginia

Minner om at forelesningene i dag er i Postscript - 2 etasje i OJD.

Oblig 2 er lagt ut - frist 18 mars

Ukeoppgaver: 4.2, 4.3, 4.4, 4.11, 4.18, 4.20

Ekstra utfordring 4.22

Fra mars av overtar Lars Kristiansen forelesninger. Han starter med kompleksitet.

Forelesningene på tirsdag er nå i Postscript - 2.etasje OJD

Ukeoppgaver 3.2, 3.3, 3.5, 3.6, 3.7, 3.8a

Ekstra utfordring 3.11

• Andreas

En student skrev

Har problemer med oppgave 2.2 under obligen og er usikker på hvordan jeg skal angrepe oppgaven. Ordet høyreinvariant finner jeg veldig lite om. På Google dukker det opp kun 2 treff. Har også søkt igjennom kompendiet til INF2080 og INF1080. Takk for hjelp

----

Jeg svarte

Høyreinvariant betyr at hvis a ekvivalent b, så ac ekvivalent bc for alle c. Det er det som står i oppgaven.

-----

Begrepet høyreinvariant brukes ikke i oppgaven. Det er til orientering for de som ønsker å se videre på det, men det er ikke en del av oblig'en som det står i teksten.

OBLIG kan leveres i devilry

Obligen kan leveres i devilry. - Andreas

Levering av oblig 1 - send dem med email til gruppelæreren. Det er enten Andreas Nakkerud eller Peter Broch

Rettet opp noen transisjoner i Turing basic - basic 3. Si i fra om dere ser flere feil.

OPPGAVER - uke 7

Ukeoppgaver: 2.9, 2.12, 2.13, 2.14, 2.16, 2.17

• Andreas

Om partisjoner

I obligen bruker jeg altså partisjoner på en litt annen måte enn Roger i INF1080. Han ønsker ikke partisjoner som inneholder tomme mengder, jeg tillater det. For obligen der det var en tilstand som var inaksessibel gjør det litt forskjell. Så enten skulle jeg lage en ny DFA til oppgaven der alle tilstander kunne nås fra start, eller insistere på min definisjon av partisjon.

Dette er situasjoner dere godt kunne ha kommet opp i andre steder. Jeg pleier i eksamensoppgaver og obliger ha med en setning av formen - hvis du er i tvil om hvordan oppgaven skal forstås, så redegjør for det og deretter gjør dine egne presiseringer.

Spørsmål fra student: "I oppgave 2.1 skal vi bevise at at L(A) .... L(H) gir en partisjon av sigma*. Jeg ser at tilstand D har inngrad null, slik at L(D) blir det tomme språket. I INF1080 lærte jeg at en partisjon ikke inneholder den tomme mengden, som motsier det vi må bevise. Bruker du en annen definisjon av partisjon eller er dette bare en slurvefeil?"

Svar:

Hei

Med en partisjon K, L, M, N av P mener jeg to ting

• unionen er hele P
• mengdene K, L, M, N er disjunkte - snittet av to og to av dem er tomme

Med en slik definisjon kan en godt bruke at en av mengdene er tom - det spiller ingen rolle.

Dette er den vanlige definisjonen. Så til det som er gjort i INF 1080. Jeg så ikke på det før jeg lagde oppgaven. Det er mulig at Roger har unntatt det enkle tilfellet at noen av mengdene er tomme. Men jeg skjønner ikke helt hvorfor.

Jeg skal legge ut beskjed om dette på web-siden.

-- Herman Ruge Jervell

Ukens bevis, uke 6

Oppgave 1.41 (Sipser, 3 ed, p. 89).

• Andreas

Oppgaver uke 6

Andreas foreslår i tillegg 2.11 som øvingsoppgave og 2.18 som utfordringsoppgave.

Oppgaver uke 6

Legger her ut noen oppgaver for uke 6. Det er mulig at hjelpelærerne gir noen andre - i så fall vil dere få beskjed.

Fra oppgavene 2.3, 2.4, 2.5, 2.6, 2.7, 2.8

Her er det mange enkle oppgaver - og noen litt vanskeligere.

Fikk beskjed fra Torbjørn Bull Høgstmyr

--- Jeg ville bare si ifra om at C-noden i tilstandsmaskinen (oppg 2) går både til seg selv og til A når 0 blir lest inn (mens 1 ikke kan leses inn i C-tilstanden). Dette har muligens ikke direkte relevans for løsning av oppgavene, men flere av bevisoppgavene må jo løses med utgangspunkt i at maskinen faktisk er en DFA. ----

Dette er helt riktig - min feil. Det spiller ingen rolle for løsningene, bortsett fra at det var vesentlig i oppgave 2 at vi har en DFA. Jeg har endret på figuren i oppgaven slik at det da skulle bli riktig.

Fra Andreas

Ukens bevis er en beviskonkurranse der deltakerene hver uke får mulighet til å levere inn et bevis. Bevisene gis fra 0 til 2 poeng. Blant de som i løpet av et semester får flest poeng trekkes det ut en premie (TBA).

Besvarelser sendes inn til ukens-bevis-svar@ifi.uio.no innen utgangen av kalenderuken oppgaven er gitt. Poeng telles per UiO-brukernavn, så svar må alltid sendes fra samme UiO-adresse. Emne skal være ukenummer. Eventuelt vedlegg skal ha navn som innholder ukenummer og UiO-brukernavn.

Oppgave uke 5 (frist 2012-02-03T23:59):

Bevis at enhver NFA kan gjøres om til en ekvivalent NFA med kun én aksepterende tilstand. (Oppgave 1.11 i læreboka for INF2080.)

Merk: Det er ikke tilstrekkelig å gi en metode for omgjøring. En slik metode må i så fall bevises å være rett.

Oblig 1 er lagt ut. Frist 18 februar.

Oppgavene skal leveres elektronisk - enten som pdf eller tekst. Se etter på hjemmesiden for INF 1080 hvordan symboler kan skrives.

For figurer er det flere muligheter:

Den mest avanserte er å bruke latex og tegneprogram som tikz. En annen mulighet er å bruke word eller openoffice og tegnemulighetene der. Men få det oversatt til pdf før innlevering - både word og openoffice har den muligheten. En mulighet er også å bruke en ren tekstfil og legge ved scannede illustrasjoner.

Kommer senere med nærmere opplysninger om hvor det skal sendes.

Nummerering 2. og 3.utgave

Det er ikke sikkert at alle oppgavene har samme nummer i 2. og 3. utgave. Oppgave 1.50 i 3. utgave svarer til oppgave 1.55 i 2. utgave - tror jeg. Det er nummereringen fra 3.utgave som gjelder, så sjekk med den før dere hiver dere innpå oppgavene.

OPPGAVER UKE 05

Ukeoppgaver: 1.12, 1.16, 1.17, 1.19, 1.21, 1.28

Anbefalte utfordringer: 1.23, 1.50

OPPGAVER UKE 04

Samme oppgaver i 2. og 3.utgave. Løs de to siste deloppgavene i hver av oppgave 1.4 - 1.5 - 1.6 - 1.7 - 1.8 - 1.9 - 1.10

Gruppe 1 er flyttet til kl 0815-10, fortsatt på tirsdager. Gruppe 2 har fortsatt gruppe tirsdag kl 10.15. Se tid og sted-siden.

VELKOMMEN

Kort om INF2080. Det er en fortsettelse av INF1080 med vekt på fire emner

• endelige automater - 2 uker
• kontekstfrie språk - 2 uker
• turing maskiner - 3 uker
• kompleksitet - 6 uker

Boka er Sipsers bok, 3.utgave, men 2.utgave kan brukes. Vi vil følge boka tett. Vi tar ikke med 2.4 som er det vesentlige skillet mellom 2. og 3. utgave. Som ekstrabok har jeg min Compact Companion.

På web er det mye stoff rundt Sipsers bok. Jeg kommer til å bruke noen slides fra Emanuele Viola og se også på slides fra i fjor.

Dette er temaer som det er masse om på web. Slå opp i wikipedia på finite automata, contextfree languages, turing machines, complexity og søk videre derfra. Jeg vil sikkert nevne en del av dette på forelesningene.

Vi har forelesninger i Store Auditorium, Kristen Nygaards hus og felles regneøvelser i CAML. Vi måtte flytte på grunn av stor oppmelding.