Beskjeder
The exam workshop on June 4 will be in seminar room C on the third floor.
We have uploaded the past exams previously, but for convenience, you can also find them here.
On Sunday June 4 we are hosting an eksamensverksted (exam workshop) at IFI. We will go through old exams, discuss questions you might have, and have some pizza! Binding registration here.
Hei
Eksamenssettet skal besvares digitalt, med unntak av noen enkeltoppgaver skal besvares med penn og papir. Se instruksjonsvideo.
Arkene du bruker til å besvare penn- og papiroppgavene, er spesialtilpassede "skisseark" som blir delt ut i eksamenslokalet. Du leverer inn skissearkene på vanlig måte etter endt eksamen. Arkene blir deretter skannet av eksamensvaktene og lastet opp til din digitale besvarelse. Det er derfor viktig at du fyller ut skissearkene på riktig måte. Skissearkene må fylles ut med blå eller sort kulepenn (ta med dette selv). Det er ikke anledning til å bruke blyant eller penn med annen farge. Se "Instruksjon for digital håndtegning" (ligger på pult)....
Fra Lars:
Siste forelesning i kompleksitetsterori er over, og jeg er ferdig med mine forelesninger. Daniel vil gi en forelesning i neste uke.
I de kommende gruppetimene vil man gå gjennom eksempel 7.44 (VERTEX-COVER is NP-complete) og eksempel 7.55 (UHAMPATH is NP-complete) i Sipsers bok.
Fra Lars:
Jeg er ferdig med å forelese kapittel 8. Siste forelesning blir tirsdag 8. mai. Da vil jeg oppsummere pensum i kompleksitetsteori samt snakke om noe utvalgte temaer fra kapittel 9.
Screencast fra infomøte om digital eksamen her
Her er flere oppgaver som kan løses og diskuteres i gruppeundervisningen: 8.5, 8.7, 8.11 (a), 8.18, 8.19, 8.23, 8.33 og 8.34. (8.34 er en vanskelig oppgave for de sesielt interesserte,)
Fra Lars:
Jeg har forelest fram til Theorem 8.25 på side i 353. Neste uke vil jeg bevise Teorem 8.25. Deretter vil jeg forelese seksjon 8.6. Reghner med at det blir sånn circa hva vi rekker neste uke.
Disse oppgavene vil løses i gruppetimene denne uken (eller muligens neste uke): 8.1, 8.2, 8.3, 8.4, 8.6, 8.25 og 8.27.
Fra Lars:
Jeg har nå forelest kap. 8 fram til teorem 8.14.
Neste uke vil jeg bruke litt tid på beviset av teorem 8.14 (ca. en time). Deretter vil jegbegynne å forelese seksjon 8.4 (om kompleksitetsklassene L og NL).
Fra Lars:
Jeg er ferdig med å forelese kapittel 7. Etter påske begynner jeg å forelese kapittel 8 (Space Complexity). God påske.
Den tredje (og siste) obligatoriske oppgaven i kurset finner du her:
Fra Lars:
God mandag morgen. Denne uken vil vi bruke mye av forelseningstiden på beviset for at SAT (3SAT) er NP-komplett (jeg rakk ikke å forelese dette beviset forrige uke slik jeg oprinnelig hadde satt meg fore). Det er et langt og vanskelig bevis. Oppgaver som skal løses denne uken finner dere på listen nedenfor.
Vi vil også bruke litt forelesningstid tid på beviset for at 3SAT er polynom-tid reduserbart til SUBSET-SUM, men detaljene i beviset vil bli gått gjennom i gruppeundervisningen.
Fra Lars:
Jeg har sammen med gruppelærerne laget en liste som består av følgende oppgaver:
7.13, 7.27, 7.35, 7.37, 7.43, 7.43, 7.44, 7.49, og 7.50.
Oppgavene på denne lista anbefales. De kommende ukene vil et utvalg av oppgavene gjennomgås i guppetimene. Gruppelærerne vil gi nærmere informasjon om hvike av oppgavene de vil prioritere.
Vær oppmerksom på at disse oppgavene slett ikke er enkle. Man kan ikke forvente at man klarer å løse alle oppgavene på egenhånd.
Fra Lars:
Denne uken har jeg forelest fra seksjon 7.3 og seksjon 7.4. Forelesningene i neste uke vil også dreie seg om stoff i seksjon 7.4, og vi vil bruke mye av forelesningstiden på beviset av teorem 7.37 (SAT is NP-complete). Forhåpentligvis rekker jeg også å forelese litt fra seksjon 7.5 i løpet av neste uke.
Fra Lars:
Neste uke fortsetter jeg å forelese stoffet i seksjon 7.3. Deretter starter jeg å forelsese seksjon 7.4 (sannsynligvis i annen time på trisdag eller på onsdag).
Fra Lars:
Side 322 (exercises): 7.1, 7.5, 7.6, 7.7, 7.8, 7.9, 7.10.
Hvis man man er spesielt interessert og har tid til å gjøre enda flere oppgaver kan man også prøve seg på 7.11 og 7.12.
Fra Lars:
Forelesningene i kompleksitetsteori har startet. Forelesningene i kompleksitetsteori vil følge boka (alt jeg sier står i boka, men jeg vil ikke si alt som står i boka). I løpet av denne første uka regner jeg med å komme meg gjennom sånn circa de tre første seksjonene av kapittel 7 (side 275-298).
Stor-O notasjon er viktig. Det står også noe i boka om liten-o notasjon. Alt om liten-o notasjon kan glemmes nå i første omgang. Vi vil gjennomgå liten-o notasjon mot slutten av kurset dersom vi skulle få brukt for det. (Om vi får brukt for det, eller ikke, avhenger av hva vi legger opp som pensum.)
Boka er tung og vanskelig å lese. Det kan være en god ide å følge forelesninger for å finne ut hva i boka som er essensielt og hva som som er mindere essensielt.
Oblig 1 has now been published. Please submit your solutions as a single PDF to Devilry by 20 February, 23:59. Those of you who wish to use LaTeX can use the oblig source file as a starting point. If you have any questions feel free to ask me or any of the group teachers.
Unfortunately, I am going to have to cancel tomorrow's lecture as well due to sickness. We will resume again on Wednesday, where we will talk about the next level of languages: context-free languages.
Hi,
tomorrow's lecture must unfortunately be cancelled due to sickness. This is not a problem, as we went through the important material for this week in today's lecture.
Some students were wondering about minimization of DFAs, that is, given a DFA is it possible to find an equivalent DFA with a minimal number of states. This is, in fact, possible! For those who are interested, I recommend looking into the Myhill-Nerode theorem and, for example, Hopcroft's algorithm.
This is not exam relevant, just something to look into if you're interested.