Eine Normsprache ist eine konstruierte Sprache,die durch methodische Rekonstruktion einer in einem Anwendungsbereich eingesetzten natürlichen Sprache (Gemeinsprache oder Fachsprache) gewonnen wird, z.B., indem vage und homonyme Benennungen entfernt und synonyme Benennungen nur in kontrollierter Form zugelassen werden. Sie stellt nicht das Ergebnis der Normungsarbeit einer Normungsorganisation wie z.B. des Deutschen Instituts für Normung (DIN) dar, sondern ist das Resultat unternehmensinterner Normierungsbestrebungen. Man könnte demzufolge statt von „Normsprache" auch von „Unternehmensnormsprache" oder „genormter Unternehmens(fach)sprache" sprechen,wobei „Unternehmen" hier im weitesten Sinne zu interpretieren ist.

Das Besondere an einer Normsprache im Vergleich zu formalen Sprachen ist ihr materialsprachlicher Charakter. Dieser besagt, daß eine Normsprache im Hinblick auf ihr konkretes Anwendungsgebiet nicht nur in ihrer Grammatik (formaler Teil) sondern auch in ihrem Bestand zulässiger Wörter (materialer Teil) – der einem bestimmten Anwendungsgebiet (z.B. Betriebswirtschaftslehre, Medizin) zugeordnet ist – zur Bildung korrekter Aussagen über dieses Gebiet vorher festgelegt wird [10]. Zur Festlegung des Wortschatzes wird ein entsprechendes Wörterbuch aufgebaut und gepflegt. Dagegen beschränken sich formale Sprachen auf die Festlegung der Grammatik (Satzbaupläne) gültiger Aussagen eines Anwendungsgebiets. Ausdrücke in einer formalen Sprache sind deshalb allein gültig aufgrund ihrer Form, unabhängig davon, welche Fachwörter sie enthalten.

Die Wörter der Normsprache unterscheiden sich von Wörtern der natürlichen Sprache grundsätzlich darin, daß sie nicht erst in einem bestimmten Anwendungskontext eine bestimmte Bedeutung annehmen,sondern als Terminologie eines Gegenstandsbereichs für stets dieselbe Verwendung vorgesehen sind [3]. Die Kernidee einer Normsprache lautet somit,eine normierte Sprache, die permanent an die Unternehmensverhältnisse anzupassen ist, zur besseren Kommunikation in und zwischen Organisationen einzuführen, deren Verwendung obligatorisch sein muß. Eine Verbesserung der Kommunikation innerhalb eines Unternehmens wird aufgrund des gemeinsamen Gebrauchs einer Normsprache durch alle Unternehmensangehörigen dadurch erzielt, daß mit Hilfe der genormten Terminologie Mißverständnisse bei der Benennung von Situationen und Gegenständen vermieden werden.

Ein wichtiges Einsatzgebiet von Normsprachen ist die Entwicklung rechnerunterstützter Informationssysteme. Die entsprechende Entwicklungsarbeit erfordert eine intensive Kommunikation zwischen Anwendern und Entwicklern, um Aussagen über das Anwendungsgebiet zu erheben, aus denen alle weiteren Entwicklungsergebnisse – ohne Beteiligung der Anwender – abgeleitet werden können. Problematisch ist, daß sich die von Anwendern und Entwicklern bevorzugt eingesetzten Sprachen stark voneinander unterscheiden. Während Anwender in einer gewachsenen, natürlichen Sprache kommunizieren, werden von den Entwicklern künstliche, konstruierte Sprachen (z.B. Diagrammsprachen) wegen ihrer „formalen Eindeutigkeit" bevorzugt [10]. Demzufolge können Informationssysteme nur dann effizient und den Anwendern angemessen konstruiert werden, wenn die Sprachlücke zwischen gewachsenen und konstruierten Sprachen durch eine Sprache geschlossen wird, die sowohl Anwender als auch Entwickler verstehen können [1]. Zur Schließung dieser Lücke wird die Einführung einer sowohl in ihrer Grammatik als auch bezüglich ihres Wortschatzes gegenüber der natürlichen Sprache eingeschränkten, dennoch aber vertraut wirkenden reglementierten Sprache in Gestalt der Normsprache vorgeschlagen,denn eine höchstmögliche Klarheit des angestrebten Ausdrucks ist mit den gegebenen Formen der natürlichen Sprache nicht zu erreichen [12]. Eine solche reglementierte Sprache sollte deshalb so aufgebaut sein, daß es den Anwendern nicht schwerfällt, die gegenüber der natürlichen Sprache erforderlichen Einschränkungen in Grammatik und Wortschatz zu akzeptieren [10].

