Algoritmer

Kursen kan ingå i följande program:

1. Datavetenskap, kandidatprogram (N1COS)
2. Computer Science, masterprogram (N2COS)
3. Applied Data Science, masterprogram (N2ADS)
4. Matematiska vetenskaper, masterprogram (N2MAT)
5. Matematikprogrammet (N1MAT)

Kursen ges även som fristående kurs vid Göteborgs Universitet.

Ett krav är att ha en kandidatexamen om 180 hp inom datavetenskap (eller motsvarande), alternativt avklarade kurser om 120 hp i ämnena datavetenskap och matematik. Vidare gäller följande krav:

• 7,5 hp diskret matematik (DIT984 Diskret matematik för datavetare, eller delkursen Inledande algebra i MMG200 Matematik I, eller motsvarande),
• ytterligare 10 hp matematik,
• 15 hp programmering, och
• 7,5 hp datastrukturer (DIT962 Datastrukturer, DIT375 Python for Data Scientists, eller motsvarande).

Följande kunskapsnivå i Engelska krävs: Engelska 6/Engelska nivå 2 eller motsvarande från ett erkänt internationellt test, t.ex. TOEFL, IELTS.

Kursen ger kunskaper om:

• Vad är kriterier för en effektiv algoritm?
• Verktyg för analys av algoritmer. O-notation. Analysera loopar och rekursiva anrop. Lösa rekurrensrelationer.
• Datastrukturer och algoritmer. Granskning av grundläggande datastrukturer.
• Grafalgoritmer.
• Giriga algoritmer.
• Divide-and-conquer.
• Dynamisk programmering.
• Uttömmande sökning.
• Grundläggande komplexitetsteori. Komplexitetsklasserna P, NP och NPC, reduktioner. Exempel på NP-fullständiga problem. Att hantera svåra problem.
• Kombinera olika designtekniker och datastrukturer.
• Kort orientering om andra designtekniker: exempelvis randomiserade algoritmer, förbehandling, etc.

Efter godkänd kurs ska studenten kunna:

Kunskap och förståelse

• beskriva algoritmer och deras egenskaper: förklara algoritmer skriftligen, så att andra kan förstå hur de fungerar, varför de är korrekta och snabba, och var de är användbara;
• inse att icke-triviala beräkningsproblem, som måste lösas med hjälp av algoritmer, dyker upp i olika verkliga datortillämpningar och att formalisera dem;
• intractability: känna igen "intractable problems" och andra klasser av problem som P, NP, NPC;
• bevisa korrektheten av algoritmer.

Färdigheter och förmåga

• design: tillämpa de viktigaste designteknikerna för effektiva algoritmer (t.ex. giriga, dynamisk programmering, divide-and-conquer) på problem som liknar läroboksexemplen men är nya;
• utföra hela utvecklingscykeln av algoritmer: problemanalys, välja, modifiera och kombinera lämpliga tekniker och datastrukturer, analys av korrekthet och komplexitet, hitta möjliga förbättringar, etc.;
• utföra enkla reduktioner mellan problem, förklara NP fullständighet och känna igen olika beräkningssvåra problem som tenderar att dyka upp om och om igen i olika applikationer.

Värderingsförmåga och förhållningssätt

• kritiskt bedöma algoritmiska aspekter och visa förmåga att se igenom uppenbara och tillsynes rimliga algoritmer som ofta visar sig vara felaktiga,
• analysera: förklara varför tidseffektivitet hos algoritmer är avgörande, uttrycka tidskomplexitet på ett rigoröst och vetenskapligt korrekt sätt, analysera tids komplexiteten hos algoritmer (summera operationer i nästlade loopar, lösa vanliga rekursionsekvationer, etc.) det vill säga göra en objektiv bedömning av prestanda för att kunna jämföra med andra algoritmer.

Kursen ges i form av föreläsningar, kombinerat med övningstimmar för problemlösning och ett antal inlämningsuppgifter som syftar till att utveckla förmågan att analysera och utforma algoritmer.

Undervisningsspråk: engelska

Kursen examineras genom individuell skriftlig salstentamen.

Om en student som har underkänts två gånger på samma examinerande moment önskar byta examinator inför nästa examinationstillfälle ska en sådan begäran bifallas om det inte finns särskilda skäl däremot (6 kap. 22 § HF).

Om en student har fått besked om pedagogiskt stöd från Göteborgs universitet med rekommendation om anpassad examination och/eller anpassad examinationsform kan examinator, i det fall det är förenligt med kursens lärandemål och förutsatt att inte orimliga resurser krävs, besluta att bevilja studenten anpassad examination och/eller anpassad examinationsform.

Om en kurs har avvecklats eller genomgått en större förändring ska studenten erbjudas minst två examinationstillfällen, utöver ordinarie examinationstillfälle. Dessa tillfällen fördelas under en tid av minst ett år, dock som längst två år efter det att kursen avvecklats/förändrats. Vad gäller praktik och verksamhetsförlagd utbildning (VFU) gäller motsvarande, men med begränsning till endast ett ytterligare examinationstillfälle.

Om en student har fått besked om att denne uppfyller kraven för att vara student vid Riksidrottsuniversitetet (RIU-student) har examinator rätt att besluta om anpassning vid examination, om detta görs i enlighet med Lokala regler gällande RIU-studenter vid Göteborgs universitet

Delkurser

1. Skriftlig salstentamen, 7,5 hp
   Betygsskala: Mycket väl godkänd (5), Väl godkänd (4), Godkänd (3) och Underkänd (U)

Kursen utvärderas genom möten, både under och efter kursen, mellan lärare och studentrepresentanter. Ett anonymt skriftligt frågeformulär skickas även ut till studenterna efter kursens slut. Resultaten av utvärderingarna används för att förbättra kursinnehållet och som indikation till vilka delar som skulle kunna läggas till, tas bort, förbättras eller ändras.

Kursen är samläst med Chalmers.

Kursen ersätter DIT602 Algorithms, 7,5 hp. Den här kursen kan inte ingå i en examen som innehåller DIT602. Den kan inte heller ingå i en examen som bygger på en annan examen där DIT602 ingår.