Tillämpad datalogi, kursPM

Ändringar i kursPM kommer att meddelas under "Aktuellt" på kursens webbsida

http://www.csc.kth.se/utbildning/kth/kurser/2D1320/tilda06/

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 2D1385 Programutvecklingsteknik, 2D1352 Algoritmer, datastrukturer och komplexitet, 2D1378 Text- och bildbehandling, 2D1418 Språkteknologi, 2D1373 Artificiella språk och syntaxanalys, 2D1334 Databasteknik, 2D1377 Maskinnära programmering och datorarkitektur, 2D1392 Internets protokoll och principer, 2D1431 Maskininlärning, 2D1323 Datorgrafik med interaktion, 2D1640 Grafik- och interaktionsprogrammering

Lärare

	Namn	Datorpostadress
Kursledare/föreläsare	Magnus Rosell	rosell@csc.kth.se
Grupp 1	Magnus Rosell	rosell@csc.kth.se
Grupp 2	Jonas Sjöbergh	jsh@csc.kth.se
Grupp 3	Per-Anders Staav	pastaav@algonet.se

Har du frågor om innehållet i föreläsningarna, prata med föreläsaren. Har du övningsfrågor, prata först med din övningsassistent. För övriga frågor, kontakta kursledaren.

Enklaste sättet att komma i kontakt med kursledaren är att skicka datorbrev, näst enklast är att lägga en lapp i postfacket på Nada, Osquars Backe 2, 4 tr eller skicka ett vanligt brev till Nada, KTH, 100 44 Stockholm.

Många lärare tar hand om mer än en kurs. Var vänlig och börja alla datorbrev med rubriken tilda06:... när du kontaktar en lärare i kursen.

Vem får läsa kursen

Kursen får läsas av alla som har gått kursen 2D1310 Programmeringsteknik.

Kurslitteratur

• En kursbunt som köps på första föreläsningen eller på studentexpeditionen då de håller öppet.
  • Hederskodex
  • Kursprogram (det du läser nu!)
  • Föreläsningsanteckningar (delas ut på föreläsningarna)
  • Övningsanteckningar (delas ut på övningarna)
  • Labblydelser (delas ut på föreläsningarna)
  • Pythonkramaren. Skriv inte ut! Köp på studentexpeditionen.
  • Extentor
  • Officiellt tomt formelblad
• En bok om algoritmer och datastrukturer, för exempel se nedan.

Kursbok

En bok om datastrukturer och algoritmer. Rekommenderad kursbok är:

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 Läsanvisningar

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

Nadas studerandeexpedition finns på Osquars backe 2 plan 2. Den har öppet må­-fr 9.45­-11.30 och må­-to 12.45­-14.15. Kursbunten säljs på studentexpeditionen. Där kan du också hämta ut din tenta efter kursens slut.

Delfi är Nadas systemgrupps mottagning som har hand om konton och passerkort. 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 i mitten av oktober. I början av november ligger en sista föreläsning med tentagenomgång, samt 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 labbar godkända är det viktigt att du gör

res checkin tilda06

som det beskrivs i laboration 1. Alla måste göra detta. Under kursen kan du med kommandot
res show tilda06 kolla att dina labbar har blivit rapporterade.

Examination

På KTH CSC tillämpar vi en hederskodex. Läs den!

Kursen har två obligatoriska moment:

• Laborationer - lab1, 2 kurspoäng
• Skriftlig tenta - ten1, 2 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 16/11! Alla labbarna måste vara godkända för att labbdelen ska bli godkänd. Har man inte redovisat alla labbar 16/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 för bonuspoäng	-	29/9 eller 2/10	29/9 eller 2/10	29/9 eller 2/10	11/10 eller 12/10	11/10 eller 12/10	-
Ger antal bonuspoäng	0	1	1	1	1	1	0

Labb 1 är en introduktion. Alla kursdeltagare måste registrera sig på kursen som det beskrivs i den. Däremot behöver behöver man inte redovisas 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	6/9	13/9	20/9	27/9	4/10	11/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 ett bonuspoäng om man har gjort ett ärligt försök. Det behöver inte ha blivit rätt.

Tentamen

Tentan går 23/10 8-13 i Q24 - Q25, Q31 - Q34. Ingen tentaanmälan krävs. Alla är välkomna till tentan. Förbered dig mha extentorna från webben.

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

• En valfri algoritmbok.
• Ett eget med bläckpenna handskrivet formelblad av A4-storlek. Här är 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 2006-2007:

50-69 poäng ger betyg 3

70-89 poäng ger betyg 4

90+ poäng ger betyg 5

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 fick 47-49 poäng har möjlighet att komplettera med en individuell uppgift som delas ut vid tentaåterlämningen i K1 kl 8-10 den 31 oktober. Kompletteringen ska lämnas in senast 7 november.

Tentaresultatet anslås på institutionens anslagstavla (Osquars Backe 2, plan 3). Om du inte hämtade 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 kontakta sedan kursledaren.

Konto vid Nada

Nadas datorsalar har UNIX-datorer och sköts av Nadas systemgrupp. Om du inte redan har konto på Nadas 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 vid två tillfällen plan 5 (Grå, Karmosin, Magenta). 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å Nada. Det kan till exempel behövas extra rättigheter för att komma in på plan 5 även om man kan komma in på plan 4.

Läsanvisningar

I den här kursen är det viktigt att lära sig i vilket sammanhang de olika algoritmerna och datastrukturerna är användbara. Exempel på ett tentatal 22 augusti 2002:

Kursen har tagit upp de fyra sökmetoderna linjärsökning, binärsökning i vektor, binärt sökträd och hashning. Alla metoder är inte alltid lämpliga. Ta för varje metod upp något unikt exempel där just den metoden diskvalificerar sig och beskriv utförligt varför.

Här är tanken att man ska kunna tala om i vilket sammanhang en viss metod är olämplig. Ett svar som bara beskriver hur metoderna fungerar skulle inte ge poäng.

Läsanvisningar för kursboken: "Problem Solving with Algorithms and Data Structures Using Python"

Förändringar sedan förra läsåret

Kursen ges nu i Python!