In der Praxis wird der normsprachliche Ansatz sowohl auf der Ebene der eingesetzten Sprachen als auch auf der Ebene der Sprachprodukte (der Ebene der Ergebnisse sprachlich basierter Entwicklungsarbeit) schon teilweise eingesetzt. Auf der Ebene der Sprachen ist neben dem beschriebenen konstruktivistischen Ansatz mit einer normierten Terminologie und festgelegten Satzstrukturen an die Normierung von Datenelementen [9], an die Verwendung von Terminologien und Ontologien in der Künstlichen Intelligenz (KI) [2, 13] sowie an die in der komponentenorientierten Entwicklung von Informationssystemen verwendeten Anwendungselemente (Business Objects) [7] zu denken. Auf der Ebene der Sprachprodukte sind der Aufbau von Unternehmensdatenmodellen bzw. Branchendatenmodellen, der Einsatz von Produktdatenmodellen (z.B. STEP) und der Einsatz von Referenzmodellen (z.B. das SAP R/3-Referenzmodell) zu nennen. Diese normsprachlichen Sprachprodukte basieren jedoch auf einer formalen und keiner materialen Sprache, denn das Spektrum zulässiger Wörter wird nicht separat, d.h. neutral gegenüber ihrem Einsatz in Anwendungen, als Teil der Entwicklungssprache festgelegt.

Die Benennung „Normsprache" selbst geht auf Schienmann [11] zurück,der sie anstelle der von Lorenzen [5, 6] eingeführten Benennung „Orthosprache" (gr.: orthos,richtig) verwendet, um nicht den falschen Eindruck zu erwecken, eine Normsprache sei die einzig richtige Sprache, etwa im Sinne einer Idealsprache. Als Idealsprache wiederum gilt eine durch geeignete syntaktische und semantische Normierung präzisierte und deshalb formalisierbare Wissenschaftssprache [8]. Die Idee der Normsprache stammt aus der konstruktiven Wissenschaftstheorie der Erlanger Schule (W. Kamlah, P. Lorenzen u.a.). Lorenzen kam in seinen Arbeiten zu dem Ergebnis, daß die Komplexität natürlicher Sprachen nicht vollständig im Sinne des Programms der analytischen Wissenschaftstheorie analysiert werden kann [6]. Statt dessen wird die Einführung einer künstlichen Sprache vorgeschlagen und zwar einer in ihrer Mächtigkeit der natürlichen Sprache vergleichbaren, jedoch präziseren Sprache, die methodisch und zirkelfrei konstruiert werden kann und den im Zusammenhang mit der Entwicklung von Informationssystemen erhobenen Forderungen nach Eindeutigkeit und Präzision der Fachbegriffe genügt. Die konstruktive Wissenschaftstheorie sieht vor, daß in den Fachwissenschaften auf diese Weise jeweils präzise Fachsprachen aufgebaut werden, die dann das wissenschaftliche Arbeiten unterstützen und gleichzeitig den wissenschaftlichen Charakter dieser Arbeiten unterstreichen. Im Bereich der Informatik hat erstmals Wedekind die Idee der Normsprache (respektive Orthosprache) verwendet [14] und in einem Lehrbuch für den Bereich der Datenbanksysteme [15] umfassend ausgearbeitet.

Eine ähnliche Zielsetzung wie eine Normsprache verfolgen auch fachspezifische Programmiersprachen (Domain Specific Languages) bezogen auf formalisierte Fachsprachen [4]. Formalisierte Fachsprachen weisen einen sehr hohen Abstraktionsgrad auf, wie er für theoretische Grundlagenwissenschaften und experimentelle Wissenschaften charakteristisch ist. Sie verwenden bevorzugt künstliche Symbole als Sprachelemente. Formalisierte Fachsprachen sind jedoch nur für spezielle Anwendungsgebiete geeignet, denn wegen ihres hohen Abstraktionsgrads sind sie für die Kommunikation mit Anwendern im kommerziellen Umfeld in der Regel ungeeignet, da ihre Beherrschung durch die Anwender nicht vorausgesetzt werden kann. Eine an die natürliche Sprache angelehnte Normsprache bietet dann wiederum die geeignete Lösung, als gemeinsame Kommunikationsbasis zwischen Entwicklern und Anwendern im Rahmen der Entwicklung von rechnergestützten Informationssystemen zu dienen.

Artikelanfang Seitenanfang

Literatur

