November « 2009 « brianp.de

Archiv für November 2009

Scheme Kurs – Teil 7: IO

Samstag, 28. November 2009

Bis jetzt habe ich noch nichts zur Ein- und Ausgabe von Daten in Scheme gesagt. Simple Ausgaben kann man realisieren indem man einfach die Variable hinschreibt, ohne sie auf eine Funktion anzuwenden.

(define hallo-welt "Hallo Welt!")
hallo-welt

Es gibt aber auch eine Menge Funktionen mit denen man Ausgaben bewältigen kann. Darunter ist das aus C/C++ bekannte printf.
Ich möchte nicht näher auf die Ausgabefunktionen eingehen, da sie keine große Schwierigkeit darstellen. Alle nötigen Informationen dazu findet man unter:
http://download.plt-scheme.org/doc/html/reference/Writing.html

Das gleiche gilt für die Eingabe von Daten. Alle nötigen Informationen findet man hier:
http://download.plt-scheme.org/doc/html/reference/Reading.html

Ein kleines Beispiel zum Abschluss:

(printf "Bitte geben Sie Ihren Name ein: ")
(define name (read))
(printf "Hallo ~v" name)

Schlagworte:Ausgabe, EA, Eingabe, IO, Scheme
Veröffentlicht in GdI1, Scheme | Keine Kommentare »

Scheme Kurs – Teil 6: set!

Samstag, 28. November 2009

Bis jetzt haben wir in Scheme nur mit Konstanten gearbeitet, die man einmal mit einem Wert belegen kann.
Mit set! kann man aber den Wert einer Variable ändern. Davor muss man die Variable aber wie eine Konstante mit define erstellen, dass heißt, wir haben bis jetzt auch schon mit Variablen gearbeitet, nur konnten wir deren Wert noch nicht ändern.

(define i 0)
(set! i 1)
(set! i (+ i 1))

Die Variable i hat nach der ersten Zeile den Wert 0, da sie mit define mit dem Wert 0 definiert wird.
Nach Zeile 2 ist der Wert von i 1, da wir es explizit mit set! festlegen.
In Zeile 3 nutzen brechnen wir den neuen Wert von i mit dem alten (oder bisherigem) Wert von i. i ist also nach dieser Zeile 2.

Das Ausrufezeichen ist eine Scheme Konvention. Man muss sich nicht daran halten, aber es ist extrem sinnvoll. Denn so kann jeder sofort erkennen dass eine Funktion eine oder mehrere Zuweisungen vornimmt.
Wenn man also eine Funktion schreibt, die einen Parameter verändert, dann sollte man an den Funktionsname ein Ausrufezeichen anhängen.

Schlagworte:!, define, Konstante, Konvention, Scheme, set!, Variable
Veröffentlicht in GdI1, Scheme | Keine Kommentare »

Apache2 mit SSL unter Debian 5

Freitag, 20. November 2009

Nach längeren Probieren habe ich endlich ein HowTo gefunden, das aus funktioniert. Es beschreibt wie man Apache2 so konfiguriert, dass es SSL unterstützt. In der Beschreibung werden auch gleich noch die Zertifikate generiert.
Link: http://venthur.de/Linux/ApacheSSLHOWTO

Schlagworte:Apache, Debian, https, Linux, SSL
Veröffentlicht in Internet, Linux | Keine Kommentare »

Online Funktionsplotter

Donnerstag, 19. November 2009

Der Funktionsplotter von http://www.mathe-fa.de/de ist sehr gelungen. Besonders gut finde ich, das das Ergebnis vom Server erzeugt wird und als Bild an an den Browser geschickt wird. Deshalb braucht man keine Plugins auf Clientseite, sondern einfach nur einen simplen Browser!

Link: http://www.mathe-fa.de/de

Schlagworte:Bild, Funktion, Mathematik, Plotter
Veröffentlicht in Internet, Mathe 1 | Keine Kommentare »

O-Notation oder Komplexitätsklasse

Mittwoch, 18. November 2009

