Archiv für die Kategorie „Studiumsblog“
Mittwoch, 23. Dezember 2009
Mit dem Binomialkoeffizient kann man die Anzahl der Möglichkeiten berechnen, wie man k-Elemente aus einer n-elementigen Menge anordnen kann. Dabei gibt es keine Wiederholungen und die Reihenfolge spielt auch keine Rolle.
Das Symbol ist: 
(gesprochen “n über k”).
Die Formel zur Berechnung ist: 
Bedeutung der einzelnen Elemente
Man stellt sich dabei am besten vor, dass man die n-Elemente beliebig anordnet und dann die ersten k-Elemente zieht (sich also nur die ersten k-Elemente ansieht). Der Rest wird ignoriert. Deshalb steht im Zähler 
– also die Anzahl der Möglichkeiten n-Elemente anzuordnen wenn die Reihenfolge wichtig ist.
Da die Reihenfolge beim Binomialkoeffizient aber keine Rolle spielen soll, steht im Nenner 
multipliziert mit den restlichen Elementen die unwichtig sind, also 
.
Schlagworte:Binomialkoeffizient, Fakultät, Mathematik
Veröffentlicht in Mathe 1 | Keine Kommentare »
Samstag, 28. November 2009
foldr und foldl
Die Funktion fold wendet eine Funktion auf jedes Element einer Liste an, speichert das Ergebnis in einer neuen Liste und gibt diese zurück.
foldr liest die Liste von links nach rechts ein. foldl von rechts nach links, also falsch herum. Daraus ergibt sich auch gleich eine sehr hilfreiche Anwendung von foldl:
> (foldl cons empty (list 1 2 3 4 5))
(list 5 4 3 2 1)
Es invertiert also einfach die übergebene Liste.
Ein anderes Beispiel (bei dem es keinen Unterschied macht, ob man foldr oder foldl nutzt):
> (foldr + 0 (list 1 2 3 4 5))
15
map
map wendet eine Funktion auf alle Elemente einer Liste an, und gibt die jeweiligen Ergebnisse als neue Liste zurück.
> (map (lambda (x) (* x x)) (list 1 2 3 4 5))
(list 1 4 9 16 25)
filter
filter filtert eine Liste. Dazu übergibt man eine Funktion die entweder true zurückgibt, wenn das gerade getestete Element in die neue Liste soll, oder eben false, wenn es nicht in die neue Liste soll.
> (filter even? (list 1 2 3 4 5))
(list 2 4)
Schlagworte:filter, fold, Funktion, list, Liste, map, Scheme
Veröffentlicht in GdI1, Scheme | Keine Kommentare »
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 »
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 »
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 »
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 (
).
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 
mal aufgerufen wird. Nach sollte man allerdings die Algorithmus g vorziehen.
Man kann sagen: “Der Algorithmus f ist in O(g).” Das trifft zu, für alle n > .
“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 > , 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: 
.
Beispiel:
so schreibt man abkürzend: 
und 
. f ist also in O(g(n)), wenn auch erst ab einen 
. Man untersucht das Verhalten wenn n gegen unendlich geht (). Dabei kann man alle konstanten Werte weglassen.
Asymptotische untere Schranke Ω
f(n) wächst mindestens so schnell wie g(n): 
Asymptotische exakte Schranke Θ
f(n) wächst genauso schnell wie g(n) wenn:
und 
Veranschaulichung der O-Notation
Wachstumsreihenfolge
Schlagworte:Algorithmus, Asymptotisch, Funktion, Komplexitätsklasse, Laufzeit, n0, Notation, O, Schranke, Verhalten
Veröffentlicht in GdI1 | Keine Kommentare »
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 »
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 »
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: 
.
Wenn 
dann folgt daraus, dass 
und 
.
gilt nur wenn 
.
Ein geordnetes Paar wird auch als Tupel bezeichnet. Dabei ist ein Tupel mit 2 Elementen ein 2-Tupel, mit 3 Elementen 
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: 
Beispiele und weitere Gesetze, siehe Wikipedia.
Definitionsbereich, Wertebereich und Graph
Nehmen wir eine an, wir hätten 2 Mengen 
und 
und Funktion von nach ist gegeben durch die Menge 
. Wobei gilt: 
. Die Funktion ist demnach 
.
Definitionsbereich: 
Wertebereich: 
Graph: 
2 Funktionen sind gleich, wenn der Wertebereich, Definitionsbereich und Graph identisch ist.
Eine Funktion f von nach schreibt man 
.
Die Funktion g ist die Erweiterung von f, wenn 
.
Eigenschaften
-
Eine Funktion ist injektiv, wenn jeder Funktionswert maximal einmal erreicht wird.
-
Eine Funktion ist surjektiv, wenn jedes Element des Wertebereichs mindestens einmal abgebildet wird.
-
Eine Funktion ist bijektiv, wenn sie sowohl injektiv als auch surjektiv ist.
Beispiel I.4.5
Bilder
-
Das Bild eines Elements
der Definitionsmenge ist einfach der Funktionswert (
).
</li>
-
Das Bild einer Funktion ist die Menge der Bilder aller Elemente der Definitionsmenge , also
. Das Bild ist also eine Teilmenge des Wertebereichs.
Beispiele.
-
Das Urbild eines Elements
des Wertebereich ist die Menge aller Elemente des Definitionsbereichs, deren Bild (resultierender Funktionswert) ist. Man schreibt 
.
Beispiele.
-
Das Urbild einer Teilmenge
des Wertebereiches ist die Menge aller Elemente des Definitionsbereichs, deren Bild Element dieser Teilmenge ist: 
.
-
Die Umkehrfunktion einer bijektiven Funktion weist jedem Element des Wertebereichs das Urbildelement zu.
-
Unter der Verkettung oder Komposition versteht man die Hintereinanderausführung
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
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 »
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 
. Angenommen es gibt ein 
, für das gilt: 
– man kann auch 
schreiben -
“jedes Element der Menge ist kleiner als s”
Wenn gilt 
, so heißt die Menge nach oben beschränkt.
Mehr Informationen im der Wikipedia: Beschränkte Mengen.
Beispiel:
so ist die Menge nach oben und unten beschränkt: ![[-3 \mid 3]](http://l.wordpress.com/latex.php?latex=%5B-3%20%5Cmid%203%5D&bg=FFFFFF&fg=000000&s=1 "[-3 \mid 3]")
.
Supremum und Infimum
Supremum/Infimum bezeichnet die obere/untere Schranke einer Menge.
Angenommen wir hätten eine Menge 
, 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 
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 
, so gibt es hier ein Maximum – genau 2.
Schlagworte:Beschränkt, Infimum, Mathematik, Maximum, Menge, Natürlich, reell, Supremum, Zahlen
Veröffentlicht in Mathe 1 | Keine Kommentare »
