Tag Archives: Computer Science

Neues Skript zum Vorkurs, v4.5

Eine neue Version des Skripts zum Vorkurs “formale Methoden der Informatik”ist hier verfügbar.

In Version 4.5 hat sich geändert:
Weitere Beispiele zur vollständigen Induktion hinzugefügt.
Kapitel 7.1: wesentlich mehr Beispiele für Relationen hinzugefügt.

In Version 4.4 hat sich geändert:
Hinweis auf Einschreibtermine hinzugefügt.
Kapitel 3.6: Motivation zum “Umdrehen” der Quantoren hinzugefügt.
Kapitel 6.2: Beweise zur Partialsumme der geometrischen Reihe und zu x · x = x + x hinzugefügt.

Vorkurs “formale Methoden der Informatik” im WS 2017/18

Das Institut für Informatik der Universität Bonn bietet dieses Jahr wieder den Vorkurs “formale Methoden der Informatik” an, den ich wieder halten werde, jetzt bereits im vierten Jahr.

Der Vorkurs wird angeboten für frische Erstsemester in Informatik und gibt einen Überblick über das Wissen, was von den Studenten erwartet wird und einen Ausblick, was im ersten Semester an Stoff noch kommen wird. Er ist freiwillig und unbenotet.

Ich kann allen neuen Studenten den Vorkurs nur ans Herz legen, da sie einen schnellen und einfachen Überblick über den Stoff erhalten, der dann später im Semester noch einmal in Tiefe behaltelt wird. Und Sie lernen schon etwas vor dem Semster Ihre Kommilitonen und den Betrieb der Universität kennen.

Interessenten melden sich bitte im precampus-System an.

Der Vorkurs findet statt von Montag, 18.9.2017 bis Freitag, 29.9.2017, jeden Tag von 10-12 Uhr im Hörsaal 2, Institut für Informatik, Römerstr. 164, Bonn.

Weiterhin finden jeden Tag Übungen dazu statt, von 12-14 Uhr. Allen Studenten sei angeraten, zu den Übungen zu gehen, auch wenn der Stoff vielleicht einfach erscheint. In den Übungen besteht Gelegenheit, Fragen zu stellen, es werden Aufgaben zur Vorlesung gerechnet und man kann die neuen Kommilitonen kennenlernen. Es werden keine Hausaufgaben gestellt.

Es gibt ein Skript, welches hier verfügbar ist (Version 4.0 vom 12.9.2017). Da es auch während des Vorkurses Updates geben wird, drucken Sie besser immer nur Teile aus—falls Sie es überhaupt ausdrucken!  Ich werde hier immer die neueste Version des Skripts anbieten. Ich bin sehr interessiert daran, Fehler im Skript zu korrigieren: bitte sprechen Sie mich in oder nach der Vorlesung an oder auch online.

Vorkurs “Formale Methoden der Informatik” im WS 2016/17

Ich halte auch im WS 2016/17 wieder den Vorkurs “Formale Methoden der Informatik” an der Universität Bonn. Der Vorkurs wendet sich an Studierende, die jetzt im Wintersemester ihr Studium der Informatik beginnen.

Der Vorkurs ist freiwillig und unbenotet, aber eine Anmeldung ist hier erforderlich.

Der Vorkurs findet statt von Montag, 26.9.2016 bis Freitag, 7.10.2016, jeden Tag von 10-12 Uhr im Hörsaal 2, Institut für Informatik, Römerstr. 164, Bonn. Am 3.10. (Feiertag) fällt der Kurs ersatzlos aus.

Weiterhin finden jeden Tag Übungen dazu statt, von 12-14 Uhr. Wir raten Ihnen, zu den Übungen zu gehen, auch wenn Sie denken, dass Sie das alles schon voll drauf haben. 😉 In den Übungen haben Sie Gelegenheit, Fragen zu stellen, es werden Aufgaben zur Vorlesung gerechnet und Sie lernen Ihre neuen Kommilitonen kennen. Es gibt keine Hausaufgaben.

Es gibt ein Skript, welches hier verfügbar ist (Version 3.2 vom 7.10.2016). Da es auch während des Vorkurses Updates geben wird, drucken Sie besser immer nur Teile aus, falls Sie es überhaupt ausdrucken. 🙂 Ich werde hier immer die neueste Version des Skripts anbieten. Ich bin sehr interessiert daran, Fehler im Skript zu korrigieren: bitte sprechen Sie mich in oder nach der Vorlesung an oder auch online.

Vorkurs “Formale Methoden der Informatik” WS 2015/16

Ich halte in diesem WS 2015/16 wieder den Vorkurs “Formale Methoden der Informatik” an der Universität Bonn. Der Vorkurs ist gedacht für Studenten, die jetzt im Wintersemester ihr Studium der Informatik beginnen.

Der Vorkurs ist freiwillig und unbenotet, aber eine Anmeldung ist hier erforderlich.

