bild
Skolan för
elektroteknik
och datavetenskap

Tillämpad datalogi, kursPM

Ändringar i kursPM kommer att meddelas under "Aktuellt" på kursens webbsida: http://www.csc.kth.se/DD1320/

Kursens mål

I den här kursen bygger du på dina kunskaper om algoritmer, datastrukturer och programmering. Programspråk i kursen är Python. Efter genomförd kurs ska du kunna följande:
  • systematiskt testa program för att upptäcka fel,
  • använda abstraktion som ett verktyg för att förenkla programmeringen,
  • välja lämplig algoritm till ett givet problem,
  • jämföra algoritmer med avseende på tids- och minnesåtgång,
  • beskriva olika algoritmer för sökning och sortering och deras egenskaper,
  • formulera och implementera rekursiva algoritmer,
  • skriva en liten BNF-syntax för ett formellt språk och skriva ett program som undersöker om ett uttryck följer en BNF-syntax,
  • modellera verkliga problem som sökproblem och implementera algoritmer för breddenförstsökning, djupetförstsökning och bästaförstsökning,
  • beskriva grundläggande komprimeringsalgoritmer och i vilka typer av komprimering dom används,
  • konstruera en automat för textsökning och beskriva hur den fungerar,
  • implementera och använda stackar och köer,
  • implementera insättnings-, genomgångs- och sökoperationer i binära sökträd och allmänna träd samt använda dessa,
  • implementera och använda hashtabeller och hashfunktioner,
  • använda prioritetsköer,
  • identifiera problem där datastrukturerna ovan är användbara och konstruera enkla algoritmer med dessa,
för att du ska:
  • bli bra på att lösa problem med programmering,
  • kunna använda datalogiska metoder i tillämpningsprojekt och
  • få tillräckliga förkunskaper för att kunna läsa fortsättningskurser i datalogi.

Fortsättningskurser är bland annat DD2385 Programutvecklingsteknik, DD1352 Algoritmer, datastrukturer och komplexitet, DH2418 Språkteknologi, DD1334 Databasteknik, DD2377 Maskinnära programmering och datorarkitektur, DD2392 Internets protokoll och principer, DD2431 Maskininlärning, DH2323 Datorgrafik med interaktion, DH2640 Grafik- och interaktionsprogrammering

Lärare

Namn Datorpostadress
Kursledare/föreläsare Linda Kann lk@csc.kth.se
Grupp a (vanliga övningar) Mika Cohen mikac@csc.kth.se
Grupp b1 (övningsgrupp med lugnare tempo) Linda Kann lk@csc.kth.se
Grupp b2 (övningsgrupp med snabbare tempo) Öjvind Johansson ojvind@csc.kth.se

Linda sitter i rum 1428 på Osquars backe 2, plan 4 (rummet intill bysten av Germund Dahlquist) och har telefon 08-790 6292, men nås enklast via datorpost.

Börja gärna datorbrev med rubriken tilda07:... när du kontaktar en lärare i kursen (vi undervisar i regel på flera olika kurser).

Vem får läsa kursen

Kursen får läsas av alla som har gått någon av kurserna i Programmeringsteknik (2D1310, 2D1311, 2D1312).

Kurslitteratur

Kursbok

Kursbok är:
Problem Solving with Algorithms and Data Structures Using Python Bradley N. Miller & David L. Ranum, Problem Solving with Algorithms and Data Structures Using Python, Franklin Beedle & Associates, Luther College, ISBN 1-59028-053-9 Boken kostar 470:- i kårbokhandeln.

Läsanvisningar och erratalista finns på webben.
Nästan vilken bok som helst om datastrukturer och algoritmer går bra, men jämför bokens innehållsförteckning med kursplanen innan du köper den! De flesta andra böcker använder något annat språk än Python.

Studentexpedition och Delfi

CSCs studerandeexpedition finns på Osquars backe 2 plan 2. Den har lunchstängt 12-13, och öppet vardagar 9.30­-12 (utom onsd) och 13-15 (utom torsd-fred). Efter första föreläsningen säljs kursbunten på studentexpeditionen. Där kan du också hämta ut din tenta om du inte gjort det på tentaåterlämningsföreläsningen.

Delfi är CSCs systemgrupps mottagning som har hand om konton och passerkortsrättigheter. Delfi har öppet må-fr 10-12 och må-to 13-15.

Kursuppläggning och schema

Kursen pågår huvudsakligen i september-oktober, med två föreläsningar, en övning och ett labbtillfälle varje vecka. Tentan går den 24 oktober. En vecka senare ligger en sista föreläsning med tentagenomgång, och efter det några labbtillfällen då man kan redovisa den sista labben (och ev restlabbar).

Blir det ändringar under kursens gång, kommer schemat på kursens webbsida att uppdateras.

Registrering hos KTH CSC

För att du ska kunna få dina kursmoment registrerade i LADOK är det viktigt att du checkar in på kursen som det beskrivs i laboration 1. Kontrollera också via "Mina sidor" att ditt utbildningskansli har lagt in kursval på DD1320.

Examination

På KTH CSC tillämpar vi en hederskodex. Läs den på webben eller i labbhäftet.

Kursen har två obligatoriska moment:

  • Laborationer - lab1, 3 kurspoäng
  • Skriftlig tenta - ten1, 3 kurspoäng

