Dette er en oversikt over vanlige spørsmål (Frequently Asked Questions) om IT1105 Algoritmer og datastrukturer, både faglige og om det praktiske opplegget. Hvis det er noe du lurer på, så kan det hende at noen har spurt om det får, og da vil det forhåpentligvis stå her.

I Hvis du vil sende oss en mail med spørsmålet ditt, gjør gjerne det, men forsikre deg først om at du ikke kan få svar på spørsmålet av en stud-ass og at spørsmålet ikke står besvart nedenfor. Hvis du bestemmer deg for å sende en mail, ta gjerne en kikk på How To Ask Questions The Smart Way av Eric S. Raymond. (Om ikke annet, så kikk i hvert fall igjennom innholdsfortegnelsen.)

Oversikt

1.1   Øvingen min blir ikke automatisk godkjent. Hva skal jeg gjøre?

Hvis du ikke får øvingen automatisk godkjent, kan du ta kontakt med en stud.ass. eller und.ass. De kan ofte gi litt hjelp og råd om hvordan du kan få programmet fungerer. Dersom dette krever store omskrivinger, og du ikke er instilt på dette, kan stud.assen godkjenne øvingen på grunnlag av at det er et godt forsøk. Merk at dette kun gir 40% uttelling.

1.2   Kan jeg sende kildekoden per mail til fagansvarlige?

Nei. Vi får nok mail som det er. Det nytter lite å sende oss kildekoden når det er systemet eller stud.ass'ene som skal godkjenne den. Enten lever ved hjelp av øvingssystemet eller henvend deg til en stud.ass.

1.3   Er øvingene obligatoriske?

Øvingsopplegget er obligatorisk, men det kreves ikke at man gjør alle øvingene. For mer informasjon, se på siden med øvingsoppgaver (i avsnittet "Om øvingsopplegget", under tabellen med alle øvingene).

1.4   Teller øvingene direkte for karakteren i faget?

Nei, det gjør de ikke.

1.5   Kan vi samarbeide om øvingene?

Det er ikke anledning til å levere felles besvarelser; hver student skal levere sin egen besvarelse for de øvinger han eller hun har gjort. Ut over dette er det naturligvis tillatt å hjelpe hverandre og samarbeide om å løse oppgavene. (Direkte kopiering av en annens øving, såkalt "kok", regnes ikke som samarbeid, og aksepteres ikke.)

1.6   Kan vi forandre rammeverket på øvingene?

Ja, med mindre det står i øvingen at du ikke kan gjøre dette.

1.7   Jeg klarer å finne svaret på test-caset. Bør jeg utnytte det?

Nei. Vi kommer til å kontrollere mistenkelig raske programmer manuelt, og vi vil kreve at resultatene er etterprøvbare. Vi aksepterer ikke at man "jukser" på denne måten.

1.8   Hvilke forelesnings-transparenter legges ut på nettet?

Det er ikke noen klar systematikk her; det kommer an på den enkelte foreleser. I utgangspunktet er det bare transparenter fra øvings­gjennomgangene som blir lagt ut (men heller ikke der kan det garanteres at alle vil være tilgjengelige). Merk at det kan gå noen dager fra forelesningen til notatene legges ut, siden det kan være nødvendig å rette opp feil og lignende.

1.9   Kan jeg levere øvinger i et annet språk enn Python/Java?

Ja, se leveringsskjemaet for en oversikt over hvilke språk som er støttet. Du er ikke garantert at noen av assistentene kan hjelpe deg hvis du skriver i andre språk.

1.10   Hvorfor får bare bonuspoeng for levering i Python og Java?

Dette er ikke ment som et forsøk på å tvinge folk til å bruke python eller java. Det kreves såpass få poeng for å bestå øvingsopplegget at ingen skal være avhengige av disse bonuspoengene. De er kun ment som ekstra motivasjon. Hvis det skulle vært bonuspoeng for alle språk, måtte poeng blitt beregnet ut ifra sammenligning med andre som har levert i samme språk. Dette ville ført til at det lønte seg å levere i så obskure språk som mulig.

1.11   Jeg har fått øvingene godkjent fra før. Må (eller kan) jeg gjøre dem om igjen?