Dahme, C., Raeithel, A.: Ein tätigkeitstheoretischer Ansatz zur Entwicklung von brauchbarer Software. Informatik Spektrum 20, 5-12 (1997)
Gruber, T.: A Translation Approach to Portable Ontology Specifications. Knowledge Acquisition 5, 2, 199-221 (1993)
Kamlah,W., Lorenzen, P.: Logische Propädeutik, 2. Aufl., Mannheim: BI-Wissenschaftsverlag 1973
Lampe, J.: Fachsprachen. Informatik Spektrum 20, 372-373 (1997)
Lorenzen, P.: Semantisch normierte Orthosprachen. In: Kambartel, F., Mittelstraß, J. (Hrsg.): Zum Normativen Fundament der Wissenschaft, Frankfurt/Main: Athenäum 1973, 231-249
Lorenzen, P.: Lehrbuch der Konstruktiven Wissenschaftstheorie, Mannheim: BI-Wissenschaftsverlag 1987
McDavid, D.: Business language analysis for object-oriented information systems. IBM Systems Journal 36, 2, 128-150 (1996)
Mittelstraß, J. (Hrsg.): Enzyklopädie Philosophie und Wissenschaftstheorie, 4. Bde., korr. Nachdr., Stuttgart, Weimar: Metzler 1995
Ortner, E., Rössner, J., Söllner, B.: Entwicklung und Verwaltung standardisierter Datenelemente. Informatik Spektrum 13, 17-30 (1990)
Ortner, E.: Methodenneutraler Fachentwurf, Stuttgart, Leipzig: Teubner 1997
Schienmann, B.: Objektorientierter Fachentwurf: ein terminologiebasierter Ansatz für die Konstruktion von Anwendungssystemen, Stuttgart, Leipzig: Teubner 1997
Schnelle, H.: Sprachphilosophie und Linguistik: Prinzipien der Sprachanalyse a priori und a posteriori, Reinbek b. Hamburg: Rowohlt 1973
Studer, R., Benjamins, V., Fensel, D.: Knowledge Engineering: Principles and Methods, Arbeitspapier o. J.
Wedekind, H.: Eine Methodologie zur Konstruktion des Konzeptionellen Schemas. In: Band zur Tagung „Datenbanktechnologie" des German Chapters der ACM, Bad Nauheim, 21.-22.9.1979, Stuttgart: Teubner 1979, 65-79
Wedekind, H.: Datenbanksysteme I - eine konstruktive Einführung in die Datenverarbeitung, 2., völlig neu bearb. Aufl., Mannheim: BI-Wissenschaftsverlag 1981

Artikelanfang Seitenanfang

Autor & Copyright
Frank R. Lehmann
Technische Universität Darmstadt
Fachgebiet Wirtschaftsinformatik I,
Hochschulstraße 1
64289 Darmstadt
Tel 06151/16-4932, Fax: 06151/16-4301
fl@bwl.tu-darmstadt.de

Artikelanfang Seitenanfang

Nullfenster-Suche

Erläuterung
Literatur
Autor & Copyright

Erläuterung

Ein Nullfenster (engl.: null window, minimal window) ist ein bis zur Größe Null reduziertes Suchintervall, das in der Spielbaumsuche zur Beschleunigung der Minimaxwert-Berechnung eingesetzt wird. Während die Vorteile des normalen, d.h. nicht-leeren Suchfensters schon seit langem in Theorie [1] und Praxis [6] bekannt ist, kam man erst in de 80er Jahren auf die Idee, das Suchfenster bis zum absoluten Minimum zu reduzieren. Auf den ersten Blick mutet die Nullfenster-Suche nicht besonders effizient an, denn sie birgt das Risiko, daß einzelne Teile des Spielbaums mehrfach durchsucht werden müssen. Der Mehraufwand ist jedoch gering, und er tritt so selten auf, daß die mit dem Nullfenster erzielten Einsparungen überwiegen. Dies gilt für Zufalls-Bäume [4, 5] und in besonderem Maße für praktische Anwendungen, in denen heuristische Verfahren zur Knoten-Vorsortierung für eine günstige Expansionsreihenfolge sorgen [2].

Schach, Dame und Go sind typische Beispiele für Zwei-Parteien-Null-Summen-Spiele, in denen die Nullfenster-Suche angewendet wird. Zwei Spieler führen abwechselnd Züge aus, bis das Spielende erreicht ist und der Gewinn entsprechend dem Spielerfolg aufgeteilt wird. Die möglichen Spielverläufe ergeben einen Spielbaum, dessen Knoten die Spielstellungen und dessen gerichtete Kanten die Zugvarianten repräsentieren. Die Blätter sind mit (echten oder geschätzten) Stellungswerten bewertet. Ein Spieler wird versuchen, seinen Gewinn zu maximieren, während sein Gegenspieler nach dem Gegenteil, der Minimierung, trachtet. Ziel der Baumsuche ist die Berechnung des Minimaxwertes der Wurzel, der dem Spielergebnis der Ausgangsstellung entspricht.

