Einfluss von Sprachkonstrukten auf die Lösbarkeit von Answer-Set-Programmen

MS-Photo-8443… ist der Titel der 1. Platz des Roland-Mittermeir-Preis und wurde vom Förderverein Technische Fakultät mit EUR 1.500,– ausgezeichnet. Dem Autor und Preisträger, Herrn Dipl.-Ing. Richard Taupe, wurde der Preis im Rahmen des Festakts 30 Jahre Informatik an der Alpen-Adria-Universität Klagenfurt übergeben und die Arbeit wird hier kurz vorgestellt:

Im traditionellen Paradigma der imperativen Programmierung werden Computer auf die folgende Art verwendet, um Probleme zu lösen: Ein Mensch entwirft einen Algorithmus, also eine Schritt-für-Schritt-Anleitung, mit der das Problem gelöst werden kann, übersetzt diesen in eine Programmiersprache und lässt den Computer dieses Programm ausführen. Bei der deklarativen Programmierung hingegen wird dem Computer nicht vorgeschrieben, wie er das Problem zu lösen hat. Stattdessen wird ihm nur das Problem selbst in einer geeigneten Sprache beschrieben, sodass die Lösungen für das Problem von einem universell einsetzbaren Suchalgorithmus gefunden werden können.

Answer Set Programming (ASP) ist ein Ansatz zur deklarativen Programmierung. Dazu gehört auch eine formale Sprache, in der Probleme deklarativ beschrieben werden können. Die Syntax dieser Sprache definiert verschiedene Sprachkonstrukte, mit denen ein und der selbe Sachverhalt oft auf mehrere unterschiedliche Arten dargestellt werden kann. Aus diesem Grund gibt es oft viele unterschiedliche Möglichkeiten, ein Problem in ASP zu modellieren.

Die Frage, die in dieser Arbeit beantwortet wird, ist, ob – und, gegebenenfalls, wie – die Wahl der verwendeten Sprachkonstrukte die Lösbarkeit von in ASP modellierten Problemen beeinflusst. Mit Lösbarkeit ist hier im Wesentlichen die Laufzeit der Lösungs- algorithmen gemeint, die die Probleme möglichst schnell lösen sollen. Um diese Frage zu beantworten, wurde eine große Anzahl an Versuchen durchgeführt, in denen verschie- dene in ASP modellierte Probleme gelöst wurden. Dabei wurde gemessen, wie lange die Lösungsfindung jeweils dauerte. Jedes Problem wurde in mehreren Darstellungen modelliert, die sich nur in den verwendeten Sprachkonstrukten unterschieden.

Die statistische Analyse der bei diesen Experimenten angefallenen Daten zeigt vor allem, dass der Einfluss der verwendeten Sprachkonstrukte von Problem zu Problem stark schwankt: Was sich in einem Fall günstig auf die Lösbarkeit auswirkt, kann in einem anderen Fall unerwünschte Folgen haben. Bei praktischen Anwendungen von ASP sollten die verwendeten Sprachkonstrukte daher nicht leichtfertig gewählt werden. Stattdessen sollten verschiedene äquivalente Darstellungen angefertigt und ihre Lösbarkeit verglichen werden, um dann das am schnellsten lösbare Programm tatsächlich zu verwenden.

Posted in News | Leave a comment

Schreib einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind markiert *

This blog is kept spam free by WP-SpamFree.