Hvis du har fått godkjent øvingsopplegget i et tidligere semester trenger du ikke å følge øvingsopplegget. Du kan melde deg på eksamen i nåværende semester via StudentWeb. Hvis du har spørsmål om godkjenning kan du ringe instituttekspedisjonen.

Husk uansett på at øvingene iblant endres fra år til år, så på grunn av dette og for treningens del kan det være lurt å gjøre øvingene på nytt uansett. Din gamle brukerkonto vil ha blitt slettet, men det er fritt frem for å registrere seg på nytt og begynne å levere øvinger, uten at man da binder seg til å måtte oppnå poengkravet på nytt.

Et spesialtilfelle er om du f.eks. har fått godkjent øvingsopplegget i IT1105 og har tenkt å ta eksamen i IT1105. Dette vil også normalt være uproblematisk men du må da ta kontakt for å få en eksplisitt godkjenning. Oppgi i så fall hvilket år du fulgte øvingsopplegget og hva brukernavnet ditt var.

1.12   Hvilke hjelpemidler er tillatt på eksamen?

Bestemt enkel kalkulator. Ingen trykte eller håndskrevne hjelpemidler er tillatt; merk at dette er en endring fra tidligere år. Hjelpemiddelkoden er D. For mer informasjon om hjelpemidler, se Instruks for eksamenskandidater.

1.13   Når er eksamen?

1.14   Når kommer sensuren?

Dette kan vi sjelden gi noe nøyaktig svar på. Enten jobber vi fremdeles med sensuren (og kan da ikke gi annet enn et grovt estimat) ellers så er resultatene overlevert administrasjonen, og saken er da i deres hender. Generelt (i følge reglementet) skal resultatene være tilgjengelige innen tre uker fra eksamensdato (+ helligdager, med 10 dagers tillegg for julehelga) eller første virkedag etter dette, og vi prøver å holde denne fristen. Sensuren vil først bli tilgjengelig i institutt-ekspedisjonen. Det tar gjerne lenger tid før studweb og sensurtelefon blir oppdatert.

1.15   Når legger dere ut løsningsforslag til eksamen?

Etter eksamen (naturligvis), og antagelig etter at sensuren er ferdig, ettersom det kan dukke opp ting under sensur som vi vil få med i løsningsforslaget (uklarheter i oppgaven, for eksempel).

1.16   Hvordan får jeg skrevet ut disse nettsidene?

Velg "Utskrifts-versjon" i menyen til venstre, så vår du opp en mer skriver-vennlig versjon av den siden har oppe.

1.17   Er det flere pensumbøker?

Nei, det er kun Introduction to Algorithms (Cormen et al., MIT Press), tredje utgave, som er pensum.

1.18   Hva er ntnu.fim.idi.algdat?

Det er en såkalt nyhets-gruppe (newsgroup) som du kan bruke med et eget program (en såkalt newsreader). PINE og Outlook Express kan brukes til dette. Under unix har du for eksempel xrn, trn og slrn, eller hvis du bruker Emacs, kan du lese news med Gnus.

Hvis du er usikker på hvilket program du skal bruke, kan du klikke her og se hva som skjer. Forhåpentligvis får du opp et program du kan bruke. Det er mulig du må oppgi et server-navn. Da kan du bruke:

Nyhetsgrupper brukes for elektroniske plenums-diskusjoner ved hjelp av tekstlige meldinger, omtrent som e-post. For mer informasjon kan du lese ITEA sin nettside om News ved NTNU.

Se også www.usenet.no og eventuelt denne FAQ'en om hvordan du setter opp newsreaderen din.

1.19   Hvordan bruke PINE til å lese news?

På hovedskjermen, velg SETUP (S). Velg deretter Config (C). Gå til nntp-server (den 4. øverste verdien i versjon 4.58) og endre verdien (C) til 'news.ntnu.no'. Gå ut av setup (E) og velg å lagre endringene hvis du blir spurt.

I Folder list, vil du kunne velge mellom "Mail" og "News". Velg News og legg til nyhetsgruppene du vil lese.

1.20   Hvorfor er det ikke pensum-referanser i øvingene?

