DD1320 Tillämpad Datalogi

Föreläsning 1: Introduktion till kursen

Kursen och formalia

Kursen examineras med labbar (7 st) och tentamen (betyget ges av tentan). Förra året var det tre fjärdedelar som var klara med kursen efter höstterminen. Titta ofta på kursens webbsida för dagsaktuell information!

Kursansvariga studenter sökes!
Gärna en per program/inriktning. Anmäl dig bums till Linda.

Placeringskort (för att undvika kaos i datorsalen).

Webbsidan - kursmaterial

KTH Social - frågeforum

Diagnostiskt prov i Python

Endast CMEDT: Utdelning av konton fem i tolv.

Datalogikurser världen över är mycket lika varandra. Innehållet är i huvudsak det här.

Abstraktion
Datastrukturer
Algoritmer

Läranvisningar

För varje datastruktur och algoritm gäller det att kunna:

Förstå
- Abstrakt: hur använder man den?
- Implementation: hur funkar den i detalj?
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)

Preliminär plan över föreläsningarna

Föreläsning 1 - Introduktion till kursen
Extraföreläsning i Python för CMEDT2 och CMEDT3
Föreläsning 2 - Abstrakta datatyper
Föreläsning 3 - Komplexitetsanalys, sökning
Föreläsning 4 - Rekursion, binära träd
Föreläsning 5 - Mer om binära träd, binära tal
Föreläsning 6 - Problemträd
Föreläsning 7 - Hashning, bloomfilter
Föreläsning 8 - Sortering, prioritetskö, trappa (heap)
Föreläsning 9 - Automater, textsökning
Föreläsning 10 - Syntax, rekursiv medåkning
Föreläsning 11 - Datakomprimering
Föreläsning 12 - Dokumentering, testning, kryptering
Föreläsning 13 - Repetition inför tentan
Föreläsning 14 - Testning

På föreläsningarna går vi igenom algoritmer och datastrukturer.
På övningarna övar vi problemlösning (som på tentan) och ni redovisar hemtalen..
På labbarna implementerar ni datastrukturer och algoritmer.

Algoritmer

Räkna alla i salen!

Förslag 1: Linda räknar alla
Förslag 2: Varje rad räknar sig själv, den längst ut till höger på raden skriver ner antalet. Den längst upp till höger skickar ner sin summa till raden under osv.

Vilket går snabbast?

I kursen ska vi titta på algoritmer och deras komplexitet för många olika typer av problem.

Datastrukturer

En datastruktur är till för att lagra data (som en variabel), men med plats för flera värden. Exempel som du sett:

I Python: lista, objekt
I Matlab: matris, struct

I den här kursen ska vi titta på datastrukturena:

Objekt
Länkade listor bestående av noder (objekt) med referens till nästa nod
Stack
Kö
Allmänna träd
Binära träd
Hashtabeller
Booleska hashtabeller och bloomfilter
Trappa/heap
Prioritetskön

Abstraktion

Anta att vi vill skriva ett kalenderprogram.
Data: Olika typer av händelser kopplade till datum och tid.

Exempel på operationer:
find_instances(start_date, end_date) add_appointment() delete_item()

Man behöver inte veta exakt hur data lagras för att använda operationerna.

Likadant i Python - vi vet inte hur strängar, listor och uppslagslistor är definierade, ändå kan vi använda dom. Det här är ett exempel på abstraktion. Om implementationen av listans metoder ändras (i en ny Python-version) behöver vi inte bekymra oss, alla våra program som använder listor fungerar ändå. Vi använder listan som en abstrakt datastruktur.