Schlagwort: Logik

Wissen(schaft)spodcasts 👍 👎

In früheren Beiträgen hatte ich bereits ein paar Podcast-Empfehlungen ausgesprochen und auf mein Feedreader-Projekt hingewiesen, welches ebenfalls einige Podcasts aus verschiedenen Themenbereichen bereithält.

Mit diesem Beitrag möchte ich darüber hinaus gerne auf Wissenschaftspodcasts hinweisen. Diese Seite wurde von einigen Podcastern aus dem Bereich der Wissenschafts- und Wissensvermittlung ins Leben gerufen. Zu den Gründern gehören u. a. auch Nicolas Wöhrl von methodisch inkorrekt und Markus Völter von omega tau – beides Podcasts, die ich schon seit sehr langer Zeit verfolge und auch hier bereits beworben habe.

Die von den genannten und weiteren Personen eröffnete Seite bietet nun eine Sammlung verschiedenster Podcasts aus den Bereichen Wissen und Wissenschaft. Das Themenspektrum ist breit abgedeckt und reicht von Archäologie, Geschichte und Technik über Astronomie, Forschung im Allgemeinen und Speziellen bis hin zu Mathematik und Naturwissenschaften. Ich gehe also davon aus, dass für (fast) alle meiner – sicherlich hauptsächlich technisch interessierten – Besucher etwas dabei sein dürfte. Ihr könnt darüber hinaus auch neue Vorschläge einreichen.

Da mir die Vermittlung von Wissen und das Gespräch über wissenschaftliche Erkenntnisse persönlich äußerst wichtige Angelegenheiten sind, würde ich mich sehr freuen, wenn ihr etwas Passendes findet und die Seite(n) weiterempfehlt. Der Vollständigkeit wegen möchte ich abschließend noch kurz darauf hinweisen, dass ich mit den genannten Seiten in keiner weiteren Verbindung außer als Zuhörer einiger Podcasts stehe.

Schaltjahr ermitteln 👍 👎

Viele Beispiele ermitteln ein Schaltjahr über eine Prüfung darauf, ob das fragliche Jahr durch vier teilbar ist. Diese einfache Prüfung, die bereits im julianischen Kalender Anwendung findet, ist jedoch nur eine von drei Regeln des gregorianischen Kalenders. Für eine vollständige Prüfung müssen folgende drei Bedingungen überprüft werden:
  • Ist das Jahr durch 4 teilbar, ist es potentiell ein Schaltjahr. (2016 ist ein Schaltjahr)
  • Ist das Jahr durch 100 teilbar, ist es grundsätzlich kein Schaltjahr. (2100 ist kein Schaltjahr)
  • Ist das Jahr durch 400 teilbar, ist es generell ein Schaltjahr. (2000 ist ein Schaltjahr)
Dies lässt sich in C# nun beispielsweise wie folgt als statische Methode umsetzen:
Schaltjahr-Prüfung implementieren und verwenden
01020304050607
public static bool IsLeapYear(int year) {    return (((year % 2 == 0) && (year % 100 != 0)) || (year % 400 == 0));}
bool isLeapYear = IsLeapYear(2016); // trueisLeapYear = IsLeapYear(2100); // falseisLeapYear = IsLeapYear(2000); // true
Besonders spannend ist diese Methode jedoch nicht, das .NET-Framework bietet mit DateTime.IsLeapYear(…) nämlich bereits eine entsprechende Implementierung an. Es gilt jedoch den Hinweis der Dokumentation zu beachten, dass die Prüfung dabei immer im Rahmen des gregorianischen Kalenders erfolgt, was für manche – beispielsweise historische – Anwendungen unpässlich sein kann. Das Framework bietet im Namensraum System.Globalization jedoch weitere Kalender-Implementierungen an, welche jeweils eine entsprechende Umsetzung der IsLeapYear(…)-Methode zur Verfügung stellen.

Parität einer Zahl prüfen 👍 👎

Manchmal kann es für ein Problem relevant sein, ob eine Zahl (un-)gerade ist. Dies lässt sich sehr einfach durch Verwendung der ganzzahligen Division mit Rest (Modulo) bewerkstelligen – wir dividieren dabei einfach durch 2.

