Mathematik-Brückenkurs an der FU Berlin (1/2) 👍 👎

Im Folgenden der Ablauf der ersten Woche des Mathematik-Brückenkurses an der FU Berlin im WS14/15:

Montag

Elementare Logik

Wir haben den Begriff der mathematischen Aussage als sinnvolles sprachliches Gebilde definiert, welches entweder wahr oder falsch sein kann. Es handelt sich in diesem Sinne um eine zweiwertige Logik.

  • Junktoren

    Wir haben grundlegende logische Verknüpfungen eingeführt. Konkret handelt es sich um die Verknüpfungen Negation (NOT), Konjunktion (UND), Disjunktion (ODER – einschließend), Kontravalenz (ODER – ausschließend), Implikation (mit Prämisse als Voraussetzung und Konklusion als Folgerung) und Äquivalenz (Gleichwertigkeit). Die Definition erfolgte jeweils über Wahrheitstafeln. Wir haben darüber hinaus zusammengesetzte Aussagen aus den zuvor genannten Verknüpfungen betrachtet und dazu eine entsprechende Operatorpräzedenz vereinbart.

  • Tautologien

    Wir haben uns zusammengesetzte Aussagen, die unabhängig von den Wahrheitswerten der Einzelaussagen wahr sind und entsprechend allgemeingültig genannt werden, angesehen. Dazu gehören – neben einigen anderen – insbesondere das Kommutativ-, Assoziativ- und Distributivgesetz, die De Morganschen Gesetze, die doppelte Negation und die Kontraposition.

Dienstag

Beweisprinzipien

Wir haben die Vereinbarungen getroffen, dass ein mathematischer Satz eine wahre Aussage ist und mit einem Beweis der Nachweis dieser Wahrheit geführt wird.

  • Abtrennungsregel

    Sind Prämisse und Implikation jeweils wahre Aussagen, dann ist auch die Konklusion eine wahre Aussage. Sofern die Prämisse nicht wahr ist, ist dieser Schluss nicht zulässig (aus Falschem folgt Beliebiges).

  • Direkter Beweis

    In diesem Fall wird ausgehend von einer wahren Aussage eine Folge wahrer Implikationen ermittelt, so dass die sukzessive Anwendung der Abtrennungsregel die Wahrheit der Aussage bestätigt.

  • Indirekter Beweis

    Man nimmt das Gegenteil der eigentlichen Aussage an und leitet daraus einen Widerspruch her.

Quantoren

Wir haben Quantoren – als Aussageform mit einer Variablen und einem Objektbereich – betrachtet.

  • Allaussage

    Mit einer Allaussage wird die Aussage getroffen, dass eine Aussage für alle Elemente des Objektbereiches wahr ist.

  • Existenzaussage

    Mit einer Existenzaussage wird die Aussage getroffen, dass eine Aussage für mindestens ein Element des Objektbereiches wahr ist.

Mittwoch

Mengenlehre

Wir haben Mengen als eine Zusammenfassung bestimmter Objekte zu einem Ganzen eingeführt, wobei die einzelnen Objekte als Elemente bezeichnet werden. Eine Menge ist durch die Angabe ihrer Elemente (z. B. durch Aufzählung) eindeutig bestimmt; auf die Reihenfolge kommt es dabei nicht an.

  • Gleichheit

    Zwei Mengen sind dann gleich, wenn sie die gleichen Elemente enthalten.

  • Leere Menge

    Die leere Menge ist die Menge, die kein Element enthält und eindeutig bestimmt.

  • Zahlbereiche

    Wir haben u. a. die Menge der natürlichen, ganzen, rationalen und reellen Zahlen betrachtet.

  • Teilmengen

    Eine Menge ist Teilmenge einer anderen Menge, wenn alle Elemente dieser ersten Menge in der anderen Menge enthalten sind.

Donnerstag

Mengenlehre
  • Operationen

    Wir haben den Durchschnitt, die Vereinigung und die Differenz von Mengen betrachtet. Zur Illustration dienten uns hierbei zusätzlich Venn-Diagramme.

Freitag

Abbildungen

