of 33 /33
2. Mathematische und informatische Grundlagen Mathematische Grundlagen wichtig für Modellierung der Realität und für die Informationsverarbeitung Grundlagen der • Mengenlehre Formalen Logik • Graphentheorie

2. Mathematische und informatische Grundlagen Mathematische Grundlagen wichtig für Modellierung der Realität und für die Informationsverarbeitung Grundlagen

Embed Size (px)

Text of 2. Mathematische und informatische Grundlagen Mathematische Grundlagen wichtig für Modellierung der...

  • 2. Mathematische und informatische GrundlagenMathematische Grundlagen wichtig fr Modellierung der Realitt und fr die Informationsverarbeitung

    Grundlagen der MengenlehreFormalen LogikGraphentheorie

  • 2.1 Mengentheoretische Grundbegriffe Mengen zur Bildung und Selektion von Geoobjektklassen

    Unter einer Menge A versteht man eine Zusammenfassung von bestimmten wohlunterschiedenen Objekten unserer Anschauung oder unseres Denkens zu einem Ganzen; diese Objekte werden Elemente a der Menge A genannt. Schreibweise: a A "a ist Element der Menge A" b A "b ist nicht Element der Menge A"

  • Die Festlegung einer Menge A kann erfolgen explizit durch Angabe aller Elemente, z.B. M = {a, b,..., z}; dies ist nur bei einer endlich grossen Menge mglich.implizit durch Angabe eines Prdikates, d.h. einer charakteristischen Eigenschaft aller Elemente dieser Menge, z.B. M = { x x Z und x > 0; Z = Menge der ganzen Zahlen } Auf diese Weise kann man auch unendlich grosse Mengen definieren.Die Anzahl M der Elemente einer Menge Mheisst Kardinalitt von M.

  • Beziehungen zwischen Mengen

    Gleichheit: A = B jedes Element von A ist Element von B und umgekehrt; anderenfalls ist A B

    Teilmenge: A B (x A x B) fr alle x A A B A B und A B (echte Teilmenge) Transitivitt: A B und B C A C

    A = B

  • Spezielle Mengen

    Leere Menge: = { }Potenzmenge:P(A) = { X X A } Menge aller Teilmengen von A Beispiel: A={1,2} P(A)={, {1}, {2}, {1,2}}

    Produktmenge (Kartesisches Produkt): A B := {(x,y) x A und y B} Menge aller geordneten Paare (a,b) mit a A und b B Allgemein: ABC usw.

  • Mengenalgebraische Verknpfungen

    Durchschnitt: A B = { x x A und x B} A und B sind disjunkt, wenn A B = Schnittmenge

    Vereinigung: A B = { x x A oder auch x B} Vereinigungsmenge

    Differenzmenge: A \ B = { x x A und x B} "A ohne B"

  • Einige Gesetze ('Rechenregeln') der Mengenalgebra

    Kommutativitt:A B = B A (gilt ebenso fr )Assoziativitt:(A B) C = A (B C) (gilt ebenso fr )

    Distributivitt:A (B C) = (A B) (A C); A (B C) = (A B) (A C)

  • Anwendungsbeispiele

    Zeige alle Biotope, die hchste Schutzprioritt haben

    Zeige alle Straen, die verkehrsberuhigt aber nicht in Ortschaften liegen Zeige alle Waldflchen und Grnflchen in Berlin.

    Zeige alle Waldflche ohne geschtzte die Waldflchen

  • Relationen

    Unter einer Relation R einer Menge M versteht man die Beziehung, die zwischen je zwei Elementen von M besteht oder nicht besteht. Z.B. a

  • Beispiel 1: "
  • Relationstypen quivalenzrelation Beispiele: g, h sind parallele Geraden A, B haben selbe Nationlitt a-d = b-c sind differenzgleiche Paare

    Mittels quivalenzrelationen kann man Partitionen (Klasseneinteilungen) in einer Menge bilden.

  • Ordnungsrelation z.B. a < b. Ordnungsrelationen sind z.B. fr das grenmige Sortieren von Daten wichtig.

  • AnwendungsbeispieleSortiere alle Grundstcke entsprechend ihrer Gre / ihres Wertes

    Sortiere die Lnder der Erde nach ihren Ausgaben fr Bildung im Verhltnis zu Rstungsausgaben

    Gruppiere die Gewsser entsprechend ihrer Gewssergte

  • 2.2 Grundbegriffe der formalen Logik

    Hauptaufgabe der formalen Logik ist die Unter-suchung des formalen Denkens und Schlieens.

    Unter einer Aussage versteht man ein natrlich-sprachiges Konstrukt, dem man einen der beiden Wahrheitswerte WAHR (W) oder FALSCH (F) zuordnen kann.

  • Bei der logischen Bewertung einer Aussage kommt es nicht auf die Syntax sondern auf die Semantik an. Die Bewertung erfolgt nach dem Prinzip entweder W oder F.

    Eine Verallgemeinerung dieser zweiwertigen Logik stellt die fuzzy-logic dar, nach der Aussagen auch "etwas falsch" und zugleich "etwas wahr" sein drfen; Sie spielt heute eine wichtige Rolle bei Entscheidungsproblemen (z.B. bei der Zuordnung von Objekten zu Klassen).

  • Beispiele"Die Lufttemperatur liegt unterhalb von Null Grad Celsius" ist eine Aussage, die W oder F sein kann.

    "Regnet es immer noch?" ist keine Aussage.

  • Enthlt ein sprachliches Konstrukt anstelle eines konkreten Subjektes nur einen Platzhalter (Variable), so handelt es sich um eine Aussageform.

    Beispiel: "X < 0 C" ist eine Aussageform, die keinen Wahrheitswert besitzt.

    Erst nachdem man die Variable X an ein konkretes Subjekt gebunden hat, entsteht eine wahre/falsche Aussage.

    Beispiel: "Die Lufttemperatur ist < 0 C" kann W oder F sein.

  • Von besonderer Bedeutung sind Aussageformen, die bei jeder Bindung der Variablen eine wahre Aussage ergeben = Tautologien.

    Beispiel: "X < 0C oder X > 0C oder X = 0 C"

  • Aussagenverknpfungen

    In der Umgangssprache werden Aussagen auf vielfltige Weise miteinander zu komplexeren Aussagen verknpft.

    Beispiel: "Wenn die Lufttemperatur unter 0C liegt und Niederschlag fllt, dann ist dies Schnee"

    In der formalen Logik begngt man sich mit einigen wenigen, aber dafr eindeutig bestimmten Verknpfungsoperationen (Junktoren):

  • VerknpfungsoperationenVerknpfungBenennungnichtNegationundKonjunktionoderAlternativewenn...,soImplikationgenau dann..., wennuquivalenz

  • Implikationen sind eine wichtige Grundlage fr die Schlussregeln in der Wissensverarbeitung. Eine Schlussregel ist eine Vorschrift, die angibt, wie man aus wahren Aussagen neue, ebenfalls wahre Aussagen gewinnen kann.

    Beispiel:wenn a < b, so ist 2a < 2bWenn Sonnabend ist, will ich frische Brtchen essen. Wenn ich frsiche Brtschen essen will, mu ich frh zum Bcker. Also: Wenn Samstag ist, mu ich frh zum Bcker.

  • Um die reale Welt besser modellieren zu knnen, bentigt man neben solchen Formeln der Aussagenlogik noch weitere Operatoren, z.B.: All-Quantor "x: Fr alle x gilt die Aussage P(x)Existenz-Quantor $x: Es existiert mindestens ein x, fr das P(x) gilt

  • 2.3 Grundbegriffe der Graphentheorie Die Graphentheorie ist eine mathematische Theorie, durch die sich komplexe Sachverhalte sowie rumliche Strukturen und Beziehungen leichter visualisieren und analysieren lassen.

    Bedeutung fr die Geoinformatik z.B. Abbildung von Straen-, Kommunikations-netzen

  • Ein Graph besteht aus Kanten und Knoten, wobei eine Kante durch zwei Knoten gebildet wird.

    Ein Graph ist eine Zusammenfassung zweier Mengen, der Menge X der Knotenpunkte x und der Menge U der Kanten u sowie einer auf U erklrten Funktion f, der Inzidenzfunktion (Inzidenz=Punkt liegt auf Geraden). Diese ordnet jeder Kante u U genau ein geordnetes oder ein ungeordnetes Paar von Knotenpunkten zu; dementsprechend unterscheidet man gerichtete bzw. ungerichtete Graphen.

  • Zwei Knoten heissen adjazent (benachbart), wenn sie zu einer gemeinsamen Kante gehren; diese beiden Knoten heissen dann inzident zur betreffenden Kante.

    Beispiel zur Notation: G = (V, E) mit V = {v1, v2, v3} und E = {e1, e2, e3}, wobei e1 = (v1, v2); e2 = (v2, v3); e3 = (v3, v1)

  • Eine einfache (aber redundante) Form der DV-adquaten Darstellung von Graphen mit n Knoten ist die Adjazenzliste

    Beispiel: Adjazentliste fr abgebildten Graphen: { [v1, v2, v3], [v2, v3, v1], [v3, v1, v2] }

    v = vertice (Knoten)e = edge (Kante)

  • Typen von Graphenvollstndiger Graph wenn alle Knotenpaare adjazent sind

    zusammenhngender Graph wenn fr je zwei verschiedene Knoten stets ein Weg von x nach y existiert. Gerichteter Graph wenn alle Kanten aus geordneten Knoten-Paaren bestehen, d.h. mit Vorgnger- Knoten und Nachfolger-Knoten.

  • Typen von Graphen II Baum-Graph ein zusammenhngender, schleifenloser, gerichteter Graph. WurzelbaumBinrbaum

  • Typen von Graphen IIIWurzelbaum ist ein Baum, der genau einen Knoten ohne Vorgnger-Knoten besitzt; dieser heisst die Wurzel des Baumes. Alle anderen Knoten besitzen genau einen Vorgnger-Knoten ('Vater'). Ein Knoten, der keinen Nachfolger-Knoten ('Sohn') besitzt, heisst ein Blatt. In der Informatik werden Bume stets mit der Wurzel nach oben dargestellt.

  • Typen von Graphen IVBinrbaum, wenn jeder Knoten hchstens zwei Shne besitzt und diese in linken und rechten Sohn unterschieden werden. Binrbume spielen eine sehr wichtige Rolle z.B. bei Suchvorgngen.

  • AnwendungsbeispieleModellierung von Straennetzen fr KFZ-NavigationModellierung von FlusystemenModellierung von Versorgungsnetzen (Wasser, Gas, Strom)Berechnung des Handlungsreisenden-Problem (Wegoptimierung)

  • Aufgaben Aufgabe 1: Verdeutlichen Sie sich am Beispiel von Flu-Einzugsgebieten die Teilmengen-Beziehung und die Transitivitt dieser Beziehung.

    Aufgabe 2: Auf einem Kartenblatt wird die Menge P aller Punkte innerhalb eines Untersuchungsgebietes G betrachtet. Beschreiben Sie formal mit Hilfe des Begriffes der Produktmenge die Menge aller mglichen (horizontalen) Untersuchungsprofile, die nicht die Lnge Null besitzen.

  • Aufgabe 3: Autobahnabfahrt B liegt zwischen Abfahrt A und C. Schreiben Sie dies formal als Relation Aufgabe 4: Beschreiben Sie mit Hilfe graphentheoretischer Grundbegriffe ein Fliegewsser-System in einem Einzugsgebiet.