Das Erfüllbarkeitsproblem der Aussagenlogik – auch als SAT-Problem bezeichnet nach dem englischen Begriff satisfiablity für Erfüllbarkeit – fragt nach der Erfüllbarkeit einer gegebenen aussagenlogischen Formel durch eine geeignete Variablenbelegung. Man kann das Problem natürlich durch Aufstellen einer Wahrheitstabelle lösen, aber dann wächst der Zeitverbrauch exponentiell mit der Anzahl der Variablen. Man weiß bis heute nicht,…
Multiplizieren kann mensch seit mindestens 4000 Jahren, wie babylonische Multiplikationstabellen belegen. Aber erst jetzt wurde der schnellstmögliche Algorithmus zur Multiplikation zweier Zahlen gefunden, in einer letzte Woche auf dem französischen Preprintserver HAL angelegten Arbeit „Integer multiplication in time O(n logn)“. Zur Vorgeschichte: 1971 hatten Arnold Schönhage und Volker Strassen vermutet, dass es für die Multiplikation…
Der Satz von Bolyai-Gerwien-Wallace besagt, dass Vielecke gleichen Flächeninhalts in kongruente Stücke zerlegt werden können, so wie im Bild oben das Quadrat und das gleichseitige Dreieck in vier jeweils kongruente Drei- und Vierecke. (Gleichfarbige Stücke sind jeweils kongruent.) Laut Ian Stewart war das Finden solcher Zerlegungen Ende des 19. Jahrhunderts eine gern gestellte Rätselaufgabe. Der…
Einige Mathematiker von der TU Braunschweig verfolgen mit dem Projekt IDEA die Idee, Algorithmen im Ikea-Stil zu erklären, also als Beipackzettel ohne verbale Erläuterungen und mit schwedisch-klingenden Namen von Kwick Sört bis One Strök Dråw. Die Seite mit den bereits verpackten Algorithmen findet man hier und ein Interview mit einem der Autoren ist hier.
“Ich persönlich bin auch der Meinung, dass Algorithmen transparenter sein müssen, sodass interessierten Bürgern auch bewusst ist, was eigentlich mit ihrem Medienverhalten und dem anderer passiert” meint die Kanzlerin und “Die Kanzlerin meint sicher nicht, dass die Firmen ihre Geschäftsgeheimnisse offenlegen sollen. Aber wir brauchen mehr Informationen von Betreibern wie Facebook darüber, wie ihr Algorithmus…
Vom Torus zum Stier.
Die Lösung des “Problems des Handelsreisenden” hätte dramatische Konsequenzen – das behauptet jedenfalls ein im Juni in die Kinos kommender Film. Nicht dieser, sondern dieser.
Interkulturelle Informatikausbildung: Sortieren durch Aufsteigen – der einfachste (und wenig effiziente) Sortieralgorithmus Bubblesort funktioniert auch in der Volksmusik.
Noch einige Erklärungen zum mathematischen Hintergrund von SnapPy:
Letzte Kommentare