Upp till webbsidan för doktorandseminarierna.
Informationsfusion är beteckningen på ett forskningsfält där man studerar metoder att kombinera information från olika källor för att dra slutsatser. Ett paradexempel är det framtida nätverksbaserade försvaret, där man tänker sig att information från olika typer av sensorer och underrättelsetjänst ska "fusioneras" för att ge en tydlig bild av fiendens placering, kapacitet och i sista hand avsikt.
Inom området finns ett antal konkurrerande skolor som alla anser sig ha den slutliga lösningen på fusionsproblemet. De går under namnen (Robust) Bayes, DS - Dempster/Shafer, DSm - Dezert/Smarandache och FISST - finite set statistics (Goodman, Mahler, Nguyen). De kan alla betraktas som — sinsemellan olika — generaliseringar av Bayes metod. Jag tänkte ge en översikt över dessa skolors filosofiska grunder och speciellt visa att Robust Bayes och Dempster/Shafer inte verkar vara kompatibla, vilket jag själv (och andra) länge trott. Inkompatibiliteten består i inkoherens: med exakt samma ingångsdata kan Bayes metod och DS-metoden ibland leda till konkret olika förordade beslut.
This talk will introduce a few sample combinatorial problems and a give an overview of selection of techniques to solve them, mainly from the mathematical and constraint programming communities.
Topics covered will include linear programming, integer programming, network flows, constraint satisfaction problems and constraint programming with notes on global constraints and local search.
The talk is intended as an introduction to the field and does not require advanced mathematical or algorithmic background.
For several types of applications, it is interesting to be able to securely communicate with a group that has a dynamic membership. Such scenarios would include cable TV, media players and multimedia streaming. Since this talk is part of a Master's thesis work commissioned by Ericsson, the context will be that of multimedia streaming to mobile phones.
The mobile setting is particularly challenging due to the very limited bandwidth available compared to the number of users. China Mobile has over 100 million customers, and in 3G networks we may be able to afford around 64 kbps for the broadcast encryption scheme's network traffic.
A few different schemes for broadcast encryption will be covered. The focus will be on somewhat high-level descriptions of their design, rather than diving too deep into technical details.
The problem of estimating evolutionary trees from molecular sequences has received a lot of attention in the last 30 years and a multitude of models and methods have been suggested.
Despite the tremendous progress the field has seen, a few questions have kept haunting biologists. What do you do when a tree constructed from a gene tree clearly contradicts a species tree? Is it due to recombination or a simply weak signal in the data? When the gene family is large and several similar member-genes exists in one species, how do you tell which genes are each others functional equivalents in different species?
This talk will present progress on addressing these questions through an MCMC approach using a new probabilistic model that for the first time includes both sequence evolution as well as duplication and loss of genes.
Max k-CSP är ett så kallat villkorssatisfieringsproblem (eng. constraint satisfaction problems, CSP). Givet ett antal villkor, där varje villkor beror på som mest k stycken binära variabler, så är målet att satisfiera så många av dem som möjligt. Att lösa detta problem tar i allmänhet för lång tid (det är NP-fullständigt) och därför är det rimligt att undersöka hur bra man kan approximera problemet i effektiv tid.
Jag kommer att gå igenom en approximationsalgoritm för Max k-CSP. Tekniker som används i algoritmen är bland annat semidefinit relaxering och slumprestriktioner.
The dispensation order generation problem is a real-life combinatorial problem that arises in the context of analyzing large numbers of short to medium length DNA sequences with the Pyrosequencing method.
First, I will describe the Pyrosequencing method, its applications, the notions of dispensation order and sequence template, and the complications arising from diploid (or higher) genomes.
Secondly, I will introduce the problem of generating a dispensation order for a single sequence template, and its solution. The algorithm has the structure of a non-deterministic rewrite system, giving rise to a search tree. It uses nogood generation and limited discrepancy to improve the search.
Finally, I will introduce the problem of generating a dispensation order for a multiplexed reaction involving several unrelated sequence templates, and its solution. The algorithm is modelled as a constraint optimization problem, and has a constraint programming implementation using a custom search procedure.
Joint work with Nicolas Beldiceanu. Parts of this talk were (will be) presented at APBC2004 (CP2004).
Den jobbigaste uppgift en lexikograf kan ställas inför är nog att sätta ihop ett synonymlexikon. Därför finns det mycket få stora synonymlexikon, och dom som finns är inte fritt tillgängliga eftersom upphovsmännen lagt ner så mycket tid på att konstruera dom.
Vid seminariet ska jag beskriva hur man kan sätta ihop Sveriges största synonymlexikon utan större ansträngning och utan att någon upphovsman kräver ersättning. För att lyckas med detta behövs en stor lista med synonymförslag och en stor mängd datoranvändare som är villiga att lägga ner någon minut var på att bedöma hur bra ett antal synonymförslag är.
Synonymförslag produceras med hjälp av lexikonsökningar. Dåliga förslag rensas sedan automatiskt bort med en metod som kallas Random indexing. Det är en statistisk metod som bedömer hur pass relaterade ord är genom att mäta ordens avstånd i ett vektorrum där varje ord representeras av en så kallad kontextvektor.
Den beskrivna synonymgenereringsmetoden kommer att testas i höst med hjälp av ett system som utvecklades av D- och I-teknologer i Nadas programutvecklingsprojektkurs i våras.
An important problem in genome rearrangements is sorting permutations by transpositions. A transposition is a rearrangement operation, in which a segment is cut out of the permutation, and pasted in a different location. The complexity of this problem is still open, and it has been a ten-years-old open problem to improve the best known 1.5-approximation algorithm.
In this paper we provide a 1.375-approximation algorithm for sorting by transpositions. The algorithm is based on some new results regarding the transposition diameter of several subsets of the symmetric group, which are considered in the genome rearrangement literature: We determine the exact transposition diameter of 2-permutations and simple permutations, and find an upper bound for the diameter of 3-permutations.
Joint work with Tzvika Hartman.
Osäkerhetsmodellering, inferens och beslutsfattande kan i många applikationer göras framgångsrikt med hjälp av influensdiagram eller liknande strukturer för agentmodellering. Algoritmernas snabbhet och modellernas lättillgänglighet gör influensdiagrammet till det självklara verktyget för beslutsfattande i såväl realtidssituationer som situationer karakteriserade av att många okända variabler påverkar varandra på sätt som bara en beslutsfattare med domänkunskap kan förutse.
Ibland uppstår dock beslutssituationer där aktörens nytta är intimt förknippad med övriga aktörers agerande. Dessa spelteoretiska beslutssituationer karakteriseras av att aktörerna ägnar sig åt att resonera om övriga aktörers resonerande och sådana beroenden kan inte modelleras i ett influensdiagram. Lösningar till spelteoretiska problem utgörs i stället av jämviktslösningar, så kallade Nashjämvikter, som innebär att alla aktörer gör så bra de kan givet vad de tror att de andra aktörerna gör.
Jag kommer att presentera ett förslag till en beslutsstödskomponent som kombinerar influensdiagram och spelteori. I mån av tid kommer jag sedan att skrapa på ytan till de många intressanta och svåra problem som uppkommer vid beräkning och tolkning av Nashjämvikter.
Antag att vi vill kunna använda anonyma kreditkort. En kortinnehavare ska alltså kunna bevisa för en handlare att han har ett kort utgivet av banken och skapa en signatur som handlaren kan verifiera. Banken ska kunna se vem som har skapat signaturen, men handlaren ska inte kunna avgöra om två signaturer är skapade av samma person. Detta är vad gruppsignaturer åstadkommer. I mån av tid kommer vi också titta på hur man kan göra gruppsignaturer hierarkiska.
Upp till webbsidan för doktorandseminarierna.