haku: @supervisor Janhunen, Tomi / yhteensä: 234
viite: 6 / 234
| Tekijä: | Bomanson, Jori |
| Työn nimi: | Developing Efficient Encodings for Weighted Expressions in Answer Set Programs |
| Tehokkaiden esitystapojen kehittäminen painosäännöille vastausjoukko-ohjelmissa | |
| Julkaisutyyppi: | Diplomityö |
| Julkaisuvuosi: | 2014 |
| Sivut: | 85 Kieli: eng |
| Koulu/Laitos/Osasto: | Perustieteiden korkeakoulu |
| Oppiaine: | Tietojenkäsittelytiede (IL3010) |
| Valvoja: | Janhunen, Tomi |
| Ohjaaja: | Gebser, Martin |
| Elektroninen julkaisu: | http://urn.fi/URN:NBN:fi:aalto-201408292568 |
| OEVS: | Digitoitu arkistokappale luettavissa Harald Herlin -oppimiskeskuksen asiakaskoneilla | ohje
Digitaalisten opinnäytteiden lukeminen Aalto-yliopiston Harald Herlin -oppimiskeskuksen suljetussa verkossaOppimiskeskuksen suljetussa verkossa voi lukea sellaisia digitaalisia ja digitoituja opinnäytteitä, joille ei ole saatu julkaisulupaa avoimessa verkossa. Oppimiskeskuksen yhteystiedot ja aukioloajat: https://learningcentre.aalto.fi/fi/harald-herlin-oppimiskeskus/ Opinnäytteitä voi lukea Oppimiskeskuksen asiakaskoneilla, joita löytyy kaikista kerroksista.
Kirjautuminen asiakaskoneille
Opinnäytteen avaaminen
Opinnäytteen lukeminen
Opinnäytteen tulostus
|
| Sijainti: | P1 Ark Aalto 1755 | Arkisto |
| Avainsanat: | answer set programming cardinality rule normalization translation weight rule weighted expression kardinaliteettisääntö käännös normalisointi painosääntö vastausjoukko-ohjelmointi |
| Tiivistelmä (fin): | Vastausjoukko-ohjelmointi on kombinatoristen hakuongelmien ratkontaan soveltuva ongelmanratkontamenetelmä, jossa ohjelmointi koostuu loogisten yhteyksien deklaratiivisestä määrittelemisestä. Työssä käsitellyt vastausjoukko-ohjelmat koostuvat säännöistä, jotka määräävät atomisten lauseiden, tai atomien, väliset yhteydet. Tämänmuotoiseen ohjelmaan kytkeytyy formaali ongelma, jonka ratkaisemiseksi on löydettävä yksi tai useampi totuusjakelu näille atomeille, eli vastausjoukko, joka täyttää ohjelmaan kirjatut säännöt. Jokainen atomi on lisäksi asetettava epätodeksi paremman tiedon puutteessa. Vastausjoukko-ohjelmointi muodostaa yleiskäyttöisen ongelmanratkontamekanismin, sillä on mahdollista kirjoittaa ohjelma jonka vastausjoukoista on luettavissa kiinnostuksen kohteena olevan hakuongelman ratkaisut ja näiden vastausjoukkojen etsintää varten löytyy automatisoituja työkaluja. Tässä diplomityössä keskitytään erilaisten sääntötyyppien välisiin muunnoksiin ja erityisesti niin kutsutuiden painosääntöjen uudelleenkirjoittamiseen vain normaalisääntöjä käyttäen. Työn tavoitteena on kehittää tähän soveltuvia normalisointimenetelmiä olemassaolevien tekniikoiden pohjalta. Diplomityössä esitellään uusi heuristiikka sekakannan hakemiseksi sekä rakenteenjakoalgoritmi erään normalisointimenetelmän vaatiman atomi- ja sääntömäärän karsimiseksi. Näiden ja muiden tekniikoiden käyttöä varten on kirjoitettu tietokoneohjelma, jonka avulla tehtyjä kokeellisia tuloksia esitellään lopuksi. Saatujen tuloksien perusteella työssä kehitetyt tekniikat tuovat parannuksia muunnoksien tiiviyteen, haussa kohdattujen umpikujien määriin sekä erään johtavan ratkaisinohjelman aikavaatimuksiin. Tiettyjen testiongelmien kohdalla työssä esitetyt tekniikat auttavat ylittämää jopa ratkaisinohjelmaan sisäänrakennettujen painosääntömenetelmien tehokkuuden. |
| Tiivistelmä (eng): | Answer set programming is a declarative problem solving paradigm suitable for searching solutions to combinatorial search problems. Propositional answer set programs, studied in this thesis, consist of rules that state logical connections between atomic propositions, or atoms. A program represents the problem of finding truth assignments, called answer sets, that satisfy the rules in the program, under the condition that by default atoms are false. Answer set programming can be used as a general purpose problem solving mechanism, by writing programs whose answer sets correspond to solutions of a chosen search problem, and then using automated tools to find them. In this work, we focus on normalizing a particular type of rules, weight rules, into so called normal rules. We develop normalization strategies that extend existing translations applied in answer set programming and propositional satisfiability checking. In particular, we propose to incorporate a base selection heuristic and a structure sharing algorithm into a weight rule translation that decomposes the rule in a mixed-radix base. Both the previous and novel techniques have been implemented in a normalization tool, and we experimentally evaluate the effect of our methods on search performance. The proposed techniques improve on the compared normalization methods in terms of conciseness, the number of conflicts encountered during search, and the amount of time needed to find answer sets using a state-of-the-art solving back-end. On certain benchmark classes, the normalization techniques improve even on native weight-handling capabilities of the solver. |
| ED: | 2014-08-31 |
INSSI tietueen numero: 49695
+ lisää koriin
INSSI