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.