Göm menyn

TDDC30 Programmering i Java, datastrukturer och algoritmer

Vt1, 2016

Välkommen till TDDC30. Använd menyn till vänster för att navigera.

Senaste nytt...


2016‑02‑10  Matematik
 

Hejsan.

Vi har fått lite kommentarer från er som går 725G82-kursen vad det gäller matematiken i kursen. De senaste föreläsningarna har varit lite mattetunga så vi tänkte klargöra lite hur vi ser på detta. OBS! Vi ser inte detta som en mattekurs och vi vet att I:arna har läst mer matte än vad ni gjort så fråga om det är något som känns oklart. Det är det assistenterna och vi är till för.

Det som vi ser som nödvändigt för att klara av kursen är en grundläggande förståelse för ekvationer och begreppet funktioner. Detta innebär inte att ni skall behöva räkna med dessa uttryck utan mer att förstå hur dessa delar "ser ut" om man ritar upp dem i ett diagram och att kunna jämföra vilken av dem som är "störst"/"värst" när man följer x-axeln åt höger (x-axeln beskriver antal data, N, och y-axeln beskriver hur lång tid det tar att lösa ett problem). De används framförallt för att beskriva hur lång tid olika algoritmer (sorteringar etc.) tar beroende på hur många data man har att utföra algoritmen på. Man se på detta vis vilka algoritmer som är bättre än andra (de som tar mindre tid).

En kort sammanfattning av de vanliga funktionerna är (givet att N är antal data):

1) Konstant tid ger inget beroende av N. f(N) = konstant

2) Logaritmisk tid: f(N) = log(N) * konstant

3) Linjär tid: f(N) = N * konstant

4) Exponentiell tid: f(N) = N^2 eller N³ eller liknande

5) Riktigt besvärliga saker kan vara: f(N) = konstant^N eller f(N) = N!

Det som är viktigt för er att veta är att de som kommer senare i listan ovan är sämre (långsammare) än de som kommer tidigare. Om man kombinerar saker så blir det förstås lite klurigare, men vi kommer inte att ha superkluriga saker. det värsta vi kommer att ha med är att man multiplicerar två av ovanstående:

T.ex. "log(N) * log(N)" eller "N * log(N)" eller "N * N" (samma sak som N²)

Om man gör på detta vis ser man att log(N)*log(N) är bättre än N*log(N) som i sin tur är bättre än N*N.

Denna matematik täcks, om vi inte kommer ihåg fel, av matte A och matte B i gymnasiet. Just logaritmfunktioner är det inte säkert att man har stött på, men det viktiga här är INTE att man vet hur man räknar med log-uttryck (det kommer inga sådana uppgifter på tentan) utan att man förstår att log(n) är en funktion som beror av n och ungefär hur den beter sig då n ökar. Erik ritade upp en bild av detta på senaste föreläsningen, och motsvarande finns i kapitel 4 i kursboken. Om man ändå är mer intresserad av detta så finns det beskrivet ganska noga i kapitel 4.

Det är också viktigt att man förstår varför log-uttryck uppstår i vissa algorimers komplexitetuttryck. Detta visade Erik på föreläsning 5, när han jämförde två algoritmer, en som gissade tal en efter en, och en annan som halverade sökmängden efter varje gissning. Det var just denna halvering som gav log-uttrycket. Titta tillbaka på era anteckningar, eller läs i boken om ni är osäkra på den biten. Prata också med assistenterna om ni vill.

Eftersom matematik och programmering är nära besläktade så är det även troligt att olika matematiska koncept dyker upp under kursens gång, men då är det inget som inte borde täckas av grundskolans matematik. Om tvivel fortfarande råder då sådant uppstår, fråga oss gärna! Det finns inga dumma frågor!

M.v.h.

/TJ och EN


2015‑12‑18  Kurshemsidan uppdaterad
 

Dessa kurshemsidor har börjats uppdaterats. Mer info kommer fyllas på inför kursstarten.



Sidansvarig: Erik Nilsson
Senast uppdaterad: 2015-11-07