Vi prøver å være mer problem-orienterte (evt. løsnings-orienterte, avhengig av perspektiv ;) enn pensum-orienterte. Det er ikke alltid lett å finne ut hvilken del av pensum som er relevant, og det er ikke heller alltid meningen. Tanken er at man skal lære noe av å finne løsninger på problemene, ikke at man skal slå opp i pensum og finne en ferdig løsning der. Vi vil likevel referere til relevant kapittel på en del oppgaver, i tillegg til at oppgavene vanligvis omhandler emner som er gjennomgått på forrige forelesing.

1.21   Hvordan blir jeg med i øvings-opplegget?

Det er bare å logge seg inn på leverings-sidene. Første gang du logger deg inn, blir navnet ditt registrert.

1.22   Hvordan får jeg tildelt stud.ass?

Øvingene blir rettet automatisk. Vi har derfor valgt å ikke knytte dere til faste stud.asser. I stedet kan dere ta kontakt med den stud.assen dere vil på sal. Under lenken "timeplan" kan du se når det er stud.asser på sal.

1.23   Hvordan fungerer poengberegningen på praksisøvingene?

Korrekthetspoeng er intuitivt nok avhengig av hvor mange av testene programmet ditt passerer.

Hastighetspoeng er en bonus på en del øvinger, men blir ikke tildelt med mindre alle korrekthetstestene er godkjent. Når innleveringsfristen er ute, vil hastighetspoengene bli beregnet ut ifra din beste kjøretid sammenlignet med de andres kjøretider.

1.24   Hvordan lese dokumentene på denne siden?

Alle dokumenter på disse nettsidene skal enten være tilgjengelige som i HTML-format eller i PDF-format. For å lese PDF-filer, må du ha et eget program (eller en utvidelse til nettleseren din) som skjønner dette formatet. De to vanligste programmene for dette er Acrobat Reader og Ghostview. Acrobat Reader finnes også som plug-in (en utvidelses-modul) for de vanligste nettleserne. For å laste ned et av disse programmene, kan du bruke knappene nedenfor.

I tillegg til PDF, så er enkelte dokumenter også tilgjengelig i PostScript-format. Ghostview kan brukes til å lese disse også. Noen få dokumenter vil i tillegg være tilgjengelige i proprietære formater, som Microsoft Word.

1.25   Jeg får ikke tilgang til øvingstjeneren, hva er galt?

Øvingstjeneren kjøres av fagstaben og det hender den dør slik at du får beskjed om at den ikke er tilgjengelig når du klikker på en lenke til den (f.eks. Øvingsoppgaver eller Øvingslevering i menyen). Det kjøres en automatisk sjekk av øvingstjeneren hver hele og halve time, men det er ikke alltid denne klarer å starte øvingstjeneren. Hvis det haster med å få tilgang på å se øvingsoppgaver/levere øvinger, kan du ringe teknisk ansvarlig for web (se kontakt). Telefonnummeret finner du ved å søke i telefonkatalogen.

1.26   Jeg får ikke python til å virke på datasalen, hva er galt?

Dessverre har vi litt oppstartsproblemer med dette pga drift. Det er endel ting vi kan foreslå som muligens vil løse problemet midlertidig. Hvis du får beskjed om at python ikke eksisterer på maskinen du sitter på er løsningen følgende:
Bruk Remote Desktop til ts-stud02.idi.ntnu.no. Denne har ny versjon av python installert. Remote desktop finner du på windows på Start-menyen - All Programs - Accessories - Communications - Remote Desktop. Dersom du skulle ha lyst til å gjøre tilsvarende på *nix kan du bruke kommandoen rdesktop, men du kan like gjerne bruke ssh mot en idi-server her. Disse har python installert.