Man måste bli godkänd på båda för att bli godkänd på kursen. Poängsumman på tentan avgör slutbetyget på kursen.

Utöver labbar och tenta finns ett frivilligt moment: Hemtal.

Från både labbar och hemtal kan man få bonuspoäng som man tillgodoräknar sig på tentan.

Laborationer

Man måste redovisa laborationerna senast 14/11! Alla labbarna måste vara godkända för att labbdelen ska bli godkänd. Har man inte redovisat alla labbar 14/11 får man vänta till kursomgången nästa år.

Man redovisar laborationerna i datorsal (boka tid på kursens webbsida).

Laboration 1 2 3 4 5 6 7
Redovisas senast 7/10 eller 10/10 28/9 eller 1/10 28/9 eller 1/10 28/9 eller 1/10 17/10 17/10 14/11
Ger antal bonuspoäng 0 1 1 1 1 1 0

Labb 1 är en introduktion. Alla kursdeltagare måste registrera sig på kursen såsom det beskrivs i den. Man behöver inte redovisa den, men vill man få feedback på den så går det bra.

Av både pedagogiska- och utrymmesskäl vill vi gärna att ni gör labbarna i grupper om två. Den som absolut vill labba ensam måste rådgöra med kursledaren först.

Hemtal

Hemtalen är frivilliga. De lämnas in snyggt handskrivet på övningarna enligt nedan. Man rättar någon annans hemtal och lämnar vidare till övningsassisten som kontrollerar i efterhand. OBS. Skriv namn och personnummer på din lösning!

Hemtal 1 2 3 4 5 6
Lämnas in snyggt handskrivet på övning Ö2 Ö3 Ö4 Ö5 Ö6 Ö7
Dvs datum 12/9 19/9 eller 20/9 26/9 4/10 eller 5/10 10/10 15/10 eller 16/10
Ger antal bonuspoäng 1 1 1 1 1 1

Men man kan maximalt få 5 bonuspoäng för hemtalen! Man har gjort sig förtjänt av en bonuspoäng om man har gjort ett ärligt försök. Det behöver inte ha blivit rätt.



Tentamen

Tentan går 24/10 kl 9-13 i L21 - 22, L41 - 44, L51 - 52. Ingen tentaanmälan krävs. Alla är välkomna till tentan. Förbered dig med hjälp av extentorna från webben.

Tillåtna hjälpmedel på tentan är:

  • En valfri algoritmbok.
  • Ett eget med bläckpenna handskrivet formelblad av A4-storlek. På webbsidan finns det officiella tomma formelbladet. Skriv ditt namn och personnummer på formelbladet och lämna in det med tentan.

Tentan kommer att ha 100 poäng. Betygsgränserna är följande under läsåret 2007-2008:
50-59 poäng ger betyg E
60-69 poäng ger betyg D
70-79 poäng ger betyg C
80-89 poäng ger betyg B
90+ poäng ger betyg A
Man kan få maximalt 10 bonuspoäng från hemtal och labbar. Dessa får man tillgodoräkna sig på tentan. Bonuspoäng från labbar och hemtal försvinner ett år efter kursstart.

Den som bara fått 47-49 poäng har möjlighet att komplettera med en individuell uppgift som delas ut vid tentaåterlämningen i D1 kl 8-10 den 31 oktober. Kompletteringen ska lämnas in senast 7 november.

Om du inte hämtar ut tentan på återlämningsföreläsningen kan du få tillbaka den från studentexpeditionen (Osquars Backe 2, plan 2).

Klagomål på rättning av tentan lämnas till kursledaren inom tre veckor från det att tentaresultatet anslagits. Observera att du inte bör ta med dig tentan från expeditionen eller tentaåterlämningen om du vill klaga på rättningen. Kolla tentan på expeditionen, skriv ned dina kommentarer och lämna till kursledaren.

Konto vid CSC

CSCs datorsalar har UNIX-datorer och sköts av CSCs systemgrupp. Om du inte redan har konto på CSCs datorer måste du gå till Delfi, Osquars Backe 2, plan 2 och be att få ett.

De datorsalar som används i kursen är belägna på Osquars backe 2 plan 4 (Röd, Orange, Gul, Grön och Brun). Du har tillträde till datorsalarna dygnet runt, men du måste lämna företräde om salen är bokad för en annan kurs.

Som inpasseringskort använder du din kårlegitimation. På kvällar och helger krävs även kort och kod för ingången till E-huset. Vänd dig till Delfi om du får problem med ditt passerkort eller konto på CSC.

Läranvisningar

Följande kan vara bra att ha med sig då man tar till sig innehållet i tildan. För varje datastruktur och algoritm gäller det att åtminstone kunna:

  • Förstå
    • Abstrakt: hur använder man den?
    • Konkret: hur funkar det i detalj?
      kunna beskriva i ord (och implementera)
  • Analysera
    • Hur snabb/effektiv är den? Komplexitet mm.
    • Vad har den för fördelar/nackdelar? Begränsningar?
    • När är den lämplig/olämplig?
      (jämfört med andra algoritmer/datastrukturer)










Copyright © Sidansvarig: Linda Kann <lk@csc.kth.se>
Uppdaterad 2007-10-18