Algoritmer och komplexitet
Vad kostar en algoritm, räknat i tid och minne? Lär dig att jämföra alternativa algoritmer, konstruera datorprogram som effektivt utnyttjar tid och minne och att identifiera och angripa problem som är orealistiskt resurskrävande eller inte alls går att lösa med dator.
I denna kurs lär du dig utveckla, implementera och analysera algoritmer avseende korrekthet och effektivitet; definiera begreppen P, NP, NP-fullständighet, oavgörbarhet, m m, för att kunna identifiera/angripa orealistiskt resurskrävande/olösliga problem samt konstruera program som effektivt utnyttjar tid/minne.
Innehåll
Konstruktionsprinciper för algoritmer: Dekomposition, giriga algoritmer, dynamisk programmering, lokal och total sökning. Algoritmanalys. Approximation, algoritmer och heuristiker. Tillämpningar med algoritmer för problem på mängder, grafer, aritmetik och geometri. Implementation av algoritmer.
Datastrukturer: Repetition av hashtabeller och heapar; balanserade träd; randomiserade datastrukturer. Användning och implementation av datastrukturer.
Beräkningsbarhet och komplexitet: Reduktionsbegreppet, komplexitetsklasserna P (polynomisk tid) och NP (ickedeterministisk polynomisk tid). NP-fullständiga problem, oavgörbara problem. Hur man kan hantera problem med hög komplexitet.
För dig som är antagen HT2023
Grattis! Du har blivit antagen till den utbildning du sökt på Stockholms universitet och vi hoppas att du kommer att trivas med dina studier hos oss.
På den här sidan listar vi vad du behöver göra och känna till innan du börjar dina studier.
Följ de instruktioner du fått för att acceptera din plats.
Mer information på antagning.se
Checklista för antagna studenter
-
Aktivera ditt SU-konto
Första steget för att kunna registrera dig och få tillgång till universitetets alla IT-tjänster.
-
Registrera dig på din institution
Registrering kan ske på olika sätt. Läs noga informationen från din institution nedan.
-
Ta del av institutionens information
På den här sidan hittar du det du behöver veta inför starten på din kurs eller ditt program.
Notera
Din plats kan tas tillbaka om du inte registrerar dig och deltar vid eventuellt upprop enligt anvisningarna från institutionen.
Information från institutionen - kurser
Här hittar du viktig information om registreringstider, lärplattform, och information för dig som är antagen med villkor eller reservantagen.
Först: Svara på ditt antagningsbesked!
Om du erbjuds en plats eller reservplats på en kurs i första antagningsbeskedet måste du svara på antagningbeskedet via Antagning.se senast 21 juli för att behålla platsen!
Mer info hos Antagning.se om att svara på antagningsbesked
Om du glömmer att svara på antagningsbeskedet måste du söka kursen igen om du vill läsa den, vilket kräver att den är öppen för sen anmälan.
Registrering i Ladok
Du som är antagen till en kurs måste webbregistrera dig via student.ladok.se för att behålla din plats på kursen. Webbregistrering för kurser HT23 öppnar 7 augusti, och stänger olika tider för olika kurser.
- Matematik I, alla varianter inklusive ULV- och VAL-versioner samt fortsättningsregistrering för de som började kursen på halvfart våren 2023: sista dag för registrering är måndag 21 augusti.
- Kurser som ges på KTH, alltså kurserna med kurskod BE3009, BE7001, BE7009, BE7013, DA7011, DA7048, MM7044, MM7045, MM7046: sista dag för registrering är måndag 4 september. Registrera dig gärna tidigare för att få KTH-konto i tid.
För distanskurserna Förberedande kurs i matematik och Utmanande matematik är webbregistrering öppen nästan hela höstterminen, eftersom studietakten på dessa kurser är flexibel.
För övriga kurser är webbregistrering öppen till och med 17 september om kursen börjar i augusti (period 1 eller AB), eller 19 november om den börjar i månadsskiftet oktober-november (period 2 eller CD).
Du kan inte webbregistrera dig på självständiga arbeten i matematik (du registreras när din arbetsplan har godkänts).
Lärplattform
Våra kurssidor finns på kurser.math.su.se, med undantag för kurserna Förberedande kurs i matematik (math.su.se/förberedande) och Utmanande matematik (math.su.se/utmanande).
På många kurssidor kan du aktivera dig själv, men att du gör det innebär inte att du är registrerad på kursen! Du måste alltid webbregistrera dig på kursen via Ladok, se ovan om registrering.
Villkor för antagning
Villkorshanteringen brukar ske strax före kursstart. Du behöver i allmänhet inte visa upp några intyg på att villkoren är uppfyllda, denna information har vi tillgång till.
Så länge villkoret finns kvar kan du inte webbregistrera dig, därför bör du kontakta studievägledningen om villkoret fortfarande finns kvar vid kursstart, och du inte har fått något besked om huruvida du får läsa kursen. Om kursen har kort registreringsperiod, kontakta oss innan webbregistrering stänger (du bör i så fall ha fått instruktioner i ditt välkomstbrev).
Reservantagning
Eventuell reservantagning sker kring terminsstart, och vi kontaktar dig då på den e-postadress du angivit på Antagning.se om vi kan erbjuda dig en plats. Om du är reservantagen med villkor och blir erbjuden en plats på kursen, så måste du också uppfylla villkoret för att kunna ta din plats i anspråk.
Mer information
Ny student: om antagning, registrering, kurslitteratur och kurssidor
Välkomstaktiviteter
Vid terminsstart ordnar vi ett antal aktiviteter – både online och på campus – för att välkomna och introducera dig som är ny student. En av dessa är Välkomstdagen på Campus Frescati som är ett utmärkt tillfälle att bekanta sig med universitetet och andra nya studenter. Programmet riktar sig till alla nya studenter, oavsett ämne, kurs eller program. För dig som är ny student vid Institutionen för data- och systemvetenskap, DSV, arrangeras en motsvarande välkomstdag på Campus Kista.
Information som rör din utbildning får du via din kurs-/programgivande institution.
Hitta hit
Stockholms universitet sträcker sig över en stor yta. Läs om vilka campus som finns och var du hittar din institution, alla undervisningslokaler, lunchställen, bibliotek, läsplatser, mm.
Läs mer
I denna kurs lär du dig utveckla, implementera och analysera algoritmer avseende korrekthet och effektivitet; definiera begreppen P, NP, NP-fullständighet, oavgörbarhet, m m, för att kunna identifiera/angripa orealistiskt resurskrävande/olösliga problem samt konstruera program som effektivt utnyttjar tid/minne.
Innehåll
Konstruktionsprinciper för algoritmer: Dekomposition, giriga algoritmer, dynamisk programmering, lokal och total sökning. Algoritmanalys. Approximation, algoritmer och heuristiker. Tillämpningar med algoritmer för problem på mängder, grafer, aritmetik och geometri. Implementation av algoritmer.
Datastrukturer: Repetition av hashtabeller och heapar; balanserade träd; randomiserade datastrukturer. Användning och implementation av datastrukturer.
Beräkningsbarhet och komplexitet: Reduktionsbegreppet, komplexitetsklasserna P (polynomisk tid) och NP (ickedeterministisk polynomisk tid). NP-fullständiga problem, oavgörbara problem. Hur man kan hantera problem med hög komplexitet.
-
Kursupplägg
Kursen består av tre moment; teori, individuella uppgift samt laborationer.
Undervisning
Undervisningen består av föreläsningar, övningar, och laborationer.
Examination
Kursen examineras genom ett skriftligt prov, skriftlig och muntlig redovisning av laborationer, och hemuppgift och muntlig redovisning av den individuella uppgiften.
Examinator
Lista över examinatorer finns på
-
Schema
Schema finns tillgängligt senast en månad före kursstart. Vi rekommenderar inte utskrift av scheman då vissa ändringar kan ske. Vid kursstart meddelar utbildningsansvarig institution var du hittar ditt schema under utbildningen. -
Kurslitteratur
Observera att kurslitteraturen kan ändras fram till två månader före kursstart.
Cormen, Leiserson, Rivest, and Stein: Introduction to algorithms.
-
Mer information
Kurshemsida
Vi använder inte Athena, utan du hittar kurshemsidan på kurser.math.su.se.
-
Kontakt
