Revision 138918012 of "Bereichstheorie" on dewiki

{{In Bearbeitung|[[Benutzer:Schweigerl|Schweigerl]] ([[Benutzer Diskussion:Schweigerl|Diskussion]]) 23:12, 16. Feb. 2015 (CET)}}
Die '''Bereichstheorie''' ist ein ''Zweig der Mathematik'' und dient auf dem Gebiet der [[Theoretische Informatik|theoretischen Informatik]] zum mathematischen Nachweis der korrekten Funktionalität (Wirkungsweise) von Computerprogrammen [[Formale Semantik|(formale Semantik)]] bzw. zum Nachweis von Programmier- und Spezifikationssprachen [[denotationelle Semantik|(denotationelle Semantik)]]. Die Bereichstheorie kann ebenso als ein Teilgebiet der [[Ordnungstheorie]] betrachtet werden.

Konkret kann man mit Hilfe der Bereichstheorie die Wirkungsweise eines Computerprogrammes im Zusammenhang mit einer formalen Programmiersprache berechnen. Die [[formale Sprache]] dient hierbei als mathematisches Modell für eine echte Programmiersprache. Somit kann die Wirkungsweise eines Computerprogramms mit Hilfe der formalen und denotationellen Semantik beschrieben werden. [[Korrektheitsbeweis|(Korrektheitsbeweise).]]

== Motivation und Formulierung ==  
Die primäre Motivation für die Initiierung der Bereichstheorie erfolgte in den späten 1960er Jahren durch den amerikanischen Mathematiker und Informatiker [[Dana Stewart Scott]], im Zuge seiner Suche nach der denotationellen Semantik (Funktionensemantik) des [[Lambda-Kalkül|Lambda-Kalküls]]. Der Lambda-Kalkül ist ebenso eine formale Sprache zur Untersuchung von Funktionen und beschreibt Funktionsdefinitionen, das definieren formaler Parameter sowie das Auswerten und Einsetzen aktueller Parameter. Strukturell gesehen, kann man bezugnehmend auf das Lambda Kalkül von [[Einfache Funktion|einfachen Funktionen]] ausgehen. Das bedeutet es handelt sich um Funktionen die wiederrum andere Funktionen und deren Eingabeargumente übernehmen. Unter Berücksichtigung dieser einfachen Funktionen erhält man formale Parameter, sogenannte Fixpunktkombinatoren (der bekannteste ist der ''Y-Kombinator''). 

Um nun eine entsprechende Funktionensemantik zu formulieren, könnte man zunächst versuchen, ein Modell für den Lambda-Kalkül , in dem eine tatsächliche Funktion ohne freie Variablen (Lambda-Term) assoziiert ist, zu konstruieren. Man würde dadurch ein sogenanntes Kombinator-Kalkül erhalten. Jedoch wären die Elemente eines solch erhaltenen Kombinator-Kalküls Funktionen aus Funktionen zu Funktionen. Sie können also nicht tatsächlich, wirkliche Funktionen sein, sondern lediglich Teilfunktionen. Folglich würde man nur „teilweise“ oder „unvollständige“ Informationen erhalten.

Dieses Kombinator-Kalkül [[Kombinatorische Logik|(Kombinatorische Logik)]] kann aber in weiterer Folge als alternativer Ansatz zum Lambda-Kalkül gesehen werden.

== Berechnung und Modellierung == 
Um nicht nur ''"teilweise"'' oder ''"unvollständige"'' Informationen zu erhalten und zu einem tatsächlichen Ergebnis zu gelangen muss man bei der Berechnung (Modellierung) folgende Variablen berücksichtigen:

Für jede Definitionsmenge oder den Definitionsbereich [[Domäne|(Domäne)]] einer Berechnung (zb. natürliche Zahlen), wird ein zusätzliches Element, das eine undefinierte Ausgabe darstellt herangezogen. Die Folge ist das Ergebnis einer Berechnung, die niemals endet. Diese Berechnung wird in weiterer Folge mit einer Verallgemeinerung der „kleiner-gleich“ Beziehung (Ordnungsrelation) versehen, wodurch dieses undefinierte Ergebnis das kleinste Element darstellt, die sogenannten [[Halbordnung|„Halbordnungen“.]]

Um daraus die richtige Berechnung abzuleiten, ist es nun notwendig den Funktionen solcher Halbordnungen garantierte Mindestfixpunkte (Beschränkungen) zuzuweisen. Die Teilmenge dieser dadurch erhaltenen Funktionen, zusammen mit einer geeigneten Reihenfolge, bezeichnet man wiederum als "Domäne" im Sinne der Bereichstheorie.