Hvis du opplever at det ikke skjer noen ting når du skriver python mittprogram.py, er grunnen at det ligger noe annet i PATH miljøvariabelen som heter python. Du kan få denne mistanken bekreftet ved å skrive which python i cmd. Ideellt sett skal den første oppføringen her være: c:\python24\python.exe, men hos fagstaben fungerer det fint selvom o:\tools\python.cmd står først. Måten å få det til å virke er nå å modifisere pathen sin. Dette kan gjøres på to måter. Den ene er å gjøre det i kommandolinjen hver gang du starter et nytt cmd-shell, ved følgende kommando:
set PATH=c:\python24\;%PATH%
Ellers kan du modifisere pathen i kontrollpanelet.
Uansett ser vi gjerne at du sender oss en mail dersom du har slike problemer. Sørg for at vi får vite brukernavnet ditt, og gjerne resultatet av which python-kommandoen, så tar vi kontakt med drift.

1.27   Arrangeres det midtsemesterprøve?

Nei, det vil ikke bli arrangert noen prøve midt i semesteret. Det vil helt sikkert ikke bli gitt noen karaktergivende oppgaver (f.eks. midtsemestereksamen) i løpet av semesteret (se studiehåndboken).

1.28   Hvordan få tilgang til datasaler?

Hvis du ikke har tilgang til datasalene der det gis veiledning, send en mail til øvingsansvarlig (venstad (at) idi.ntnu.no). Denne mailen må innholde navn på de som mangler tilgang samt kortnummer. Kortnummeret finnes på baksiden av studentkortet. Det skal være en 6-sifret kode som står under strekkoden.

1.29   Hvordan kan jeg logge ut av øvingssidene?

Vi bruker https-innlogging med en mekanisme fra Innsida, og det er ikke mulig på noe enkelt vis å få til utlogging fra vår side. Det enkleste er å avslutte nettleseren din helt; du vil da bli utlogget. Hvis du ønsker å unngå det kan du skru på privat modus i nettleseren før du logger inn. Da vil du bli logget ut når du lukker de relevante vinduene. (Du bør selv sjekke at dette faktisk stemmer for din nettleser.)

2.0   Faglige spørsmål

2.1   Hva er målet med faget?

Fra studiehåndboken:

Læringsmål: Å gi studentene nært kjennskap til et bredt spekter av etablerte algoritmer med nytteverdi på tvers av mange fagområder.

2.2   Hvilke forutsetninger kreves for å ta faget?

Fra studiehåndboken:

Anbefalte forkunnskaper: Bygger på emnene IT1103 Programmering GK og MA0301 Elementær diskret matematikk for informatikere

Hvis du føler at programmeringsferdighetene er litt rustne, så er det kanskje på tide å pusse litt på dem. En kjapp repetisjon av litt diskret matematikk kan også være lurt. (Har du ikke hatt diskret matematikk er det ingen grunn til å fortvile.)

2.3   Hva er en algoritme?

En algoritme er en vel-definert prosedyre som tar en verdi, eller en mengde verdier, som input og produserer en verdi, eller en mengde verdier, som output. En algoritme er altså en sekvens av trinn som transformerer input til output, med andre ord en "oppskrift" for å løse et problem i et endelig antall trinn.

2.4   Hva er en datastruktur?

En datastruktur er en måte å organiserte data på, som gjør at man kan utføre enkelte operasjoner på spesielt effektivt på dem.

2.5   Krever faget dyp forståelse av språket Python/Java?

Nei. Du må beherske grunnleggende programmering i Python eller Java for å kunne besvare programmerings-delen av øvingene og forstå eventuelle programmer på eksamen, men det er alt. Det du lærer i dette faget er (eller bør være) mest mulig uavhengig av programmerings-språk. Grunnen til at vi har valgt å bruke akkurat Python i øvingene og evt. på eksamen, er at dette er et lettlært språk som kan ligge ganske nært pseudokode. Java brukes i mange andre fag på NTNU, og er derfor inkludert.

De fleste kode-eksemplene, både i læreboka og i forelesningene, skrives med pseudokode. Eventuelle algoritmer som skal beskrives på eksamen kan også beskrives med pseudokode. Du må likevel kunne lese og forstå algoritmer skrevet i Python. Forhåpentligvis vil det være lettere å konvertere mellom Python og pseudokode og vice versa enn mellom pseudokode og f.eks. java.

2.6   Hvordan fungerer divisjon i Python?