Mit der O-Notation kann man Klassen von Algorithmen erstellen. Im Grunde geht es darum, dass man abschätzen kann, wie sich die Laufzeit eines Algorithmus im Vergleich zu einem anderen Algorithmus verhält. Die Algorithmen erledigen natürlich die gleiche Aufgabe, aber mit unterschiedlichen Herangehensweisen. Zum Beispiel Algorithmus 1 für kleine (kurze) Aufgaben effizienter ist, aber Algorithmus 2 besser für komplexe (lange) Aufgaben. Da man das Laufzeitverhalten eines Algorithmus aber nicht genau vorhersagen kann, teilt man Algorithmen in Klassen ein.
Man kann mit der O-Notation nicht berechnen wie lang ein Algorithmus brauchen wird bis er fertig ist. Vielmehr stellt es eine Vergleichsmöglichkeit von Algorithmen dar – und zwar bezogen auf große Werte ( $n \rightarrow \infty$ ).

f in O(g)

O-Notation

Nehmen wir an, wir hätten 2 Algorithmen g und f. Wie man auf dem Bild rechts erkennen kann, ist der Algorithmus g effizienter, wenn er weniger als $n_0$ mal aufgerufen wird. Nach $n_0$ sollte man allerdings die Algorithmus g vorziehen.
Man kann sagen: “Der Algorithmus f ist in O(g).” Das trifft zu, für alle n > $n_0$ .

“f liegt in groß-O von g.”

f wird auf dauer also der effizientere Algorithmus sein; er arbeitet die gleiche Aufgabe schneller ab (ab n > $n_0$ , aber kleinere Werte werden ignoriert).
Mit dieser O-Notation stellt man also dar, dass f(n) maximal (auch gleich!) so schnell wächst wie g(n). Somit gilt: $f(n) \in O(g(n))$ .

Beispiel:
$f(n) = 100n$
$g(n) = n^2$
so schreibt man abkürzend: $f(n)$ und $g(n^2)$ . f ist also in O(g(n)), wenn auch erst ab einen $n_0 \geq 100$ . Man untersucht das Verhalten wenn n gegen unendlich geht ( $n \rightarrow \infty$ ). Dabei kann man alle konstanten Werte weglassen.

Asymptotische untere Schranke Ω

f(n) wächst mindestens so schnell wie g(n): $f(n) \in \Omega(g(n))$

Asymptotische exakte Schranke Θ

f(n) wächst genauso schnell wie g(n) wenn:
$f(n) \in O(g(n))$ und $f(n) \in \Theta(g(n))$

Veranschaulichung der O-Notation

Wachstumsreihenfolge

$1 < \log n < \sqrt{n} < n < n(\log n)^2 < n^2 < n^x < x^n$

Schlagworte:Algorithmus, Asymptotisch, Funktion, Komplexitätsklasse, Laufzeit, n0, Notation, O, Schranke, Verhalten
Veröffentlicht in GdI1 | Keine Kommentare »

Mergesort

Dienstag, 17. November 2009

Mergesort ist ein schneller Algorithmus zum sortieren von Elementen. Er wurde bereits 1945 vorgestellt.

Vorgehensweise
Als erstes teilt man die zu sortierende Liste in der Mitte in 2 Teillisten, um diese dann wieder zu teilen bis man nur noch Listen mit max. zwei Elementen hat. Diese kleinen Listen kann man dann sehr einfach sortieren. Danach werden die kleinen Listen schrittweise wieder zu großen Listen zusammengefügt, wobei man darauf bauen kann, dass alle Listen sortiert sind. Man fügt aber immer nur 2 Listen zu einer Neuen zusammen, weil man sich dabei immer nur die ersten Elemente der beiden Liste ansehen muss. Diese Funktion ist sehr gut durch Rekursion lösbar. Am Ende erhält man das Ergebnis als zusammengesetzte sortierte Liste.

Beispiel

Quelle: http://upload.wikimedia.org/wikipedia/de/thumb/9/99/Mergesort_example.png/600px-Mergesort_example.png

Schlagworte:Algorithmus, Mergesort, Rekursion, sort
Veröffentlicht in Algorithmen, GdI1 | Keine Kommentare »

Quicksort