Durch diese Beschränkung auf eine Teilmenge der verfügbaren Funktionen ist es in der Bereichstheorie möglich, Domänen die ihre eigenen Funktionsleerzeichen beinhalten zu erhalten. Also erhalten diese Domänen wiederum eine Funktion, die auf sie selbst angewendet werden kann. Domänen werden immer teilweise angeordnet. Diese Reihenfolge stellt eine Hierarchie von Informationen oder Wissen dar. Je höher ein Element innerhalb dieser Hierarchie ist, desto spezifischer ist es und desto mehr Informationen enthält es. In der Hierarchie unten angesiedelte Elemente repräsentieren unvollständiges Wissen oder unvollständige Zwischenergebnisse. 

Diese Berechnung wird in weiterer Folge durch das Anlegen gleichbleibender Funktionen auf Elemente der Domäne solange wiederholt, bis ein fester Punkt erreicht ist. Das Erreichen dieses festen Punktes bedeutet das Ergebnis (Endbearbeitung) einer solchen Berechnung.

== Definitionen und Konkretisierung ==
[[File:Gerichtete Teilmengen Bereichstheorie.jpg|thumb|Gerichtete Teilmengen zur Berechstheorie;]]
Die Bereichstheorie befasst sich mit Halbordnungen um die Berechnung einer Domäne zu modellieren. Das Ziel besteht darin, die Elemente einer solchen Reihenfolge wie Informationsteile oder Teilergebnisse einer Berechnung so zu interpretieren, das die in der höheren Hierarchie angesiedelten Informationen mit den darunterliegenden Elementen einen gleichbleibenden Weg aufweisen. 
  
Eine zentrale Rolle der Bereichstheorie spielt die Teilmenge einer Domäne. Das bedeutet, es müssen in der betreffenden Teilmenge jeweils zwei Elemente eine Obergrenze aufweisen, die für sich selbst wieder ein Element dieser Teilmenge darstellen. Bezugnehmend auf Domänen bedeutet dies, dass die oben angeführten Teilmengen innerhalb der höherwertigen Teilmenge konsequent durch ein anderes Element in eben dieser Teilmenge erweitert werden.

Diese Vorgangsweise kann mit dem Begriff einer [[Konvergenz|konvergenten Folge]] verglichen werden, wobei jedes Element spezifischer ist, als das Vorhergehende.

Als Alternative zur Bereichstheorie stehen die „metrischen Räume“. Die Abfolgen (Sequenzen) dieser metrischen Räume stehen in vielerlei Hinsicht analog zu den Sequenzen der Bereichstheorie. Von der Grundidee der durch die Bereichstheorie erhaltenen teilweisen Ergebnisse, (unvollständiges Wissen), wird aber auch eine andere Eigenschaft abgeleitet. Die Existenz eines kleinsten Elements. Ein solches Element enthält keine Informationen, dient aber als „Anfang“ oder „Ort“, an dem die meisten Berechnungen beginnen, bzw. als Ausgangspunkt einer Berechnung.

== Domänenfunktionen == 
Domänen beinhalten Funktionen wie Eingänge von Berechnungen und Ausgänge von selbigen. Man geht aufgrund dieser Feststellung davon aus, dass wenn der Informationsgehalt des Eingangs erweitert wird, ebenso der Ausgang einer Funktion mehr Informationen enthält. Formal bedeutet dies, dass eine Funktion monoton sein soll. 

Eine vollständige Halbordnung ist eine Halbordnung mit einem kleinsten Element und der Eigenschaft, dass jede Teilmenge, die eine aufsteigende Kette bildet, ein „Oberstes“ [[Supremum|(Supremum)]] besitzt. Zu beachten ist jedoch, dass eine solche Funktion ebenso monoton zu sein hat. 
Diese Eigenschaften sind auch in der sogenannten [[Scott-Topologie]] zu finden.
 
''Die Bereichstheorie stellt einen rein logischen Ansatz zur Modellierung einer Struktur von Informationen und Zuständen dar.'' Aufgrund dieses Ansatzes wird angenommen, dass etwas mehr Informationen enthält, aber die Menge an zusätzlichen Informationen eigentlich nicht angegeben ist. 
Dennoch stellen bestimmte Situationen eine Notwendigkeit dar, um Elemente, die in einem gewissen Sinne einen viel einfacheren oder viel unvollständigeren Zustand von Informationen beinhalten, zu erhalten.