Eine Abbildung ordnet jedem Element einer Menge (Definitionsbereich) genau ein Element einer Menge (Wertebereich) zu. Sofern der Wertebereich eine Teilmenge der reellen Zahlen darstellt, spricht man auch von einer Funktion.

  • Gleichheit

    Zwei Abbildungen sind gleich, wenn ihr Definitionsbereich, der Wertebereich und die jeweiligen Funktionswerte an jeder Stelle übereinstimmen.

  • Identische Abbildung

    Die identische Abbildung ordnet jedes Element des Definitionsbereichs sich selbst zu. Definitions- und Wertebereich stimmen entsprechend überein.

  • Konstante Abbildung

    Die konstante Abbildung ordnet jedem Element des Definitionsbereichs ein festes Element zu.

  • Injektivität, Surjektivität und Bijektivität

    Eine injektive Abbildung ordnet jedem Element aus dem Definitionsbereich ein verschiedenes Element aus dem Wertebereich zu. Eine surjektive Abbildung hat die Eigenschaft, dass jedes Element aus dem Wertebereich mindestens einmal auftritt. Eine Abbildung ist bijektiv, wenn sie sowohl injektiv als auch surjektiv ist.

  • Komposition

    Unter der Komposition versteht man die Hintereinanderausführung zweier Abbildungen. Die Komposition ist im Allgemeinen nicht kommutativ, jedoch assoziativ.

  • Umkehrabbbildung

    Die Umkehrabbildung ordnet jedem Wert einer Abbildung den ursprünglichen Wert zu. Die Komposition dieser beiden Abbildungen ergibt somit die identische Abbildung des Definitions- bzw. Wertebereichs. Die Umkehrabbildung existiert, falls die Abbildung bijektiv ist und ist dann eindeutig bestimmt.

Jeder Vorlesung schloss sich eine Übung an. Dort können Fragen zum Inhalt der Vorlesung gestellt und Aufgaben – insbesondere das Beweisen – zusammen mit anderen Teilnehmern und dem Tutor bearbeitet werden.

Bachelor-Studium 👍 👎

Ich nehme zum Wintersemester das Studium der Mathematik (B.Sc.) mit dem Ergänzungsbereich Informatik an der FU Berlin auf und möchte interessierte Leser gerne ein wenig daran teilhaben lassen.

Deshalb werde ich wöchentlich eine kleine Zusammenfassung des Studienverlaufs hier schreiben, so dass – neben dem Lerneffekt für mich – auch andere einen Einblick in das Studium der Mathematik erhalten können. Die ersten Lehrveranstaltungen beginnen Mitte Oktober, der Brückenkurs bereits Ende September.

Im ersten Semester besuche ich u. a. die Lehrveranstaltungen Analysis I/III, Lineare Algebra I/II und Computerorientierte Mathematik I/II. Diese werden entsprechend den Großteil der Beiträge beeinflussen.

Ich werde versuchen, weitere Artikel zur Softwareentwicklung mit C# zumindest einmal im Monat zu veröffentlichen.

Langzahlarithmetik in C# 👍 👎

Für manche Anwendungen kann es notwendig werden, mit ganzen Zahlen zu arbeiten, die mitunter deutlich größer (bzw. kleiner) sind, als die CLS-Typen Int16 (short), Int32 (int) und Int64 (long) definieren.

Zwar ist es eine gute Übung, arithmetische Operationen auf ganzen Zahlen, die als Zeichenkette vorliegen, selbst zu implementieren – das .NET-Framework bringt jedoch bereits seit v4.0 die Struktur BigInteger aus System.Numerics mit. Sofern du dir also nicht sehr sicher bist, eine für deinen spezifischen Anwendungsfall bessere Implementierung vorliegen zu haben, solltest du eher auf das Framework setzen.

Die Verwendung gestaltet sich denkbar einfach, insofern belasse ich es für den Moment bei ein paar Beispielen:
BigInteger verwenden
0102030405060708091011
BigInteger a = BigInteger.Parse("34872923458349238592320478");BigInteger b = BigInteger.Parse("14782398471853465710237672");
// Operatorüberladung für BigInteger.Add(a, b)BigInteger sum = (a + b); // 49655321930202704302558150
// Operatorüberladung für BigInteger.Subtract(a, b)BigInteger difference = (a – b); // 20090524986495772882082806
// Operatorüberladung für BigInteger.Multiply(a, b)BigInteger product = (a * b); // 515505450439764661138576432136536115538523372647216
Selbstverständlich stehen noch einige andere nützliche Operationen und Indikatoren zur Verfügung.

Notwendig sind derartige Vorgehensweisen beispielsweise in der Kryptologie oder bei Simulationen in der numerischen Mathematik. Hauptsächlich kam ich jedoch deswegen auf diesen kurzen Beitrag, da einige Entwickler die Einführung dieser Struktur (BigInteger ist nicht als Klasse implementiert) verpasst zu haben scheinen. Smiley: smiling

String.Format per Objekt-Eigenschaften 👍 👎

