DD1320 Tillämpad Datalogi

Föreläsning 1: Introduktion till kursen

Kursen och formalia

Kursen examineras med labbar och tentamen (betyget ges av tentan). Förra året var det 82% som var klara med kursen efter höstterminen. Läs kurs-PM och 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).

Problem med tentadatum? Samlas vid vasken i rasten och kom överens om ett alternativt datum.

Utdelning av konton (bara till den som inte redan har) under rasten.

Schemakrockar med övningar/labbar? Det diskuterar vi tio 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 kursplan med läsanvisningar

Läsanvisningarna är till kursboken "Problem Solving with Algorithms and Data Structures using Python" av Bradely N. Miller and David L. Ranum.

Föreläsning 1 - Introduktion till kursen: kap 1 (utom 1.4.4.2)
Föreläsning 2 - Abstrakta datatyper: kap 2 och 7.2
Föreläsning 3 - Komplexitetsanalys, sökning, rekursion: kap 3 (men vänta med 3.2.3 och 3.4.3) och 4.1-4.3.2
Föreläsning 4 - Binära träd, binära tal: kap 5.1-5.6 (men vänta med 5.5.1) och 3.2.3
Föreläsning 5 - Problemträd: kap 6.1-6.4.2
Föreläsning 6 - Hashning: kap 4.3.3
Föreläsning 7 - Sortering: kap 4.4
Föreläsning 8 - Prioritetskö, trappa (heap): kap 5.7, 6.4.5
Föreläsning 9 - Automater, textsökning: kap 7.6
Föreläsning 10 - Syntax, rekursiv medåkning: kap 5.5.1
Föreläsning 11 - Datakomprimering: kap 7.5
Föreläsning 12 - Dokumentering, testning, kryptering: kap 3.4.3
Föreläsning 13 - Repetition inför tentan
Föreläsning 14 - Tentagenomgång

På föreläsningarna går vi igenom algoritmer och datastrukturer.
På övningarna övar vi problemlösning (som på tentan).
På labbarna implementerar ni datastrukturer och algoritmer.
Hemtalen ligger ibland lite före, för att uppmuntra till att läsa i förväg!

Abstraktion

En mp3-spelare har
Data: ett antal musikfiler

Operationer:
play, browse, shuffle, delete

Jag har ingen aning om hur den fungerar men kan använda den ändå.

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.

Algoritmer

Räkna alla i salen!

Förslag 1: Linda räknar
Förslag 2: Varje rad räknar sig själv, dom i mitten summerar.

Vilket går snabbast?

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