=== Grundlagen von Domänen ===  
Im Allgemeinen beschränkt man sich auf eine bestimmte Teilmenge von Elementen die als immer ausreichend für alle anderen Elemente als kleinste obere Beschränkung anzunehmen ist. Man definiert folglich die Basis dieser Gruppe von mathematischen Ungleichungen (Korrelationsungleichung) sogenannte [[Posets|„Posets“]] , als eine Teilmenge. Es wird diese Teilmenge derart angeglichen, dass diese Menge der Elemente wiederum, die weit darunter stehen, eine obere Schranke, die kleiner als alle anderen oberen Schranken ist, erhalten. Durch diese Angleichung erhält man das „Oberste“ (Supremum).

=== Suprema von Mengen === 
Das Supremum („Oberstes“) einer Menge ist, anschaulich gesprochen, ein Element, welches „über“ allen oder „jenseits“ (oberhalb) aller anderen Elemente liegt. Der Ausdruck „über den anderen“ soll andeuten, dass das Supremum nicht das größte Element „unter den anderen“ sein muss, sondern durchaus auch außerhalb („jenseits“) der Menge liegen kann. Das Supremum bezeichnet also ein „unmittelbar Darüberliegendes“. Elemente, die zwar über allen Elementen einer Menge liegen, aber nicht zwingend, heißen obere Schranken. Damit ergibt sich die Definition des Supremums als kleinste obere Schranke einer Menge.

== Besondere Arten von Domänen == 
Die einfache Art einer Domäne wird als elementare oder flache Domäne bezeichnet. Diese besteht aus einem Satz von unvergleichbaren Elementen, die insgesamt mit einem einzigen "unteren" Element betrachtet, kleiner ist, als alle anderen Elemente. Eine weitere Art von Domänen sind kontinuierliche Posets und algebraische Posets. Bei gegebener Vollständigkeit erhält man kontinuierliche Gitter und algebraische Gitter.
 
Die historischen Klassen von Posets, die sogenannten Scott Domains, waren die ersten Strukturen in der Bereichstheorie, die untersucht wurden. Weitere Klassen von Domänen sind SFP-Domänen und L-Domänen.
 
Alle diese Klassen von Domänen können, unter Verwendung ihrer jeweiligen Funktionen, wieder in verschiedene Kategorien unterteilt werden. In monotone, Scott-kontinuierliche oder sogar spezialisierte Morphismen [[Kategorientheorie|(Kategorientheorie)]].

Letztendlich ist zu beachten, dass der Begriff Domäne selbst nicht genau definiert ist und somit nur als Abkürzung bzw. formale Definition verwendet wird.

== Approximationsordnung == 
Als eine aufwendigere Methode zur Modellierung gilt die sogenannte Approximationsordnung (Annäherungsordnung).  

Ein Element '''x''' ist weit unter dem Element '''y''', wenn für jede gerichtete Menge das Supremum '''D''' steht,
:<math> y \sqsubseteq \sup D </math>,
ergibt das ein Element d in D, so dass gilt
:<math> x \sqsubseteq d </math>. 
Man kann auch sagen, das sich x an y annähert und schreibt:
:<math> x \ll y </math>.
Das bedeutet dass,
:<math> x \sqsubseteq y </math>,
{ y} eine gerichtete Menge ist. 

Das Supremum der Kette ist die Menge aller natürlichen Zahlen '''N''' und zeigt, dass keine unendliche Menge '''N''' approximieren (nähren) kann.

== Siehe auch ==
* [[Scott-Topologie]] - eine Topologie, die sich aus der Halbordnung auf einer halbgeordneten Mengen ergibt
*  [[Kategorientheorie]] - Die Kategorientheorie lässt sich, ähnlich wie die universelle Algebra, als allgemeine Theorie mathematischer Strukturen auffassen 

== Weblinks ==
* [http://www.uni-siegen.de/fb6/tcs/team/spreen ''Fachgruppe für Theoretische Informatik - Universität Siegen''] - 16.Februar 2015 (deutsch)
* [http://homepages.inf.ed.ac.uk/als/Research/topological-domain-theory.html ''Topological Domain Theory-Übersicht''] - 16.Februar 2015 (englisch)
* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.903 ''Domain Theory (1994) by Samson Abramsky''] - 16.Februar 2015 (englisch)
* [http://www.cs.bham.ac.uk/~axj/pub/papers/handy1.pdf ''Domain Theory - Corrected and expanded version''] - 16.Februar 2015 (PDF, 1.06 MB)

[[Kategorie:Mathematischer Grundbegriff]]
[[Kategorie:Ordnungstheorie]]