panthema / 2011
Drawing of PG(2,3)

Vervollständigung meiner Seminararbeit in Diskreter Mathematik

Posted on 2011-08-31 20:12 by Timo Bingmann at Permlink with 0 Comments. Tags: maths university

Heute habe ich meine Seminararbeit in Diskreter Mathematik an der FernUni Hagen vervollständigt. Ich möchte mich bei Prof. Hochstättler bedanken für die erfahrene Leitung und planvolle Einführung in die interessanten Gebiete der Design Theorie und endlicher Geometrien. Die Arbeit ist auf deutsch und unter folgendem Link downloadbar.

Download PDF: Seminararbeit-Singer-Differenzenmengen.pdf Seminararbeit-Singer-Differenzenmengen.pdf (2.79 MiB).

Download Seminararbeit-Singer-Differenzenmengen.pdf

Zusammenfassung

Die Entwicklung von Differenzenmengen in der Design Theorie begann 1938 mit einer algebraischen Untersuchung endlicher projektiver Geometrien von James Singer. Nach Einführung der wichtigsten Grundbegriffe der Design Theorie und projektiver Geometrien werden in dieser Ausarbeitung die beiden Resultate von Singer entwickelt. Die Existenz einer Kollineation mit Periode \frac{n^{d+1}-1}{n-1} führt zur Definition von Differenzenmengen und beide Ergebnisse liefern elegante Konstruktionsverfahren für PG(d,p^k).


Small drawing of a B+ tree

Update Release of STX B+ Tree 0.8.6

Posted on 2011-05-18 12:44 by Timo Bingmann at Permlink with 1 Comments. Tags: c++ stx-btree

After four years I have decided to release an updated version 0.8.6 of the STX B+ Tree C++ Template Classes package. The updated release contains all patches that have accumulated in my inbox over the years. So yes, please send me patches for this project, it is not in vain! Below the highlights on the changes in this release:

  • Implemented a missing function: erase(iterator iter) by recursively searching for the referenced leaf node inside the subtree containing equal keys.
  • Applied a patch which adds support for STL allocators as template parameters.
  • Corrected limits of a for loop when shifting pairs from left to right leaf nodes during deletion.

I also reran the speed test done back in 2007 on my new hardware and compared the results with the old data. Due to the larger L2 cache sizes in my new Intel Core i7, the B-tree speed-up first starts to show at about 100,000 integer items, rather than 16,000 items with my older Pentium 4. This might also have something to do with the new CPU using 64-bit pointers and thus requiring larger nodes for child references. Read the complete speed test here.

result plot from new speedtest

The updated source code package is available for download from this webpage.


Yet Another Release of digup 0.6.40 - A Digest Updating Tool

Posted on 2011-01-31 20:25 by Timo Bingmann at Permlink with 0 Comments. Tags: c++ utilities

This is yet another release entry of digup. This time, however, it is a major release with lots of new improvements and some old fixes:

  • Added new flags --modify-window=number to allow larger deltas in the modification time of files. This is a fixup for checking backups copied onto FAT filesystems, because these store the time stamp with a precision of only 2 seconds. Since this is a common operation, the shortcut -w/--windows will set the allowed modification window to 1.
  • Also added a new flag --exclude-marker=file, which makes the recursive file system walk skip all directories (and their sub-directories) containing a special marker file usually called .nobackup in other programs. This option is persistent and stored in the created digest file, so it must only be specified once and then in all subsequent runs the same directory marker is used to selectively skip over special directories.
  • Added a --restrict=pattern temporary exclusion flag. If specified, all paths containing the pattern as a substring are temporarily skipped. This allows one to quickly check a specific folder or file structure for modifications. Especially useful in combination with -c to perform a full digest check on only a subset of the files.
  • One more smaller fixup: using 64-bit file offsets on Window, which allows files larger than 2GB to work correctly.

For more information and the new version see the digup web page.