INF4130 – Algoritmer: Design og effektivitet
Beskrivelse av emnet
Timeplan, pensum og eksamensdato
Kort om emnet
Gjennomgang av generelle algoritme-klasser som dynamisk programmering, heuristiske algoritmer, probabilistiske algoritmer med mer, samt av et representativt utvalg enkelt-algoritmer som l?ser aktuelle problemer. Vekt p? effektivitetsvurdering. Videre gjennomg?es den grunnleggende teorien for NP-kompletthet (hvilke problemer kan ikke l?ses i ”rimelig” tid), og for uavgj?rbarhet (hvilke problemer har ingen l?sningsalgoritme).
Hva l?rer du?
Etter ? ha tatt INF4130 kan du
- kjenne og kunne programmere viktige algoritmer innen flere sentrale andvendelsesomr?der.
- kjenne og kunne anvende de viktigste prinsipper for design av effektive algoritmer.
- vurdere hvor effektiv en gitt algoritme er, og kjenne begrepet ?polynomiske algoritmer?.
- kunne kjenne igjen problemer som ikke kan l?ses ved noen algoritme.
- kunne kjenne igjen problemer som kan l?ses algoritmisk, men ikke p? noen effektiv m?te.
Opptak og adgangsregulering
Studenter m? hvert semester s?ke og f? plass p? undervisningen og melde seg til eksamen i Studentweb.
Dersom du ikke allerede har studieplass ved UiO, kan du s?ke opptak til v?re studieprogrammer, eller s?ke om ? bli enkeltemnestudent.
Forkunnskaper
Anbefalte forkunnskaper
Emnet bygger p? INF1010 – Objektorientert programmering (videref?rt) og det anbefales sterkt ? ha tattINF2220 – Algoritmer og datastrukturer (videref?rt)/INF 110/HUMIT2720MN – Datalingvistikk 1 (nedlagt)/HUMIT2720 – Datalingvistikk 1 (nedlagt).
Overlappende emner
- 10 studiepoeng overlapp mot INF3130 – Algoritmer: Design og effektivitet (nedlagt)
- 3 studiepoeng overlapp mot INF4200 – Algoritmer og effektivitet (nedlagt)
Undervisning
2 timer forelesning og 2 timer gruppe?velser pr uke. Det kreves gjennomf?ring av obligatoriske oppgaver. Les mer om krav til innlevering av oppgaver, gruppearbeid og lovlig 欧洲杯在线买球_欧洲杯投注网站推荐@ under retningslinjer for obligatoriske oppgaver.
Eksamen
4 timer skriftlig eksamen. Alle obligatoriske oppgaver m? v?re godkjente for ? kunne g? opp til eksamen.
Karakterskala
Emnet bruker karakterskala fra A til F, der A er beste karakter og F er stryk. Les mer om karakterskalaen.
Begrunnelse og klage
Adgang til ny eller utsatt eksamen
Studenter som dokumenterer gyldig frav?r fra ordin?r eksamen, kan ta utsatt eksamen i starten av neste semester.
Det tilbys ikke ny eksamen til studenter som har trukket seg under ordin?r eksamen, eller som ikke har best?tt.
Trekk fra eksamen
Det er mulig ? ta eksamen i emnet inntil tre ganger. Dersom du trekker deg fra eksamen etter fristen eller under eksamen, bruker du et eksamensfors?k.
Som eksamensfors?k i dette emnet teller ogs? fors?k i f?lgende tilsvarende emner: INF3130 - Algoritmer: Design og effektivitet.
Annet
Det er sterkt anbefalt ? m?te p? f?rste forelesning fordi det vil bli gitt viktig informasjon.