| Master Thesis Topics TINF 2008-2009 |
(The description below is taken from the ``Answer set Programming'' ASP2000 conference announcement)
Answer Set Programming (ASP) (a.k.a. Stable Logic Programming or
A-Prolog) is the realization of much theoretical work in Non-monotonic
Reasoning and AI applications of Logic Programming in the last 12
years. It is based on the view of program statements as constraints
on the solution of a given problem. Subsequently, each model of the
program encodes a solution to the problem itself. For instance, an
ASP program encoding a planning scenario has as many models as valid
plans. This schema is similar to that underlying the application of
SAT algorithms to AI, and in fact the ranges of applicability of these
two techniques are similar. However, thanks to the inherent causal
aspect of Answer Set semantics, we can represent default assumptions,
constraints, uncertainty and nondeterminism in a direct way.
Several ASP systems are now available, e.g.
dlv,
and
smodels.
At TINF, we have developed extensions of answer set programming where e.g. rules are partially ordered according to their preference/weight etc., see e.g. this paper.
The goal of this thesis is to investigate other extensions that are either suitable to represent knowledge in specific application areas or have interesting complexity properties.
Contact Dirk Vermeir.
Een quantum computer is inherent parallel, vele operaties worden tegelijk uitgevoerd op grote stukken data. Bij klassieke simulatie wordt deze data exponentieel groot; een systeem van 30 qubits moeten we simuleren met een orde van 2^30 klassieke bits. Dit is ver voorbij de mogelijkheden van een enkele PC en komt zelfs aan de limiet van het geheugen van huidige high-performance computing architecturen. Simulatie is binnen dit domein cruciaal daar we nog niet over echte quantum computers beschikken. Een veelbelovende manier om deze exponentiële groei te temperen is het inherente parallelle gedrag van een quantum computer te vertalen naar een klassieke parallelle implementatie.
Er is dus een dringende nood aan a) parallellisatie van de berekeningen en b) distributie van data bij het simuleren van quantum computing. Gedistribueerde applicaties schrijven is niet gemakkelijk. Hierrond wordt veel onderzoek gedaan: agents, functioneel programmeren, data- parallellisme, etc. Deze eerder klassieke aanpakken falen als je een grote performantie wilt en het probleem automatisch wil laten opsplitsen over verschillende rekeneenheden. Men werkt allang aan compilers en frameworks die ervoor zorgen dat klassieke programma's automatisch gedistribueerd worden, maar de resultaten vallen tegen. In de praktijk wordt elk probleem apart bekeken en is de programmeur verantwoordelijk voor alle aspecten van het probleem: distributie, parallellisatie, performatie, enzovoort. Er moet worden teruggegrepen naar alternatieve programmeerstijlen. Stijlen die verplichten de programmeur zijn programma uit te drukken zodat er op een automatische manier het probleem kan worden gedistribueerd en er maximale performantie kan gehaald worden uit de hardware. Daarom pakken we voor deze thesis het probleem radicaal anders aan door gebruik te maken van Stream Programming. Stream programming laat de programmeur toe zijn probleem op een manier uit te drukken die zich veel beter leent tot het automatisch parallelliseren zonder in te binden op vlak van performantie. Deze aanpak werd al succesvol toegepast binnen verschillende rekenintensieve domeinen zoals videobewerkingen, protein folding, fysische simulaties. Het doel van deze thesis is het ontwikkelen van een stream programming omgeving die zich perfect leent tot het simuleren van quantum berekeningen. Tegelijkertijd willen we de huidige simulatielimiet van 36 qubits optrekken of op zijn minst bereiken.
Praktisch gezien bestaat deze thesis uit verschillende delen.
Contact Ellie D'Hondt
Contact Dirk Vermeir.
Make an appointment by email to Dirk Vermeir.