For å utføre heltallsdivisjon, bruk operatoren '//', for eksempel er '1//2' lik '0'. For å utføre flyttallsdivisjon, bruk operatoren '/' med minst ett flyttall som argument, for eksempel er '1.0/2' lik '0.5'. I nåværende Python-versjoner utfører '/' heltallsdivisjon, men i fremtidige er den ment å utføre flyttallsdivisjon.

2.7   Er sortering Omega(n·log(n))?

Det er ikke riktig å si at "sortering er Omega(n·log(n))", dvs. at kjøretiden for alle sorterings-algoritmer er Omega(n·log(n)). Følgende antagelser/kvalifikasjoner gjelder:

1. Man kan bare sammenligne (og bytte om på) to elementer om gangen.
   Hvis man dropper denne antagelsen ved at man f.eks. vet noe om verdi-området, kan man bruke algoritmer som telle-sortering eller radiks-sortering, som har lineær kjøretid.

2. Det er snakk om kjøretiden i verste tilfelle (worst case).
   Det er mange sorterings-algoritmer som har en beste kjøretid som er bedre enn dette (f.eks. boble-sortering).

Med andre ord: For enhver sorterings-algoritme som baserer seg på sammenligning og ombytting av to og to elementer er worst case-kjøretiden Omega(n·log(n)), der n er antall elementer som skal sorteres.

2.8   Hvordan virker memoisering?

Memoisering er en måte å implementere dynamisk programmering på, som i mange tilfeller kan være enklere enn en rent iterativ variant. Det kan ofte være nyttig hvis man har en rekursiv funksjon som beregner de samme del-progblemene flere ganger. Istedenfor å kalle funksjonen rekursivt på disse hver gang (som gjerne gir eksponensiell kjøretid), lagrer man resultatene i en tabell den første gangen de beregnes, og returnerer senere disse. Se pseudokode nedenfor.

f_table = {}

function f(n)
   if f_table[n] == nil then
      f_table[n] = <tungt rekursivt kall som bruker f() flere ganger>
   end
   return f_table[n]
end

2.9   Hva er P, NP, NPC og NP-Hard?

Først (til dere som ikke orker å lese hele dette avsnittet): NPC innebærer ikke nødvendigvis en eksponensiell (eller ikke-polynomisk) kjøretid. Man kan godt ha et NP-komplett problem som kan løses av en algoritme med polynomisk kjøretid — teoretisk sett. Ihvertfall har ingen bevist at det er umulig. Dessverre har ingen funnet en slik algoritme...

P, NP, NPC og NP-Hard er fire klasser av problemer (ikke algoritmer). Det finnes mange flere slike klasser. Man begrenser seg gjerne til ja/nei-problemer når man diskuterer NP-kompletthet.

P er klassen av problemer som kan løses i polynomisk tid.
NP er klassen av problemer der man kan teste et bevis for et "ja"-svar i polynomisk tid.

P står altså for "polynomial" og NP for "non-deterministic polynomial". Alle P-algoritmer kan også testes i polynomisk tid, så P er en delmengde av NP.

Men hva er så NPC?

Poenget er at man ikke vet om "P=NP" eller ikke. Hvis P=NP kan alle problemer der en løsning kan testes i polynomisk tid også løses i polynomisk tid. Hvis noen skulle klare å vise dette (eller motbevise det) ville det være en sensasjon.

En nøkkel til en slik løsning er klassen NPC ("NP-komplette problemer"). Klassen NPC er definert slik:

Hvis det finnes en polynomisk løsning for et problem i NPC så finnes det polynomiske løsninger for alle problemer i NP.

Dette er tilsvarende for såkalte "komplette" problemer i andre problem-klasser: Hvis man har en polynomisk løsning for et komplett problem i klassen, kan alle problemer i klassen løses i polynomisk tid. De komplette problemene er altså de "vanskeligste" problemene i klassen. Man kan altså si at de NP-komplette problemene er de vanskeligste (minst like vanskelige som de andre) i klassen NP.

Merk at dette faktisk er den definerende egenskapen til klassen NPC. Omvendt kan man si at hvis et av problemene i NP har en eksponensiell nedre grense, så har alle problemene i NPC (men ikke nødvendigvis alle problemene i NP) også en eksponensiell nedre grense.