Alpha-Beta

Grundlage der Nullfenster-Suche ist der Alpha-Beta-Algorithmus [1, 3] ein tiefenorientiertes Suchverfahren, das mittels einer ausgeklügelten Verzahnung von Knotenexpansion und Minimax-Rückbewertung redundante Teile des Suchbaums abschneidet, d.h. überspringt. Der Alpha-Beta-Algorithmus ist eine Erweiterung des bekannten Branch-and-Bound-Verfahrens für Zwei-Parteien-Spiele. Er expandiert den Baum mit zwei Schrankenwerten. Die untere alpha-Schranke entspricht dem Mindestgewinn, den der maximierende Spieler (MAX) bei beliebigem Gegenspiel garantiert erzielen kann. Analog bezeichnet beta den Mindestgewinn des MIN-Spielers unter Berücksichtigung aller MAX-Reaktionen. Zusammen begrenzen die beiden Schrankenwerte ein Intervall das (alpha,beta)-Suchfenster, in dem der Minimaxwert des Spielbaums gesucht wird. Knoten mit einem Wert von < alpha oder > beta werden ohne Informationsverlust abgeschnitten (Abb. 1). (MAX-Knoten sind als Quadrate und MIN-Knoten als Kreise dargestellt; die endgültigen Minimaxwerte befinden sich innerhalb der Knotensymbole.)

Abb. 1

Im Beispiel wird der rechte Nachfolger des mit >= 9 gekennzeichneten MAX-Knoten abgeschnitten, weil hier die Schnittbedingung 9 >= beta = 5 erfüllt ist, der MIN-Spieler also bereits eine bessere Zugvariante mit dem Wert 5 besetzt. Analog gilt im rechten Wurzel-Nachfolger 4 <= alpha = 5, was gleichfalls einen Schnitt ermöglicht. Den beteiligten Schrankenwerten entsprechend unterscheidet man alpha- und beta-Schnitte.)

Fenstersuche

Je kleiner das Suchfenster, desto mehr Knoten können abgeschnitten werden. Zwar schrumpft das anfänglich mit (- unendlich, + unendlich) initialisierte Fenster automatisch mit jeder neuen gefundenen Zugvariante. Um den Langsamen Schrumpfungsprozeß zu beschleunigen, kann man die Suche aber auch sogleich mit einem reduzierten Fenster (nu - epsilon, nu + epsilon) starten, das um einen vorab geschätzten Minimaxwert nu angeordnet ist. Diese im Englischen als "aspiration search" bezeichnete Methode [2] hat sich besonders gut in Kombination mit der iterativen Suche bewährt, bei der derselbe Baum mehrfach mit sukzessiv erhöhter Suchtiefe (1, 2, ..., d) expandiert wird. Trotz der Mehrfachexpansionen ist die iterative Suche mit einem direkten Suche einem direkten Suchvorgang der Tiefe d überlegen, weil die in der vorangegangenen Iteration gewonnenen Knoten-Informationen größere Einsparungen ermöglichen. So wird u.a. der vorhergehende Minimaxwert Nu zur Initialisierung des nächsten Suchfensters (nu - epsilon, nu + epsilon) verwendet.

Nullfenster

Nullfenster-Suchverfahren expandieren den Baum mit einem extrem reduzierten Suchfenster, dem sog. Nullfenster. Dabei handelt es sich um ein leeres Such-Intervall (nu, nu + 1), das kein Element enthält - vorausgesetzt, der Wertebereich ist ganzzahlig. Nullfenster sind natürlich nicht zur Berechnung des Minimaxwertes geeignet, da dieser stets außerhalb des Fensters liegt. Mit ihnen kann jedoch geprüft werden, ob der Minimaxwert unter oder oberhalb eines gegebenen Referenzwertes r liegt (Abb. 2).

Abb. 2