Montag, 16. November 2009

Mit Quicksort kann man sehr schnell und Ressourcen sparend sortieren. Den Algorithmus gibt es bereits seit 1960!

Vorgehensweise am Beispiel einer Liste mit Zahlen:
Zuerst wählt man ein zufälliges Pivot-Element (Drehpunktelement). Danach sortiert man die verbleibenden Elemente in 2 Listen, in der Ersten sind alle Elemente die kleiner oder gleich dem Pivot-Element sind, in der Zweiten alle die größer oder gleich sind. Das Pivot-Element merkt man sich – man kann es jetzt bereits als Fertig markieren – und wendet das gleiche Verfahren auf die beiden kleineren Listen an.

Beispiel:

Pseudocode und weitere Beispiele: siehe Wikipedia.

Schlagworte:Algorithmus, Drehpunktelement, Pivot, Quicksort, sort
Veröffentlicht in Algorithmen, GdI1 | Keine Kommentare »

Funktionen

Sonntag, 15. November 2009

Eine Funktion besteht aus geordneten Paaren. Das bedeutet zu jedem x-Wert gibt es einen (!!) y-Wert. Deshalb kann man ein geordnetes Paar auch so schreiben: $(x, y)$ .
Wenn $(x_1, y_1) = (x_2, y_2)$ dann folgt daraus, dass $x_1 = x_2$ und $y_1 = y_2$ .
$(x, y) = (y, x)$ gilt nur wenn $x = y$ .
Ein geordnetes Paar wird auch als Tupel bezeichnet. Dabei ist ein Tupel mit 2 Elementen $(x, y)$ ein 2-Tupel, mit 3 Elementen $(x, y, z)$ 3-Tupel oder auch Tripel, usw.

Kartesisches Produkt

Das Kartesisches Produkt ist die Menge aller geordneten Paare die sich aus den beiden Ausgangsmengen bilden lassen.

“Jedes mit jedem”

Die Definition ist: $A \times B := \{(a, b) | a \in A, b \in B \}$
Beispiele und weitere Gesetze, siehe Wikipedia.

Definitionsbereich, Wertebereich und Graph

Nehmen wir eine an, wir hätten 2 Mengen $A$ und $B$ und Funktion von $A$ nach $B$ ist gegeben durch die Menge $G \subseteq A \times B$ . Wobei gilt: $\forall x \in A \exists y \in B (x, y) \in G$ . Die Funktion ist demnach $f = (A, B, C)$ .
Definitionsbereich: $D(f) = A$
Wertebereich: $W(f) = B$
Graph: $graph(f) = G$
2 Funktionen sind gleich, wenn der Wertebereich, Definitionsbereich und Graph identisch ist.

Eine Funktion f von $A$ nach $B$ schreibt man $f: A \to B$ .

Die Funktion g ist die Erweiterung von f, wenn $D(f) \subseteq D(g)$ .

Eigenschaften

Eine Funktion ist injektiv, wenn jeder Funktionswert maximal einmal erreicht wird.
$\forall x_1, x_2 \in A (f(x_1) = f(x_2) \implies x_1 = x_2)$
Eine Funktion ist surjektiv, wenn jedes Element des Wertebereichs mindestens einmal abgebildet wird.
$\forall y \in B \exists x \in A f(x) = y$
Eine Funktion ist bijektiv, wenn sie sowohl injektiv als auch surjektiv ist.
$\forall y \in B \exists^1 x \in A f(x) = y$

Beispiel I.4.5

Bilder

Das Bild eines Elements $a$ der Definitionsmenge ist einfach der Funktionswert ( $f(a)$ ).
</li>
Das Bild einer Funktion ist die Menge der Bilder aller Elemente der Definitionsmenge $A$ , also $f(A) := \{f(a) | a \in A\}$ . Das Bild ist also eine Teilmenge des Wertebereichs.
Beispiele.

Das Urbild eines Elements $b$ des Wertebereich ist die Menge aller Elemente des Definitionsbereichs, deren Bild (resultierender Funktionswert) $b$ ist. Man schreibt $f^{-1}(b) := \{a \in A | f(a)=b\}$ .
Beispiele.

