Funktion « brianp.de

Artikel-Schlagworte: „Funktion“

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 »

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 »

Schaltungen
Donnerstag, 5. November 2009

Eine Schaltung besteht mindestens aus Eingängen, Ausgängen, einer Spezifikation der Funktion sowie des Zeitverhaltens – also was die Schaltung macht, und wie lang sie dafür benötigt. Dabei kann man sich eine Schaltung wie eine Black-Box vorstellen. Es interessiert nicht, wie sie das tut was sie tun soll, solange sie es in der spezifizierten Art und Weise tut. Das ist ein wichtiger Grundsatz der Abstraktion (Beherrschung von Komplexität). Eine Schaltung kann intern aus weiteren Schaltungen bestehen, für die natürlich genau das gleiche gilt.

Dabei gibt es zwei grundlegende Arten von Schaltungen:

Kombinatorische Logik
Der Zustand der Ausgänge hängt nur vom Zustand der Eingänge ab. Es ist also jeder Ausgangswert reproduzierbar, wenn man den gleichen Eingangswert erneut anlegt.

Sequentielle Logik
Hier hängt der Zustand der Ausgänge nicht nur von den Eingängen ab, sondern auch von den vorherigen Zuständen. Die sequentielle Logik kann also Zustände speichern und bei späteren Berechnungen einbeziehen.

Dabei gibt es eine Reihe von Regeln, wie Schaltungen verknüpft werden dürfen:

Jedes Element der Schaltung muss kombinatorisch sein.

Jeder Verbindungsknoten ist ein Eingang in eine Schaltung oder an genau einem Ausgangsterminal angeschlossen. (Folie 6)

Die Schaltung enthält keine Zyklen, d.h. ein Ausgang einer Schaltung darf nicht gleichzeitig auch ein Eingang der gleichen Schaltung sein.

Die Folien von Prof. Andreas Koch (TU Darmstadt, http://www.esa.informatik.tu-darmstadt.de/twiki/bin/view/Lectures/TGdI09De.html) wurden als Vorlagen benutzt.

   Sende Artikel als PDF an

Schlagworte:Abstraktion, Ausgang, Eingang, Funktion, Schaltung, Spezifikation, Zeitverhalten, Zyklen
Veröffentlicht in TGdI1+2 | Keine Kommentare »

Disjunktive und Konjunktive Normalform
Dienstag, 3. November 2009

Diese beiden Normalformen werden besonders in der boolschen Algebra benutzt um boolsche Funktionen darzustellen. Boolsche Funktionen beschrieben die Ausgänge einer Schaltung als eine Funktion der Eingänge.

Zwischen DNF und KNF gibt es nur einen kleinen – aber entscheidenden – Unterschied:

Disjunktive Normalform
Alle Ausdrücke (der obersten Ebene) werden durch OR Verknüpft: $A \lor B \lor C$ .
Dabei können die Ausdrücke auch komplexere Ausdrücke sein, die untereinander dann mit AND Verknüpft sind: $(A_1 \land A_2) \lor B \lor (C_1 \land C_2 \land C_3)$ .

Konjunktive Normalform
Alle Ausdrücke (der obersten Ebene) werden durch AND Verknüpft: $A \land B \land C$ .
Dabei können die Ausdrücke auch komplexere Ausdrücke sein, die untereinander dann mit OR Verknüpft sind: $(A_1 \lor A_2) \land B \land (C_1 \lor C_2 \lor C_3)$ .

Anwendung

Gehen wir von folgender Wahrheitstabelle aus:

a b Y

0 0 0

0 1 1

1 0 1

1 1 0

DNF
Wenn man diese boolsche Funktion nun in der DNF darstellen will, sucht man sich alle Ausgänge Y die 1 sind. In diesem Fall also wenn a=0 und b=1 oder a=1 und b=0. Wenn der Eingang 0 ist, so muss mal den Eingang in der Formel negieren, ist er 1 so bleibt er unverändert. Und genau das ist auch schon die Form in der man als DNF darstellt:
$Y=\neg AB \vee A \neg B$

KNF
Bei der KNF ist es etwas anders. Man sucht sich alle Ausgänge Y die 0 sind und negiert die positiven Eingänge:
$Y=(A+B)(\neg A + \neg B)$

   Sende Artikel als PDF an

Schlagworte:Bool, Disjunktive, DNF, Funktion, KNF, Konjunktive, Normalform
Veröffentlicht in TGdI1+2 | Keine Kommentare »

Surjektivität, Injektivität, Bijektivität
Montag, 2. November 2009

Surjektivität, Injektivität und Bijektivität sind Eigenschaft von mathematischen Funktionen.

Surjektivität $\forall y \in Y \exists x \in X : f(x)=y$
Eine Funktion ist surjektiv, wenn jeder Wert des Wertebereiches als y-Wert der Funktion angenommen wird (mindestens einmal).
Beispiele und Gegenbeispiele in der Wikipedia

Injektivität $\forall x_1, x_2 \in X : (f(x_1)= f(x_2) \Rightarrow x_1=x_2)$
Eine Funktion ist injektiv, wenn jedes Element des Wertebereiches max. einmal angenommen wird.
Beispiele und Gegenbeispiele in der Wikipedia

Es darf keine 2 x-Werte geben, die den gleichen y-Wert haben.

Bijektivität
Eine Funktion ist bijektiv, wenn sie sowohl surjektiv als auch injektiv ist.
Beispiele und Gegenbeispiele in der Wikipedia

   Sende Artikel als PDF an

Schlagworte:Bijektivität, Funktion, Injektivität, Mathematik, Surjektivität
Veröffentlicht in Mathe 1 | Keine Kommentare »

Bild einer Funktion (auch Bildmenge)
Montag, 2. November 2009

Das Bild einer Funktion (auch als Bildmenge bekannt) ist ein Teilbereich des Wertebereich der Funktion. Es bezeichnet dabei allerdings nur die Elemente des Definitionsbereiches die die Funktion auch wirklich annimmt.

Beispiele:
1) $f(x)=\frac{1}{x}$ Bildmenge von $f(\mathbb{R} \setminus \{0\})$ ist $\mathbb{R} \setminus \{0\}$