For å bevise at et problem er NP-komplett må man altså bevise at problemet har denne egenskapen: Hvis problemet kan løses i polynomisk tid så må det implisere at alle problemer i NP også kan løses i polynomisk tid. I praksis er dette et svært vanskelig problem. Heldigvis har vi teoremer som Cook-Levin-teoremet som sier at:

SAT er NP-komplett (NPC).

(Se pensum for mer om SAT.) For å bevise det viser man at alle problemer i NP kan reduseres til SAT i polynomisk tid.

Når vi så har ett slikt problem er det lettere å bevise den samme egenskapen hos andre problemer. Det holder at vi (i polynomisk tid) kan transformere et kjent NP-komplett problem til vårt problem. Det er da innlysende at problemet vårt også har NPC-egenskapen. (Med andre ord: Hvis vi kan løse vårt problem i polynomisk tid, kan vi transformere alle andre NPC-problemer til det i polynomisk tid, og dermed løse disse. Alle NP-problemer kan reduseres til NPC-problemer, og altså også til vårt problem i polynomisk tid, og kan dermed også løses i polynomisk tid.)

En praktisk side ved klassen NPC er at NP-komplette problemer er kjent for å være vanskelige å løse. (Ingen har funnet noen polynomiske løsninger for dem ennå). Hvis man kan vise at et problem er NP-komplett vet man altså at det er et (svært) vanskelig problem...

At et problem er NP-hard ("NP-vanskelig") er noe annet. Det defineres slik:

Et problem er NP-hard hvis alle problemer i NP kan reduseres til det i polynomisk tid, selv om det ikke nødvendigvis selv ligger i NP.

Dette er altså verken det samme som P, NP eller NPC. NP-hard brukes gjerne om optimeringsproblemer, for eksempel, som er "minst like vanskelige" som et beslektet beslutningsproblem.

3.0   Diverse

3.1   Hvordan uttales "Dijkstra"?

Dijkstra er et hollandsk navn, som uttales omtrent [dejk-stra]. Mannen bak den såkalte "Dijkstras algoritme" er Edsger Wybe Dijkstra (f. 1930 i Rotterdam). Algoritmen konstruerte han opprinnelig i 1956.

3.2   Hvordan uttales "Knuth"?

Ifølge Donald E. Knuth's egen FAQ uttales navnet [ka-nooth], eller med fornorsket "lydskrift": [k'nooth]. "K"-en er altså ikke stum som i endel andre engelske ord og navn.

3.3   Hva er forskjellen på "ikke nødvendigvis" og "nødvendigvis ikke"?

(Kanskje ikke direkte relevant for faget, men irritasjons-moment ved eksamensretting.)

Disse to formuleringene har vidt forskjellige betydninger, noe det kan være lurt å tenke på i en eksamensbesvarelse, f.eks.

"Ikke nødvendigvis" betyr at noe ikke er nødvendig, mens "nødvendigvis ikke" betyr at det er nødvendig at noe ikke inntreffer. F.eks:

"Noen av delproblemene må ikke nødvendigvis løses." Dette betyr at det er noen delproblemer det ikke er nødvendig å utføre.

"Noen av delproblemene må nødvendigvis ikke løses." Dette betyr at det er noen delproblemer der det er nødvendig at vi ikke utfører dem. De skal/kan med andre ord ikke løses.

Her er det stort potensiale for rot. Hva med f.eks. "Ikke noen av delproblemene må nødvendigvis løses"?

3.4   Jeg har funnet selvmotsigende informasjon på disse sidene. Hva er riktig?

Sjekk datoene på sidene der du fant informasjonen. De nyeste opplysningene er antagelig riktige. Hvis det er snakk om viktig informasjon (om pensum, f.eks.) så gi gjerne beskjed.

3.5   Spørsmålet mitt er ikke besvart her. Hva gjør jeg?

Først, sjekk om det har blitt gitt noen beskjeder om saken. Deretter, forsikre deg om at informasjonen du leter etter ikke er tilgjengelig via disse nettsidene.

Hvis du har et spørsmål som du mener burde besvares her, enten fordi du selv lurer på det eller fordi du har inntrykk av at mange andre lurer på det, så send en mail til algdat@idi.ntnu.no.