Göm menyn

Nyheter 2015

Om kombinatorisk optimering

Vissa optimeringsproblem är i praktiken olösbara; de algoritmer vi har till förfogande kräver enorm körtid. Andra problem kan däremot lösas effektivt. Varför är det på det här viset? Vilka egenskaper är det som gör problem hanterbara, eller omvänt, svårlösta? I en doktorsavhandling på IDA om komplexitet av kombinatoriska optimeringsproblem studerar Hannes Uppman frågor av den här typen.

Huvuddelen av avhandlingen handlar om för vilka optimeringsproblem det finns en effektiv algoritm, och för vilka det är mycket osannolikt att en sådan algoritm existerar. En mer exakt formulering av frågan som ställs är: Vilka problem har en polynomisk algoritm och vilka problem är NP-svåra? Problem för vilka det finns en polynomisk algoritm kan i någon mening ses som effektivt lösbara. NP-svåra problem tros däremot inte kunna lösas effektivt. Att visa att inget NP-svårt problem har en polynomisk algoritm (eller att det mot förmodan faktiskt finns en sån algoritm) är ett välkänt öppet problem känt som P mot NP frågan, och tros vara mycket svårt. Till exempel har Clay Mathematics Institute utlyst en belöning på en miljon dollar för en lösning.

Istället för att studera enskilda problem undersöks stora familjer, familjer som innehåller många viktiga problem med åtskilliga teoretiska och praktiska
tillämpningar och som tidigare studerats enskilt. Syftet med det här angreppssättet är att avslöja fundamentala egenskaper som antingen möjliggör eller omöjliggör effektiva algoritmer. Fokus ligger alltså inte på att hitta den snabbaste algoritmen för ett enskilt problem, utan på att hitta enkla förklaringar till varför en stor klass av problem är NP-svåra, eller egenskaper som omvänt kan utnyttjas och därigenom möjliggöra en effektiv algoritm.
Läs mer

Firande av D40IT20 jubileum

Tisdagen den 19 maj bjöds på fest och jubileumskonferens på Konsert och Kongress i Linköping. Detta med anledning av att första Datateknikutbildningen i Sverige (D programmet i Linköping) fyllde 40 år och att samtidigt fyllde civilingenjörsprogrammet i informationsteknologi (IT) 20 år. Dagen till ära hade alumner från en rad olika verksamheter samlats för mingel med nuvarande studenter och undervisare. Bland alumni-talarna fanns John Wilander verksam på Apple som rest hit från Cupertino, Petter Weiderholm från Spotify, Helena Mischel från Microsoft, och Ulrik Lindblad från SP devices. Dessutom fick inbjudna gäster en rejäl dos av framtidsspaning från Erik Kruse (marknadsföringsstrateg från Ericsson) och Tracy Hammond som är forskare inom området AI, IoT, lägesmedevetande, och koncept inlärning. Mingel, tårta, musik och underhållning kompletterade programmet och skapade en perfekt möjlighet till nätverkande. Åhörarna fick utmaningen av John Wilander att kombinera det vassa tekniska kunnandet som finns i regionen med mekanismer uppfunna av Silicon Valley för att lansera (rik och lyckade) ingenjören som samhällets beslutsfattare.
Läs mer

Pris för bästa exjobb

Årets pris för bästa examens arbete delades ut av Dataföreningen i samarbete med Linköpings universitet under en ceremoni där över 400 alumner och teknologer firade 40 års jubileum för utbildningsprogrammet Datateknik, som sammanföll med IT-programmets 20 års jubileum. D40-IT20 firades med en jubileumskonferens där framstående talare från Texas A&M University, Apple, Microsoft, SP devices, Spotify, och Ericsson talade.

Fem exjobbare hade nominerats till priset och två av dessa fick diplom och blomma efter tårtfesten. Dessa var Klervie Toszé (för exjobb utfört på Ericsson), och Viktor Löfgren (för exjobb utfört på Valtech).

Årets nominerade examensarbetare var: Viktor Löfgren (Civing Informationsteknologi och Double Degree med Harbin Inst. Technology), Martin Nilsson (Civing Teknik fysik och elektronik), Niclas Norman (Dataingenjör), Johan Persson (Masterprogrammet Kognitionsvetenskap), Klervie Toczé (Datateknik och Double degree med UTC). Alla exjobb är åtkomliga via LiU e-press: http://liu.diva-portal.org/smash/search.jsf


Sidansvarig: Webmaster