Emissionen Nr 3 2003


Teoretisk Datalogi

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.

[Bild]

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.

P och NP

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.

Grafer

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å.

[Bild]

Foto: Harald Barth, PDC

Kryptering

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.

Relevanta kurser

Algoritmer, Datastrukturer, Komplexitet, 6p

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.

Avancerade algoritmer, 4p

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.

Kryptografins grunder, 4p

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.

Komplexitetsteori, 4p

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

Seminariekurs i teoretisk datalogi, 4p

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.

Algoritmisk bioinformatik, 4p

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.

Rasmus Kaj


Källor: Diverse kurslitteratur, Studiehandboken.



Emissionen är Konglig Elektrosektionens tidning vid KTH.

Valid

W3C html, W3C css, WAI aaa.