Edwards JavaScript vom Hartz-IV Empfänger Homepage

Mathematische Irrtümer und Programmfehler vorbehalten. ;-)

OCW OpenCourseWare

Mit 6.6k schleichen die Lektionen auf meine Platte, bis zu drei Stueck kann ich am Tag downloaden und sogar gucken. Dabei mache ich Uebungen.

Jetzt ist 6.01 (Intro to EECS und Programming) fertig. Na gut, die Recitations kommen (aus eigenem Willen) noch dran. Jetzt folgen 6.02 Circuits und Electronics und 6.03 Signals and Systems. 6.006 DS und Algos mache ich ja schon seit Maerz (6.046j diesen Monat, die Recitations von 6.006 muss ich noch). April habe ich mit Mathe (18.*) angefangen (siehe plot.js =) und bessere Ergebnisse) und Physics (8.*, schon die ersten Lektionen und Versuche gesehen) und Chemie (Solid State/Intro to) stehen ebenso auf dem Plan wie andere Faecher. Ich komme dem nicht ganz hinterher, soviel Zeit habe ich nicht und mit 5GB im Monat ist das archivieren und spaeter gucken auch etwas zeitaufwaendiger.

ready(function(e) {
    var fp = new FunctionPlotter("#stat", { width: 320, height: 200 });
    fp.statistic_bars({
	name: "Mit oder ohne OCW",
	data: [
	    { name: "Ohne OCW",
	    value: 10 },
	    { name: "Mit OCW",
	    value: 45 }
	],
	fillStyle: "gold"
    });
});

Einfach zu empfehlen. ocw.mit.edu MIT OpenCourseWare. Wer anders als ich, das haben die meisten, normal studiert hat, oder arbeitet, wird hier bestimmt trotzdem noch fuendig, sich mal was rauszupicken.

Math.log2 und Math.log10 uebrigens werde ich mir mit der naechsten Node Version kompilieren. Ich kann auch mal wieder upgraden. Zu empfehlen ist uebrigens, bereits mit Maps, Sets und WeakMaps zu arbeiten. Gerade diese Strukturen werden spaeter euer Alltag und bevorzugt sein.

Augmenting Data Structures

Das Erweitern von vorhandenen Datenstrukturen. An und fuer sich ein Alltagsding. Man passt die Basisdatenstrukturen dem Zweck entsprechend an. Dazu erstellt man eine neue Unterklasse oder kopiert sich den Code und editiert den.

Beim Splay Tree rotiert das zuletzt drauf zugegriffene Element nach oben. Vielleicht inpraktikabel vielleicht aber auch nuetzlich ist ein lastXs Pointer zur letzten Node. Die Kosten muessen addiert werden, sind aber konstant.

Size Operationen, Tiefe, Hoehe, Vorfahre, Nachfahre, Onkel, Grossvater, Rotation. Das sind alles Operationen, die durch Erweiterung der Datenstruktur BST entstanden sind. Vielleicht braucht ihr ja nur den Nachbarn des Nachbarn und keine Komplettsuche.

Wollte nur nochmal dran erinnern. Komme heute nicht zum Coden.

Update: Abends habe ich dann noch Graphen und Liste ausprobiert. Gerade bearbeite ich den Graphen, hehe. Der ist so voller Bugs und Fluechtigkeitsfehler, dass ich grinsen muss. Nebenbei habe ich eine Backpointer Idee ausprobiert, die ich ebenfalls entferne. Wenn ich mit fertig bin, poste ich den neuen Code.

Ca. 20 Minuten spaeter habe ich alles entfernt und sogar eine Unlogik in der Konstruktion entdeckt, eine Mischung aus directed und undirected Graph ist nicht besonders klug. Darum ist der hier gerichtet und darauf bereit fuer die Graphik und die Shortest Path Formeln, die ich noch nicht ausprobiert habe.

Update: (Mittlerweile bin ich was weiter)

function Graph (options) {
    "use strict";

    var me = this;
    var vertices = [];
    var fastXS = {}; // eigtl. kann man in vertices auch noch die stringkeys speichern.
    function isString (x) { return typeof x === "string"; }
    function isFunction (x) { return typeof x === "function"; }
    function isVertex (x) { return x instanceof Vertex; }
    
    function Arc(o, d, w) {
	return Object.seal({
	    constructor: Arc,
	    __proto__: Arc.prototype,
	    o: o, 
	    d: d,
	    w: w || null
	});
    }

    function Vertex(key, value) {
	return Object.seal({
	    constructor: Vertex,
	    __proto_: Vertex.prototype,
	    key: key,
	    value: value || null,
	    adjacents: [],
	    cursor: { x: 0, y: 0 }	    
	});
    }
    
    function get (u) {
	var v;
	if (isString(u) && (v = fastXS[u])) return v;
	else {
	    for (var x in vertices) {
	        if (vertices.hasOwnProperty(x)) {
		    if ((v = vertices[x]).key === u) return v;
		}
	    }
	}
	return null;
    }
    
    function getedge (u,v) {
	var e;
	var a = get(u);
	var b = get(v);
	var l = a.adjacents;
	for (var f in l) {
	    if (l.hasOwnProperty(f)) {
		e = l[f];
		if (e.d === b) return e;
	    }
	}
	return null;
    }
    
    function indegree (u) {
	var deg = 0;
	if (!isVertex(u)) u = get(u);
	// O(V+E)
	vertices.forEach(function (v) {
	    v.adjacents.forEach(function (e) {
		if (e.d === u) ++deg;
	    });
	});
	return deg;
    }
    
    function outdegree (u) {
	// O(1) oder O(n) je nachdem ob get() fastXS hat oder for in duchzulaufen
	if (!isVertex(u)) u = get(u);
	return u.adjacents.length;
    }
    
    
    function connect(u, v, w) {
	var a, b, e;
	a = get(u);
	b = get(v);
	if (!a || !b) {
	    return null;
	} else {
	    e = new Arc(a,b,w);
	    a.adjacents.push(e);
	    return true;
	}
	return null;
    }
    
    function disconnect(u, v) {
    	var a, b, e, succ = null;
    	a = get(u);
    	b = get(v);
	a.adjacents = a.adjacents.filter(function (x) {
	    if (x.d === b) { succ = true; return false; }
	    return true;
	});
	return succ;
    }
    
    function insert(k, v, u, w) {
	var a;
	if (k === undefined) throw "insert key";
	a = get(k);
	if (!a) {
	    a = new Vertex(k,v);
	    vertices.push(a);
	    if (isString(k)) fastXS[k] = a;
	    if (u) connect(k, u, w);
	    return true;
	} else {
	    return null;
	}
    }
    function find(k) {
	var a = get(k);
	if (!a) return null;
	else return { key: a.key, value: a.value };
    }
    
    function remove(k) {
	var a;
	if (k === undefined) throw "remove key";
	a = get(k);
	if (a) {
	    // O(V+E)
	    vertices.forEach(function (u) {
		if (u != a)
	        u.adjacents.forEach(function (v) {
	    	    disconnect(v, u);
	        });
	    });
	    a.adjacents = [];
	    vertices = vertices.filter(function (v) { return v.key !== k; });
	} else {
	    return null;
	}
	return true;
    }
    
    function update(k,v) {
	var a = get(k);
	var old;
	if (a) { old = a.value; a.value = v; return old; }
	return null;
    }

    function setweight(u,v,w) {
	var e, old;
	e = getedge(u,v);
	if (e) {
	    old = e.w;
	    e.w = w;
	    return old;
	}
	return null;
    }
    function getweight(u,v) {
	var e = getedge(u,v);
	if (e) return e.w;
	return null;
    }
    
    function dfs (v, f) {
    	var visited = [];
	if (isFunction(v) && !f) { f = v; v = vertices[0]; }
	else v = get(v);
	if (!v) return null;
	f(v.key, v.value, null);
	visited.push(v);
	traverse(v.adjacents);
	function traverse (adj) {
	    for (var i = 0, j = adj.length; i < j; i++) {
		v = adj[i].d;
	        if (visited.indexOf(v) === -1) {
		    f(v.key, v.value);
		    visited.push(v);
		    if (v.adjacents.length) traverse(v.adjacents);
		}
	    }
	}
    }

    function bfs (v, f) {
    	var nodes = [];
	var visited = [];
	var e;
	if (isFunction(v) && !f) { f = v; v = vertices[0]; }
	else v = get(v);
	if (!v) return null;
	nodes[0] = [{ v: v, e: { o: { key: null, value: null }, w: 0 }}]
	visited.push(v);
	summarize(v, 1);
	nodes.forEach(function (level) {
	    level.forEach(function (data) {
		f(data.v.key, data.v.value, data.e.o.key, data.e.w);
	    });
	});
	function summarize (v, depth) {
	    if (!nodes[depth]) nodes[depth] = [];
	    var edges = v.adjacents;
	    var v;
	    for (var i = 0, j = edges.length; i < j; i++) {
		e = edges[i];
		if (e) {
		    v = e.d;
		    if (visited.indexOf(v) === -1) {
		        nodes[depth].push({ v: v, e: e });
	    		visited.push(v);
			summarize(v, depth+1);
		    }
		}
	    }
	}
    }
    
    function sort_pq (a,b) {
	return a < b;
    }
    
    function shortest (u,v) {
	var a = get(u);
	var b = get(v);
	var Q = [];
	var S = {};
	var d = {}; 
	var s, path;
	function search (e) {
	    var v = e.d;
	    var o = e.o;
	    var w = e.w;
	    var dist = d[o.key] + w; 
	    if (!d[v.key] || dist <= d[v.key]) { d[v.key] = dist; S[dist] = { v:v, w:w, o:o, d: dist, p: d[o.key] }; }
	    if (v.key === b.key) Q.push(d[v.key]);
	    else v.adjacents.forEach(search);
	}
	if (!a || !b) throw "there is no u or no v";
	d[a.key] = 0;
	a.adjacents.forEach(search);
	Q.sort(sort_pq);
	s = S[Q.pop()]; 
	path = [];
	do {
	    path.push({ key: s.v.key, w: s.w, d: d[s.v.key] });
	} while (s = S[s.p]);
	return path.reverse();
    }

    function print () {
	vertices.forEach(function (v, i) {
	    console.log((i+1)+". vertex: "+v.key+", "+v.value);
	    v.adjacents.forEach(function (e,j) {
		console.log((i+1)+".; edge ("+(j+1)+"): o="+e.o.key+", d="+e.d.key+", w="+e.w);
	    });
	});
    }


    function draw (context, options) {
	"use strict";

	/* Ich sollte lieber Cluster suchen, und die Grueppchen malen */

	var x = 35, y = 35, w = context.canvas.width - 20, h = context.canvas.height - 20;
	var size = vertices.length;
	var cols = w / 100;
	var rows = size / cols;
	var r = (options && options.r) || 15;
	var n = 1;
	var fontSize = 10;
	
	function open(s,f,l) {
	    context.save();
	    context.beginPath();
	    context.strokeStyle = s||"black";
	    context.fillStyle = f||"beige";
	    context.lineWidth = l||0.5;
	}
	
	function close () {
	    context.closePath();
	    context.stroke();
	    context.restore();
	}
	
	vertices.forEach(function (v) {
	    var s1, s2, s3;
	    ++n;
	    if (n > cols) {
		x = 30;
		y += 100;
		n = 0;
	    } else x += 100;
	    v.cursor.x = x;
	    v.cursor.y = y;
	    open("lightgrey", "beige", 0.1);
	    context.arc(x,y, r, 0, 360);
	    context.fill();
	    close();

	    open();
	    context.strokeText(""+v.key, x-r, y-20, 100, 25);
	    close();
	    s3 = v.value;
	    if (s3.length*5 > 2*r) {
		s3 = s3.substr(0, 2*r-1);
		s1 = s3.substr(0, Math.floor(s3.length / 2)) + "-";
		s2 = s3.substr(Math.floor(s3.length / 2)) + "...";
		context.strokeText(""+s1, x-35, y, 100, 10);
		context.strokeText(""+s2, x-35, y+15, 100, 10);		
	    } else {		context.strokeText(""+s3, x-35, y, 100, 25);
	    }
	    close();
	});
	
	vertices.forEach(function (v) {
	    v.adjacents.forEach(function (e) {
		var d = e.d;
		var vx = v.cursor.x;
		var vy = v.cursor.y;
		var dx, dy;
		dx = d.cursor.x; 
		dy = d.cursor.y;
		var a = dx - vx;
		var b = dy - vy;
		var i=Math.floor(dx - a/1.2);
		var j=Math.floor(dy - b/1.2);
		var x1,y1,x2,y2;	
			
		open("blue", "blue", 0.5);
		context.moveTo(vx, vy);
		context.lineTo(dx, dy);
		context.globalCompositeOperation = "destination-over";
		close();
		
		open("green", "lightgreen", 1);
		context.strokeText(""+e.w, i, j, 25, 15);
		close();
	    });
	});
    
    }
    
    function draw_shortest (u, v, context, options) {
	var path = shortest(u,v);
	
	path.forEach(function (key,i) {

	        var u = get(key);
		var v = get(path[i+1]);

		if (u && v) {
		    open("red", "red", 1);
		    context.moveTo(u.cursor.x, u.cursor.y);
	    	    context.lineTo(v.cursor.x, v.cursor.y);
		    close();
		}
	});
    }
    
    function animate (context, options) {
	var data = options.data;
	var i = 0;
	function paint () {
	    var node = data[i];
	    if (node.type === "insert") {
		insert();
		draw(); // quickly: draw whole graph
	    }
	    if (node.type === "remove") {
		remove();
		draw();
	    }
	    if (node.type === "connect") {
		connect();
		draw();
	    }
	    if (node.type === "disconnect") {
		disconnect();
		draw(); // spaeter mal schrittchen dazu und weg
	    }
	    if (i === data.length) {
		i = 0;
	    }
	    setTimeout(paint, 1000);
	}
	setTimeout(paint);
    }
    var me = this;
    if (me instanceof Graph === false) return new Graph(options);
    me.insert = insert;
    me.find = find;
    me.remove = remove;
    me.update = update;
    me.setweight = setweight;
    me.getweight = getweight;
    me.connect = connect;
    me.bfs = bfs;
    me.dfs = dfs;
    me.shortest = shortest;
    me.draw_shortest = draw_shortest;
    me.print = print;
    me.draw = draw;
    me.draw_shortest = draw_shortest;
    me.indegree = indegree;
    me.outdegree = outdegree;
    return Object.freeze(me);
}

