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.
Criteria of this press release:
Information technology, Mathematics, Physics / astronomy
transregional, national
No categories were selected
German
You can combine search terms with and, or and/or not, e.g. Philo not logy.
You can use brackets to separate combinations from each other, e.g. (Philo not logy) or (Psycho and logy).
Coherent groups of words will be located as complete phrases if you put them into quotation marks, e.g. “Federal Republic of Germany”.
You can also use the advanced search without entering search terms. It will then follow the criteria you have selected (e.g. country or subject area).
If you have not selected any criteria in a given category, the entire category will be searched (e.g. all subject areas or all countries).
