Sök i kursutbudet

Använda sökfunktionen för att hitta i Chalmers utbildningsutbud, både vad gäller kurser och program. När det finns en kurshemsida visas en hus-symbol som leder till denna sida. Tänk på att välja det läsår du vill se information om.
Sök program och utbildningsplaner


Institutionernas kurser för doktorander

​​​​​​​​​​​​​​​​​​​​

Kursplan för

Läsår
TIN093 - Algoritmer  
Algorithms
 
Kursplanen fastställd 2020-02-11 av programansvarig (eller motsvarande)
Ägare: MPALG
7,5 Högskolepoäng
Betygskala: TH - Mycket väl godkänd (5), Väl godkänd (4), Godkänd (3), Underkänd
Utbildningsnivå: Avancerad nivå
Huvudområde: Datateknik, Informationsteknik
Institution: 37 - DATA- OCH INFORMATIONSTEKNIK


Kurstillfälle 1


Undervisningsspråk: Engelska
Anmälningskod/tillfälleskod: 02122
Sökbar för utbytesstudenter: Ja
Blockschema: A
Max antal deltagare: 135
Endast studenter med kurstillfället i programplan

Modul   Poängfördelning   Tentamensdatum
Lp1 Lp2 Lp3 Lp4 Sommarkurs Ej Lp
0114 Tentamen 7,5hp Betygskala: TH   7,5hp   24 Okt 2020 em L   05 Jan 2021 fm J   26 Aug 2021 em J

I program

MPDSC DATA SCIENCE OCH AI, MASTERPROGRAM, Årskurs 1 (obligatoriskt valbar)
MPDSC DATA SCIENCE OCH AI, MASTERPROGRAM, Årskurs 2 (valbar)
MPALG DATAVETENSKAP - ALGORITMER, PROGRAMSPRÅK OCH LOGIK, MASTERPROGRAM, Årskurs 1 (obligatorisk)
MPCAS KOMPLEXA ADAPTIVA SYSTEM, MASTERPROGRAM, Årskurs 1 (obligatoriskt valbar)
MPCAS KOMPLEXA ADAPTIVA SYSTEM, MASTERPROGRAM, Årskurs 2 (valbar)
MPCSN DATORER, NÄTVERK OCH SYSTEM, MASTERPROGRAM, Årskurs 2 (valbar)
MPEES INBYGGDA ELEKTRONIKSYSTEM, MASTERPROGRAM, Årskurs 2 (valbar)

Examinator:

Peter Damaschke

  Gå till kurshemsida


Kurstillfälle 2


Undervisningsspråk: Engelska
Anmälningskod/tillfälleskod: 02128
Sökbar för utbytesstudenter: Ja
Blockschema: A+
Max antal deltagare: 100

Modul   Poängfördelning   Tentamensdatum
Lp1 Lp2 Lp3 Lp4 Sommarkurs Ej Lp
0114 Tentamen 7,5hp Betygskala: TH   7,5hp   17 Mar 2021 fm J,  26 Aug 2021 em J

I program

MPHPC HÖGPRESTERANDE DATORSYSTEM, MASTERPROGRAM, Årskurs 1 (valbar)
MPDSC DATA SCIENCE OCH AI, MASTERPROGRAM, Årskurs 1 (obligatoriskt valbar)
TKITE INFORMATIONSTEKNIK, CIVILINGENJÖR, Årskurs 3 (valbar)
TKDAT DATATEKNIK, CIVILINGENJÖR, Årskurs 3 (valbar)
MPENM MATEMATIK OCH BERÄKNINGSVETENSKAP, MASTERPROGRAM, Årskurs 2 (valbar)
MPENM MATEMATIK OCH BERÄKNINGSVETENSKAP, MASTERPROGRAM, Årskurs 1 (obligatoriskt valbar)
MPSYS SYSTEMTEKNIK, REGLERTEKNIK OCH MEKATRONIK, MASTERPROGRAM, Årskurs 1 (valbar)
MPCSN DATORER, NÄTVERK OCH SYSTEM, MASTERPROGRAM, Årskurs 1 (valbar)
MPSOF SOFTWARE ENGINEERING AND TECHNOLOGY - UTVECKLING OCH IMPLEMENTERING AV MJUKVARA, MASTERPROGRAM, Årskurs 2 (valbar)
MPSOF SOFTWARE ENGINEERING AND TECHNOLOGY - UTVECKLING OCH IMPLEMENTERING AV MJUKVARA, MASTERPROGRAM, Årskurs 1 (obligatoriskt valbar)