Jeder C#-Entwickler wird sicherlich bereits die eine oder andere Überladung der String.Format-Methode verwendet haben – ansonsten wird es auf jeden Fall höchste Zeit, sich damit zu beschäftigen. Beispiel:
String.Format verwenden
0102030405
string message = String.Format("{0} ist {1} Jahre alt und besitzt {2:C}.",    "Bernd",    35,    1234.56);  // "Bernd ist 35 Jahre alt und besitzt 1234,56 €."
Noch etwas bequemer – insbesondere auch im Zusammenhang mit anonymen Typen – wäre es jedoch, die Eigenschaften eines Objekts als Ersetzungsdaten verwenden zu können. Wir werden uns dazu eine (nicht ernsthaft optimierte) Erweiterungsmethode für den Typ String schreiben, welche auf Reflexion setzt:
FormatByObject implementieren
01020304050607080910111213
public static string FormatByObject(this string str, object obj) {    StringBuilder stringBuilder = new StringBuilder(str);    {        foreach(PropertyInfo propertyInfo in obj.GetType().GetProperties()) {            stringBuilder.Replace(                "{" + propertyInfo.Name + "}",                propertyInfo.GetValue(obj).ToString()            );        }    }
return stringBuilder.ToString();}
Nun können wir statt numerischer Indizes komfortablere Zeichenketten verwenden:
FormatByObject verwenden
0102030405
message = "{Name} ist {Age} Jahre alt und besitzt {Balance} €.".FormatByObject(new {    Name = "Bernd",    Age = 35,    Balance = 1234.56});  // "Bernd ist 35 Jahre alt und besitzt 1234,56 €€."
Dieses sehr einfache Vorgehen unterstützt jedoch bei Weitem nicht alle Möglichkeiten der ursprünglichen Implementierung, so ist beispielsweise kein {Balance:C} zur Währungsformatierung möglich. Dies könnte dadurch behoben werden, indem wir unsere erweiterte Formatierung auf das Basisformat zurückführen – sprich, die Zeichenketten durch einen Index ersetzen. Ich werde dies in einem separaten Beitrag noch einmal aufgreifen.

Zahl auf Zweierpotenz prüfen 👍 👎

Für manche Algorithmen bestehen Optimierungsansätze, wenn eine zu untersuchende Zahl eine Zweierpotenz ist. Daher möchte ich mit diesem Beitrag aufzeigen, wie sich diese Problemstellung möglichst effizient lösen lässt.

Naive Ansätze arbeiten mit Schleifen und prüfen schrittweise alle in Frage kommenden Zweierpotenzen – es ist leicht einzusehen, dass dieses Vorgehen insbesondere für größere Zahlen eher mäßig effizient ist. Alternativ könnte man auf die Idee kommen, das Problem mit Logarithmen zu lösen – hier kann es jedoch zu Rundungsproblemen kommen. Wir sollten uns daher die Struktur entsprechender Zahlen einmal genauer ansehen:
Zweierpotenzen
010203040506
                  Dualzahl     Dezimalzahl--------------------------------------------       20               1            1       21              10            2       22             100            4       23            1000            8
Offensichtlich ist bei einer Zweierpotenz 2n demnach das (n + 1)-te Bit auf 1 gesetzt und alle ggf. nachfolgenden Stellen besitzen den Wert 0 – was kaum eine Überraschung darstellen sollte. Wir müssen nun jedoch nicht jedes Bit einzeln prüfen, ob die Zahl auf dieses "Muster" passt, sondern können uns das Bitmuster der Zahl 2n – 1 zu Nutze machen:
Voränger von Zweierpotenzen
010203040506
                  Dualzahl     2n – 1 (dual)--------------------------------------------       20               1            0       21              10           01       22             100          011       23            1000         0111
Wie selbstverständlich zu erwarten war, muss der Vorgänger ein inverses Bitmuster besitzen. Dies hilft uns insofern weiter, als dass wir diese beiden Zahlen mit einem bitweisen UND verknüpfen und auf Gleichheit mit 0 prüfen können, was bei Zweierpotenzen zutreffen muss.

In C# könnte die Implementierung beispielsweise wie folgt aussehen:
Zahl auf Zweierpotenz prüfen (Basis)
010203
public static bool IsPowerOfTwo(uint number) {    return ((number & (number – 1)) == 0);}
Dieses Vorgehen liefert jedoch auch für die Zahl 0 den Wert true zurück. Wir prüfen diesen Fall daher separat:
Zahl auf Zweierpotenz prüfen (Erweiterung)
01020304050607
public static bool IsPowerOfTwo(uint number) {    return (        (number != 0)          &&        ((number & (number – 1)) == 0)    );}

Projektverweise

Kategorien / Archiv  |  Übersicht RSS-Feed

Schlagworte

Suche