Das Urbild einer Teilmenge $T$ des Wertebereiches ist die Menge aller Elemente des Definitionsbereichs, deren Bild Element dieser Teilmenge ist: $f^{-1}(T) := \{a \in A | f(a) \in T\}$ .

Die Umkehrfunktion einer bijektiven Funktion weist jedem Element des Wertebereichs das Urbildelement zu.

Unter der Verkettung oder Komposition versteht man die Hintereinanderausführung $(g \circ f)(a) := g(f(a))$ zweier Funktionen für alle Elemente des Defnitionsbereiches.

Stetigkeit

Eine Funktion ist stetig, wenn sehr kleine Änderungen an den Eingangswerten auch nur sehr kleine Änderungen an den Ausgangswerten verursachen. Beispiele: http://de.wikipedia.org/wiki/Stetigkeit#Beispiele_und_Gegenbeispiele

Sende Artikel als PDF an

Schlagworte:bijektiv, Bild, Definitionsbereich, Funktion, geordnet, Graph, Hintereinanderausführung, injektiv, Kartesisch, Komposition, Mathematik, Paar, Produkt, surjektiv, Tripel, Tupel, Umkehrfunktion, Urbild, Verkettun, Wertebereich
Veröffentlicht in Mathe 1 | Keine Kommentare »

Eigenschaften von Mengen
Samstag, 14. November 2009

In diesem Artikel möchte ich alle Eigenschaften sammeln, die man zu den Reellen und Natürlichen Zahlen wissen sollte.

Beschränkte Mengen

Seit die Menge $A \in \mathbb{R}$ . Angenommen es gibt ein $s \in \mathbb{R}$ , für das gilt: $\forall x \in A x \leq s$ – man kann auch $A \leq s$ schreiben -

“jedes Element der Menge ist kleiner als s”

Wenn gilt $\exists s \in \mathbb{R} \: A \leq s$ , so heißt die Menge $A$ nach oben beschränkt.
Mehr Informationen im der Wikipedia: Beschränkte Mengen.

Beispiel:
$\{x \in \mathbb{R} \mid x^2 < 9\}$ so ist die Menge nach oben und unten beschränkt: $[-3 \mid 3]$ .

Supremum und Infimum

Supremum/Infimum bezeichnet die obere/untere Schranke einer Menge.
Angenommen wir hätten eine Menge $A = \{x \in \mathbb{R} \mid x < 2 \}$ , so liegt das Supremum dieser Menge bei 2, weil 2 die kleinste obere Schranke von A ist. 3 wäre auch eine Schranke, aber nicht die kleinste und damit auch nicht das Supremum von A. Es gibt immer max. ein Supremum und Infimum, aber nicht zwangsweise.
Das Infimum ist ziemlich ähnlich zum Supremum, es ist bloß die größte untere Schranke von einer Menge. So hat zum Beispiel A kein Infiumum, weil alle Zahlen $< 2$ in der Menge enthalten sind.
Beispiel I.2.3

Maximum

Das Maximum ist dem Supremum sehr ähnlich. Jedes Maximum ist auch gleichzeitig das Supremum der Menge. Das Maximum ist die größte Zahl die in der Menge enthalten ist. Dabei muss es nicht immer ein Maximum geben: In der Beispielmenge A von Supremum und Infimum gibt es kein Maximum, weil es unendlich viele Zahlen gibt, die größer sind als ihr Vorgänger, aber kleiner als 2.
Definieren wir eine neue Menge $B = \{x \in \mathbb{R} \mid x \leq 2 \}$ , so gibt es hier ein Maximum – genau 2.

Sende Artikel als PDF an

Schlagworte:Beschränkt, Infimum, Mathematik, Maximum, Menge, Natürlich, reell, Supremum, Zahlen
Veröffentlicht in Mathe 1 | Keine Kommentare »

« Ältere Einträge

brianp.de

Archiv für November 2009

Scheme Kurs – Teil 7: IO

Scheme Kurs – Teil 6: set!

Apache2 mit SSL unter Debian 5

Online Funktionsplotter