Examinator:

Birgit Grohe


  Gå till kurshemsida


Behörighet

Grundläggande behörighet för avancerad nivå
Sökande med en programregistrering på ett program där kursen ingår i programplanen undantas från ovan krav.

Särskild behörighet

Engelska 6
Sökande med en programregistrering på ett program där kursen ingår i programplanen undantas från ovan krav.

Kursspecifika förkunskaper

För att kunna följa kursen krävs kunskaper om datastrukturer och diskret matematik, motsvarande inledande kurser i ämnena.

Syfte

Kursen kretsar kring tre naturliga frågeställningar man ställs inför då man vill använda en dator för att beräkna lösningen på ett problem:
  • Är problemet beräkningsmässigt lösningsbart?
  • Hur kan lösningen utformas?
  • Hur snabbt kan problemet lösas?
 I kursen behandlas grundläggande metoder för att kunna besvara dessa typer av frågor så exakt som möjligt, och dessutom förbättra förmågan att skriva snabba och väl underbyggda program.

Det viktigaste målet med kursen är att ge allmänna principer för att skapa bra algoritmer för nya problem där det inte finns en känd lösningsmetod.

Andra viktiga aspekter är: att förbättra studenternas intuition för tidskomplexitet hos beräkningsproblem och algoritmer, att visa hur valet av datastrukturer kan påverka prestandan (exekveringshastigheten) för ett program, samt vikten av att anpassa datastrukturer efter algoritmen man vill använda.

Lärandemål (efter fullgjord kurs ska studenten kunna)

  1. Kunskap och förståelse
    • beskriva dina 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.

  2. Färdighet och förmåga
    • design: tillämpa de viktigaste designteknikerna för effektiva algoritmer (t.ex. giriga, dynamisk programmering, söndra och härska, backtracking, heuristiska) 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, fylla i implementationsdetaljer, hitta möjliga förbättringar, etc.
    • utföra enkla reduktioner mellan problem, förklara NP fullständighet, känna igen olika beräkningssvåra problem som tenderar att dyka upp om och om igen i olika applikationer, klara, åtminstonei princip, beräkningsmässigt svåra problem med hjälp av heuristik förfiningar av uttömmande sökning, approximativa lösningar, etc.

  3. Värderingsförmåga och förhållningssätt
    • kritiskt bedöma algoritmiska idéer och visa förmåga att motstå frestelsen att skapa uppenbara och till synes 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.
Var dock medveten om att detta inte är en kurs i programmering! Fokus ligger på design av algoritmer från en given problemformulering och analys av effektiviteten i dessa algoritmer. Det är, så att säga, det analytiska arbete som måste göras innan du skriver någon kod, om man vill lösa ett nytt problem med hjälp av datorer.

Innehåll

Kursen ger kunskaper om:
  • Introduktion. Vad är en effektiv algoritm?
  • Verktyg för analys av algoritmer. O-notation. Analysera loopar och rekursiva anrop. Lösa rekursionekvationer.
  • Datastrukturer och algoritmer. Granskning av grundläggande datastrukturer.
  • Kombinera datastrukturer. Merge-and-find.
  • Grafalgoritmer.
  • Giriga algoritmer.
  • Divide-and-conquer.
  • Dynamisk programmering.
  • Kort introduktion till lokala sök-och approximationsalgoritmer.
  • Grundläggande komplexitetsteori. Komplexitetsklasserna P, NP och NPC, reduktioner. Exempel på NP-fullständiga problem. Att hantera svåra problem.

Organisation

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

Litteratur

Information om litteratur ges på kursens hemsida före kursstart.

Examination inklusive obligatoriska moment

Kursen examineras genom individuell skriftlig salstentamen.


Sidansvarig Publicerad: må 13 jul 2020.