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.