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!