När jag började på KTH var ett av mina mål att bli en så
bra
programmerare som möjligt. Här är kurserna som
uppfyller det målet.
Hur jämför man två algoritmer som är tänkta att
göra samma sak?
Man kan naturligtvis implementera båda algoritmerna och köra dem
på exakt samma indata, och jämföra hur lång tid det tog. För att
ge en rättvis jämförelse måste man i så fall köra båda programmen
på samma dator, och man måste undvika en mängd störningar
som att andra program kan stjäla tid och så vidare. Dessutom
kanske man kommer fram till att en sämre algoritm är bättre bara
för att man gjort en sämre implementation av den bättre algoritmen.
Ett mer användbart mått på hur effektiv
en algoritm är får man
genom att se på hur programmets körtid beror av storleken på indata.
När man börjar mäta på ett program ser man visserligen ofta att
körtiden varierar ganska godtyckligt med små ändringar i indata,
men om man tittar på rejält olika mängder indata – man kanske
sorterar strängar, och jämför tiderna för att sortera 10, 100,
1000, 10 000, eller 100 000 strängar – så stämmer det
ofta grovt med någon enkel funktion.
Om man har en hyfsad sorteringsalgoritm så tar det ofta
O(n log n) tid att sortera n tal.
Problem kan delas upp i grupper, beroende på hur effektivt ett program som löser dem kan vara. En sådan grupp är P, problem som går att lösa i polynomisk tid, alltså O(nx) för någon konstant exponent x.
En annan sådan grupp är NP, problem som går att lösa ickedeterministiskt i polynomisk tid (Nondeterministic Polynomial). En ickedeterministisk lösning innebär att man tillåter programmet att gissa bitar. Om programmet gissar fel någon gång ska det märka att det misslyckas, det får inte ge fel svar, men man tar tid på en körning där den gissar rätt hela tiden. Ett annat sätt att definiera NP är att man kan verifiera en föreslagen lösning i polynomisk tid, vilket man kan bevisa ger samma mängd av problem.
P är en delmängd av NP, dvs alla problem som ligger i P ligger även i NP. Huruvida det faktiskt finns problem som ligger i NP men inte i P är fortfarande okänt. Däremot finns det en klass problem, de NP-kompletta, som har egenskapen att om man lyckas lösa ett NP-komplett problem i P-tid så går det att lösa alla problem i NP i P-tid, dvs då är P = NP. I praktiken utgår man från att P ≠ NP, så när man har bevisat att ett problem är NP-komplett antar man att det inte går att lösa i polynomisk tid.
Om man har flera saker (till exempel datorer, platser, växter,
elementarpartiklar) och någon form av relationer (som
nättrådar, busslinjer, släktskap eller kraftverkningar) och
vill veta något
om det (routingfrågor, hur åker man enklast hem? hur lika är
de här två molekylerna?) – då har man ett
grafproblem.
Sakerna
kallas noder och relationerna
är
kanter.
En grundfråga om grafer är huruvida en given graf är samanhängande, alltså, om du börjar i en godtycklig nod och bara följer kanter, kan du då nå vilken nod som helst i grafen?
Ett grafproblem som förekommer naturligt i många applikationer är frågan om en given graf är ekvivalent med en annan, dvs om man kan göra den om den ena grafen till den andra genom att bara numrera om noderna (och kanske flytta dem, om man har ritat grafen på ett papper, men det ingår egentligen inte i grafen). Problemet ligger i NP. Huruvida det också ligger i P, är NP-komplett, eller rentav både och återstår att ta reda på.
När man vill hålla något hemligt vill man kryptera på ett sådant sätt att man vet att det är svårt att knäcka kryptot. Samtidigt vill man kunna hantera kryptonyckeln enkelt. För att åstadkomma det kan man använda asymmetriska krypton, som använder en nyckel för att kryptera och en annan för att dekryptera.
Det måste vara någorlunda enkelt att skapa ett nyckelpar, men det ska vara så svårt som möjligt att lista ut den dekrypteringsnyckeln från krypteringsnyckeln. För att åstadkomma det kan man ta ett känt numeriskt problem, som faktorisering eller diskret logaritm, och bygga en kryptering runt det, vilket man också gör i RSA och andra moderna krypton.
2D1352. Grundkursen i teoretisk datalog,
förutsätter att man kan programera
(obligatorisk på
data).
Beskriver hur man angriper ett problem för att nå en lämplig algoritm och hur man analyserar en given algoritms egenskaper.
Går period 3-4.
2D1440. En avancerad kurs i gränsområdet mellan datalogi och diskret matematik som behandlar moderna tekniker för konstruktion av effektiva algoritmer.
Här handlar det mycket om faktoriseringar och andra beräkningar på stora heltal, men också om algoritmer på grafer och strängar.
Går period 2.
2D1449. Klassiska kryptosystem. Vad innebär säkerhet? Bakgrund inom informationsteori, entropi. Symmetriska krypteringsalgoritmer som t ex Advanced Encryption Standard (AES). Öppna nyckelsystem för kryptering och digitala signaturer t ex RSA. Kryptografiskt säkra hashfunktioner i teori och praktik (SHA). Pseudoslumptalsgeneratorer. Anknytningar till komplexitetsteori
Här tillämpas datalogin på ett både teoretiskt och praktiskt intressant ämne. Mycket rolig matematik med fält och kroppar.
Går period 3.
2D1446. Grundmålet inom komplexitetsteorin är att klassificera problem efter på hur mycket resurser (i första hand tid eller minne) som krävs för att lösa dem. Ett fullständigt problem för en komplexitetsklass är ett problem som kan ses som det svåraste inom klassen.
Behandlade områden: Komplexitetsklasserna L, NL, P, NP, PSPACE, BPP etc. Reduktion och fullständighet. Cooks' sats. Approximerbarhet. Probabilistiska algoritmer. Interaktiva bevis.
Ges vartannat år
2D1441. En avancerad kurs i teoretisk datalogi med varierande innehåll från år till år. I år handlar den om kryptografi, tidigare år har det bland annat gällt approximationsalgoritmer, probabilistiska algoritmer, och parallella beräkningar
Går period 4.
2D1450. En introduktion till den datalogiska delen av bioinformatik.
Kursens mål är att ge en introduktion till de algoritmer som används inom bioinformatik samt de som studeras inom bioinformatisk forskning.
Går period 4.
Källor: Diverse kurslitteratur, Studiehandboken.