Gitterpunkte

Aus ProgrammingWiki

Aufzählbarkeit der Menge der Gitterpunkte

Die Menge G der Gitterpunkte (0,0),(0,1), ... einer x-y-Ebene ist aufzählbar.

1. Geben Sie eine Funktion f an, die \NN bijektiv auf G abbildet.

Cantorsche Paarungsfunktion, s. auch Wikipedia

var f = function (z) {
    var w = Math.floor((Math.sqrt(8*z+1)-1)/2);
    var t = w*(w+1)/2;
    var y = z-t;
    var x = w-y;
    return [x,y];
};

Da f eine bijektive und total berechenbare Funktion ist, kann man die Menge G aufzählen:

for (z=0; z<10; z++) {
    console.log("(" + f(z) + ")");
};

2. Geben Sie eine Funktion k zur Berechnung der Platznummer k(x,y) des betrachteten Gitterpunktes (x,y) an.

var k = function (x, y) {
    return (x+y)*(x+y+1)/2+y;
};

console.log("Platznummer von (1,2): " + k(1,2));
console.log("Platznummer von (2,0): " + k(2,0));

3. Definieren Sie eine Ordnungsrelation p_< in G.

Die folgende Prozedur gibt eine ganze Zahl zurück, die man gemäß Vorzeichen als true bzw. false deutet.

var p_kleiner = function (a,b) {
    return k(b[0],b[1])-k(a[0],a[1]);
};

console.log(p_kleiner([1,2],[2,0]));

Für das folgende Beispiel einer endlichen Gitterpunktmenge

var gps = [[ 0, 0 ],[ 2, 0 ],[ 3, 0 ],[ 1, 0 ],[ 0, 3 ],[2, 1],[ 0, 2 ],[ 1, 1 ],[ 1, 2 ],[ 0, 1 ]];

kann eine aufsteigende Sortierung mit p_< vorgenommen werden:

gps.sort(p_kleiner);
gps.reverse();
for (i=0; i<gps.length; i++ ) {
    console.log("(" + gps[i] +")");
};

4. Geben Sie eine Aufzählprozedur für G an und begründen Sie deren Berechenbarkeit.

f erfüllt die geforderten Eigenschaften und kann als Prozedur (s.o.) implementiert werden.