var g = Graph();
g.insert("Edward");
g.insert("Edward1");
g.insert("Edward2");
g.insert("Edward3");
g.insert("Edward4");
g.insert("Edward5");
g.insert("Edward6");
g.connect("Edward",  "Edward1", 2);
g.connect("Edward1", "Edward2", 1);
g.connect("Edward2", "Edward6", 9);
g.connect("Edward2", "Edward3", 5);
g.connect("Edward",  "Edward3", 6);
g.connect("Edward3", "Edward4", 1);
g.connect("Edward4", "Edward6", 10);
g.connect("Edward4", "Edward5", 7);
g.connect("Edward3", "Edward5", 4);
g.connect("Edward5", "Edward6", 1);

console.log("--");
console.log(g.shortest("Edward1", "Edward5"));
console.log("--");
console.log(g.shortest("Edward","Edward6"));
/*
--
[ { key: 'Edward2', w: 1, d: 1 },
  { key: 'Edward3', w: 5, d: 6 },
  { key: 'Edward5', w: 4, d: 10 } ]
--
[ { key: 'Edward3', w: 6, d: 6 },
  { key: 'Edward5', w: 4, d: 10 },
  { key: 'Edward6', w: 1, d: 11 } ]
*/

Update: Den Origin Pointer in der Adjacency Liste kann ich mir glaube ich sparen. Genauso ist nicht ueberall geprueft, ob die Eingabe valide ist. Bei einer fertigen Datenstruktur muss das aber vollstaendig sein. Hier throwen insert und update.

Und hier ist noch die Liste (doubly mit Sentinel). Die Malfunktion muss ich noch. nth-item ist zerobased - aus Gewohnheit, auch mit Arrays bei 0 zu beginnen. Ich glaube hiermit kann man dann listenbasierte Sortieralgorithmen ueben. Oder SkipLists oder self-adjusting Lists.

function List () {
    "use strict";
    
    var list = Node (null, null, null); // Sentinel mit null Item
    var size = 0;
    var me = this;

    function Node (item, next, prev) {
	var node = Object.seal({
	    item: item,
	    next: next,
	    prev: prev
	});
	if (next) next.prev = node;
	if (prev) prev.next = node;
	return node;
    }
    
    function nth (i) {
	var node, j = 0;
	if (size < i) return null;
	else node = list.next;
	while (j < i) {
	    node = node.next;
	    j++;    
	}
	return node.item;
    }
    
    function find_intern (item) {
	var node = list.next;
	while (node != list) {
	    if (node.item === item) {
		return node;
	    }
	    node = node.next;
	}
	return null;
    }	
    
    function insertFront (item) {
	var node = Node(item, list.next, list);
	++size;
	return size;
    }
    function insertBack (item) {
	var node = Node(item, list, list.prev);
	++size;
	return size;
    }
    function insert (item, pos) {
	var at;
    	if (size === 0) return insertFront(item); 
    	else if (!pos || pos > size-1) return insertBack(item);
	else {
	    node = list.next;
    	    while (node != list) {
		++at;
		if (at === pos)  break;
		node = node.next;
	    }
	}
	Node(item, node, node.prev);
	++size;
	return size;
    }
    
    function remove (item, pos) {
	var at = 0, a, b, node;
	if (size == 0 || pos > size-1) return null;
	if (!pos) node = find_intern(item);
	else {
	    node = list.next;
    	    while (node !== list) {
		if (at === pos)  break;
		++at;
		node = node.next;
	    }
	}
	if (node) {
	    a = node.prev;
	    b = node.next;
	    a.next = b;
	    b.prev = a;
	}
	--size;
	return size;
    }
        
    function walk (f) {
	var node = list.next;
	var pos = -1;
	if (size > 0) {
	    do {
		f(node.item, ++pos);
		node = node.next;
	    } while (node !== list);
	}
	else return null;
    }

    function walk_rev (f) {
	var node = list.prev;
	var pos = size;
	if (size > 0) {
	    do {
		f(node.item, --pos);
		node = node.prev;
	    } while (node !== list);
	}
	else return null;
    }
    
    function join (l) {
	l.walk(function (item) {
	    insert(item);
	});
    }
    
    function draw (context, options) {
	var startx = (options && options.x) || 0;
	var starty = (options && options.y) || 0;
	var w = context.canvas.width;
	var h = context.canvas.height;
	var cols = Math.floor((w-20) / 75);
	var rows = Math.ceil(size / cols);
	var r = 0, c = 0, n = 0, p = 0;
	var x = startx, y = starty, lx = 0, ly = 0;
	var rw = 40, rh = 55;
	var node = list.next;
	
	function open (f,s,l) {
	    context.save();
	    context.beginPath();
	    context.fillStyle = f || "beige";
	    context.strokeStyle = s || "black";
	    context.lineWidth = l || 0.5;
	}
	function close () {
	    context.stroke();
	    context.closePath();
	    context.restore();
	}
	
	open("black", "black", 0.1);
	context.arc(3,3, 3, 0, 360);
	context.fill();
	context.moveTo(lx=startx+5,ly=starty+5);
	context.lineTo(lx+=25,ly);
	context.stroke();
	close();
	node = list.next;
	p = 0;
	n = 0;
	while (p < size) {
		open();
		context.moveTo(lx, ly+32);
		context.lineTo(x,y+32);
		context.stroke();
		context.moveTo(x,y+47); 
		context.lineTo(lx, ly+47);
		close();
		
		
		open(); // <-
		context.moveTo(lx, ly+32);
		context.lineTo(lx+4, ly+32+4);
		context.stroke();
		context.moveTo(lx, ly+32);
		context.lineTo(lx+4, ly+32-4);		
		close();

		open();
		context.moveTo(x,y+47);
		context.lineTo(x-4,y+47+4);		
		context.stroke();
		context.moveTo(x,y+47);
		context.lineTo(x-4,y+47-4);
		close();
		
	    open();
	    context.fillRect(x, y, rw, rh);
	    context.fill();
	    close();
	    open("black", "gold");
	    context.fillText(node.item, x+2, y+10, 36, 15);
	    context.fillText("prev", x+2, y+35, 36, 15);
	    context.fillText("next", x+18, y+50, 36, 15);
	    context.fill();
	    close();
	    ++n;
	    lx = x+rw;
	    ly = y;
	    if (n >= cols || x > w - 10) {
		x = 10;
		y+= 70;
		n = 0;
	    } else {
		x += 75;
	    }
	    ++p;
	    node = node.next;   
	}
    }

    if (me instanceof List === false) return new List();
    list.prev = list;
    list.next = list;
    me.insertFront = insertFront;
    me.insertBack = insertBack;
    me.insert = insert;
    me.nth = nth;
    me.remove = remove;
    me.join = join;
    me.walk = walk;
    me.walkrev = walk_rev;
    me.draw = draw;
    return Object.freeze(me);
}

var l = new List();
l.insert("Eddie");
l.insert("Daddy");
l.insert("Freddy");
l.insert("Marsi");
l.remove("Marsi");
console.log(l.nth(0));
console.log(l.nth(1));
console.log(l.nth(2));
console.log(l.nth(3));

var l2 = new List();
l2.insert("a");
l2.insert("b");
l.join(l2);
l.walk(console.log);
l.walkrev(console.log);

/*
Freddy
Daddy
Eddie
null
Freddy 0
Daddy 1
Eddie 2
Eddie 2
Daddy 1
Freddy 0
*/

ECMA-262: May 14

Auf ecmascript.org kann man seit zwei Wochen die neueste Fassung vom ES.next (ES6) Standard lesen. Auf der es-discuss Mailing Liste kann man die Diskussionen verfolgen.

Ich werde mich in das neue Draft (mit Markup) einblaettern, wenn ich wieder zuhause bin. Ich gehe jetzt meine Frau abholen.

Update: Wird ein guter Standard. Lesen des Annex ist empfohlen. Dort werden zur Zeit Dinge festgehalten, die wieder gestrichen wurden, oder auch eine Definition von Begriffen, die in der Spec vorkommen.

Sequenz finden

6.01SC Intro to EECS und Programmming, was viel von Robotern handeln wird, beginnt unter anderem mit Programmiergrundlagen. Hier wird eine Sequenz von 1..n gesucht, die nur aus "increment" und "square" bestehen kann. Er legt den Schuelern zum einen die Applikation von Funktionen nah, sowie den Baum zur Verdeutlichung, wie man jeder Zahl dann in zwei Richtungen weiterverfolgt. Ich habe eine ganze, nein, zwei, gar drei Stunden noch drueber philosophiert, ob es moeglich waere mit Memoisation von 1..n zu arbeiten. Definitiv ist von n..1 durch Verwendung von "sqrt" und "decrement" der kuerzeste Weg sofort zu finden, in die andere Richtung hat man sehr viele Zweige zu probieren.

var find_seq = (function () {
"use strict";

var results = [];
var wrong_paths = [];

function Node (k, v, p) {
    return {
	key: k,
	value: v,
	parent: p
    };
}

function get_path(node) {
    var path = [];
    do {
	path.push({ n: node.key, op: node.value });
    } while (node = node.parent);
    return path.reverse();
}

function find_seq(i, node) {
    var n;
    if  (node === undefined) {
	results = [];
	wrong_paths = [];
        node = Node(1, "start", null);
    }
    n = node.key;
    if (n === i) { 
	results.push(get_path(node));
    } else if (n < i) {
        node.left = Node(n*n, "sqr", node);
	if (n > 1) { 
	    find_seq(i, node.left);
	} else wrong_paths.push(get_path(node.left));
	node.right = Node(n+1, "inc", node);
	find_seq(i, node.right);
    } else if (n > i) {
	wrong_paths.push(get_path(node));
    }
    return { r: results, w: wrong_paths };
}
return find_seq; 
}());

function analyze (i) {
var r = find_seq(i);
var rl = r.r.length;
var wl = r.w.length;
var k = +Infinity;
var s;
r.r.forEach(function (p) { if (p.length < k) k = p.length, s = p; });
console.log("Anzahl der Pfade bis "+i+": "+rl);
console.log("Anzahl der falschen Pfade bis "+i+": "+wl);
console.log("Das sind wohl mindestens "+(rl+wl)+" Pfade");
console.log("Kuerzester Pfad: "+k);
console.dir(s);
}
analyze(100);
analyze(16);
/*
Anzahl der Pfade bis 100: 19
Anzahl der falschen Pfade bis 100: 945
Das sind wohl mindestens 964 Pfade
Kuerzester Pfad: 6
[ { n: 1, op: 'start' },
  { n: 2, op: 'inc' },
  { n: 3, op: 'inc' },
  { n: 9, op: 'sqr' },
  { n: 10, op: 'inc' },
  { n: 100, op: 'sqr' } ]
Anzahl der Pfade bis 16: 5
Anzahl der falschen Pfade bis 16: 30
Das sind wohl mindestens 35 Pfade
Kuerzester Pfad: 4
[ { n: 1, op: 'start' },
  { n: 2, op: 'inc' },
  { n: 4, op: 'sqr' },
  { n: 16, op: 'sqr' } ]
*/