Eine Erweiterungsmethode für den Typ int in C# könnte beispielsweise wie folgt aussehen:
int.IsEven implementieren und verwenden (Modulo)
0102030405
public static bool IsEven(this int number) {    return ((number % 2) == 0);}
bool isEven = (7).IsEven(); // false
Im Stellenwertsystem zur Basis 2 (Dualsystem) kann man sich zu Nutze machen, dass bei ungeraden Zahlen die letzte Ziffer mit der Wertigkeit 1 gesetzt sein muss, da ansonsten die Zahl in jedem Fall gerade wäre. Übertragen auf die Arbeit im Binärsystem soll also das letzte Bit [nicht] gesetzt sein, was wir durch eine bitweise Verknüpfung ermitteln und dadurch eine entsprechende Optimierung ermöglichen:
int.IsEven implementieren und verwenden (Bitarithmetik)
0102030405
public static bool IsEven(this int number) {    return ((number & 1) == 0);}
bool isEven = (7).IsEven(); // false
Entsprechende IsOdd()-Methoden können ggf. analog dazu implementiert werden.

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)    );}

Notation formaler Ausdrücke 👍 👎

a + b ist ein Term, wobei a und b als Summanden bezeichnet werden. Das sollte soweit jedem Leser dieses Blogs klar sein – mit Grundschulmathematik soll es nun aber gar nicht weitergehen, wir benötigen nur eine gemeinsame Grundlage für den weiteren Teil des Artikels. Smiley: grinning

Einen Bestandteil haben wir bisher jedoch gar nicht näher betrachtet: Das beinahe selbstverständliche Symbol der Addition, das +. Dabei ist das gar nicht so uninteressant. Was genau ist das eigentlich? Nun, auf jeden Fall wird es als Operator bezeichnet. Diese Schreibweise ist uns so vertraut, dass sich die meisten bisher wahrscheinlich gar keine Gedanken zu den Hintergründen einer solchen Schreibweise gemacht haben – und wir auch andere ganz selbstverständlich verwenden.

Tatsächlich handelt es sich nämlich um den in sogenannter Infixnotation geschriebenen Aufruf der Funktion +(a,b); der Name der Funktion lautet also + und Funktionen dieser Darstellung werden üblicherweise in Präfixnotation geschrieben. Dies ist einem aus der Mathematik bei Funktionen wie sin und cos geläufig und selbstverständlich auch als Entwickler der meisten Programmiersprachen und sogar bei Konsoleneingaben.

Präfixnotation findet in der Mathematik meist bei unären Operationen Anwendung, wohingegen bei binären Operationen für gewöhnlich die Infixnotation zum Einsatz kommt. Mehrstellige Operationen werden (auch) in einfacher Funktionsschreibweise notiert.

Bei in Infixnotation geschriebenen Ausdrücken ist unbedingt die Operatorpräzedenz (und ggf. Operatorassoziativität) zu berücksichtigen. Dazu gehört auch der den meisten Lesern sicherlich bekannte Spruch "Punkt vor Strich": Manche Operationen müssen vor anderen ausgewertet werden, um das Ergebnis eindeutig zu halten; im Allgemeinen gilt beispielsweise:

(a + b) * c  ≠  a + (b * c)

Wie dadurch bereits ersichtlich und hoffentlich bekannt, lässt sich eine bestimmte Rangfolge mit Klammerung auch erzwingen. Üblicherweise gilt ohne nähere Spezifikation folgende Rangfolge bei einfachen Rechnungen:
  1. Klammerung
  2. Potenzierung
  3. Multiplikation, Division ("Punktrechnung")
  4. Addition, Subtraktion ("Strichrechnung")
Auch Programmiersprachen (z. B. C#, PHP) besitzen eine solche Rangfolge und unterscheiden sich teilweise.

Um aber noch einmal auf unsere Feststellung der unterschiedlichen Schreibweisen einzugehen: Tatsächlich ist dieses Problem nämlich der Infixnotation geschuldet; Präfixnotation (im Übrigen auch die umgekehrte Variante, die Postfixnotation) kann nämlich klammerfrei erfolgen und ist ganz einfach – wenn auch für die meisten sicherlich eher etwas ungewohnt – auf unser Beispiel der Addition übertragbar:
Addition mit Symbol und Präfixnotation
01
+ a b
Auch "komplexere" (na ja …) Anwendungen stellen kein Problem dar:
Vergleich von Infix- und Präfixnotation
0102030405
  // Infixnotation(a + b) * (c – d)
// Präfixnotation* + a b – c d
Wie man sieht, können hier die Klammern entfallen und man erhält dennoch das erwartete Ergebnis. Diese Darstellungsform vereinfacht im Übrigen das automatisierte Verarbeiten erheblich.

Projektverweise

Kategorien / Archiv  |  Übersicht RSS-Feed

Schlagworte

Suche