Gitterpunkte

Aus ProgrammingWiki

Archivierte Version vom 2016-06-22T09:26:25+00:00. Aktuelle Version

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:

console.log(gps.sort(-p_kleiner));