NegaScout [5] ist eine verbesserte Variante von Pearls Scout-Algorithmus [4], die auf der kompakteren Negamax-Rückbewertungsmethode beruht. NegaScout ermittelt den ersten Blattwert als anfänglichen Referenzwert r und versucht, mit Hilfe eines Nullfensters zu beweisen, daß die Alternativen unterlegen sind, d.h. den Minimaxwert nicht beeinflussen können. Das ist dann der Fall, wenn die restlichen MAX-Knotennachfolger <= r und die restlichen MIN-Knotennachfolger >= r sind. Gelingt der Beweis, so hat NegaScout mit minimalem Aufwand an Knotenexpansionen gezeigt, daß der Minimaxwert = r ist. Schlägt er hingegen fehlt, muß der betreffende Unterbaum im Rahmen einer Wiederholungssuche (engl.: re-search) noch einmal durchsucht werden, um seinen Minimaxwert als neuen Referenzwert zu ermitteln. Das geschieht nach demselben rekursiven Verfahren.

Auf den ersten Blick erscheint die Nullfenster-Suche ein riskantes Unterfangen, da selbst bei guter Knoten-Sortierung Wiederholungssuchen nicht gänzlich vermieden werden können. Empirische [2, 5] und analytische [4, 5] beweisen jedoch, daß die mit dem Nullfenster erzielten Einsparungen den Mehraufwand gelegentlicher Wiederholungssuchen bei weitem übertreffen. Die negativen Auswirkungen der Wiederholungssuche können durch Verwendung eines möglichst engen Schrankenwertes weiter reduziert werden [2]. Der Erfolg der Nullfenster-Suche beruht darauf, daß es einfacher ist, die Unterlegenheit eines Unterbaums zu beweisen, als seinen exakten Minimaxwert zu berechnen (was sich im nachhinein oftmals als überflüssig herausstellt). Dieses Vorgehen erlaubt neben den üblichen alpha- und beta-Schnitten eine weitere Schnittart, die Nullfenster-Schnitte. In Abb. 3 expandiert NegaScout den rechten Wurzel-Unterbaum mit dem Nullfenster (5, 6), um zu beweisen, daß sein Wert <= 5 (dem bisherigen Referenzwert) ist. Dabei tritt ein Nullfenster-Schnitt auf, den Alpha-Beta mit seinem größeren Suchfenster (5, unendlich) nicht durchführen kann.

Abb. 3

Da NegaScout zusätzlich zu den Nullfenster-Schnitten auch die "regulären" alpha- und beta-Schnitte realisiert, gilt die folgende Dominanzrelation: Jeder Knoten, der von NegaScout expandiert wird, muß auch von Alpha-Beta expandiert werden (umgekehrt jedoch nicht) [5]. Die Suche mit einem Nullfenster ist sogar optimal, und zwar in dem Sinne, daß kein anderes Suchverfahren zur Minimaxwert-Berechnung im statistischen Mittel weniger Knotenexpansionen benötigt [4, 5]. Das schließt auch die aufwendigen Besten-Suchverfahren SSS* und Dual* [5] ein, die gleichfalls der reinen Nullfenster-Suche unterlegen sind.

NegaScout profitiert von den bekannten heuristischen Verfahren zur Vorsortierung der Knoten-Expansionsreihenfolge sowie von diversen Speichertabellen, ohne die moderne Schachprogramme gar nicht mehr konkurrenzfähig wären, genau diejenigen Informationen die auch zur Abkürzung (bzw. Vermeidung) von Wiederholungssuchen erforderlich sind. Das hat zur Folge, daß NegaScout in Bäume der Breite w und Tiefe d oft nur geringfügig mehr als die minimale Knotenzahl w**[d/2] + w**[d/2] - 1 durchsucht [2].

Artikelanfang Seitenanfang

Literatur

Brudno, A.L.: Boudaries and estimates for abridging the search of estimates. Probl. Cybernet. 10, 225-241 (1963)
Kaindl, H., Shams, R., Horaces, H.: minimax search algorithms with and without aspiration windows. IEEE Trans. Pattern Anal. Mach. Intell. PAMI-13 1225-1235 (1991)
Knuth, D.E., Moore, R.W.: An analysis of alpha-beta pruning. Art. Intell. 6, 293-326 (1975)
Pearl, J.: Heuristics: Intelligent Search Strategies for Computer Problem Solving, Reading, Mass.: Addison-Wesley 1984
Reinefeld, A.: Spielbaum-Suchverfahren. Informatik-Fachberichte 200, Berlin: Springer 1989
Slate, D.J., Atkin L.R.: Chess 4.5 - The Northwestern University chess programm, in: P.W. Frey (ed.): Chess Skill in Man and Machine, p. 82-118. New York: Springer 1977

Artikelanfang Seitenanfang

Autor & Copyright
Alexander Reinefeld
Paderborner Zentrum für Paralleles Rechnen
Warburger Str. 100, W-4790 Paderborn
ar@uni-paderborn.de

Artikelanfang Seitenanfang