Weil ich das Memoizing nicht beachtet hatte, dachte ich, ich koennte das noch einbauen. Der Versuch erwies sich als interessanter Fehlschlag, weil der erste Pfad, inc 1, sqr 2, sqr 4, sqr 8, sqr 16, inc 17 ... inc 100 rauskommt, oder mal nach Quadrat vier bereits nur incs. Wenn man mit table[n] arbeitet wird 3*3 durch table[3] == inc 2 verdeckt und gar nicht mehr ausgefuehrt. Das habe ich hier gestern nodeweise abgezaehlt.

    /* mal */
    
    if (!table[n]) {
	table[n] = node;
	/* recur */	
    } else "do nothing no more";
    
    /* und */
    
    if (!sqrs[n*n] node.left
    if (!incs[n+1]) node.right
    // bzw.
    if (!sqrs[n] node.left
    if (!incs[n]) node.right
    
    /* probiert */
    /* Funktioniert aber alles nicht */

Dann habe ich ueberlegt, wie man eine Ableitung (Calculus, derivative) zur Funktion formuliert, die den kuerzesten Weg zurueck anzeigt. Ich bin mir ganz sicher, es hier mit einer herkoemmlichen Ableitung zu tun zu haben. Ohne jetzt genau zu werden und T(n) zu verwenden, habe ich dann die Wurzel gezogen und solange, falls, dekrementiert, bis man die naechste Wurzel ziehen kann, mit der Bedingung, dass die Wurzel eine ganze Zahl ist. Und um die schneller zu ermitteln und auch hier nicht bei jeder Zahl erst die Wurzel zu ziehen, habe ich alle Quadrate von 2 bis zur Wurzel der gesuchten Zahl memoisiert. Heraus kommt eine super Top-Down (n..1) Funktion, die genau den schnellsten Weg findet.

/*
Pseudocode der Ableitung fuer den kuerzesten Pfad

1. Memoize alle Ganzzahl Quadrate <= i
2. Dekrementiere bis zum ersten Quadrat <= i
3. Ziehe die Wurzel 
4. Wiederhole 2.-3. und speichere den Pfad.
*/

Die Funktion find_seq2 (oder find_seq&apos) ermittelt den kürzesten Weg.

function find_seq2(i) {
    var memo = {};
    var path = [];
    var j, k;
    for (j=2, k = Math.sqrt(i)+1; j < k; j++) {
	memo[j*j] = j;
    }
    j = i;
    do {
	if (memo[j]) {
	    path.push({ n: j, op: "sqr" });
	    j = memo[j];
	} else {
	    path.push({ n: j, op: "inc" });
	    j--;
	}
    } while (j > 1);
    path.push({ n: 1, op: "start" });
    return path.reverse();
}

console.dir(find_seq2(100));
console.dir(find_seq2(16));

/*
[ { n: 1, op: 'start' },
  { n: 2, op: 'inc' },
  { n: 3, op: 'inc' },
  { n: 9, op: 'sqr' },
  { n: 10, op: 'inc' },
  { n: 100, op: 'sqr' } ]
[ { n: 1, op: 'start' },
  { n: 2, op: 'inc' },
  { n: 4, op: 'sqr' },
  { n: 16, op: 'sqr' } ]
*/

Die Methode ist auch die, die man beim Kopfrechnen verwenden wuerde, weil von unten nach oben das Ding unabschaetzbar ist, ohne dass man viel oefter vergleichen muss.


/*

Bessere Methode Bottom-Up statt Tree ? NEIN. 
Gibt den ersten Pfad. Quadrate von 2 bis 16, dann
wird inkrementiert. 16 * 16 ist bereits groesser
als 100. Da kann man mit memo nix reissen.

1. Memoize Quadrate <= i
2. Incrementiere bis Quadrat
3. Springe bis Quadrat + 1
4. Wiederhole 2. bis 3

*/

Beim weiteren durchlesen habe ich meinen Erlaeuterungsansatz wieder entfernt. Weil er nicht konkret ist, ist er eigentlich auch nicht so wichtig. Ist eigentlich nur fuer mich interessant.

2er Logarithmus

Der folgende Beitrag geht einfach zu ersetzen durch folgenden Befehl.

    function log2(a) {
	return Math.log(Math.pow(a, Math.LOG2E));
    }

Weil der Rest unwichtig ist, habe ich den Beitrag gekuerzt. Ich habe vier Funktionen geschrieben, um mich dem 2er Log zu naehern. Als ich mit fertig war, wusste ich dann, da ich die Ergebnisse mir gerade gemerkt hatte, dass, wenn ich die Math.LOG2E Konstante als Exponent nehme mit Math.log dann den 2er Logarithmus bestimmen kann. Hier nochmal die Methode mit der ich mich naehern kann. Es ist garantiert nicht die beste Loesung und auch keine fehlerfreie, denn bei einigen Zahlen scheint es doch laenger zu dauern.

/* Diese Methode ist die, die am naechsten rankommt. */

function log2(a) {
    "use strict";
    var b = 0;
    var n = -1;
    var i = 1;
    var dev = 10e-14;
    while (1) {
	if (b >= a) break;
	while (b < a) {
	    n += i; 
	    b = Math.pow(2, n);
	} 
	if ((b > a) && (b-a > dev)) {
	    n -= i;
	    b = Math.pow(2,n);
	    i /= 10;
	} 
    }
    return n;
}

console.log("Ausprobieren");
console.log(log2(1));
console.log(log2(2));
console.log(log2(3));
console.log(log2(4));
console.log(log2(5));
console.log(log2(6));
console.log(log2(7));
console.log(log2(8));
console.log(log2(16));
console.log(log2(32));
console.log(log2(64));
console.log(log2(63));
console.log(log2(65));

console.log("Wiederholung mit Einsetzen des Ergebnisses");
var x = log2(64);
console.log(Math.pow(2, x));
x = log2(63);
console.log(Math.pow(2, x));
x = log2(128);
console.log(Math.pow(2, x));
x = log2(33);
console.log(Math.pow(2, x));
x = log2(2000);
console.log(Math.pow(2, x));
x = log2(100);
console.log(Math.pow(2, x));

Die Praezisionsmethode kann man nach dem "Binary Search" Schema noch verbessern. Anstatt den Zaehler zurueckzusetzen und in kleineren Schritten von der letzten Naeherung ranzutasten sollte man in der Mitte teilen und gucken, ob es kleiner oder groesser ist. Damit kann man sich noch einige falsche Ergebnisse streichen, die gar nicht erst in Frage kommen.

/*
Ausprobieren
0
1
1.5849625007212005
2
2.3219280948873644
2.5849625007211614
2.8073549220576104
3
4
5
6
5.977279923499917
6.022367813028454
Wiederholung mit Einsetzen des Ergebnisses
64
63.000000000000014
128
33
2000
100.00000000000004
*/

berechneQuadratwurzel

Die Funktion ist aus [Balzert09] Lehrbuch der Softwaretechnik: Basiskonzepte und Requirementsengineering, 3. Auflage 2009. Der Java Code besagte, die Quadratwurzel zu berechnen. Eine Probe bestaetigt das.

function sqrt(x) {
    var y0, y1, i;
    if (x < 0.0) throw "error";
    y1 = 1.0;
    i = 1;
    for (;;) {
	y0 = y1;
	y1 = 0.5 * (y0 + x / y0);
	i++;
	if (i > 50) throw "error2";
	if (Math.abs(y1-y0) < 1e-6) return y1;
    }
}

console.log(sqrt(25));
console.log(sqrt(2));

/*
5
1.414213562373095

*/

Dann war ich ja letzten schon nah dran, als ich bei der 6.006 Lecture Newtons Method und High Precision Number Computing, versuche, diese zu ermitteln. Und in 6.000 Introduction to Computer Science and Programming kam eine andere verwandte Methode zum Naehern an die Wurzel dran. Wie man sieht, geht die hier aber wunderbar.

RedBlackTree (cont'd)

Ich moechte mir die RedBlackTrees nun programmieren und visualisieren. Ich habe das Kapitel ueber RedBlackTrees, was zur Vorlesung gehoert. Dadurch kann ich die Implementation in Kuerze vervollstaendigen.

In der aktuellen Abbildung kann man eindeutig erkennen, dass die RedBlackProperties, d.h. die mathematischen-programmatischen Eigenschaften des Baumes, verletzt werden. Eine rote Node kann keinen roten Parent haben.

Und nicht nur das Problem mit der 8. Der Baum ist noch ein Fall fuer den Debugger. Wenn ich beliebige Werte eingebe, funktioniert er nicht. Ich denke mal, da ich mit null Pointern statt einem NIL-Sentinel (dummy node) arbeite, dass beim rotieren oder recolorn mal ein Zugriff versagt. Man muss ja nur einen Case uebersehen und schon wirkt sich das auf viele Inserts aus. Oder ich habe RED und BLACK vertauscht und es "waere" sonst richtig gewesen.

Update: Beobachtung: Wenn ich 3 und 6 sehe, muesten die ebenfalls wie 8 und 9 die Farben tauschen. Die 8 Nodes ueberschreiten Normalhoehe(7) === 3 um 1 Node, darum ist die Hoehe ok. Auch die Black Height ist daher in jedem Fall 2. Roootnode (nix), Rot, Schwarz (1), Rot, Pointer Schwarz (2) = 2.

    ready(function (e) {
	var canvas = document.querySelector("#rbt");
	var context = canvas.getContext("2d");
	var tree = new RedBlackTree();
	tree.insert(7, "Hallo"); 
	tree.insert(3, "Welt");	 
	tree.insert(9);
	tree.insert(18);
	tree.insert(6);
	tree.insert(23);
	tree.insert(8);
	tree.insert(15);
	tree.draw(context);
    });
    

Da ich den Baum komplett gekapselt habe, und keine Nodes leake, kann man den Context an den Baum uebergeben. Ich habe inzwischen ein weiteres Feld gefunden, was ich nicht richtig gelernt habe. Animation. Alle Algorithmen, die ich in den letzten 2-3 Monaten ausprobiert habe, sind fundamental fuer die Daten, aber zum malen habe ich, bis auf was Vektormathe und Winkelfunktionen im Anriss, noch keine Strategie.

Die folgende Routine fuehrt die Rotationen und das Rekolorieren durch und ist wie leftrotate und rightrotate auf jeden Fall mit einem Bug behaftet. Es kommen invalide Baeume raus.

    function insert_fixup (z) {
	    var y;
	    var p, q;
	    while (z && (p = z.parent) && p.color === RED) {
		q = p.parent;
		if (q && p === q.left) {
		    y = q.right;
		    if (y && y.color === RED) {
			p.color = BLACK;
			y.color = BLACK;
			q.color = RED;
			z = q;
		    } else {
			if (z === p.right) {
			    z = p;
			    leftrotate(z);
			    if (z.parent) z.parent.color = BLACK;
		        } 
			p.color = BLACK;
	    	        q.color = RED;
		        rightrotate(q);
		    } 
		} else if (q && p === q.right) {
    		    y = q.left;
		    if (y && y.color === RED) {
			p.color = BLACK;
			y.color = BLACK;
			q.color = RED;
			z = q;
		    } else {
			if (z === p.left) {
			    z = z.parent;
			    rightrotate(z);
			    if (z.parent) z.parent.color = BLACK;
			}
			p.color = BLACK;
			q.color = RED;
	    		leftrotate(q);
		    }	
		} 
	    }
	    if (root) root.color = BLACK;
    }
    

Trip down memory lane

Brendan Eich erzaehlt auf der OWASP AppSecUSA 2012 The Same-Origin Saga.

Interessante Geschichte und viele Details, was frueher war, woher das kam, und welche Bedeutung vieles davon heute noch hat, wie document.write fuer Ads oder document.domain fuer die Same-Origin-Policy.

GgT

Der greatest common divisor (gcd) oder auf deutsch GgT laesst sich mit dem bekannten Euklidischen Algorithmus errechnen. Wenn q gleich 0 ist, dann gebe p zurueck, ansonsten rechne den Rest aus p % q aus, und gebe das Ergebnis des rekursiven Aufrufs von gcd mit q und r zurueck. Wenn r jetzt 0 ist, dann wird q direkt zurueck gegeben (Zeile 2, if q===0 return p).

function gcd(p, q) {
    if (q === 0) return p;
    var r = p % q;
    return gcd(q, r);
}
function print(a,b) {
    console.log(gcd(a,b));
}
print(1,2);
print(10,20);
print(40,30);
print(12,4);
print(444,400);
print(44, 40);
print(44444,4444);
print(127,254);
/*
1
10
10
4
4
4
4
127
*/

Aus [Sedgewick] Algorithmen in Java. Pearson Studium/Addison Wesley. Was ich als Algorithmen in C vor 10 Jahren mal hatte.

Türme von [6~Hanoi

Gestern Abend habe ich es noch geschafft, "Divide and Conquer Recurrences" (18.062j Mathe für CS) zu wiederholen.

Die Türme von Hanoi habe ich vor zwei oder drei Monaten schon probiert, da war die Wikipedia zu schnell mit der Loesung, dass ich den Sinn der Mathematikaufgabe verpasst hatte. Diesmal habe ich sie im halbschlaf begriffen.

Man hat kurz ausprobiert. Fuer eine Scheibe T(1) braucht man 1 Move. Fuer 2 Scheiben T(2) braucht man 3 moves, fuer 3 Scheiben T(3) braucht man bereits 7 Zuege. Die Frage war, wie viele man fuer n Discs braucht?

Wenn man bis zur vorletzten Scheibe T(n-1) geht, dann die letzte Scheibe +1 bewegt, und dann wieder alle draufhebt T(n-1) kommt man auf 2*T(n-1) + 1.

Die Daten wurden ermittelt, indem man die ersten Scheiben bewegt und mitgezaehlt hatte. Ich hab sie mir von gestern bis heute merken koennen. Wollte eigentlich gestern abend schon was zu schreiben.

Formel durch Erraten (Clever Guessing): Bei den Daten T(1)=1, T(2)=3, T(3)=7, T(4) = 15, draengt sich die Vermutung auf, dass es sich um die Formel T(n) = 2^n - 1 handelt.

T(n) = 2*T(n-1) +1 = 2^n -1

Beweis durch Einsetzen (Substitution Method)..

Achtung: Die richtige Substitution schreibweise kann man hier lesen (Wikipedia). Das ist erstmal von mir so aufgeschrieben. Jetzt muss ich meine Schreibung auch noch anpassen.

Beispiel T(3): T(3) = 2*T(n-1) + 1 = 2*T(2) + 1 = 2 * 3 + 1 = 7; 7 = 2^3 - 1 = 8 - 1 Für drei Schreiben sind mindestens sieben Schritte zu verrichten.

Bei T(n) bei n = 64 sind 2^64 - 1 Schritte zu verrichten, das sind 18446744073709552000 Schritte bei 64 Scheiben. Quasi unloesbar in der Zeit eines Menschenlebens, jedenfalls sagte der Professor gestern auch, dass die Moenche wohl bis ans Ende der Welt zu tun hatten..

Mathematische Beweise muss ich noch was schriftlich ueben. In 6.046 oder 6.006 wird praktisch mit Algorithmen gerechnet, in 6.042/18.062j Mathe fuer Informatiker liegt der Schwerpunkt auf mathematischen Beweisen. Ich bin im Moment noch ein wenig unsicher, wie ich mir gerade bestaetigte. Denn die paar Zeilen obendrauf haette ich mit den Angaben bereits als perfekten Beweis formulieren koennen muessen. So steht er jetzt in meinem Deutsch da. Das ist noch falsch.


Eine Animation, die ich gestern im Anschluss ausprobieren wollte, habe ich entfernt. Ich habe mich der Funktion bewege der Wikipedia: Die Türme von Hanoi bedient, die ich letzten Monat mal ausprobiert hatte und dabei einen Fehler uebersehen. Die Ausgabe stimmte glaube ich mit der der Wikipedia ueberein, aber enthielt einen Fehler. Ich hab das noch nicht geprueft, wer jetzt den Fehler machte, jedenfalls darf ich das nochmal machen.

Uebrigens hat hanoi eine exponentielle Komplexitaet O(2n), was das Problem schon recht hart macht. Auch wenn es einfach ausschaut, wenn man die Loesung sieht, steckt da mathematisch noch ein gewisser Anspruch hinter, es als Lehrbeispiel zu verwenden..

RedBlackTrees und SplayTrees

Splay Trees kann man unter Spreizbaum nachlesen. Die Rotation durch den Parent nach rechts oder links habe ich nun mehrere male fuer verschiedene Baumtypen wiederholt, dass ich sie mir auch als allgemeingueltig merken kann. Vor zwei Monaten hatte ich solche Funktionen schonmal auf meiner Frontpage vermerkt, als ich gerade mit dem BST uebte. Das hier sind natuerlich neue. Da die Subtrees A und C nicht veraendert werden, habe ich sie weggelassen. Nur B wandert von der einen node rechts innen nach links innen und umgekehrt, da sich zwischen den beiden Nodes ihr Intervall befindet.

    
    function rightrotate (x) { // rotiert x rauf nach p, p nach rechts (zick)
	var p = x.parent;
	var q = p.parent;
	var B = x.right;
	if (q !== null) {
	    if (q.left === p) q.left = x;
	    else if (q.right === p) q.right = x;
	} 
	x.parent = q;
	p.parent = x;
	x.right = p;
	p.left = B;
	if (B) B.parent = p;
    }
    
    function leftrotate (p) { // rotiert p rauf nach x, x nach links (zack)
	var x = p.parent;
	var q = x.parent;
	var B = p.left;
	if (q !== null) {
	    if (q.left === x) q.left = p;
	    else if (q.right === x) q.right = p;
	} 
	p.parent = q;
	x.parent = p;
	p.left = x;
	x.right = B;
	if (B) B.parent = x;
    }
        
    

Ist genau so einfach wie Binary Search, was von dem O(log n) Verhalten des Baumen bzw. dem Vergleich in der find/search Methode O(log n) abstammt.

Binary Search

Einen sortierten Array in O(log n) Zeit durchsuchen. Diese hier ermittelt die Position p des Elements. Man kann auch S[p].key vergleichen und ganze Records returnen, ist ja logisch.

        function bsearch(k,S) {
	    return binary_search(k,S,0,S.length);
	}

	function binary_search(k, S, l, h) {
	    var el, p;
	    p = Math.floor((h-l) / 2) + l;
	    if ((el = S[p]) === k) return p;
	    else if (k < el) return binary_search(k, S, l, p-1);
	    else if (k > el) return binary_search(k, S, p+1, h);
	    return null;
	}
    

Naechstes Beispiel. Und so stelle ich mir den ohne Rekursion vor. Randomisierung und testen adjacenter Elemente bringt Vorteile gegenueber dem, was hier geschiert, einfaches halbieren der Suchfelder. Aber was passiert, wenn ich den floor von 0/2 will? Gottseidank kommt 0 raus. Koennte also klappen. Heute gibt es mal eine ungetestete Schleife, hehe.

	function binary_search(k, S, l, h) {
	    var el, p;
	    l = l || 0;
	    h = h || S.length;
	    do {
		p = Math.floor((h-l) / 2) + l;
	        if ((el=S[p]) === k) return p;
	        else if (k < el) h = p-1;
	        else if (k > el) l = p+1;
	    } while (h-l > 0);
	    return null;
	}
    

9.00SC Psychologie Primer

/hiphop - da mache ich mir schon lange Luft. Meine Alten hatten ja, ich bin ja dank ihnen Hartz-IV Empfaenger, das wird meine Mutter garantiert noch freiwillig zugeben, wie auch einiges anderes, was sie mit mir angestellt haben, was man nichtmal mit seinen Feinden macht, mir auch nahegelegt, mal Psychologie zu lernen. Die zwei sind nicht nur Zeichens ihres Berufes Alkoholiker mit derben Ausdruecken. Nein, sie haben Jahre auf mir rumgehackt. Nur was sie von mir wollten, haben sie bis heute nicht bekommen. Liegt daran, dass ich mir nichts antuen kann und so. Nun gut. Dieses Semester wird mir eine Freude sein. Denn sie haben so einiges verbrochen, was mir nichtmal im Traum einfallen wuerde. Ich bin eher der, dem was nachgesagt wird, was dann hinterher doch nicht stimmt, den das aber mitgenommen hat, weil das unverschaemt ist. Wohlan.

Diagram 2

Heute komme ich dazu. Ich hab zwar den ganzen Nachmittag verpennt. Aber jetzt habe ich Koordinaten hinzugefuegt und trenne Namen und Typen, was mir das Assoziieren von Objekten einfach macht. Man braucht nur Namen und src Property und dest Property (weglassen der dest prop zeigt auf dest name selbst) angeben. Fuer Handeingabe optimal kurz und aussagekraeftig.

(Schomal im voraus eingegeben, etwas spaeter sitzt das Diagram perfekt. Ich fange gleich erst an.)

Ich habe schon Ideen, wie man das soweit ausgestalten kann, dass man JavaScript Diagramme mit der Hand schreiben kann. Ebenso denke ich an Drag und Drop. Aber nur im kleinen, nicht im Rahmen eines fetten CASE Tools.

Oh, ref bei var, var sollte ausser eine Referenz auf eine andere Variable, natuerlich value kriegen, oder die Assoziationslinie zur korrekten Property habe ich noch nicht, sie geht nur von der rechten Ecke von src an die linke Ecke von dest. Und ich wundere mich gerade, momentan ist sie gar unsichtbar. Dabei wird sie erst nach den Objekten, die erst berechnet werden, gezeichnet, damit ich weiss, wohin ich zeichnen will, dann kann ich die Objekte naemlich kurz nachgucken im diagram hash. Ich muss noch vieles schreiben, ebenso wie function. Ich sehe, ich hab schon zwei, drei Worte mehr definiert.

Manchmal schreibe ich echt dumme Absaetze. Nach zehn Minuten und einer Bildschirmausgabe hatte ich wieder keine Lust mehr.

ready(function (e) {
    var objects = [
	{ 
	     type: "var",
	     name: "list",
	     ref: "l1",
	     x: 10,
	     y: 20,
	},
	{	
	    type: "ListNode",
	    name: "l1",
	    data: {
		item: "23.244",
	        next: "l2"
	    },
	    x: 50,
	    y: 70
	},
	{
	    type: "assoc",
	    src: "l1",
	    srcp: "next",
	    dest: "l2"
	}, 	
	{ 
	    name: "l2",
	    type: "ListNode",
	    data: {
		item: "46",
		next: "l3"
	    },
	    x: 200,
	    y: 70
	},
	{
	    type: "assoc",
	    src: "l2",
	    srcp: "next",
	    dest: "l3"
	},     
	{
	    type: "ListNode",
	    name: "l3",
	    data: {
		item: "14.1",
		next: "null"
	    },
	    x: 350,
	    y: 70
	},
	{ 
	    type: "function",
	    name: "glob_op",
	    args: ["a", "b", "c"],
	    returns: "number",
	    x: 150,
	    y: 20
	}
    ];
    var fp = new FunctionPlotter("#dia2", { width: 500, height: 200 });
    fp.dia(objects);
});
    

Ich denke mal, srcp und destp bei den associations sind noch nicht perfekt gewaehlt. Aber ich muss Object, Array, Date, etc. anzeigen, function, var (let, const schon heute), und dann die Verbindungslinien zwischen den properties, Variabeln, Instanzen und schon ist alles gut. Dieses verdammte Keyboard hakt aber, dass ich, sieht man auch auf der Seite, eher zwei als zwanzig Zeilen schreibe, was im Code eher zweihundert ausmacht. Ist gerade urschwer, einen Buchstaben rauszukriegen.

T(n)

Ich glaube, ich habe die Substitutionsmethode verstanden. Die und das Master-Theorem. 6.046j, 6.006 und 6.042 (Mathe) behandeln die Mathematik ausfuehrlich. Ich kann die schon vorwaerts und rueckwaerts pfeifen. Ich glaube, sogar schreiben. Und genau das will ich ueben. Ich werde das noch ein paar Monate lang machen.

Document Distance

Algorithmus: Fuer jedes Wort in doc1 und doc2. Q = Anzahl der Vorkomnisse in Doc 1, R = Anzahl in Doc 2, Summiere Q * R

Der Algorithmuskurs 6.006 beginnt mit einem Document Distance Algorithmus, mit dem ein Vektor zwischen zwei Dokumenten festgelegt wird, der ihre Aehnlichkeit anzeigt. In Anlehnung daran habe ich schonmal mit dem Code angefangen. Die Lektion werde ich aber wiederholen, um ihn dann zu schreiben. Die Funktionen difference und equality sind von mir. In Anlehnung ans Original sind da einige Moeglichkeiten drin. Ach, und der Prof. nutzt den Algorithmus, um Arbeiten zu kontrollieren. Ist doch cool, oder? Wer den DD Algorithmus kennenlernen will, sollte sich 6.006 angucken.

(function (global) {

    function inc_counter(word, counter) {
	var w; 
	if (typeof counter[word] === "number") counter[word] += 1;
	else counter[word] = 1;
    }

    function count_words (doc) {
	var counter = Object.create(null);
	doc.split(/\s/).forEach(function (w) {
	    inc_counter(w, counter);
	});
	return counter;
    }
    
    function equality(c1, c2) {
	var eq = Object.create(null);
	Object.keys(c1).forEach(function (k) {
	    if (c2[k]) eq[k] = c1[k] / c2[k];
	});
	return eq;
    }
    
    function difference(c1, c2) {
	var diff = Object.create(null);
	Object.keys(c1).forEach(function (k) {
	    if (!c2[k]) diff[k] = c1[k];
	    else diff[k] = c1[k] - c2[k];
	});
	Object.keys(c2).forEach(function (k) {
	    if (!diff[k]) diff[k] = -c2[k];
	});
	return diff;
    }

    function docdist(doc1, doc2) {
	var record = {};
	
	if (typeof doc1 !== "string" || typeof doc2 !== "string") throw "docdist(d1,d2)";
	
	record.count1 = count_words(doc1);
	record.count2 = count_words(doc2);
	record.difference = difference(record.count1, record.count2);
	record.equality = equality(record.count1, record.count2);
    
	return record;
    }

    Object.defineProperty(global, "docdist", { value: docdist, configurable: false, writeable: false });
    

    if (typeof exports !== undefined) {
	    var fs = require("fs");
	    var doc1 = fs.readFileSync(process.argv[2],"utf8");
	    var doc2 = fs.readFileSync(process.argv[3],"utf8");
	    console.dir(docdist(doc1,doc2));
    }
    
}(this));

/*
{ count1: { Ich: 1, bin: 1, schoen: 1, und: 1, 'toll.': 1, '': 1 },
  count2: { Ich: 1, bin: 1, gross: 1, und: 1, 'stark.': 1, '': 1 },
  difference: 
   { Ich: -1,
     bin: -1,
     schoen: 1,
     und: -1,
     'toll.': 1,
     '': -1,
     gross: -1,
     'stark.': -1 },
  equality: { Ich: 1, bin: 1, und: 1, '': 1 } }
{ count1: { Ich: 1, bin: 1, schoen: 1, und: 1, 'toll.': 1, '': 1 },
  count2: { Er: 1, ist: 1, anders: 1, '': 1 },
  difference: 
   { Ich: 1,
     bin: 1,
     schoen: 1,
     und: 1,
     'toll.': 1,
     '': -1,
     Er: -1,
     ist: -1,
     anders: -1 },
  equality: { '': 1 } }
{ count1: { Ich: 1, bin: 1, schoen: 1, und: 1, 'toll.': 1, '': 1 },
  count2: { Ich: 1, war: 1, schoen: 1, und: 1, 'stark.': 1, '': 1 },
  difference: 
   { Ich: -1,
     bin: 1,
     schoen: -1,
     und: -1,
     'toll.': 1,
     '': -1,
     war: -1,
     'stark.': -1 },
  equality: { Ich: 1, schoen: 1, und: 1, '': 1 } }
{ count1: { Ich: 1, bin: 1, gross: 1, und: 1, 'stark.': 1, '': 1 },
  count2: { Er: 1, ist: 1, anders: 1, '': 1 },
  difference: 
   { Ich: 1,
     bin: 1,
     gross: 1,
     und: 1,
     'stark.': 1,
     '': -1,
     Er: -1,
     ist: -1,
     anders: -1 },
  equality: { '': 1 } }
*/

Amortized Analysis

Heftig waer, wenn es im JavaScript Object Hashtable so abgehen wuerde, aber ich denke, die ersten 4 oder 8 Properties wird es dann bestimmt gratis geben, weil das ja unmoeglich waere, wenn man properties zuweisen will...

Table Doubling. So nennt man das verdoppeln der Tabelle, wenn ein Ueberlauf droht. Das heisst, wenn der Table beim insert dann voll oder fast ist. Ein insert in einen Hashtable liegt so bei O(1) in Python. Wenn die Tabelle aber mit einem Eintrag beginnen wuerde, und sich dann auf 2 vergroessert, dann auf 4, dann auf 8, dann wuerde gerade die Spielerei mit 0-4 Properties, oder 0-8 Properties, sehr sehr teuer werden, da staendig der Hashtable vergroessert oder verkleinert werden wuerde.

	function insert(k,v) {
	    if (size +1 === max) {
		// Doubling the Table (-1 Dollar pro Bucket)
		// resize + O(n) inserts 
		resize(size+1 * 2);
	    }
	    // insert O(1)
	    var code = h(k); // +2 Dollar pro insert (reicht fuer 1* Table Doubling)
	    table[code] = v;
	}
    

Darum legt man Hashtables in Erwartung an eine reelle Groesse von vornherein guenstig an. Ich denke, auch bei JavaScript wird das {} so viel Platz bieten, dass ich mit vielen kleinen Objektliteralen im Schnitt mit dem Zugriff praktisch konstant auf die Keys bin wie bei konstant hardgecodeten Vergleichen mit den keys.

Die Amortized Analysis beschaeftigt sich mit dem Table Doubling im Grossen und im mathematischen Sinne. Besonderheit der Anwendung. Es wird in Dollar statt in Zeit gerechnet. Und durch eine kluge Verteilung von insert, delete und resize Operationen, kann man mit den konstanten Einkuenften der Zugriffe das Geld fuer das Tableresizing aufwenden (sprich hat man dann die Zeit fuer).

	function resize(size) {
	    var oldTable = table;
	    table = new HashTable(size);
	    for (var i = 0; i < oldTable.length; i++) {
		table.insert(oldTable[i]);
	    }
	}
	
	/* Das kostet beim resize nochmal O(n) bzw. alle Dollar. Alle alten Elemente muessen
	einen neuen Schluessel fuer den neuen Table bekommen. Mitunter sind
	das viele viele Elemente, die in eine neue Datenbank eingefuegt werden
	wollen. */
    

Damals wird es um Hashtables in anderen Performancedimensionen gegangen sein. Die Analyse ist etliche Jahre alt. Aber bis heute ist Hashing eins der besten Verfahren, um Daten mit einem Schluessel zu speichern und wiederzufinden. Man errechnet aus dem Schluessel einen Code, und sollte der passende Slot belegt sein, rotiert der Code, er wird in so vielen Versuchen, wie er rotierte wiedergefunden (in der Grundlage), und es gibt Beweise und Praktiken fuer optimale Groessen und Verteilunge.

Die Amortized Analysis ist eine unterhaltsame Lehre. Sie liefert fundierte Kenntnisse und mathematische Beweise aus dem Umgang mit Hashtables. Man weiss genau, wie lange die Operationen im einzelnen brauchen. Und das kann man mathematisch bestimmt schon ab der 5. oder 6. Klasse verstehen. Jedenfalls kommt da nicht mehr vor als ein Bruch n/2 bzw. nichts schwereres.

Im weiteren hilft diese Analyse Sprachen wie JavaScript, optimal mit ihren internen HashTables umzugehen. Darum denke ich, mit um Objektliterale mit 1-8 Attributen keine Sorgen machen zu muessen, weil die Startgroesse des Hashes bestimmt optimaler gewaehlt ist.

Plotter

Oh, ich bin gestern Abend eingenickt, bevor ich herausfand, ob ich dem Context translated habe. Dabei fiel mir bereits ein, der Plotter nutzt in Zukunft einen Stack fuer contexts. Dadurch kann ich einen Plotter fuer mehrere Views nehmen. Denn die Kosten fuer die Instanz werden immer groesser.

Wenn er mehrere Views (mind. 1 je Funktion) kann, und weiter ausreift, dan irgendwann kann ich auch Subprobleme und kleine Plotter raus machen. Aber jetzt kommt erstmal der Stack/View Fix, dann kann man einen plotter nehmen und bei jedem draw Aufruf auf ein anderes Element malen kann.

	/* vorher */
    	var context;
    	
    	/* nachher */
	var contexts = [];
	function pushContext() {
	    return contexts.push(context);
	}
	function popContext () {
	    context = contexts.pop();
	    return context;
	}
    

Da macht auch das auslesen der canvasOptionen, die ich bereits anfing Sinn, weil man jeden dann gleich konfigurieren kann. Ich muss das noch verfeinern, dass alle Breiten und Farben korrekt eingestellt werden koennen, am besten, man kann sogar className angeben :-).

return this; gefaellt vielen an jQuery, dass es auch Sinn macht, weil man neue Canvas Objekte oder ViewElemente (erzeuge Canvas darin) angeben kann.

    var fp = new FunctionPlotter();
    fp.plot({ el: "#plot1", width: ... }).plot({ el: "#plot2", ... });
    

Das ist cooler, als wenn ich jetzt jedesmal ein neues FunctionPlotter Objekt erzeuge. Denn je oefter ich das Tool anwende, um so mehr Daten wuerde ich gerne schnell anzeigen.

Hier bin ich gestern abend eingeschlafen, bevor ich die zweiten fuenfzehn Minuten opfern konnte.

Diagram

Ich habe schon seit 2006 nichts mehr im Sinne vom Softwareengineering nach Elsevier (damals Spektrum) gemacht.

Ich hardcode jetzt kurz eine Funktion, die eine JSON nimmt um Objekte, Assoziationen zu zeichnen. Nicht in UML, sondern in meiner JavaScript Notation.

Das kann ich dann verfeinern, um Objektliterale, Arrays und Functions abzubilden, sowie Variablen, Pfeile und Notizen.

Die Abbildung zeigt zwei Objekte, die einseitig assoziiert sind, indem die Variable next auf das naechste Objekt zeigt. Das beschreibt zugleich eine linked list.

--

Eine Assoziationlinie ist auch gezeichnet. Ich habe inzwischen ein korrektes Objekt fuer jede Diagrammkomponente mit aktuellem Status im Kopf. Gestern habe ich die Linie einfach salopp dazwischen gezeichnet. Aber ich weiss, wo ich die Daten (x,y, aber auch Drag-und-Drop) speicher.

Und - Eingabe ist JSON statt xml, intuitiv fuer viele.

SkipLists

Auch in 6.046j dran kommen SkipLists. Das sind linked Lists, beziehungsweise mehrere, von denen die "hoeheren", in groesseren Abstaenden verlinkt sind, dass man zum Beispiel jede 100. = 10 Nodes (L4), 50. = 20 Nodes (L3), 10. = 100 Nodes (L2), 5. = 200 Nodes (L1), alle 1000 (L) Nodes ansteuern kann. Man kann dabei lineare Suchgeschwindigkeiten unterschreiten, indem man durch kluge Entscheidung viele Elemente der Liste (L) ueberspringt.

Im 6.046j kommt das Beispiel New Yorker U-Bahn, die local line und xpress line per SkipList verbindet, dran. Ob die BVG das mit dem TXL und dem 123 so auf unserer Strecke macht? Ich denke nicht. Die haben ihre eigenen Graphen, Listen, Bäume, PriorityQueues, das ist sicher. Aber das ist ein fantastisches Beispiel komplexer Software, die auf vernuenftige Linked List zurueckgreift.

Habe in etwa sowas Code wie beim Redblack Tree angefangen. Code kommt, wenn er mit nem Beispiel laeuft.

OCW Scholar

Einen Überblick über die Selbstlernerkurse habe ich mittlerweile auch.

Die Mathefakultaet habe ich "leergezogen" (den April mit 6.6k und den Rest mit den 5GB fuer Mai) und werde ich machen, aber auch die Faecher Psychologie, Solid State Chemistry, und Microeconomics (hatte ich viele deutsche dtv, Vahlen, Schaeffer-Poeschel, wrw frueher) tun es mir genau so an.

Ich denke, im naechsten Monat komme ich zu Physik I + II + III. Angucken, anwenden dauert etwas laenger.

Im 6er Department (EECS) habe ich ein paar Vorteile, weil ich die Informatiklektionen meist schonmal gelesen hatte, als ich juenger war. Dennoch bin ich sicher, mit Electronics und Circuits und erst recht mit Signals und Systems noch was fuers Leben zu lernen.

Ich denke, hier kann ich studieren, bis ich 40 bin. Und dann kann ich das mal richtig machen. Bis dahin werde ich aber wohl auch HTML5 gelernt haben.

Aufgaben

Damit ich das auf dem Schirm hab.

Ich muss noch mit den Dreiecken weitermachen

Ich hab noch ein paar Probleme mit den Winkelfunktionen.

Vermutung Also ich bemerke den gesuchten Fehler. Ich habe es vom falschen Winkel aus berechnet. Der Winkel, in dem die Hypothenuse den Mittelpunkt des Kreises, gemessen an der x Achse, schneidet, den habe ich verwendet. Ich wollte aber damit nur die Anpassung der Koordinaten um jeweils ihren Sinus und Kosinus. Das Dreieck, das muss ich mit den Winkeln des Dreiecks berechnen.

Vermutung Darum der Fehler. Ich bin einfach nicht drauf gekommen. Jetzt habe ich gerade das Objekt uebergeben, die Winkel ausprobiert, und mir war klar, was ich definitiv falsch machte. Denn der Alpha Winkel des Dreiecks, bei Gamma = 90°, der ist gar nicht mehr in der Formel drin. Die Koordinaten werden falsch berechnet. Darum liegt das nicht auf dem Kreis, sondern ist nur ein Dreieck. Ein in zwei Beziehungen vom Winkel abhaengiges Dreieck, von dem Winkel von der x-Achse ab, mit dem die Hypothenuse durch M vom r des Kreises geht.

Asymptoten

Ich glaube ich habe das mit dem Weglassen der Konstanten und niederen Terme verstanden. Die Multiplikation mit der Konstante habe ich nun x-mal wiederholt. Ich glaube, hier liegt eine Ordnung von O(n), gar Θ(n) vor, da sich mit c bzw. d sowohl Ober-, als auch Untergrenze finden lässt.

Ich muss es nur noch nichtig beschriften (und noch ein paar mal lernen). Zur Zeit ist es das folgende Objekt. Davor hatte ich noch T, O, Omega (weiter unten oder April). Inzwischen habe ich ein wenig dazugelernt, daß ich es mir zumindest anders wünsche.

    fp.compare_asymptotes({
	n: Math.pow(2, 4),
	scale: 10,
	prec: 0.1,
	f: function (n, N) {
	    return 2* n;
	},
	g: function (n, N) {
	    return n;
	},
	c: 2.1,
	d: 1.9
    });

Idee fuer die automatische Analyse. Wenn ich C neu waehle, und sie N uebersteigt, dann aendert sich der Test von O(N) dann zum Test auf O(N^2). Und umgekehrt bei C < N^-1. Und so aehnlich. Muß ich mir mal weiter ausdenken, ob das geht.

Binary Trees: Red Black Trees

Das wird mal ein Red Black Tree mit function recolor (x) {}

Wenn man in den folgenden BST jetzt 1..10 einfuegt gibt es einen O(n) "Baum" mit height n statt lg n, weil das eigentiche rot-schwarze noch nicht drin ist. Ich bin mir nicht sicher, ich glaube anhand meine Faerbung und Hoehe verbiete ich die Aufnahme der neuen Keys. Ich hab die paar Minuten ueberhoert. Hehe. Aber das laest sich nachholen. Stimmt. Es sind Erweiterungen von BST-insert und BST-remove, wo LEFTROTATE, RIGHTROTATE und RECOLOR und ein Coin zu flippen beim Colorieren. In jedem Fall balanciert er durch Rotation.

Fuer O(n) Hoehe kann man beim BST entweder einen un(!)sortierten Array einfuegen, oder den sortierten in zufaelliger Reihenfolge und dann mit inorder arbeiten. BST-insert ist so auch als Randomized-BST-insert oder der Baum ueberhaupt als Random-BST bekannt. Auf das zufaellige Einfuegen bei geordneten Keys bin ich auch bereits gekommen, weil ich ebenfalls diesen O(n) Baum bemerkt habe, der so hoch ist, wie es Elemente gibt.

Der naechste Baum ist was anders. Jetzt fehlen die RB-Eigenschaften aber noch komplett, die eine ist, dass er wohl immer die Hoehe lg n hat. Ich muss die Lektion nochmal gucken. Dann praesentiere ich diesen Code mit RB-Eigenschaften in einer laufenden Fassung.

function RedBlackTree () {
    "use strict";
    
    var BLACK = "BLACK";
    var RED = "RED";
    // var NIL = null; 
    
    var LeftArrow = "\u2190";
    var RightArrow = "\u2192";

    var root = null;
    
    var NIL = new RedBlackNode(null, null, null, null, null, BLACK);
    NIL.parent = NIL;
    NIL.left = NIL;
    NIL.right = NIL;

    function RedBlackNode (k, v, p, l, r, color) {
	if (!(this instanceof RedBlackNode)) return new RedBlackNode(k,v,p,l,r,color);
	this.parent = p || null;
	this.key = k !== undefined ? k : null;
	this.value = v !== undefined ? v : null;
	this.color = color || RED;
	this.left = l || null;
	this.right = r || null;
	return Object.seal(this);
    }
    
    function size (node) { // alle mit node selbst
	if (!node) return 0;
	return size(node.left) + size(node.right) + 1;
    }
    
    function height (node) {
	if (!node) return 0;
	return Math.max(height(node.left), height(node.right)) + 1;
    }
    
    function insert_node (k,v,node) {
	if (!node) return null;
	if (node.key === k) {
	    return null;
	}
	if (k < node.key) {
	    if (node.left) return insert_node(k,v, node.left);
	    else node.left = new RedBlackNode(k, v, node, null, null, RED);
  	    insert_fixup(node.left);
	    return node.value;
	} else if (k > node.key) {
	    if (node.right) return insert_node(k,v, node.right);
	    else node.right = new RedBlackNode(k, v, node, null, null, RED);
	    insert_fixup(node.right);
	    return node.value;
	}
	return null;
    }
    
    function insert_fixup (z) {
	    var y;
	    var p, q;
	    while (z && (p = z.parent) && p && p.color === RED) {
		q = p.parent;
		if (q && p === q.left) {
		    y = q.right;
		    if (y && y.color === RED) {
			p.color = BLACK;
			y.color = BLACK;
			q.color = RED;
			z = q;
		    } else {
		    if (z === p.right) {
			    z = p;
			    leftrotate(z);
			    if (z.parent) z.parent.color = BLACK;
		    } //else { 
		    p.color = BLACK;
	    	    q.color = RED;
		    rightrotate(q);
		//    }
		    }
		} else if (q && p === q.right) {
    		    y = q.left;
		    if (y && y.color === RED) {
			p.color = BLACK;
			y.color = BLACK;
			q.color = RED;
			z = q;
		    } else {
		     if (z === p.left) {
			    z = z.parent;
			    rightrotate(z);
			    if (z.parent) z.parent.color = BLACK;
		    } // else {
		    p.color = BLACK;
		    q.color = RED;
	    	    leftrotate(q);
	    	//    }
	    	    }
		} 
	    }
	    if (root) root.color = BLACK;
    }
    
    function insert (k,v, node) {
	node = node || root;
	if (!root) {
	    root = new RedBlackNode(k,v, null, null, null, BLACK);
	    return root.value;
	} else {
	    return insert_node(k,v, node);
	}
    }
    
    function black_height2 (x) {
    	if (x === null) return 1;
	if (x.color === RED) return Math.max(black_height2(x.left), black_height2(x.right));
	if (x.color === BLACK) return Math.max(black_height2(x.left), black_height2(x.right)) + 1;
    }
    
    function black_height (x) {
	if (x === null) return 0;
	return Math.max(black_height2(x.left), black_height2(x.right));
    }
    
    
    function rightrotate (x) {
	if (!x) return;
	var p = x.parent;
	if (!p) return;
	var q = p.parent;
	var B = x.right;
	if (q !== null) { // case root
	    if (q.left === p) q.left = x;
	    else if (q.right === p) q.right = x;
	} else {
	    return;
	}
	x.parent = q;
	p.parent = x;
	x.right = p;
	p.left = B;
	if (B) B.parent = p;
    }
    
    function leftrotate (p) {
	if (!p) return;
	var x = p.parent;
	if (!x) return;
	var q = x.parent;
	var B = p.left;
	if (q !== null) { // case root
	    if (q.left === x) q.left = p;
	    else if (q.right === x) q.right = p;
	} else {
	    return;
	}
	p.parent = q;
	x.parent = p;
	p.left = x;
	x.right = B;
	if (B) B.parent = x;
    }
    
    
    
    function remove_node (n) {
	var p = n.parent;
	return n.value;
    }
    
    function remove_fixup () {
    }
    
    function remove (k, node) {
	var n = find_node(k, node);
	if (n) return remove_node(n);
	return null;
    }

    function find_node(k, node) {
	node = node || root;
	for (;;) {
	    if (k === node.key) return node;
	    if (k < node.key) {
		if (node.left) { node = node.left; continue; }
		else return null;
	    }
	    if (k > node.key) {
		if (node.right) { node = node.right; continue; }
		else return null;
	    }
	}
	return null;
    }
    
    function find (k) {
	var node = find_node(k);
	if (node) return node.value;
    }
    
    function replace_value(k,v,node) {
	if (!node) throw "replace_value";
	if (node.key === k) {
	     var oldvalue = node.value;
	     node.value = v;
	     return oldvalue;
	} 
	return null;
    }
    
    function replace(k,v, node) {
	var record = find_node(k,node);
	if (record) return replace_value(k,v,record);
	return null;
    }
        
    
    function inorder(f, node) {
	node = node || root;
	if (!node) return;
	if (node.left) inorder(f, node.left);
	if (typeof f === "function") f(node.key, node.value, node.color, size(node));
	else throw "inorder function fails";
	if (node.right) inorder(f, node.right);
	return true;
    }
    
    function print () {
	return inorder(function (k, v, c, s) {
	    console.log("+ node: key="+k+", value="+v+", color="+c+", size="+s);
	});
    }
    
    function draw (context) {
    
	function open () {
	    context.save();
	    context.beginPath();
        }
	function close() {
	    context.closePath();
	    context.restore();
        }
        
	function drawerse(node, x, y, px, py, l) {
	    var r, s;
	    
	    if (node === null) {
	    	r = 5;
	    	
	    	// NIL
	    	open();
	    	context.strokeStyle = "black";
	    	context.fillStyle = "black";
	    	context.rect(x-10, y-2, 20, 4);
	    	context.fill();
	    	close();
		if (px != undefined && py != undefined) {
		    open();
		    context.lineWidth = 0.5;
		    context.strokeStyle = "darkblue";
		    context.globalCompositeOperation = "destination-over";
		    context.moveTo(x,y);
		    context.lineTo(px,py);
		    context.stroke();
		    close();
		}
	    	
	    } else {

		r = 10;
		var color = node.color;
		open();
	        context.strokeStyle = color === RED ? "brown" : "darkgrey";
		context.fillStyle = color === RED ? "red" : "black";
		context.arc(x,y, r, 0, 360);
		context.fill();
		close();
		
		open();
		context.fillStyle = color === RED ? "black" : "white";
		context.strokeStyle = color === RED ? "lightred" : "lightgrey";
		context.fillText(node.key, x, y, 20, 15);
		context.fill();
		close();
		if (px != undefined && py != undefined) {
		    open();
		    context.lineWidth = 0.5;
		    context.strokeStyle = "darkblue";
		    context.globalCompositeOperation = "destination-over";
		    context.moveTo(x,y);
		    context.lineTo(px,py);
		    context.stroke();
		    close();
		}
		if (node.left) s = 50; else s = 20;
		drawerse(node.left, x - fullw/(fullsize*l) , y + s, x,y, l+1);
		if (node.right) s = 50; else s = 20;
		drawerse(node.right, x + fullw/(fullsize*l), y + s, x,y, l+1);
	    }
	}
    
	if (!context || context.canvas instanceof HTMLCanvasElement === false) throw "context err";
	var fullw = context.canvas.width;
	var fullh = context.canvas.height;
	var fullsize = size(root);
	var fullht = height(root);
	var blackheight = black_height(root);
	var size_str = "not rb: nodes != null => " + fullsize;
	var ht_str = "not rb: full height without nullptrs => " + fullht;
	var bh_str = "RB black_height with null-leaves but no root => "+ blackheight;
	
	var li = 15;
	var lh = 15;
	var r = 10;

	open();
	context.lineWidth = 1;
	context.strokeStyle = "darkgreen";
	context.fillStyle = "green";
	context.fillText("RedBlackTree", 0, li, fullw, lh);
	context.fillText(size_str, 0, li+=lh, fullw, lh);
	context.fillText(bh_str, 0, li+=lh, fullw, lh);
	context.fillText(ht_str, 0, li+=lh, fullw, lh);	
	context.fill();
	close();
	drawerse(root, Math.floor(fullw / 2), 11, undefined, undefined, 1);
    }

        
    var me = this;
    me.insert = insert;
    me.remove = remove;
    me.replace = replace;
    me.find = find;
    me.inorder = inorder;
    me.print = print;
    me.draw = draw;
    me.black_height = function () { return black_height(root); };
    me.size = function () { return size(root); };
    return Object.freeze(me);
}
/*
var tree = new RedBlackTree();
tree.print();
for (var i = 1; i < 20; i++) tree.insert(i);
tree.print();
*/

Es wird noch ein Weilchen dauern, bis das ein Redblacktree ist. Aber auch diesen sollte man mal ausprobieren. Moeglicherweise kann man ihn einsetzen. Ausserdem hilft sein seltsames Design, das Design von Bäumen zu verstehen.

Das war jetzt BST insert in 30 Sekunden, oder BST find in 30 Sekunden programmiert, aber den 2. Level habe ich noch nicht. Vollstaendig kann ich das erst, wenn ich sie auch aus dem FF balancieren kann. So in 3-4 Varianten, AVL, Splay und RB, und 2-3-4 zum Beispiel.

Tierarzt

Samstag war ich mit Racker da, heute am Montag fahren wir nochmal. Alles in Ordnung. Sogar viel besser, als ich erst dachte. Wir waren um 21 Uhr wieder zuhause, dabei waren wir schon um 14 Uhr da. Das war ein toller Ausflug für mich. Gestern war Racker auch total gut gelaunt. Ich freue mich schon auf den Nachmittag, denn die Praxis ist einsame Spitze.

Natürlich vergesse ich jetzt kurz was zu coden und amüsiere mich so. Von 6.046j schleicht die vorletzte Lektion auf meine Platte. Alles ist im Lot. Für meine soziale Situation quasi hervorragend.

Parser

Wo ich auf den Schnittkonstanten object[key] glotze, sehe ich aber auch Funktionen, in denen if (ch === "A" || c === "B") vorkommt, die quasi je konstant sind. Ich denke, hiermit kann man ein paar object[key] Zugriffe noch auf kleineren Code, die aktuelle Variable zu vergleichen, bringen. Das wird wohl dann noch cheaper sein.

Was vernuenftiges, das gesamte Programm betreffend, erhalte ich aber auch nur, wenn ich die Generierung der Spans und das Einfuegen aller anderen Elemente auch ueberarbeite. Tokenizer und Scanner sind aber zwei voellig unabhaengige Komponenten im Code, dass man sie jederzeit ohne den Highlighter einsetzen kann. Man kann sie praktisch mit Copy + Paste in ein eigenes Modul verwandeln. Bei denen habe ich wie sonst auch dran gedacht.

Plotter

Der Plotter ist hingegen eine durcheinandergeratene Sammlung von Funktionen geworden, aber ich Gedenke, als naechstes anstatt O, T und Omega einfach c, n0, f(n) und g(n) zu verwenden und das richtig zu beschriften und zu bounden. Jetzt sehe ich die Beschriftung mit O, T und Omega schon als falsch an. Jedenfalls muss man da was richtiges Eintragen, mit c, n0, f(n) und g(n) kann man das aber bereits richtig angeben, dass man es ablesen kann. Das Weglassen von niedrigeren Termen und den Konstanten fuer die O Bezeichnung kann man mit O(g(n)) statt mit function O dann auch nachvollziehbar zeigen. Kann man doch so nachvollziehen, oder?

Die Analyse dann Heiter bis SWT..

Hier ist also das options Objekt neu zu formulieren, und dann natuerlich der Programmablauf. Nervig waere das, wenn ich fuer das Stueckchen Code erstmal einen Programmablaufplan zeichnen muesste. Darum verzichte ich auf Notationen. Aber richtig ist, ein Drag-und-Drop-Diagramm-Tool, mit Codegenerator, das waere mal wieder eine Steigerung. Den Parser kann man da auch gebrauchen und einbauen, da muss man nicht alles doppelt schreiben.

Oder nicht ganz so ernst.

Shortest Path

Graphentheorie. Der kürzeste Pfad ist die kleinste Summe ∑ aller Gewichte w der Edges E im Graphen G = {V,E}, zwischen dem Knoten u (Start) und v (Ziel). Der Dijkstra Algorithmus behandelt positive Integer. Der Bellmann-Ford Algorithmus kann auch negative Zahlen. Einfache Mathematik aber abstraktes Beispiel Integer.

Klingt schwer? Gut. Ich stelle mal meine Vereinfachung vor. Wir stellen uns die Gewichte als richtige Strecken und Pfade als richtige Gesamtstrecken vor. Die Edges haben Gewichte wie 1km, 2km, 3km, oder auch -3km, was einen Umweg auf der Gesamtstrecke von -3km signalisiert.

Parser

Vorher hatte ich es geschafft, aus reiner Faulheit, Objektliterale zu nutzen, mit einem Array.indexOf() auf eine EXTRA-Suche um jeweils O(n) PRO keyword gebracht. Ich glaube, ich weiss jetzt, was Array.indexOf(keyword) kostet. O(n). Jedesmal neu bis zum jeweiligen Keyword durchzulaufen, oder ganz und -1 returnen. Vermutung: object[key] ist schneller. Moeglicherweise genausoschnell, aber das ist vermutet, wie ein array[0], wenn der [0] der gleiche HashingAlgorithmus zu Grunde liegt wie dem object[key], es handelt sich um JavaScript. Behauptung: Im Schnitt (on average) erreiche ich mit object[key] quasi konstante O(1) Zeit um das Keyword zu finden und abzugleichen auf einem dann bereits in O(n) laufenden Tokenizer/Parser.

var keywords = [ "if", "else" ];
if (keywords.indexOf("else") > -1) {}

Gestern: Als ich gerade meinen ersten Strukturen von Array nach Objekt aenderte, war ich zuversichtlich. Gerade habe ich die anderen Funktionen gesehen, fuer die einzelnen Operatoren. Ich denke, ich lerne meinen Teil aus der Algorithmenklasse gerade. Denn ich koennt den unendlich optimieren. Das wird genaugenommen einige Stunden (oder eine oder zwei reines umschreiben) dauern. Mit der klemmenden Tastatur und dem lahmen Rechner aber noch eine bis drei länger. Der Code ist lang und der Editor wird langsamer.

var keywords = {
    "if":true,
    "else":true
};
var punctuators = {
    "=":true,
    "==":true,
    "===":true,
    ...
};
var whitespaces = {
    "\u000a":true,
    "\u000d":true,
    "\u2028":true
};

if (keywords["else"]) {}
    

Anstelle von punctuators.indexOf("===") > -1 compute ich in Zukunft noch punctuators["==="]. Wenn ich jetzt die Engine dahinter schreiben wuerde, &implies; wuerde ich die Behauptung und wahrscheinlich die Vermutung erfuellen (Und diese implikation ist richtig, weil ich die Engine nicht geschrieben habe/schreiben würde).

Ich glaube das Ding ist bereits sichtbar schneller. Die grossen alten JavaScript Dokumente schleichen nicht mehr. Das Einfuegen der Elemente im DOM und das sich verlaengernde Dokument geht deutlich schneller auf meinem alten Rechner, aber springen tut so ein langes Dokument trotzdem.

Das Menue muesste zum Beispiel als Overlay Feld und Menue designt werden, dass sich die Laenge nicht mehr veraendert. Sowas kann man da machen. Anderseits war das auch nur eine Idee und kein geplantes Program. Auf Blatt Papier nach Lehrbuch habe ich vor zehn Jahren versucht. Heute spiel ich mal mit ner Idee rum, dieses "oh ich habe ein geiles Softwareengineeringbuch gelesen" Image habe ich vor ein paar Jahren mit der letzten Wohnung verloren, als ich ein halbes Jahr kein Hartz IV kriegte und meine reichen Eltern nicht einlenkten, sondern die Folge mitprovozierten. Die Bücher mußte ich alle stehen lassen. Meine Eltern habe ich später aus entsprechenden Gründen dann auch verlassen. Die Geschichte erzaehle ich uebrigens als MC Edwin Hold von Zeit zu Zeit.

Tastatur

Die neue Billigtastatur hakt nach ein paar Anschlägen schon stärker als die alte!!! Muß ich wohl auf den Scheck warten, bis ich wieder programiere.

Workflow

Klemmende Tasten. Diese Tastatur hatte 2,99EUR gekostet. Ich schliesse die andere wieder an. Ich muss jeden 2. Buchstaben doppelt mit festem Aufdruck wiederholen. Ich hab damit nichtmal diese Frontpage neu schreiben koennen, und habe das gleiche noch mit /hiphop vor.

Samstag. Ich fahre mit Racker zum Tierarzt. Vielleicht hoere ich mir unterwegs 6.046j im MP3-Player an. Kommt auf Racker an. Davon gibt es Audio. Ich habe die Asymptoten, sowie das korrekte weglassen von Konstanten und lower-order terms zur Errechnung der Big O Formel jetzt 100% begriffen. Ist gar nicht schwer.

Sobald ich neue Tasten habe, mache ich aber mit dem Parser weiter. Die Regex Grammatik fehlt noch und die Korrektur, alle keywords.indexOf(token) und /key|word|if|else/.test(token) eliminieren (es macht den Parser quadratisch). Und einiges andere, um es fast (schnell) zu machen, hardcoden (siehe function probe()). Oder heute abend (hehe, ich hab schon lange Bock drauf, weiter zu coden).

Schon in ein paar Tagen geht es weiter mit Grafiken, ich bin mit den Dreiecken doch noch nicht fertig. Die letzten liegen nicht auf dem Einheitkreis. Ich hab da noch voll Spass dran.

6.046j

Noch eine Introduction to Algorithms?

Jawohl. Die Dritte. Diese ist vor allem mathematiklastig. Und auch als Audio für unterwegs verfügbar. Da kann man dann genau zuhören, habe ich mit Lektion 2 schon gemacht und mir die Big O Notation endlich auswendig gelernt. Mit passenden Konstanten c so dass c * f(n) &LessSlantEqujal; g(n). und so.

Lil O und Klein Omega (ℴ und ω) sind nicht nur < oder > c * f(n), sondern auch so definiert, das es fuer ALLE c gilt und nicht nur ausgesuchte, wie bei O und Ω moeglich ist.

Das wird gleich noch richtig schwierig (sieht nur aus, zum wiederholen sind die Audios gut fuer morgens auf den Weg). Randomized Quicksort und Randomized Select werden analysiert. Was ich jetzt weiss ist, wie ich das k-te Element finde.

War schon am überlegen aufzustehen, und randomized Quicksort und Randomized Selection Sort zu schreiben. Randomizd heisst, dass der Pivot zufaellig gewaehlt wird.

Ich will mein angefangenes Dokument irgendwie auch fortsetzen. Das war vor zwei Monaten, als ich CS61B und 6.006 nacheinander gemacht (<=>mit Algorithmen angefangen, vor zehn Jahren hatte ich ein Buch darüber, Algorithmen in C) hatte. Und natürlich gehoert das zu neinen Favoriten. Vor allem die Analyse meiner eigenen ist mir dadurch bereits sehr sehr nahe gekommen. Ich werde einiges lassen, zum Beispiel "in syntax.js und Array.indexOf(key) statt object[key]".

Noch eine Introduction to Algorithms.

Hartz IV

Oh dieses Arbeitsamt. Nicht nur, daß sie vergassen, meinen Scheck überhaupt loszuschicken.

Anstatt mir das Geld auszuzahlen, haben wir einen Abschlag bekommen, den wir uns dann geteilt haben. Die Mitarbeiterin hatte mir versprochen, daß der Scheck dann bis Mittwoch da ist. Ist er nicht.

War ja auch logisch. Seit wann schaffen die es in drei Werktagen?

Benchmark

Kurz was unsinniges, bevor ich wieder bei der Sache bin. Ich wollte dem Plotter noch was zum benchmarken beibringen. Ich hab dann was eingehackt, was meiner eigentlichen Idee, die Messung in der zu messenden Funktion durchzufuehren (measures.push(Date.now())), nicht nachkommt, aber auch einen verblueffenden Graphen zeigt.

ready(function (e) {
    var fp = new FunctionPlotter("#bench", { width: 400, height: 400 });
    fp.benchmark({
	length: 100,
	scale: 25,
	prec: 1,
	functions: [
	    function () {
		var a;
		for (var i=0;i < 100;i++) {
		    a = [].slice.call(arguments);
		}
	    },
	    
	    function () {
		var a;
	    	for (var i=0;i < 100;i++) {
	    	    a = [];
		    for (var j =0, l=arguments.length; j < l;j++) {
			a.push(arguments[i]);
		    }
		}
	    }
	]
    });
});

OpenCourse

Ich hab jetzt acht Mathesemester (alle) (plus Zusatzmaterial, wie Highlights of Calculus (a Big Picture)), die kann ich gar nicht auf einmal machen. Das Gucken von Physik I, II, III werde ich diesen Monat nicht mehr schaffen. Aber darauf freue ich mich, wie auf die anderen Courses, die da offen sind. Ich hab jetzt erstmal zu tun, durch die Mathematik durchzukommen.

Achso, 6.033 habe ich erst gestern entdeckt. Computer Systems Engineering beginnt mit dem Linker. So konnte ich von der symtab direkt bis text, rodata, data, symtab neu ordnen. Der Kurs wird noch interessant.
Ich vermute, danach werde ich wieder C/C++ probieren, wie frueher. Denn auch JS "only" wird irgendwann wieder (leicht) zu wenig, zu langweilig, auch weil man seine JS Engine in C++ schreiben sollte. Oder was anderes.
Der Linux Kernel war frueher ein Hobby. Ich hatte Addison-Wesley und O`Reilly Bücher wie Linux Kernelprogrammierung, Understanding the Linux Kernel, Linux Device-Drivers. Ich glaube zwar nicht, da noch reinzukommen. Aber es war mal noch alles offen. Vor ein paar Jahren. Nur hatten meine Alten meine Zukunft da bereits beschlossen.

Jetzt muss ich erstmal Mathe nachholen. Der Plotter kann noch keine Benchmarks und fuer die ersten Versuche der Differentiation habe ich Verbesserungen, weil ich es ein wenig besser verstehe, als an dem Tag.

Matrix Laboratory

Neben der Matrize mit den fixen Attributen ist mir nun noch die mit dem Array eingefallen, sie ist dynamisch und man kann rows: und cols: angeben. Den Rest erledigen Algorithmen. Damit meine ich aus Kontrollstrukturen wie for zusammengesetzte (meist hoffentlich) lineare Operationen auf dem Array.

In 18.06SC Lineare Algebra gibt es eine Menge ueber Matrizen zu lernen. Das Loesen von linearen Gleichungen ist das wichtigste, was Matrizen koennen, oder?

/*

    Mat4x4 (Anriss)
    Umstaendliche Variante.
    Benutzt je ein definiertes Attribut pro Determinante.
    Jede Zahl wird einzeln zugewiesen.
    Parameter sind explizit.
    Der Construtor kann dank der instanceof Zeile aber noch 
    mit apply gerufen werden und uebergibt dann selbst explizit an new.
    Jedenfalls muss man so jede Matrix einzeln schreiben.
    Darum habe ich mir was neues ausgedacht.

*/

function Mat4x4 (a1,a2,a3,a4, b1,b2,b3,b4, c1,c2,c3,c4, w1,w2,w3,w4) {
    "use strict";
    if (this instanceof Mat4x4 === false) {
	return new Mat4x4(a1,a2,a3,a4,b1,b2,b3,b4,c1,c2,c3,c4,w1,w2,w3,w4);
    }
    this.set.apply(this, arguments);
    return Object.seal(this);
}
Mat4x4.prototype = Object.freeze({
    constructor: Mat4x4,
    set: function(a1,a2,a3,a4,b1,b2,b3,b4,c1,c2,c3,c4,w1,w2,w3,w4) {
	this.a1 = a1; this.a2 = a2; this.a3 = a3; this.a4 = a4;
	this.b1 = b1; this.b2 = b2; this.b3 = b3; this.b4 = b4;	
	this.c1 = c1; this.c2 = c2; this.c3 = c3; this.c4 = c4;
	this.w1 = w1; this.w2 = w2; this.w3 = w3; this.w4 = w4;			
	return this;
    }
    
});

/*
    Matrix (Anriss)
    
    benutzt eine rows und cols property.
    und einen typed array (ansagbar)
    und liest speichert mit index-algorithmen.
    Parameter sind direkt Arrays. Oder ein Options Objekt, mit mehreren Angaben.
    Was besser ist als Parameter, deren Reihenfolge sich keiner merken kann.
    Vielleicht ist Float64 zu gross fuer die meisten defaults, aber das kann ich
    nicht feststellen, keiner nutzt die ;-)
*/


function Matrix (options) {
    "use strict";
    if (!(this instanceof Matrix)) return new Matrix(options);
    if (typeof options !== "object") throw "options object {rows,cols[,d]} expected";
    if (!options.rows) throw "rows: missing";
    this.rows = options.rows;
    if (!options.rows) throw "cols: missing";
    this.cols = options.cols;
    this.d = options.arrayType ? new options.arrayType(this.rows * this.cols) : new Float64Array(this.rows * this.cols);
    Object.freeze(this);
    if (options.d) this.set(options.d);
}
Matrix.prototype = Object.freeze({
    constructor: Matrix,
    set: function (d) {
	if (Array.isArray(d[0]) || d[0].length) {
	    /* [
		[1,0,0]
		[0,1,0]
		[0,0,1]
		] */
	    for (var r = 0, l = this.rows; r < l; r++) {
		for (var c = 0, m = this.cols; c < m; c++) {
		    this.d[r*m + c] = d[r][c];
		}
	    }
	} else {
	    /* [1,0,0,0,1,0,0,0,1] */
	    for (var i = 0, l = this.rows * this.cols; i < l; i++) {
		this.d[i] = d[i];
	    }
	}
	return this;
    }
});

var m = new Matrix({ rows: 2, cols: 2, d: [[1,0],[0,1]] });
console.dir(m);

/*

{ rows: 2,
  cols: 2,
  d: 
   { '0': 1,
     '1': 0,
     '2': 0,
     '3': 1,
     BYTES_PER_ELEMENT: 8,
     get: [Function: get],
     set: [Function: set],
     slice: [Function: slice],
     subarray: [Function: subarray],
     buffer: 
      { '0': 0,
        '1': 0,
        '2': 0,
        '3': 0,
        '4': 0,
        '5': 0,
        '6': 240,
        '7': 63,
        '8': 0,
        '9': 0,
        '10': 0,
        '11': 0,
        '12': 0,
        '13': 0,
        '14': 0,
        '15': 0,
        '16': 0,
        '17': 0,
        '18': 0,
        '19': 0,
        '20': 0,
        '21': 0,
        '22': 0,
        '23': 0,
        '24': 0,
        '25': 0,
        '26': 0,
        '27': 0,
        '28': 0,
        '29': 0,
        '30': 240,
        '31': 63,
        byteLength: 32 },
     length: 4,
     byteOffset: 0,
     byteLength: 32 } }
*/

Wie man sehen kann, beginnt die zweite Matrix dynamisch. Die enstsprechenden Transpose und Invertfunktionen kann man algorithmisch schreiben. Die Codeterminanten oder wie die hiessen, die kann man auch berechnen. In dem Kurs Lineare Algebra gibt es eine Menge Operationen, die man implementieren kann zu lernen. Und wenn man zum Beispiel Computergrafik berechnen will, braucht man einige Grundlagen daraus.

Wenn man damit Grafikkoordinaten verrechnen will, stelle ich mir das so vor, dass ich gfx.skewY(vertices, deg(20)) schreibe und dann intern die entsprechende Berechnung mit jedem Punkt durchgefuehrt wird. Intern wird eine der Matrizen verwendet und dann durch alle vertices durchgeroutet. Nicht ueberall brauche ich dabei die Matrix, aber manchmal schon. Sie ist aber als System zur Loesung von Gleichungen gedacht.

Dem Canvas sollte ich das Visualisieren der Gleichungen beibringen, so wie sie an der Tafel stehen.

Updating im Mai

Jetzt schreibe ich viele Section Tags.

Das php Script, was in das Index Template eine handvoll Files einsetzt, das liegt seit ich dieses php/mysql Dokument letztes Jahr geschrieben hab ungenutzt rum.


<?
    $app = new Application("commentsapp", "comments");
?>

Beim Starten from Scratch werden andere Anforderungen an das Skript bewußt;. Im uralten Dokument lamp.php probiere ich den Datenbankzugriff, nachdem ich die gelöscht hatte. Es waren nur alte unbenutzte Installationen von Blogs, Wiki, Foren. Spammer hatten das alte Forum lahmgelegt, und weil der Abuse Alarm losging, habe ich nach ein paar Stunden schwitzen, was denn los sei, die Datenbank geloescht. Leider hatte mich die Lust auf PHP (obwohl ich die Sprache super finde) direkt wieder verlassen.

var x = 10, y = 11;
var z = {x,y};
JSON.stringify(z);

Mich hatte die Lust, JavaScript zu lernen gepackt. Das lässt mich auch heute nicht los. Wenn man auf ToValue(ast) klickt, fuehre ich erst den Tokenizer, dann den Parser aus. Der Parser baut aus den Tokens einen AST. Und dann fuehrt ToValue(ast) den AST aus. Heraus kommt das stringifizierte Objektliteral, was ich bereits der EcmaScript 6 Spezifikization entnahm. Wie man sieht, schreibe ich {x,y} statt {x:x,y:y}. Wenn man auf eval im Browser klickt, gibt es in einem ES5 Browser von heute einen SyntaxError.

Keine Sicherheitslücke, sondern das aktuelle Objektliteral. EcmaScript 6 ist für nächstes Jahr bereits geplant, und am Ende dieses Jahres wird eine fast fertige Spezifikation vorgestellt, die nächstes Jahr dann bereits zum neuen Standard wird.

Und das Destructuring Assignment, von dem bereits geredet wird, wird eines der fettesten neuen Features der Sprache, um viele lange Zeilen Code zu vermeiden, denn man spart sich das doppelt und dreifache Zuweisen von Variablen, dadurch, dass man sie in einem Schritt rausholt oder einsetzt und die Variablen dazu gleich mit erzeugt. {x,y} ist gegenüber {x:x,y:y} eine Vereinfachung. Aber das ist noch nichts.

Parser Komplexität

Dennoch hatte mich das JavaScript Fieber so sehr gepackt, dass ich einen ersten Parser schrieb. Das war im Januar. Am Ende des Februars und den Maerz habe ich dann Datenstrukturen und Algorithmen gemacht. Das Dokument dazu ist nur noch nicht so fertig. Dadurch konnte ich mittlerweile die Komplexität des Parsers ermitteln. Ich fasse mich kurz, das computen von object[key] ist im Schnitt am guenstigsten und [].indexOf(key) und /(Reg|Exp)/.test(key) verlieren hier beide.

Der Graph zeigt eine Komplexitaetsanalyse, aber es geht noch besser. Also in CS61B habe ich bereits f(n) ∈ O(g(n)) kennengelernt. Und auch, dass man mit der Konstante c in der Form c * g(n) eine Obergrenze für f(n) festlegt. Diese Obergrenze nennt man O (Order, O von, Big O, in der Ordnung von). Zum Zeichnen von T(n) oder f(n) habe ich selbige einfach angegeben. Die Form der Konstante C wird hier aber nicht beachtet. Beim ersten Versuch hatte ich C * n bzw 1/2C * n in O und Omega ausprobiert, habe das aber nicht weiter vertieft. Es gibt keine C Konstante im options-Objekt, womit der Plot konfiguriert wird wird. Es gibt O, Omega und T statt f und g. Ich denke, mir hier nochmal Gedanken machen zu wollen. Und zu wiederholen. Anlass ist eine Wiederholung von CS61B und 6.006 mit 6.046j.

Inline Css + JS

Also ich werde das ganze Script und Css erstmal inlinen. Ich hatte schon "(Even) Faster Websites" geschrieben (so als Angeberslogan) und dann nochmal ueberlegt, das kleine Ende der Datei zu blockieren. Doch da ich alles HTML und CSS bereits ueber dem Script hab ist die Illusion bereits perfekt.

Lets try it. Alle paar JavaScript Files inlinen. Nach allem anderen. Das CSS natürlich im Head, damit die Styles direkt applied werden koennen. Als wuerde man noch auf das Laden der anderen warten. Vielleicht ist es sogar even slower. Vielleicht blockiert es Chrome, waehrend alle anderen Responsive sind. Wer weiss? Vielleicht ist es fast. Vielleicht slower. Vielleicht auch egal.

Der Gedanke, wo es Sinn macht, den zu verlieren, der handelt vom Caching. Die ge-inline-ten Skripte und CSS koennen nicht mehr im HTTP-Cache aufgelistet werden.

Neue Baustelle

Letzter Inhalt: april

Dort sind alle bislang gemachten Sachen einsehbar.

Hier entsteht "gleich" eine neue Seite...