Personal tools

SCCS Colloquium - July 23, 2008

From Sccswiki

Jump to: navigation, search
Date: July 23
Room: 02.07.023
Time: 3 pm, s.t.

15:00 Uhr - Benjamin Peherstorfer: Adaptive Sparse Grid Representation for Indicator Functions (BA)

Für charakteristische Funktionen achsparalleler Rechtecke wird die Genauigkeit der Bestapproximation in Dünngitterräumen untersucht. Hierfür wird die Menge der durch die approximierte Funktion falsch zugeordneten Punkte bestimmt. Der untersuchte Ansatz nutzt Eigenschaften der Dünngitter-Repräsentation aus, um eine möglichst gute Approximation der Höhenlinie, die der Rechtecksgrenze entspricht, zu errechnen. In diesem Zusammenhang wurden die beiden Verfahren "Marching Squares" und "Quad Squares" implementiert. Um den Fehler zu bestimmen, wird die Fläche zwischen Soll-Linie und approximierter Höhenlinie bestimmt. Dadurch ist schließlich eine Gegenüberstellung von Fehler und Level des benutzten Gitters, Aufwand des Verfahrens oder Verfeinerungsgrad des Gitters möglich.

15:30 Uhr - Ivaylo Haralampiev : Sudoku Rätselgenerator (SEP)

Es ist trivial für den Rechner ein beliebiges Sudokurätsel zu lösen. Es gibt einige sehr schnelle kleine Algorithmen die hunderte von Sudokus pro Sekunde lösen. Das Problem ein gültiges Sudoku zu generieren ist nicht so einfach. Dieses Dokument beschäftigt sich mit dem Thema Generieren und Bewerten von Sudokurätsel. Auf die Webseite http://sudokugenerator.hit.bg sieht man ein Java Applet, das die unten beschriebe Schema demonstriert. Das Sourcecode des Projekts steht im Jar. Dieses Programm basiert sich auf die klassische 9x9 Gitterstruktur und die klassische Regel "Die Ziffern von 1 bis 9 müssen in jede Zeile, Spalte und Block genau ein mal auftreten". Unter Block versteht man ein 3x3 Gitter. Es gibt genau 9 Blöcke, sowie 9 Zeilen und 9 Spalten oder insgesamt 81 Felder. Die Felder identifiziert man als [Zeile, Spalte] Tupel. Die erste Zelle ist r1c1, die letzte - r9c9. Ein wichtiges Hilfsmittel beim Lösen von Sudokus sind die so genannte Pencilmarks. Manche Spieler finden es sinnvoll bestimmte Felder zu markieren. Die Markierung enthält Information über die übrige Kandidaten für das Feld. Das Programm Sudokugenerator-1.0 kennt immer die vollständige liste der Kandidaten für alle Feldern. Das Interface erlaubt aber absichtlich keine Pencilmarks aus verschiedene Gründen (z. B Bewertung).