Grundlagen der Modellierung und Simulation

357 Tage zuvor

Während des Lernens für die Veranstaltung Grundlagen der Modellierung und Simulation (Einführung in Computational Engineering) habe ich eine recht ausführliche Zusammenfassung erstellt, die ich hiermit der Öffentlichkeit zur Verfügung stellen möchte. Die Inhalte sind den Folien zur Veranstaltung entnommen. Enthalten sind unter anderem die Themen

Differentialgleichungen
- Gewöhnliche und partielle Differentialgleichungen
- Transformation auf 1. Ordnung, Autonomisierung
- Lösbarkeit
- Variation der Konstanten
Grundbegriffe der Simulation
Diskrete Modellierung und Simulation
- Ereignisgesteuerte Simulation
- Petrinetze
Zeitkontinuierliche Modellierung und Simulation
- Allgemeine, lineare Systemdynamik
- Linearisierung um Ruhelagen
- Steife Systeme
- …
Numerische Simulation
- Gleitpunktzahlen
- Numerische Lösung nichtlinearer Differentialgleichungen
  - Euler-Verfahren (explizit/implizit)
  - Heun-Verfahren
Teilschritte einer Simulationsstudie
Modulare Modellbildung

CE-Zusammenfassung [1.19MB]
(358 mal heruntergeladen)

Changelog:

Erweiterung des Modellbegriffs (Auszug aus Probeklausur)
Ergänzung zur mathematischen Modellierung von Petrinetzen
Kleine Typographiefehler behoben
Kleine Ergänzung zur Relaxationsmatrix beim Fixpunktverfahren; Zeichensetzungsfehler behoben

— Dominic Scheurer

Wie finden Sie diesen Artikel?

Currently 7.67/10
1
2
3
4
5
6
7
8
9
10

Bewertung: 7.7/10 (9 votes)

Modellierung und Simulation, Mathematik

Kommentare

Bellman-Algorithmus

536 Tage zuvor

Der Bellman-Algorithmus ist ein (akademischer) Algorithmus zur Erstellung eines optimalen binären Suchbaums mit gewichteten Knoten. Dabei geht der Algorithmus nach einem Bottom-Up-Schema vor, um die vorhandenen Knoten in immer größere Intervalle zu gruppieren, bis schließlich der ideale Suchbaum vorliegt.

Der Algorithmus wird in den Folien zur Vorlesung “Grundlagen der Informatik 2” recht ausführlich, meiner Meinung nach aber nicht besonders verständlich behandelt, weshalb ich hier einen kleinen Kommentar dazu abgeben möchte. Nebenbei dient Wikipedia bei diesem Thema nur bedingt als Quelle – der Artikel in der deutschen Wikipedia¹ ist recht karg und theoretisch, und in der englischen Ausgabe existiert das Thema nicht einmal.

Also hier ein Beispiel:
Gegeben sei eine Menge fünf mit Gewichtungen versehener Knoten, die einer Ordnung unterliegen (hier werden die Namen der Knoten, 1 bis 5, direkt zur Herstellung der Ordnung herangezogen). Der Algorithmus wird nun Intervalle der Größe 1 bis 5 bilden (sukzessive) und jeweils den optimalen Teilbaum für jedes Intervall finden.

Für den Fall 1 ist dies Trivial: Jeder Knoten ist für sich der ideale Teilbaum.

Beim zweiten Durchlauf werden die Intervalle [1,2], [2,3] und so weiter betrachtet. Für jedes Intervall wird nun jeder enthaltene Knoten als Wurzel probiert. Dabei wird immer (auch für die folgenden Intervallgrößen) das Gewicht des jeweiligen Teilbaums berechnet als “Gewicht des linken Teilbaums + Gewicht des rechten Teilbaums + Summe der Einzelgewichte der enthaltenen Knoten”, im Fall des Intervalls [2,3] also für den Knoten zwei als Wurzel 0 (Gewicht des linken Teilbaums: Dieser ist leer) + Gewicht von 3 (Rechter Teilbaum) + Gewichte von 2 und 3 (Gewichte der Einzelknoten). Das entstehende Gewicht wird nun dem Gewicht der zweiten Option, nämlich des Baumes mit Knoten 3 als Wurzel, gegenüber gestellt; die “leichtere” Lösung wird gewählt (und gemerkt).

