DA2210 Vetenskapsteori och metodik för dataloger

KTH/CSC Henrik Eriksson

En forskare som funderar på att skriva en populärvetenskaplig bok om begreppet komplexitet ger dig denna text med osmälta funderingar och ber dig läsa och kommentera. Läs men kommentera bara en sak!

Komplexitet i vetenskapen

Komplexitet är ju den teoretiska datalogins viktigaste begrepp och det är anledning att reflektera över begreppets vetenskapsteoretiska status. Vi ser först på en dialog som tycks visa att innebörden är paradoxal.

A: Linjär sökning har högsta komplexiteten, nämligen O(n), för binär sökning är komplexiteten mycket lägre, nämligen O(log n) och allra lägst komplexitet har perfekt hashning, nämligen O(1).

B: Nu skojar du väl! Linjär sökning är ju allra enklast, binär sökning är klart mer komplext och hashning är mycket komplicerat.

Tydligen kan man lägga två olika innebörder i ordet komplexitet. Vad lurigt! Finns det bättre ord? Låt oss se hur ordet används i datalogiska sammanhang och inom andra vetenskapliga områden.

Planetbanor Ett klassiskt exempel som man inte kan komma undan.

* Tycho Brahe: Planetobservationstabeller

* Johannes Kepler: Planeterna rör sig i ellipser

* Isaac Newton: Gravitationslagen

Ökade eller minskade komplexiteten?

Algoritmer Tidskomplexitet, rumskomplexitet, bitkomplexitet och värstafalletkomplexitet är varianter på den första betydelsen.

Problem Övre och undre gränser för sortering, faktorisering osv, vilket komplexitetsbegrepp är det då fråga om? Har oavgörbarhet att göra med komplexitet? Förekommer den andra innebörden av ordet? Kan hög komplexitet vara eftersträvansvärd?

Data Bild, ljud och text kan lagras på olika format. Kan man tala om komplexitet i de båda innebörderna? Har informationsteori något med saken att göra? Vad är minimal och maximal komplexitet?

Programspråk Högnivåspråk, maskinkod, vilket har högst komplexitet? Vad betyder kompilering med de båda komplexitetsinnebörderna? Har Turingmaskinprogram hög eller låg komplexitet?

Modellering UML-diagram, abstraktion, designmönster, hur hänger de ihop med komplexitet. Eftersträvas komplexitet av något slag?

Projektmetodik Specifikation eller agila metoder? Christer Hoberg har skrivit avhandlingen Komplexitetsmax, där antalet frihetsgrader (till exempel parametrar som inte fått värde än) är mått på komplexitet och när det nått en viss maxgräns måste man ta bort friheter genom att till exempel fixera en parameter. Hur passar det in i begreppen?

Lingvistik Språk tycks ha utvecklats så här: först konkreta ord för individer (Toto), sedan generaliseringar (hund) i allt högre nivå (djur). Tolka detta med komplexitetsbegreppen!

Lagar Historikern Arne Jarrick studerar hur lagar utvecklats, från Hammurabis babyloniska lag till våra dagars. Han ger följande exempel: I den äldsta lagen stadgas

För stöld av tupp bötas sju mynt. För stöld av anka bötas sju mynt.

I senare lag har detta ändrats till

För stöld av fjäderfä bötas sju mynt.

Hur tolkas denna utveckling i komplexitetstermer?

Fysik Materien består av molekyler, som består av atomer, som består av elementarpartiklar, som består av kvarkar, som kanske består av strängar. Tolka med komplexitetsbegreppen!

Termodynamik Entropin i ett slutet system kan bara öka enligt den andra huvudsatsen. Entropi är ett mått på slumpmässigheten i systemet, alltså det som kan kallas oordning. Komplexitetstolka!

Evolution Människor tycks mer komplexa än encelliga organismer, men vilket komplexitetsbegrepp menar vi då? Och hur går evolutionen ihop med termodynamikens andra huvudsats?

Kritisk vetenskapsteori Tillhör komplexitetsbegreppet ett paradigm inom datavetenskap? Enligt Kuhn skulle det kunna bli oanvändbart inom nästa paradigm. Foucault skulle påpeka att begreppet ingår i en diskurs som konstruerar datalogins världsbild. Dekonstruera komplexiteten!

Ekonomi Depression, inflation, högkonjunktur är ord som införts av nationalekonomer och som nu alla svänger sig med. De tycks ha att göra med innehållet i plånboken men ingen förstår riktigt hur. Tolka med komplexitetsbegreppet om det går!

Kulturell evolution Hur kan modesvängningarna vara globala? Varför sprider sig vissa beteenden och idéer? Det finns inga otvetydiga svar men kanske kan komplexitet vara ett användbart begrepp?

Finns det lagar för komplexitet? I flera av exemplen ovan, till exempel Hammurabis lag och entropin, tycks komplexiteten utvecklas lagbundet.

Om man identifierar två olika komplexitetsbegrepp skulle man kanske kunna formulera en allmän komplexitetslag. Bli först i världen med att göra detta och hitta gärna på ett slående namn för principen!