Der Vorkurs findet statt von Montag, 28.9.2015 bis Freitag, 9.10.2015, jeden Tag von 10-12 Uhr (außer am 2.10. und 5.10.: 13-15 Uhr) im Hörsaal 2, Institut für Informatik, Römerstr. 164, Bonn.

Weiterhin finden jeden Tag Übungen dazu statt, von 13-15 Uhr (außer am 2.10. und 5.10.: 15-17 Uhr). Wir raten Ihnen zu den Übungen zu gehen, auch wenn Sie denken, dass Sie das alles voll drauf haben. 😉 In den Übungen haben Sie Gelegenheit, Fragen zu stellen und es werden Aufgaben zur Vorlesung gerechnet. Es gibt keine Hausaufgaben.

Ich habe ein Skript vorbereitet, welches hier verfügbar ist (Version 2.0.6). Da es auch während des Vorkurses Updates geben wird, drucken Sie besser immer nur Teile aus, wenn Sie es überhaupt ausdrucken. 🙂 Ich werde hier immer die neueste Version des Skript anbieten.

Update: der Vorkurs ist inzwischen vorbei, aber das Skript ist hier immer noch verfügbar. Hinweise sind weiterhin willkommen.

Slides and Links to my ISSAC ’15 Talk

I held my talk at ISSAC 2015 in Bath, UK on Wednesday July, 8th about “Implementation of the DKSS Algorithm for Multiplication of Large Numbers”. My paper is now available from the ACM digital library (or here locally) and the slides are available on the ISSAC website (or here locally).

To the ISSAC organizers and everyone present: the conference was awesome, thank you very much! I had a great time.

BibTeX for the paper:

@Conference{Lueders2015,
  Title                    = {Implementation of the DKSS Algorithm for Multiplication of Large Numbers},
  Author                   = {Christoph L{\"u}ders},
  Booktitle                = {ISSAC 2015 --- Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation},
  Year                     = {2015},
  Pages                    = {267--274},
  Abstract                 = {The Sch{\"o}nhage-Strassen algorithm (SSA) is the de-facto standard for multiplication of large integers. For N-bit numbers it has a time bound of $O(N \log N \log \log N)$. De, Kurur, Saha and Saptharishi (DKSS) presented an asymptotically faster algorithm with a better time bound of $N \log N 2^{O(\log^* N)}$. For this paper, a simplified DKSS multiplication was implemented. Assuming a sensible upper limit on the input size, some required constants could be precomputed. This allowed to simplify the algorithm to save some complexity and run-time. Still, run-time is about 30 times larger than SSA, while memory requirements are about 2.3 times higher than SSA. A possible crossover point is estimated to be out of reach even if we utilized the whole universe for computer memory.},
  Doi                      = {10.1145/2755996.2756643}
}

Implementation of the DKSS Algorithm for Multiplication of Large Numbers — ISSAC’15

My paper “Implementation of the DKSS Algorithm for Multiplication of Large Numbers” was accepted for ISSAC’15 Conference to be held on 6-9 July 2015 at the University of Bath, U.K. !

Abstract: The Schönhage-Strassen algorithm (SSA) is the de-facto standard for multiplication of large integers. For \(N\)-bit numbers it has a time bound of \(O(N \cdot \log N \cdot \log \log N)\). De, Kurur, Saha and Saptharishi (DKSS) presented an asymptotically faster algorithm with a better time bound of \(N \cdot \log N \cdot 2^{O(\log^∗ N)}\). For this paper, a simplified DKSS multiplication was implemented. Assuming a sensible upper limit on the input size, some required constants could be precomputed. This allowed to simplify the algorithm to save some complexity and run-time. Still, run-time is about 30 times larger than SSA, while memory requirements are about 2.3 times higher than SSA. A possible crossover point is estimated to be out of reach even if we utilized the whole universe for computer memory.

This is an improved version of what I wrote about in my diploma thesis.

My source code that was used for the tests is available here and is licensed under LGPL.

Fast Multiplication of Large Integers: Implementation and Analysis of the DKSS Algorithm — Diploma Thesis

“Fast Multiplication of Large Integers: Implementation and Analysis of the DKSS Algorithm”, that is my diploma thesis. I just uploaded it to arXiv: http://arxiv.org/abs/1503.04955

Abstract: The Schönhage-Strassen algorithm (SSA) is the de-facto standard for multiplication of large integers. For N-bit numbers it has a time bound of \(O(N \cdot \log N \cdot \log \log N)\). De, Kurur, Saha and Saptharishi (DKSS) presented an asymptotically faster algorithm with a better time bound of \(N \cdot \log N \cdot 2^{O(\log^∗ N)}\). In this diploma thesis, results of an implementation of DKSS multiplication are presented: run-time is about 30 times larger than SSA, while memory requirements are about 3.75 times higher than SSA. A possible crossover point is estimated to be out of reach even if we utilized the whole universe for computer memory.

It contains not only what the title promises, but also a long presentation of my own endeavors regarding fast multiplication, from ordinary multiplication, Karatsuba, Toom-Cook 3-way and Schönhage-Strassen with theory and some code examples.

I’m happy for any commentary.