Interessant wird es vor allem ab der Intervallgröße 3: Hier liegen nämlich schon optimale Teilbäume der Größe 2 vor und können in die Überlegung mit einbezogen werden. Betrachten wir das Intervall [3,4,5]. Für jeden Knoten als Wurzel kommt nun ganz genau je ein Baum als rechter bzw. linker Unterbaum in Frage (und hier, finde ich, fehlt die Erklärung in den Vorlesungsfolien der Veranstaltung GdI2). Eine tabellarische Veranschaulichung:

Wurzelknoten	Linker Teilbaum	Rechter Teilbaum
3	Leer	Teilbaum aus den Knoten 4 und 5, der im letzten Schritt gemerkt wurde
4	Knoten 3	Knoten 5
5	Teilbaum aus den Knoten 3 und 4, der im letzten Schritt gemerkt wurde	Leer

Ich hoffe, das das Muster heraussticht: Für jede “Wurzelknoten-Option” muss als linker Teilbaum derjenige gewählt werden, der die Knoten links (in der geordneten Liste der Knoten) der jeweiligen Wurzel beinhaltet, dementsprechend wird auch der rechte Teilbaum gebildet. Dabei können einer oder beide Unterbäume leer sein, falls sich die aktuelle Wurzel am Rand des aktuellen Intervalls befindet.

Der Algorithmus terminiert, sobald er den Teilbaum der Größe n (hier: 5) gebildet hat. Nebenbei läuft der Bellman-Algorithmus in kubischer Komplexität: $Mathematische Formel: O(n) = n^3$ ; dies lässt sich erkennen an der Verschachtelung dreier for-Schleifen (Eine Schleife zum Durchlaufen der Intervallgrößen, eine für das Bilden der Intervalle und eine für das Erproben jedes enthaltenen Knotens eines Intervalls als Wurzel).

¹ http://de.wikipedia.org/wiki/Bellman-Algorithmus

— Dominic Scheurer

Wie finden Sie diesen Artikel?

Currently 8.00/10
1
2
3
4
5
6
7
8
9
10

Bewertung: 8.0/10 (15 votes)

Algorithmen, Graphen und Bäume

Kommentare

Mathematische Formeln in Textpattern

540 Tage zuvor

Für meinen letzten Artikel über die geometrische Interpretation des Vektor- und Skalarprodukts wollte ich nette, in Grafiken gerenderte Matheformeln einbinden. Ich stand nun vor dem Problem, dass ich

Keinen Shell-Zugriff auf meinen Webspace und
Kein LaTeX installiert habe

Die verfügbaren Plugins für Textpattern (zumindest die, die ich finden konnte), setzten alle ein funktionierendes LaTeX-System voraus. Ich habe mir nun ein eigenes, kleines Plugin zur Darstellung von Formeln ohne LaTeX geschrieben, welches auf der LaTeX-Rendering-Software Mimetex basiert.

Mittels dieses Plugins und der Datei mimetex.cgi ist es möglich, über ein einfaches Textpattern-Tag Formeln darzustellen, wie z.B. im folgenden Beispiel:
<txp:math_env>x^2 = 0</txp:math_env>

Ergebnis:
$Mathematische Formel: x^2 = 0$

Installation

Die Installation verläuft denkbar einfach:

Herunterladen einer kompilierten mimetex.cgi-Datei¹ oder Source-Code zum Selbstkompilieren
Speichern der mimetex.cgi irgendwo auf dem eigenen Server
Kopieren des Base64-kodieren Plugin-Inhalts von math_env.php in das Eingabefeld im Textpattern-Administrations-Interface unter Administration -> Plugins und Bestätigung durch “Hochladen”
Ändern des Links auf mimetex.cgi durch Editieren des Plugins (“Bearbeiten”) in der Plugin-Administrations-Oberfläche
Aktivieren des Plugins durch Klick auf “Nein” in der entsprechenden Zeile in der Plugin-Administrations-Oberfläche