2) $f(x)=x^2$ Bildmenge von $f(\mathbb{R})$ ist $\mathbb{R}_+$

   Sende Artikel als PDF an

Schlagworte:Bild einer Funktion, Bildmenge, Funktion, Mathematik, Wertebereich
Veröffentlicht in Mathe 1 | Keine Kommentare »

Beliebiges Potenzieren mit Scheme
Donnerstag, 22. Oktober 2009

Leider gibt es in Scheme keine Funktion um eine Zahl beliebig zu potenzieren. Daher hab ich eine kleine Funktion dafür geschrieben:

;; Contract: ^ number number -> number
;; Purpose: Returns result of number1^number2
;; Example: (^ 2 10) -> 1024
;; (^ 2 -2) -> 0.25
(define (^ x exp)
(cond
[(> exp 1) (* x (^ x (- exp 1)))]
[(< exp 0) (/ 1 (* x (^ x (- (- exp) 1))))]
[(= exp 1) x]
[(= exp 0) 1]))

(check-expect (^ 2 10) 1024)
(check-expect (^ -52 0) 1)
(check-expect (^ 2 -3) (/ 1 8))

   Sende Artikel als PDF an

Schlagworte:Funktion, lib, Potenzieren, Scheme
Veröffentlicht in Scheme | Keine Kommentare »

Scheme Kurs – Teil 1: Grundlegendes
Mittwoch, 14. Oktober 2009

Scheme (1970) ist eine relativ alte Sprache, aber eine der neusten Abkömmlinge von Lisp. Und Lisp ist “die Mutter aller Programmiersprachen”!

Kombination oder Präfix-Notation

In Scheme ist alles in Klammern gefasst. Eine einfache Addition sieht wie folgt aus:

(+ zahl1 zahl2)

An der ersten Stelle in der Klammer steht der Operator oder die Funktion. Danach folgen die Parameter. Die Anzahl der Parameter kann variieren, so ist es bei den eingebauten Funktionen möglich, beliebig viele anzugeben (solang sonnvoll).

(* 2 2 2 2)

(Ist das gleiche wie $2 * 2 * 2 * 2 = 2^4$ .)

Diese Darstellungsform nennt man Präfixdarstellung.

Verschachtelte Kombinationen

Kombinationen können natürlich beliebig weit verschachtelt werden.

(* (+ 4 9) (- 12 3))

Konstanten und Funktionen

Konstanten und Funktionen können mit dem Schlüsselwort define definiert werden.

(define PI 3.14)
(define (square var) (* var var))

In der ersten Zeile erstellen wir eine Konstante PI mit dem Wert 3.14.
In der zweiten Zeile definieren wir eine Funktion (oder Prozedur) namens square mit dem Parameter var. Der Funktionskörper (oder Funktionsrumpf) multipliziert den Parameter var mit sich selbst und gibt das Ergebnis automatisch zurück.
Danach kann man die Konstanten wie eine Zahl benutzen und die Funktion wie einen Operator:

(square PI)

würde uns das Ergebnis 9,8596 zurückgeben bzw. in diesem Fall auf dem Bildschirm ausgeben.

Kommentare

Kommentare werden durch einen doppelten Strichpunkt eingeleitet.

;; Dies ist mein Kommentar

   Sende Artikel als PDF an

Schlagworte:define, Funktion, Kombination, Kommentar, Konstante, Lisp, Parameter, Präfixdarstellung, Prozedur, Scheme
Veröffentlicht in GdI1, Scheme | Keine Kommentare »