idw – Informationsdienst Wissenschaft
Nachrichten, Termine, Experten
Nachrichten, Termine, Experten
24.10.1997
Computerprogramm - formal korrekt? Algorithmus fuer die maschinensprachliche Grammatikkorrektur
Wenn ein Computerprogramm korrekt arbeiten soll, muss es formal korrekt geschrieben sein. Um festzustellen, ob diese Voraussetzung vorliegt, muss der Informatiker seinerseits unter Einsatz eines auf diese Aufgabe spezialisierten Computers pruefen, ob sich das Programm vollstaendig aus den Verknuepfungsregeln der zugrunde liegenden maschinensprachlichen Grammatik ableiten laesst.
Solche maschinensprachlichen "Aufsatzkorrekturen" naehmen bei komplexen Programmiersprachen kein Ende, wenn die Rechner nicht in der Lage waeren, bei jedem Teilschritt ein paar Programmeinheiten weit vorauszulesen - eine Eigenschaft, die in der Fachterminologie mit dem Praedikat "LR(k)" beschrieben wird. "LR" bedeutet "left to right" und meint die Leserichtung; das kleine k in der Klammer bezieht sich auf die Anzahl der Buchstaben, die der Rechner maximal nach vorn ueberblickt. Diese "Vorausschau" erlaubt, bei vertretbarem Rechenaufwand (in Polynomialzeit), zuverlaessige maschinengrammatische Analysen von Programmen - allerdings nur dann, wenn das Programm in einer Programmiersprache geschrieben wurde, die ihrerseits "von links nach rechts" aufgebaut ist und keine Verknuepfungen ueber die erlaubten k Elemente hinaus herstellt, die mithin, wie die Informatiker sagen, "LR(k)-Eigenschaft besitzt".
Loesung fuer den Durchschnittsfall
Bevor also ein Programm auf seine Grammatikalitaet ueberprueft werden kann, muss zunaechst einmal die zugrunde liegende Maschinengrammatik auf ihre LR(k)-Eigenschaft hin ueberprueft werden. Da es nun aber prinzipiell unendlich viele solcher Grammatiken gibt, stellt sich zuallererst die Frage, ob es ueberhaupt moeglich ist, in endlicher Zeit die LR(k)-Eigenschaft einer beliebigen Grammatik festzustellen beziehungsweise auszuschliessen.
Das ist der Hintergrund des Problems, zu dem Diplom-Informatiker Christoph Karg, wissenschaftlicher Mitarbeiter in der Abteilung Theoretische Informatik (Leiter Prof. Dr. Uwe Schoening) der Universitaet Ulm auf der IEEE Conference on Computational Complexity 1997 in Ulm (24. bis 27. Juni) einen Beitrag lieferte, der ihm den "Best Student Paper Award" eingetragen hat. Karg konnte nachweisen, dass zur schnellen Bewaeltigung der LR(k)-Frage bereits ein Algorithmus (d.h. ein Rechenweg) genuegt, der sie fuer den "Durchschnittsfall" schnell loest. Fuer diesen Durchschnitt wird angenommen, dass einfach und schwer zu testende Grammatiken etwa gleichhaeufig vorkommen. Man erhaelt damit eine Berechnungsgrundlage, die als repraesentativ fuer das LR(k)-Problem insgesamt gelten kann - das bedeutet: ein Algorithmus, der sich hier bewaehrte, koennte auf die Loesung einer Vielzahl von Problemen angewendet werden, fuer die bis zum gegenwaertigen Zeitpunkt kein schnelles, sprich: Polynomialzeit-Berechnungsverfahren existiert, darunter das aus zahlreichen Anwendungen bekannte "Travelling-Salesman-Problem".
Dass der Beantwortung einer Frage die Beantwortung der Zwischenfrage vorangeht, ob jene ueberhaupt beziehungsweise in endlicher Rechenzeit zu beantworten sei, ist in der modernen Informatik keine Seltenheit. Die zumindest teilweise Abklaerung solcher Basalfragen - loesbar oder nicht loesbar? - kann in der Anwenderpraxis gegebenenfalls Unsummen an Rechenzeit und Kosten fuer aussichtslose Analysen ersparen.
Merkmale dieser Pressemitteilung:
Informationstechnik, Mathematik, Physik / Astronomie
überregional
Es wurden keine Arten angegeben
Deutsch
Sie können Suchbegriffe mit und, oder und / oder nicht verknüpfen, z. B. Philo nicht logie.
Verknüpfungen können Sie mit Klammern voneinander trennen, z. B. (Philo nicht logie) oder (Psycho und logie).
Zusammenhängende Worte werden als Wortgruppe gesucht, wenn Sie sie in Anführungsstriche setzen, z. B. „Bundesrepublik Deutschland“.
Die Erweiterte Suche können Sie auch nutzen, ohne Suchbegriffe einzugeben. Sie orientiert sich dann an den Kriterien, die Sie ausgewählt haben (z. B. nach dem Land oder dem Sachgebiet).
Haben Sie in einer Kategorie kein Kriterium ausgewählt, wird die gesamte Kategorie durchsucht (z.B. alle Sachgebiete oder alle Länder).