Dies sollte es gewesen sein – von nun an lassen sich Formeln einfach darstellen, selbst ohne LaTeX und root-Shell.

¹ Mimetex Website mit Source Code und kompilierten Versionen

— Dominic Scheurer

Wie finden Sie diesen Artikel?

Currently 9.57/10
1
2
3
4
5
6
7
8
9
10

Bewertung: 9.6/10 (7 votes)

Web-Design, Content-Managment-Systeme

Kommentare

Geometrische Interpretation des Vektor- und Skalarprodukts

542 Tage zuvor

Mal wieder am Lernen – diesmal “Mathematik 2 für Informatiker”, fällt mir auf, dass bei dem zwar ausführlichen und sogar mit Beispielen versehenen Vorlesungsskript¹ leider schon bei unkomplizierten Konstrukten die geometrische Beziehung verloren geht. Beim Nachvollziehen des Spatprodukts kam ich rund 10 Minuten ins Grübeln bis mir die geometrische Interpretation des Skalarprodukts klar wurde. Daher hier ein kleiner Hinweis, für Menschen die manchmal nach dem roten Faden suchen ;-)

Vektorprodukt

Die geometrische Interpretation des Vektorprodukts ist noch recht einfach nachzuvollziehen, da das Vektorprodukt im Skript über diese definiert wird²:

Das Vektorprodukt zweier Vektoren $Mathematische Formel: \vec{u}$ und $Mathematische Formel: \vec{v}$ liefert einen senkrecht auf die durch diese Vektoren aufgespannte Ebene stehenden Vektor, dessen Länge (Betrag) der Fläche des durch $Mathematische Formel: \vec{u}$ und $Mathematische Formel: \vec{v}$ aufgespannten Parallelogramms entspricht. Kurz: “Willst du Fläche von Parallelogramm, machstu Vektorprodukt und Betrag” ;-)
Nebenbei bilden $Mathematische Formel: \vec{u}$ , $Mathematische Formel: \vec{v}$ und $Mathematische Formel: \vec{u}\times\vec{v}$ ein Rechtssystem, damit kann man zur Ermittlung der Richtung des beim Vektorprodukts resultierenden Vektors die Drei-Finger-Regel der rechten Hand³ anwenden.

Skalarprodukt

Bei der Einführung des Skalarprodukts vernachlässigt Prof. Streicher die bodenständige geometrische Beziehung komplett. Hier war auch bei mir der Knackpunkt. Dabei ist es recht einfach:

Das Skalarprodukt zweier Vektoren $Mathematische Formel: \vec{u}$ und $Mathematische Formel: \vec{v}$ liefert das Produkt (einen Skalar, also eine Zahl) aus der Länge des einen Vektors und der Länge der Projektion des zweiten Vektors auf den Ersten.

Damit wird das Skalarprodukt besonders nützlich z.B. für die Abstandsbestimmung zweier Geraden (ein Beispiel, das auch im Skript aufgeführt wird, allerdings ohne nähere Erläuterung): Hat man einen Einheits-Normalenvektor auf die Richtungsvektoren der beiden Geraden⁴, wird die Verbindung zwischen den beiden Stützpunkten mittels Skalarprodukt auf diesen projeziert – und schon hat man die Entfernung der Geraden zueinander⁵.

Spatprodukt

Nun also zum Spatprodukt. Dieses wird definiert über $Mathematische Formel: \left|\vec{u},\vec{v},\vec{w}\right|=\vec{u}\cdot\left(\vec{v}\times\vec{w}\right)=\left|F_{\vec{v},\vec{w}}\right|\cdot\vec{n}\cdot\vec{u}$ . Einfacher ausgedrückt: Das Volumen diese Spats ergibt sich aus dem Produkt aus Grundflächt und Höhe. $Mathematische Formel: \left|F_{\vec{v},\vec{w}}\right|$ ist hier die Grundfläche, nämlich die Fläche des durch die Vektoren $Mathematische Formel: \vec{v}$ und $Mathematische Formel: \vec{w}$ aufgespannten Parallelogramms. $Mathematische Formel: \vec{n}\cdot\vec{u}$ ist die Projektion der durch den dritten Vektor, $Mathematische Formel: \vec{u}$ , gegebenen Kante des Spats auf den Einheits-Normalenvektor der Grundfläche, $Mathematische Formel: \vec{n}$ . $Mathematische Formel: \vec{n}\cdot\vec{u}$ ist also die Höhe des Spats!

