Algoritmiska metoder för sökning och lagring

Sammanfattning

Kursen syftar till fördjupad kunskap om algoritmisk metodik med speciell tillämpning på metoder för effektiv sökning i och lagring av sekventiella datasträngar, såsom exempelvis text i naturliga eller formella språk, eller genetiska och andra biologiska data. Studenten lär sig utnyttja, anpassa och implementera praktiska effektiva metoder för representation, strukturering, sökning, och komprimering av stora mängder data.

Behörighetskrav

7,5 hp inom algoritmer och datastrukturer, alternativt Matematik 3c/Matematik D och 3 hp inom algoritmer och datastrukturer. 7.5 hp i programmering

Urval:

högskolepoäng 20% betyg 60% högskoleprov 20%

Kursplan

Kursplan för studenter höst 2019

Kurskod:
DA295A version 1
Engelsk benämning:
Algorithmic methods for search and storage
Fördjupningsnivå
G1F
Huvudområden:
Datavetenskap
Undervisningsspråk:
Engelska
Fastställandedatum:
15 februari 2019
Beslutande instans:
Fakulteten för teknik och samhälle
Gäller från:
02 september 2019

Förkunskapskrav

7,5 hp inom algoritmer och datastrukturer, alternativt Matematik 3c/Matematik D och 3 hp inom algoritmer och datastrukturer. 7.5 hp i programmering

Fördjupning i förhållande till examensfordringarna

Kursen är en fristående kurs.

Syfte

Kursen syftar till fördjupad kunskap om algoritmisk metodik med speciell tillämpning på metoder för effektiv sökning i och lagring av sekventiella datasträngar, såsom exempelvis text i naturliga eller formella språk, eller genetiska och andra biologiska data. Studenten lär sig utnyttja, anpassa och implementera praktiska effektiva metoder för representation, strukturering, sökning, och komprimering av stora mängder data.

Innehåll

• Representation av sekventiella data, såsom text eller DNA-sekvenser
• Metoder för strängsökning, samt mönstermatchning med exempelvis reguljära uttryck
• Radixsorteringsmetoder
• Datastrukturer för effektiva stränguppslag såsom inverterat index, trie, suffixträd och suffixvektor
• Metoder för förlustfri datakomprimering såsom Huffmankod, Ziv–Lempel-komprimering och Burrows–Wheeler-transformering.

Lärandemål

Kunskap och förståelse
För godkänd kurs ska studenten kunna:
• Redogöra för viktiga algoritmer och datastrukturer för sekventiella data, deras användning och effektivitetsmässiga egenskaper
• Redogöra för funktionen hos viktiga metoder för förlustfri datakomprimering
• Motivera och förklara algoritmiska metoders effektivitet för att bearbeta, söka i och komprimera sekventiella data

Färdighet och förmåga
För godkänd kurs ska studenten kunna:
• Välja, och vid behov anpassa, algoritmiska metoder för att bearbeta, söka i och komprimera sekventiella data
• Praktiskt implementera algoritmer och datastrukturer för effektiv lagring av och sökning i stora mängder data

Värderingsförmåga och förhållningssätt
För godkänd kurs ska studenten kunna:
• Utifrån en given problemställning inom behandling av sekventiella data, analysera problemet samt kritiskt välja lämpligt algoritmiskt angreppssätt för att lösa det.
• Resonera kring och kritiskt värdera utformning och implementationsval ur olika aspekter, såsom prestanda och lagringsutrymme

Arbetsformer

Föreläsningar, lärarledd tid för övningar med och utan datorarbete, samt självstudier i grupp och enskilt.

Bedömningsformer

Kursen examineras genom en skriftlig tentamen (4 hp), och obligatoriska inlämningsuppgifter (3,5 hp).

För godkänt betyg (A–E) krävs godkänt på samtliga inlämningsuppgifter, samt godkänt betyg (A–E) på skriftlig tentamen. Vid godkänt sätts kursbetyget till betyget på skriftlig tentamen.

Betygsskala

Utmärkt (A), Mycket Bra (B), Bra (C), Tillfredsställande (D), Godkänd (E) eller Underkänd (U).

Kurslitteratur och övriga läromedel

Rekommenderad litteratur:
  • Sedgewick R, Wayne K: Algorithms, 4th ed., Addison Wesley 2011.
  • Witten, I H, Moffat, A, Bell T C: Managing gigabytes: compressing and indexing documents and images, 2nd ed., Morgan Kaufman 1999.
Utöver ovanstående litteratur tillkommer en samling vetenskapliga artiklar.

Kursvärdering

Högskolan ger studenter som deltar i eller har avslutat en kurs en möjlighet att framföra sina erfarenheter av och synpunkter på kursen genom en kursvärdering som anordnas av högskolan. Högskolan sammanställer kursvärderingarna samt informerar om resultaten och eventuella beslut om åtgärder som föranleds av kursvärderingarna. Resultaten ska hållas tillgängliga för studenterna. (HF 1:14).

Övergångsbestämmelser

Om en kurs inte längre ges eller har genomgått större förändringar ska studenterna, under ett år efter det att förändringen skett, erbjudas två tillfällen för omprov baserade på den kursplan som gällde vid registreringen.

Övrigt

Överlappar till ca 50% med kursen DA357A.

Kontakt

Utbildningen ges av Fakulteten för teknik och samhälle på institutionen Datavetenskap och medieteknik.

Mer information om utbildningen

Jesper Larsson, kursansvarig
Telefon: 040-6657303

Anmälan

02 september 2019 - 10 november 2019 Dagtid 50% Malmö Anmälningskod: mau-98168

Sista anmälningsdag 15 april

Ansök