Und hier sollte sich der Kreis schließen, und Spat und Parallelogramm ebenso. Ich hoffe, der Text hier ist einigermaßen verständlich. Vielleicht werde ich demnächst, falls ich Zeit habe, ein paar Grafiken hinzufügen.

Ich finde es auf jeden Fall wichtig, dass man verstanden hat, wie das Spatprodukt zustande kommt, denn dann hat man die geometrische Beziehung zu Vektor- und Skalarprodukt nicht verloren, und damit nicht zu den beiden wichtigsten Operatoren der analytischen Geometrie.

¹ Streicher, Thomas: “Mathematik für Informatiker”. Skript zur Veranstaltung

² Seite 111 im Skript

³ http://de.wikipedia.org/wiki/Drei-Finger-Regel

⁴ Erhält man durch $Mathematische Formel: \frac{\vec{u}\times\vec{v}}{\left|\vec{u}\times\vec{v}\right|}$ , wobei $Mathematische Formel: \vec{u}$ und $Mathematische Formel: \vec{v}$ Richtungsvektoren sind.

⁵ Die komplette Formel findet sich im Skript auf Seite 114.

— Dominic Scheurer

Wie finden Sie diesen Artikel?

Currently 9.00/10
1
2
3
4
5
6
7
8
9
10

Bewertung: 9.0/10 (3 votes)

Mathematik, Lineare Algebra & Analytische Geometrie

Kommentare

Zusammenfassung Computer Microsystems

547 Tage zuvor

Momentan bin ich größtenteils mit dem Lernen für die Klausur in der Veranstaltung Einführung in Computer Microsystems beschäftigt. Im Zuge dessen habe ich eine Zusammenfassung des Stoffs erstellt, die ich hiermit zum Download zur Verfügung stelle:

CMS-Zusammenfassung [303.76KB]
(616 mal heruntergeladen)

Enthaltene Themen sind unter Anderem:

Hardware-Entwurf, Methoden, Systematischer Entwurf
Verilog HDL
Automaten
Synthese
Simulation
Speicher
Logikoptimierung
Statecharts

Wenn es euch gefällt, hinterlasst einen (netten ;-) ) Kommentar!

Links
Thema im CMS-Forum

Changelog

Fehlerkorrektur. Seite 13, Definition Minterm: “KNF” durch “DNF” ersetzt. 24. August, 21:00
Ergänzung. Seite 14, beispielhaftes KV-Diagramm (Grafik) mit Erläuterungen hinzugefügt. 25. August, 16:07
Ergänzung. Seite 15, Verbesserung der Erläuterungen zur Quine-McCluskey-Methode. 25. August, 16:44
Fehlerkorrektur. Seite 14, KV-Diagramm (Graphik): Fehlerhafte Zellenbeschriftung korrigiert (3 -> 13). 25. August, 17:09
Fehlerkorrektur. Seite 5, “Kombinatorische Logik”: Ein un vollständiges ~~und~~ oder lokales, … 25. August, 19:25

— Dominic Scheurer

Wie finden Sie diesen Artikel?

Currently 9.00/10
1
2
3
4
5
6
7
8
9
10

Bewertung: 9.0/10 (3 votes)

Hardware-Design, Verilog

Kommentare [2]

« älter

software-entwicklung und programmierung :: dominic scheurer :: webhome

Grundlagen der Modellierung und Simulation

Bellman-Algorithmus

Mathematische Formeln in Textpattern

Installation

Geometrische Interpretation des Vektor- und Skalarprodukts

Vektorprodukt

Skalarprodukt

Spatprodukt

Zusammenfassung Computer Micro­systems

Zusammenfassung Computer Microsystems