Willkommen auf meiner Homepage

Typos und Flüchtigkeitsfehler vorbehalten. Hakende Tasten halten mich ein wenig vom viel schreiben ab.

OpenCourseWare

Ich mache erstmal alle 18er (Mathematics) Kurse. Die 6.00 (EECS) sind meine Ziele. Auf dem Plan stehen aber auch 14 (Microeconomics) und 8 (PHYSIK (extrem wichtig)) und Chemie (Material und Chemie an sich). Dann gibt es da noch viele viele Kurse, aber die schaffe ich dieses Jahr auf keinen Fall mehr. Ich mache dieses Jahr erstmal Mathe, EECS und Physik (Kinetik/Mechanik fuer Grafik, und Elektrizitaet fuer EECS).

Hartz IV

Ich war am Freitag, dem 3. Mai morgens im Jobcenter. Ich hatte vom Arzt aus bereits dort angerufen. Das Geld wurde nicht rausgeschickt. Ich habe einen Abschlag bekommen und erhalte den Rest mit der Post. Das Geld habe ich mit meiner Freundin geteilt und naechste Woche fahre ich mit unserem Kaninchen Racker zum Tierarzt. Ich hoffe, mir nachher eine einfache Tastatur fuer den Mai zu kaufen.

(F#@!) II

Der sch*** Scheck ist immer noch nicht da.

Backenzahn

30.4. - Historischer Moment.

Mit 36. habe ich meinen zweiten Backenzahn verloren. Mit 34 fiel mir der erste aus. Jetzt habe ich mir den zweiten gezogen. Die Nacht hatte ich Schmerzen. Morgens zwei Paracethamol. Und abends, als sie nachliessen, bevor die Schmerzen zurueckkommen, ihn lieber extrahiert. Er hing noch fest am Haken. Aber nach einer Minute war er raus und ich fuehle mich seitdem wieder gut. Und auch der schlechte Geschmack ist raus.

(F*ck)

Heute gibt es noch kein Hartz IV. Dann wohl erst am 2. Mai.

Homepage ueberarbeiten

Ich denke mir, meine alten Edwin Hold Alben, von denen Repeat 2 nicht fertig wurde und VDSZBZ ein paar zu experimentelle (gecuttete Phrasen, als "DJ THF/Radical Rhythms" abgemischt) Tracks hat und ich mich damit blamiere, auf eine Sammlung von Best Of (gibt immernoch gut 3 LPs oder 3-4 Stunden Musik ohne Pause) zu reduzieren.

Dann moechte ich unbedingt meine JavaScript Dokumente, die Tutorials fortzsetzen, die habe ich nur zur Seite gelegt, um es sacken zu lassen. Das ist nun bereits ein Vierteljahr her. Also wird es Zeit.

Es fehlt noch Hartz IV fuer eine neue 7 EUR Tastatur oder zwei.

Inzwischen werde ich weiter Winkelfunktionen ueben, ich merke naemlich, dass ich sie nicht beherrsche und mich vor allem mit den Winkeln selbst noch vertu.

Dann muss ich unbedingt den FunctionPlotter von den neuen, nicht zum Graphen gehoerigen Funktionen trennen, weil das sonst ein Durcheinander gibt und es der Wiederverwendbarkeit schadet. Ich habe in dem Jahr eine Reihe von Top-Prototypen (require, Promises, syntaxjs) geschrieben, die dieses Jahr umgesetzt werden muessen.

Die ES6 Uebersicht, die ich ankuendige muss rein und nach dem 2d canvas muss ich auch ohne GPU in den sauren Apfel beissen und mich mit 2-3 Frames in der Minute zufrieden geben und dem Wissen, dass anderswo laeuft -> WebGL. Wird Zeit. Ein Jahr ist um.

Nochmal Sinus und Cosinus

Bevor ich es mache, ist es aber klar, dass man zu Sinus und Cosinus noch einpauken muss, ob x positiv oder negativ ist, oder y. Und ob der Winkel zwischen +90 und 0 oder -90 und 0 Grad ist. Groesser sollten die Winkel wohl nicht sein. Hier habe ich beim Ausprobieren unter anderem aber ganze 360 Grad benutzt. Das wird wohl gar nicht funktionieren, und da kann ich lange probieren.

Ich hab das durchgestrichen, weil ich merke, hier nichtmal richtig zu vermuten.

function Vec3 (x,y,z) {

    // Um unteren if-else Block zu entfernen.
    // Kann man das alles mit dem Vec Konstruktor
    // bereits berechnen. Dann kann man schoener
    // schreiben und all diese Sachen wiederverwenden

    this.up = this.y > 0;
    this.down = this.y < 0;
    this.left = this.x < 0;
    this.right = this.x > 0;
    this.out = this.z > 0;
    this.in = this.z < 0;
    
    // Wenn x,y je 0 sind, sind die Richtungen je beide false
    // was richtig ist, denn sie gehen in keine Richtung. 
}

Ich hab jetzt mal 10 Minuten (2 fuer den Code und 8 fuer den Kommentar) mit Modellieren eines Pseudocodes verbracht. Und bevor ich jetzt weiter an dem Kommentar schreibe, ihr kommt bestimmt von alleine drauf, oder wisst es schon. Der Parapgraph unter dem Code ist auf jedenfall erklaerungsfreundlicher als der Kommentar ueber den if-else Blocks, die die Vorzeichen von x und y klaeren, wohin der Vektor geht. Jede Vektorenberechnung sollte wissen, in welche x und y Direction (Vektoren haben directions und magnitudes (lengths)) sie gehen.


    // x, y sind die Endpunkte des Pfeils.
    // Ich nehme den Sinus als Pfeilspitzenstrich
    // und den Kosinus als unsichtbaren Abstand
    // Ich male ein lineTo vom Punkt des Vektors, 
    // den Abstand von sin(vektorwinkel+(1/2*winkel Spitze))
    // und von cos(vektorwinkel+(1/2*winkel Spitze))

    // Jetzt muss man beachten, in welche Richtung der
    // Vektor geht. Das gleicht das Problem bei den
    // fast perfekten Ergebnissen aus.
    
    // Man multipliziert mit der laenge der Spitze, wie lang
    // die Sinus und die Kosinuslinie sein soll.
    // Math.atan2(y,x) berechnet den Winkel des Vektors. Den
    // habe ich theta genannt, wie an der Tafel.
    // phi ist der Winkel der halben Pfeilspitze, der draufkommt

    // Ich hab den jetzt auf den Winkel verrechnet. Ob ich 
    // es falsch gemacht habe? Probieren geht ueber studieren.
    // Oder in dem Fall "ueber-kommentieren".

    // Berechnen
    
    
    // Ist psi jetzt Math.asin(tiplen); ?
    // Und psi auch Math.acos(tiplen); ?
    
    // Probieren geht ueber kommentieren

    if (x < 0) {
	// Vektor dreht nach links
	// Pfeilspitzen drehen nach rechts
	// theta-psi (positiv)
    } else if (x > 0) {
	// Vektor geht nach rechts
	// Pfeilspitzen drehen nach links
	// theta+psi (positiv)
	
	    // Vielleicht kann man das so rechnen
	
	winkel = ang(phi) + ang(theta);
	if (winkel > 90) winkel -= 180
	if (winkel - 90) winkel += 180

	lx = x - Math.cos(rad(winkel)) * tiplen
	rx = x + Math.cos(rad(winkel)) * tiplen
	
	
    } else {
	// Vektor dreht weder links noch rechts
	// Pfeile drehen genau rauf oder runter
	// uebergebe dennoch theta (die funktion antwortet richtig)
	// Algebra: Der Sinus zum Ende der Pfeilspitze ist genau waagrecht

	lx = x - cos(winkel)
	rx = x + cos(winkel)
    }
    
    if (y < 0) {
	// Vektor geht runter
	// Pfeilspitze gehen rauf
	// theta+psi (positiv)
    } else if (y < 0) {
	// Vektor geht rauf	
	// Pfeilspitzen gehen runter
	// theta-psi (negativ)
    } else {
	// Vektor geht weder rauf noch runter
	// Pfeile zeigen nach links oder rechts
	// ttheta+-psi? (egal)	
	// tiplen ? (wenn tiplen ein Vektor ist, dann dessen x Kompakte);
	// Womit ich auch im Kommentar zu einer anderen Repr. des Pfeilstuecks komme,
	// was die Berechnung viel einfacher macht.
	// Weil ich dann eine x und y Komponente habe, die man addieren und subtrahieren kann (andere Richtung)
	// Wo ich auch bei vier * vier Darstellungen der Pfeilspitze bin

	ly = y - sin(phi)
	ry = y - sin(phi)
    } 
    
    // Vielleicht hier nochmal zusammenrechnen.

    // 
    // lx = x - cos * len
    // rx = x + cos * len
    // ly = y - sin * h
    // ry = y - sin * h
    
    // ich hatte vorher (ist falsch)
    
    // x - sin * len
    // x +/- sin * len
    // y - cos * height
    // y - cos * height
    
    
    
    // Zeichnen
    context.lineTo(rx,ry);
    context.stroke();
    context.lineTo(lx, ly);
    context.stroke();
    // Dann fiel mir noch eine vermutliche ungefaehr-Loesung ein 
    // x, y sind die Endpunkte des Pfeils.
    // Man koennte den Vektor ein Stuck zurueck
    // und senkrecht hoch.
    // Das das mache ich nicht.
    // Die Division "Vektor/Weg zurueck" fuer x/weg und y/weg 
    // fehlt im Code, was einen x,y ergaebe, 
    // den man senkrecht hoch * sin/cos(Math.atan(y,x)) koennte

Ich denke mal, ich habe als Eselsbruecke Glueck, dass - und - sowie + und + bei x und sin und y und cos zusammengehoeren. Wenn man die ueber Kreuz nimmt, haette man soviele Moeglichkeiten, die Vorzeichen zu vertauschen und sich zu vertun, wie ich es beim ausprobieren getan habe. Ich moeche den Sinus und Kosinussatz nun lernen. Ich denke, dieses Beispiel weist den richtigen Weg. Anhand der Richtungen der Vektoren kann ich entscheiden, was ich tu.

Seit ich das geschrieben habe, habe ich ein ganzes if-else-Beispiel mit Pseudocode verunstaltet. Jetzt muss noch einer probieren, ob das laeuft, oder wie das jetzt richtig ist.

Was rauskommt muss ich vergleichen. Was man bemerkt, ist, wenn der Vektor in der Addition (der gruene, in die andere Richtung geht, ist der Pfeil andersrum. Besondere Pfeilkonstruktionen hatte ich viele. Ich denke, das hier bringt mich naeher an die richtige Sinus und Kosinus Konstruktion. Ich denke, dass diese Probe, das, was ich mir vorstelle, was noch in Frage kommt, Vorzeichen und falsches Winkelmaß. Ich hab echt 360 Grad wie auf dem Papier probiert, wie man weiter unten lesen kann.

Wie man weiter oben lesen kann, hat man viele Moeglichkeiten um sich zu vertun, aber nur eine ist richtig. Ich versuche mich mit dem oberen zu naehern. Die Konversion zwischen radians und Grad ist sehr wichtig. Ich hab gleich r = (Math.PI/180) * a und a = r / (Math.PI/180) definiert, weil sie brauchbar sind. Ich denke mir, die Funktion, 180 zum Winkel zu addieren, oder zu subtrahieren, die wird genauso wichtig.

Wie man merkt, mir liegt die Winkeldrehung immernoch "auf der Zunge". Ein bisschen angeben gehoert dazu, machen alle die ich kenne, und die Meisten geben mehr an. Wo wir gerade dabei sind, mein Schatz ruft. Ich mach mal Schluss mit dem Beispiel.

Calculus für Anfänger

Wer die absoluten Grundlagen verpasst hat, wie ich, der muss sich Gilbert Strangs "Highlights of Calculus" angucken. Er beginnt bei keinem Wissen, weil er meint, dass man sich in den Textbuechern leicht verlaufen kann, bei den vielen Beispielen. So ja auch in der Calculus Klasse, die als Grundvoraussetzung fuer alle MIT Studenten gilt. Ich denke mal, in Deutschland wird Infinitesimalrechnung oder wie man es hier nennt, ebenso auf der Anforderungsliste stehen. Ist ja auch richtig. Und vor allem. Einfach.

http://archive.org/details/MITRES18.005

Wer nicht weiss, wie ds/dt oder Δy/Δx zustande kommen, oder wie man aus einem Graphen einen anderen macht. (Was mich auf eine geniale Idee bringt, das auf dem Canvas zu machen.) Oder das f(t) nach ds/dt Differentierung und ds/dt nach f(t) Integration beschreibt. Wer das und alles andere nicht weiss, wie ich, der sollte sich das angucken.

Auf archive.org, auf deren wayback Machine eine alte Version meiner ersten linux-swt.de Website (von ca. 2003) zu finden ist, gibt es eine offizielle Kopie aller offenen MIT Kurse.

Neue Quelle

Wer das jetzt nicht lernt, der hat es ueberlesen. euclideanspace.com. Als ich diese Seite oeffnete war ich baff. So muss spaeter mal meine Webseite aussehen, bitte. Das muss ja ein Jahr und laenger gedauert haben, die zu korrigieren, aeh, zu schreiben. Absolut megastark. Hier gibt es alles ueber Grafik, was man sich nur vorstellen kann.

Obwohl ich schon bei den Matrizen bin, muss ich jetzt erstmal meine "noch leichte Rechenschwäche" lösen. Übrigens, für dumme Witze reicht die Überschrift nicht. Ich habe weder Förder- noch Nachhilfeunterricht gehabt oder gar empfohlen bekommen. Das war nicht der Grund. Mit dreissig war ich meine Eltern dann los (aber arbeitslos und pleite). Aber ich bin nicht verdummt. Darum habe ich alle Chancen, das heute zu lernen.

Noch leichte Rechenschwäche

Update: Ich habe die Transformation/Rotation entfernt. Aber ich habe es immernoch nicht raus.

Ich hab hier jetzt so oft ausprobiert, dass der Pfeilwinkel mittlerweile gleich dem Vektorwinkel ist. Ich werde gleich weiter probieren. Aber erstmal nehme ich was Nachhilfe (hehe).

(Dabei fiel auf, dass Math.atan2(y,x) statt Math.atan2(x,y) geschrieben werden muss. Damit habe ich das Beispiel Sinus und Cosinus weiter unten erstmal geprueft und korrigiert.)

    // ok, ergibt eine Spitze (die Schwarze)
    var tx1 = x - tiplen * Math.sin(theta);
    var ty1 = y - tiplen/2 * Math.cos(theta);
    
    // bad
    var tx2 = x - tiplen * -Math.sin(180-theta);
    var ty2 = y - tiplen/2 * -Math.cos(180-theta);
    // ebenso bad:
    // vorzeichen tauschen, winkel auswecheln
    // geht alles nicht
    // genauso bescheuert (einfach so ausprobiert, wild guessing)
    var tx2 = tx1 + Math.sin(90-theta) * Math.sqrt(tiplen*tiplen);
    var ty2 = ty1 + Math.cos(90-theta) * Math.sqrt((tiplen/2)*(tiplen/2));
    // ist auch nicht:
    var tx2 = x - (y-ty1);
    var ty2 = y - (x-tx1);
    
    // auch nicht mehr aktuell
    var angle = Math.PI/180 * 30; 
    var tx1 = x - tiplen * Math.sin(theta+angle);
    var ty1 = y - tiplen * Math.cos(theta+angle);
    var tx2 = x - tiplen * Math.sin(theta-angle);
    var ty2 = y - tiplen * Math.cos(theta-angle);
    

Gestern: Mathe muss man auch intensiv einueben und sich nicht nur angucken. Noch bin ich in der Phase, wo ich nochmal ueberlegen muss. So habe ich zum Beispeil die Pfeilspitzen auf der Zunge liegen, aber nicht zum aussprechen berechnet.

Ich wollte also vom Endpunkt (dem Vektor + dem Origin) den Sinus und Kosinus von dem Winkel + 45 oder - 45 Grad haben, und den * die Pfeilspitze auf die Koordinaten verrechnen.

Weil mir das aber nur auf der Zunge liegt, rotiere ich den Canvas mit Math.PI/180*angle±225 und zeichne dannn den Sinus und Kosinus * der Laenge. Damit kommt was wie Spitzen raus, sowie, wie man sehen kann, acuch nicht genau eine Spitze, z.B. ganz unten die.

Heute: Ich denke mal, ich werde mal ein paar Stunden Geometrie, sowie ganz dringend das Math Objekt machen, damit ich mir mit der Angabe von Winkeln und Radians sowie Koordinaten und Vektoren auch ganz sicher bin.

Was kann man da tun? Weiter ueben. Nochmal probieren, nochmal berechnen. Mathe selbst ist aber spannend.

Update:Ich war dann auch am ueberlegen, ob ich FunctionPlotter und VectorPlotter trennen sollte. In dreieinhalb Stunden habe ich gerade 1,64 Euro Pfand gesammelt. Davon konnte man nicht viel einkaufen, und Aerger habe ich von ihr dafuer auch noch gekriegt, ich habs zwar nicht verdient, aber jetzt bin ich muede.

Als ich gerade wieder nach Hause kam, habe ich erstmal kurz versucht mal addition, Kreuzprodukt, zu visualisieren. Kreuz geht in z-Richtung, wenn ich Vec3 nehme, weil er Senkrecht auf der Ebene der beiden x,y Vektoren steht. Den neuen Vektor sieht man also [noch] nicht. Dabei faellt auf, dass die Rotation der Leinwand auch nicht perfekt ist, den je nach Richtung, auch wenn die schwarzen so aussehen, geht es auch nicht mehr richtig. Wie ich an dem gruenen Pfeil sehe. Ich denke dran, das zu verbessern.

Jetzt werde ich erstmal ein wenig ueberlegen und dabei eine weiter weiter hinten seiende Lektion MVC angucken. Bis ich auf die Idee komme, hier weiter zu schreiben. Ich bevorzuge jetzt aber mal die horizontale Lage ;-).

Guthaben und 5GB Traffic

Da freue ich mich echt auf naechste Woche, wenn die Flatrate ablaeuft und ich nachladen kann. Dann kann ich mal einen ganzen Kurs auf einmal downloaden. Ist ganz schoen anstrengend, die Files mit 6.6k pro Lektion zu laden.

Weil die alte Kiste die ganze Zeit damit beschaeftigt ist und ich mit 512MB nichtmal nen anderen Browser starten kann, ohne dass das SWAPpen beginnt. Was dann ca. 5 Minuten lang geht, bis ich einen Prozess offen habe um alle anderen zu beenden, dass ich was Speicher freikriege. Wenn ich ein wenig JavaScript in der Zeit starte, reicht das manchmal aus, dass der Transfer stockt.

Ich denke mal, wieder etwas abweichend von meiner Idee, mir die 6.xx Reihe (EECS) zu vervollstaendigen, erstmal Calculus Revisited einzusammeln. Mathematik ist so spannend, dass ich mir lieber erstmal das vervollstaendige. Sowie 18.06 Lineare Algebra und 18.03 Differentialgleichungen. Denkt dran, ich habe kein Abi! Es ist wirklich das erste mal, dass ich mal einen Lehrer darueber reden hoere.

MVC

Im Multivariabel-Calculus geht es jetzt weiter mit Doppel-Integralen, sprich ∫∫. Damit kann man Flaechen summieren.

Mit dem Auge bin ich schon weiter als mit dem Code.

Statistik

Ich habe dem Plotter eine erste Statistik Funktion beigebracht.

Die nimmt Daten an, und errechnet keine. Man uebergibt sie als [Array], der {}bjekte mit den Daten Name und Value traegt. Man kann mit dem Name beschriften, der Wert wird abgebildet, und die Achse Y kann, wie man sieht, bereits beschriftet werden.

Dann sind Bars nicht alles. Ich denke mal, Pie Charts sollten auch mal geschrieben werden. So ein Plotter ist nuetzlich zum Beispiel fuer den Eigengebrauch.

Und dann sowas, was Umfrageergebnisse und Meinungen abbilden kann. Oder horizontale Balken.

Alle Angaben in nicht mehr Prozent sondern in Hoehe des lokalen Maximums, so kann man angeben, was man will, und der Computer rechnet aus, wie er es zu zeichnen hat.

Update: Pie Charts habe ich jetzt angefangen. Seltsamerweise uebermalt mir ein .fill() ein Viertel, was als .stroke() aber korrekt eingeteilt ausschaut. Ich habe one = 360 / sum (360 durch Gesamtsumme) sowie angle = value * one gewaehlt. Man kann das auch als degree = sum / 360 und angle = value / degree schreiben. Kommt das gleiche raus. Dennoch uebermalt ein .fill() einen Teil des Kuchens mit der falschen Farbe, hier darf ich nochmal ausprobieren, den richtigen subPath waehlen, man kanns am .stroke() bereits erkennen, dass was mit der Faerbung noch nicht stimmt..

linux-qc59:~ # n
> var sum = 5000;
undefined
> var one = 360 / sum;
undefined
> var value = 252;
undefined
> var angle1 = value * one;
undefined
> var degree = sum / 360;
undefined
> var angle2 = value / degree;
undefined
> angle1
18.144
> angle2
18.144

Die Probe von der Berechnung, dass bei beiden das gleiche rauskommt. Bevor es so in Frage gestellt wird. Aber auch das hier stimmt natuerlich.

Sinus und Cosinus (Gegenkathete und Ankathete)

Irrtum: Das Dumme ist, das funktioniert nur, wenn px und py den gleichen Abstand haben. Wenn ich die Punkte jetzt veraendere, andert sich das Verhaeltnis des Sinus und Kosinus so, dass ich gerade drauf nicht komme, mit welchem Faktor ich ausgleichen muss.

Update: Das funktioniert natuerlich wohl. Das Problem war Math.atan2(x,y). Die Funktion erwartet zuerst die y Koordinate, dann die x. Mit Math.atan2(y,x) funktioniert das dann auch einwandfrei.

ready(function (e) {
    var canvas = document.querySelector("#sincos1");
    var context = canvas.getContext("2d");
    var px = 33;
    var py = 47;
    var len = Math.sqrt(Math.pow(px,2) + Math.pow(py,2));
    var angle = Math.atan2(py, px);
    var sin = Math.sin(angle) * len;
    var cos = Math.cos(angle) * len;
    // Hypothenuse v=<px, py>
    context.translate(100,100);
    context.save();
    context.beginPath();
    context.strokeStyle = "red";
    context.lineWidth = 1.0;
    context.moveTo(0,0);
    context.lineTo(px,py);
    context.stroke();
    context.closePath();
    context.restore();
    // Gegenkathete (sin alpha)
    context.save();
    context.beginPath();
    context.lineWidth = 1.0;
    context.strokeStyle = "green";
    context.moveTo(px,py);
    context.lineTo(px,py-sin);
    context.stroke();
    context.closePath();
    context.restore();
    // Ankathete (cos alpha)
    context.save();
    context.beginPath();
    context.lineWidth = 1.0;
    context.strokeStyle = "blue";
    context.moveTo(0,0);
    context.lineTo(cos, 0);
    context.stroke();    
    context.closePath();
    context.restore();
});

Homogene Koordinaten

Die Linien die von oben und unten von hinten kommen gehen durch den Bildschirm. Das ist die geschnittene Ebene, auf der die Schnittpunkte gezeichnet werden. Das kann man wohl einfach berechnen. Die Formal fuer die Intersection von Lines mit Planes habe ich gesehen, probiert, und wieder vergessen. Das war mit den Punkten Q1, Q2 an der Tafel. Zu Beginn (Lektion ca. 5 oder so) von 18.02. Von meinem Auge zum hochsten Punkt, zum Tiefsten, zur Mitte, und die entsprechenden Winkel und Verhaeltnisse brauche ich da. Und noch mehr. Aber ich habe die Ruhe.

Auf der Suche nach der Loesung habe ich sie schon gesehen.

Das hier gehoerte wohl dazu.

Dann habe ich mich bei Zentralprojektion, Projektivm Raum, und sogar konstruktiver solider Geometry umgeguckt. Ich denke aber, fuer einen Wuerfel brauche ich keinen Raytracer, sondern 12 Punkte.

Ich hab mich noch nicht vor der Matrix gedrueckt. Hier kommt ne 4x4 Matrix zumEinsatz, es wird ein 4. Vektor und eine vierte Koordinate verwendet. Der Vektor kriegt eine 1, die Matrize eine 0, 0, 0, 1. Das ist die w Reihe. Und dann gibt es für verschiedene Operationen verschiedene Matrizen. Und schlaue Koepfe haben die wieder auf ein paar uebrigbleibende Operationen gekürzt.

Bei der Transformationsmatrix SVGMatrix kann man das durch 0 0 1, was a,b,c,d,e,f hinzugefuegt wurde, erkennen.

Das werde ich dann wohl als naechstes ausprobieren. Darf nur die Seite fuer die Matrizen nicht vergessen. Melde mich dann zurueck.

Ich denke uebrigens, wo ich jetzt durch die Infinitesimalklassen halb durch bin, Mathe fuer Informatiker von vor drei Wochen wieder zu gucken, dass ich Beweise durch Induktion lernen kann und so.

Verlegenheit

Ich habe die Punkte x-mal kontrolliert. Die Pfade ebenfalls. Die Figur ist aber die falsche. Es sollte ein Wuerfel rauskommen.

Das erste Beispiel zeichnet einfach x und y der 3 Koordinaten und uebermalt sich logisch mehrmals.

Das zweite Beispiel nutzt d als Berechnung zu jedem Punkt (vektor von 0 ausgehend).

Das dritte Beispiel nutzt d als Konstante (sieht besser aus, aber eigentlich gar nicht anders...).

Ich habe die Punkte alle in den positiven Raum gebracht. Kommt das gleiche raus.

Nebenbei habe ich setTransform mal angeguckt, damit kann ich die Perspektive in 2D aendern. Eine Kombination aus fillRects, sowie eine SVGMatrix habe ich noch nicht probiert. Hier muss das Rectangle mit der Matrize multipliziert werden. Mit .save() und .restore() um die Ansicht nicht zu verstellen. Ich denke, wenn ich das probiere, wird das schon funktionieren, kann mir nicht denken, dass der Canvas nicht dafuer geeignet waere.

Aber es muss doch einen Weg geben, 12 Linien zu zeichnen, die einen Wuerfel ergeben. Ich habe hier im zweiten Versuch sogar 16 Linien probiert (sind noch drin), aber auch die muessten einen Wurfel ergeben. Jeder normale Grafikprogrammierer muss das koennen. Mit x, y, Points oder Lines was dreidimensionales zu malen.

Animation

[Abt. Evolutionäres Modell] Ich dachte mir, wenn man das so plotten kann, dann kann man das auch animieren. Das macht es (hinterher) anschaulicher. Wie ich bereits bemerke, kann ich daraus dann separate Features machen. Erst durch ein paar Funktionen wird aus dem Plotter ueberhaupt eine Idee. Anders, als ein System von oben herab zu zeichnen. ;-)

syntax.js

Eine Option enableFeaturesGlobal gibt es ja bereits. Wenn man im DocumentElement, dem html Tag data-syntaxjs-controls=true angibt, wird das für alle Listings eingeschaltet. Ansonsten gibt es nur noch highlighting, oder wenn ich data-syntaxjs-controls=true angebe die Kontrollbuttons. Grund ist, dass sie einfach alle zuviel arbeit verrichten. Ich denke, sie sind optimal für den Worker. Was die linearen Lookups im Parser betrifft, die ich noch auf Konstant kriege, das ist der andere Punkt. Dann kriecht der so, der ist nicht so lahm, weil ich ihn mit setTimeout auf den Loop verteilt hatte. Jetzt muesste das Dokument aber nicht mehr so huepfen, weil keine default Controls mehr geadded werden. Wobei ich hier denke, ein kleiner Knopf zum Aktivieren waere cool. Diesen Highlighter mache ich jedenfalls noch weiter. Das Annotationsobjekt z.B. braucht nur neuen Text.


    /* Zwei Highlights von syntax.js: 
	- Create Abstract Syntax Tree
	- ToValue(AST)
    Zwei Buttons in der Leiste.
    Per default sind jetzt alle Buttons erstmal aus. */
    
    function createSyntaxTreeAndRun () {
	var hello = "AST";
	return hello;
    }
    createSyntaxTreeAndRun();

Integration

Geil. Im Single Variable Calculus faengt jetzt die Integration an. Und in 18.02 dem Multivariable Calculus fange ich ebenfalls gerade damit an, da ging es bereits um Doppel-Integrale, halt noch eine Achse lang, im Raum.

Jetzt geht die zweite Hälfte des Semesters die Flächen- und Körperberechnung los.

FTC1: If F' = f, then abf(x)dx = F(b) - F(a)

MP3

Mein Schatz hat sich gestern einen neuen MP3 Player geholt. Und mir einen mitgebracht. Jetzt habe ich gestern 4h meinen alten /hiphop gehört und weiss, wie es weitergeht und weiss, dass ich besser eine neue Kompilation aus den Alben mache, wenn ich sie nicht fertigstelle. Damit hätte ich dann genug fertiges Material und koenne auf die Alben verzichten.

Aber neues Material muss her. Ich fürchte mich nur jetzt schon vor Audacity und dem alten PC. Wenn ich einen Satz sagen will, kommt der Computer nicht mit. So musste ich alles schrittweise aufnehmen. Mit einen Computer von heute waere das kein Thema, die Strophen in einem durch zu proben. Aber da kommt schon was raus. Der neue Player inspiriert mich. Ich wusste sofort, wo ich stehen blieb.

Ausserdem ist die Homepage noch von vor meinem JavaScript-Kurs. Die wartet schon lange auf ein flottes HTML5 Design auf Höhe der Zeit.

Algorithmen

Ich hab die letzten vier Wochen eigentlich nur mit OpenCourseWare gespielt. Wird Zeit, die Algorithmen und Datenstrukturen wieder fortzusetzen. Ich habe dem Funktionsplotter gestern eine einfache Funktion für die Laufzeitanalyse eingebaut. Die habe ich in Zukunft zu verfeinern. Was mich freut ist, in algorithmen.html, dem angekuendigten Entwurf in der Sidebar, damit dann im Kapitel Asymptotische Analyse das, was der Professor an die Tafel malte, mit dem Plotter zeigen zu können. Ist doch irgendwie Zeichen eines kleinen Lernerfolges.

Zur Zeit kann man zwar nur T(n), O(n) und Ω(n) angeben. ℴ (Little-Oh) und ω (Little-Omega) noch nicht. Und richtig beschriftet und eingefaerbt sind sie auch noch nicht. Aber mir fallen langsam einzelne Features fuer den Plotter ein. Die groessten auf meiner Wunschliste sind ein Grid und ein Zoom, sowie saubere Parameter fuer alle Farben.

Ich wollte den gestern schon neu schreiben, dann habe ich gedacht, ich benote 300 Zeilen als schlecht, anstatt sie auszuarbeiten, das ist wirklich zu kurz gedacht gewesen. Nun arbeite ich sie weiter aus und entferne schlechten Code nach und nach und schreibe neu, was neu geschrieben werden will. Eine f(x) plotten, ohne weitere grossartige Details kann ich jetzt aus dem Kopf, das ist nuetzlich.

Ableitungen

Daß es da ganz bestimmte Umrechnungsregeln gibt, oder man sich die Ableitungen merken kann, habe ich auch bemerkt und zum Teil mitbekommen, wie bei f(x) = x2 und f'(x) = 2x, oder dass bei Wurzeln dann 23x32 genommen wird.

Die erste Ableitung von sin(Θ) ist -cos(Θ), die zweite ist -sin(Θ) und dann kommt als sin''' cos(Θ). Ich finde, das kann man sich merken. Genauso wie tan(x) => f(x0) + f'(x0) * (x - x0) + y0; für die ganze Linie. tan(x0) sollte f(x0) + f&apos(x0) * (x0 - x0) + y0 also f(x0) + f'(x0) * 0 + y0 also f(x0) +y0 sein, da tangiert die Tangente den Punkt ja auch, in dem Punkt. Laesst man +y0 weg, schneidet sie x0 auf y = 0

Eine Tabelle dazu gibt es in der Wikipedia. http://de.wikipedia.org/wiki/Tabelle_von_Ableitungs-_und_Stammfunktionen. Um durch den Calculus, der zur ersten Hälfte erstmal aus Ableitungen und Differentialrechnungen besteht, zu kommen, sollte man sich diese Umformungen merken, weil man dann (praktisch) problemlos mitkommt.

Hätte nie gedacht, auf einmal wieder Mathe zu machen, auch wenn es schon immer ein Wunsch von mir war, und ich neben Informatik am liebsten Mathe studiert hätte. Nunja, jetzt kann ich mich mir selbst beweisen. Neben richtiger Mathematik bin ich am Meisten darauf aus, mir die Mathematik der 3D Programmierung anzueignen.

Als ich letztes Jahr WebGL ausprobierte, zusammen mit dem WebGL 101 Tutorial, war sofort klar, dass es einfach ist, 3 Matrizen zu manipulieren und Uniforms zu setzen. Die Hälfte der Mathematik habe ich jetzt durch den Singe- und Multivariablecalculus, sowie die ersten Lektionen von Lineare Algebra (18.06) verstanden und sogar fast gelernt. Die speziellen Matrizen der Computergrafik muss ich nun noch programmieren. Und dann werde ich wohl alles einige Stunden lang durch ausprobieren analysieren duerfen. Jedenfalls braucht man fuer den 2D Canvas genauso eine Welt-, eine Projektions- und eine Modelmatrix, wie fuer den WebGL Canvas. Und das muss ich mir selbst noch einfuehren.

"Normale" Programmierung geht mir (recht) fehlerlos von den Haenden und ich kann einige tausend Zeilen am Stueck schreiben, ohne irgendeine Referenz konsultieren zu muessen. Hier gibt es aber noch zu tun. Doch es macht mir Spass. Das Leben ist halt eine Baustelle. Und wir sind nur da um zu malochen.

http://de.wikipedia.org/wiki/Tabelle_von_Ableitungs-_und_Stammfunktionen

Jetzt ist aber erstmal Sonntag und schönes Wetter. Bin ich froh, dass der Winter vorbei ist. Bei uns im Wohnheim ist es nämlich zügig und kalt, weil die Heizungen nur lauwarm sind. Jetzt gerade haben wir aber alle Fenster weit auf.

MATLAB

War schön draussen. Heute mittag hatte ich mich noch nach MatLab (Matrix Labroratory) erkundigt. Danach habe ich mich draussen mit meinem Schatz getroffen, sie war schon unterwegs. Jetzt sind wir beide wieder zuhause und sie guckt Video und ich mach was Mathe und Informatik.

Die aktuelle Linux Version ist 64 Bit, was ja heute normal ist, und nichts mehr für meinen alten Computer.

Es gibt aber eine Alternative. GNU Octave. Ich werde mal schauen, ob ich die installiert und bedient kriege. Ein RPM von Octave sagt mir erstmal, dass mir ein paar andere libs fehlen. Und ich habe keine Lust die sofort zu jagen. Muss ich erst abschreiben und dann einzeln eingeben oder zypper oder YaST nehmen. Ich bin wegen den OpenCourseWare Videos aber auf 6.6k GPRS, darum verzichte ich mal auf YaST und Co.

Eine andere Alternative heisst freemat oder so. Ich werde mal schauen. GNU Octave soll weitgehend syntax kompatibel zu MatLab sein. Das wird schon ausreichen, um die Aufgaben aus den Problem Sets zu loesen, und vielleicht ein paar schoene 3D Plots zu erzeugen, die ich dadurch erstmal zu programmieren lerne. Wenn ich das hinkriege, wird ein Traum von mir wahr. Das wollte ich naemlich schon immer lernen.

Sonne

Meine Frau ist noch nicht zuhause. Aber es ist schönes Wetter draussen.

Mein Kopf raucht mittlerweile. Ist aber logisch, wenn man zehn Erstsemesterklassen auf einmal macht.

Ich glaube, ich werde den Nachmittag draussen verbringen. Mal schauen, was sie sagt. Ich habe irgendwie keine Lust jetzt noch was zu programmieren.

ΔfΔx

Ist erst die Sekante. Fehlt noch die Tangente.

Macht Spass.

Das Wissen um die Sekante und das Steigungsdreieck habe ich aus 18.01 Single Variable Calculus.

Fehlt noch die Lösung, die Tangente.

Das Summieren unter der Kurve, im Sinne vom Riemann-Integral baue ich als eins der nächsten Features in den Plotter ein.

Was ich im Moment noch absolut nicht checke ist, da muss ich die Regeln ueberhoert haben, sind die partiellen Ableitungen, wie fxx oder fxy oder fyy. Kommt alles in 18.02 Multivariable Calculus dran.

y'=f(x,y)

Macht Spass.

ImageData

Mit context.getImageData(x,y,w,h); und context.putImageData(data, x, y); lassen sich Bilder manipulieren. Mit imageData.data[i] kann man die RGB-Werte jedes Pixels adressieren. Man kann ImageData Objekte auch so kreieren und selbst bemalen. Man muss dann nur dem .data Array die Pixel nacheinander einfaerben. In dem Fall des zerschnittenen Bildes von mir reicht ein XOR mit 32 aus, um das Bild etwas zu veraendern und ohne was zu speichern mit dem selben Befehl auch wieder zurueckzuverwandeln.

32 ist hier nicht bewusst gewaehlt und ganz ehrlich, ich muss jetzt erstmal rausfinden, was ich mit der 32 manipuliere. R oder G oder B? Wer weiss es, wenn er auf das Bild guckt, welcher Farbwert sich geaendert hat? Mit etwas Photoshop Übung, was die Meisten ja haben, oder mit Gimp-Blick, sollte das eigentlich klar sein. Für mich heisst es aber wieder mal, nachschlagen, oder solange nicht wissen, bis ich es nachgeschlagen habe. Was manchmal auch ein paar Iterationen (oder Monate, wie bei dom.html, etc.) braucht.

window.addEventListener("DOMContentLoaded", function (e) {
    var canvas = document.querySelector("#drei");
    var context = canvas.getContext("2d");
    var cols = 5;
    var rows = 5;
    var colw = canvas.width / cols;
    var rowh = canvas.height / rows;
    var col, row;
    var lastpiece;
    var imgdata;
    var x, y, lr, lc;
    var img = new Image();
    img.src = "iam.jpg";
    img.onload = start;
    function start () {
	context.drawImage(img, 0, 0, canvas.width, canvas.height);
	setInterval(manip, 1000/60);
	manip();
    }
    function manip () {
	while ((col = Math.floor(Math.random() * cols)) === lc) {}
	while ((row = Math.floor(Math.random() * rows)) === lr) {}
    	imgdata = context.getImageData(x=col * colw, y=row * rowh, colw, rowh);
	if (lastpiece) context.putImageData(lastpiece, x, y);
	for (var i = 0, j = imgdata.data.length; i < j; i++) imgdata.data[i] ^= 32;
	lastpiece = imgdata;	
	lc = col;
	lr = row;
    }
}, false);

-

    
    // ES5 (heute)

    function s(p) { return p * scale; }
    
    // ES6 (fruehestens naechstes Jahr)

    s(p) => p * scale;
    

Weil 1px zu klein ist, muss man skalieren. So habe ich den Plotter mit einer Funktion scale(p) ausgeruestet.

Wenn man einen Path nimmt (beginPath/closePath), statt schrittweise mit stroke() zu malen, wird die Berechnung schneller.

Um die Farben zu wechseln muss man aber genau aufpassen, wann man was zeichnet. Sonst zeichnet man alles in der letzten Farbe.

Der Canvas ist trickreich. Die Bilder mit der dicken Linie, die vor lineWidth kam, oder die Versuche mal mit bezierCurveTo oder quadraticCurveTo die Punkte zu verbinden, habe ich entfernt. Macht eh keinen Sinn, sich darueber Gedanken zu machen.

0.1 + 0.3

Wem JavaScript mit IEEE 754 zu ungenau ist, kann mal Number.prototype.toPrecision(digits) ausprobieren.

0.1 + 0.2
// 0.3000000000000004

(0.1 + 0.2).toPrecision(15);
// 0.300000000000000

Es gibt ja immernoch viele, die meinen, daß man mit JavaScript nicht rechnen kann.

Dabei ist der IEEE 754 auch in den anderen Programmiersprachen drin.

Potenz und Exponent

Zwanzig Jahre nach dem Gym.

4- 1 2 = 1 4 1 2 = 1 4 = 1 2

Regeln die man sich merken kann. Wikipedia hat mit den Potenzgesetzen nachgeholfen. Ausgerechnet hab ichs selbst. Ich hoffe, das nicht wieder zu vergessen. ;-) a hoch (m durch n) === die n-te Wurzel aus (a hoch m) und negative Exponenten bedeuten Division a hoch - 3 === 1 : a : a : a

Ebene

Wenn ein Vektor orthogonal auf einem anderen steht, und ausserdem auf Hoehe seines Origins, dann liegt er in seiner Ebene. Das ist der Fall, wenn das dot product zwischen Normalvektor und dem Vektor === 0 ist. Um das zu pruefen habe ich mir eine einfache Funktion geschrieben.

function Plane (a,b,c) {
    "use strict";
    if (this instanceof Plane === false) return new Plane(a,b,c);
    this.normal(a,b,c);
    return Object.seal(this);
}
Plane.prototype = Object.freeze({
    constructor: Plane,
    normal: function (a,b,c) {	// .setNormals(components)
	this.a = a;
	this.b = b;
	this.c = c;
	this.N = new Vec3(this.a,this.b,this.c);
    },
    contains: function (x,y,z) { // .isInPlane(vec)
	if (x instanceof Vec3 === false) {
	    x = new Vec(x,y,z);
	}
	return this.N.dot(x) === 0;
    },
    d: function (x,y,z) {	// ax + by + cz = d
    	if (x instanceof Vec3) {
	    y = x.y;
	    z = x.z;
	    x = x.x;
	}
	return this.a*x + this.b*y + this.c*z;
    }
});

var p1 = new Plane(0,0,10);
var pv1 = new Vec3(10,0,0); 
var pv2 = new Vec3(0,10,0); 
var pv3 = new Vec3(0,0,10); // sollte nicht so sein
var pv4 = new Vec3(10,10,0); 
var pv5 = new Vec3(10,10,10); // sollte auch nicht sein

console.log(p1.contains(pv1));
console.log(p1.contains(pv2));
console.log(p1.contains(pv3));
console.log(p1.contains(pv4));
console.log(p1.contains(pv5));

/*
true
true
false
true
false
*/

Matrix

Jetzt muss ich den Code mal langsam schreiben. Also als erstes multipliziere ich eine 3x3 Matrix mit einer 3x1 Matrix (einem Dreikomponentenvektor). Das macht man, indem man das Dot Product (Skalarprodukt) von der ersten Spalte mit dem ersten Kompenenten, der zweiten Spalte mit dem zweiten Komponenten und der dritten Spalte mit dem dritten Komponenten bildet.

function Mat3x3 (a1,a2,a3, b1,b2,b3, c1,c2,c3) {
    "use strict";
    if (this instanceof Mat3x3 === false) return new Mat3x3(a1,a2,a3,b1,b2,b3,c1,c2,c3);
    this.a1 = a1 || 0; // a a a
    this.a2 = a2 || 0;
    this.a3 = a3 || 0; 
    this.b1 = b1 || 0; // b b b
    this.b2 = b2 || 0;
    this.b3 = b3 || 0;
    this.c1 = c1 || 0; // c c c 
    this.c2 = c2 || 0;
    this.c3 = c3 || 0;
    return Object.seal(this);
}
Mat3x3.prototype = Object.freeze({
    multiply: function (x,y,z) {
    	if (x instanceof Vec3) {
	    y = x.y;
	    z = x.z;
	    x = x.x;
	}
	return new Vec3(
 	    this.a1 * x + this.b1 * x + this.c1 * x,
 	    this.a2 * y + this.b2 * y + this.c2 * y,
 	    this.a3 * z + this.b3 * z + this.c3 * z
	);
    }
});

console.log("matrix");
var m1 = new Mat3x3(10,0,0, 0,10,0, 0,0,10);
console.dir(m1.multiply(v1));
console.dir(m1.multiply(v2));
console.dir(m1.multiply(v3));
console.log("matrix 2 dot products ");
var m2 = new Mat3x3(23,23,23, 10,10,10, -20,-20,-20);
console.dir(m2.multiply(v1));
console.dir(m2.multiply(v2));
console.dir(m2.multiply(v3));

/*

matrix
{ x: 60, y: 50, z: 10 }
{ x: 10, y: 20, z: 10 }
{ x: 50, y: 30, z: 0 }
matrix 2 dot products 
{ x: 78, y: 65, z: 13 }
{ x: 13, y: 26, z: 13 }
{ x: 65, y: 39, z: 0 }

*/

fib(sys)

Zum Schluss des Abends habe ich in 6.01 noch Fibonacci als System (elektrotechnisch als sog. System) gesehen. Seit 6.042 weiss ich, dass es sich um Wachstum handelt, was der Herr untersuchte. Eigentlich Kaninchen, welche ab dem 2. Monat neue Kaninchen zeugen. Woraus das fib(n) = fib(n-1) + fib(n-2) enstand. In Mathe fuer Informatiker ging es um einen Professor der loslegt und ab dem 2. Jahr einen neuen Professor erzeugt, die wiederum ab dem 2. Jahr neue Professoren erzeugen.

Ich glaube der E-Technik Kurs wird mir richtig Spass machen, ich lerne gerade, Systeme zu verstehen, die ich schon als Buch hatte, mir aber "trocken" nur halb so einleuchteten. Freu mich schon auf 6.03 Signals and Systems, da kriegt man das alles komplett. Ich denke mal 6.01 hat nicht "alle" Lektionen, weil die anderen Sessions im Lab oder so verbracht wurden. Die 5 knuepft an die 3. an. Die 4. werden sie wohl den Wallroboter programmiert oder gebaut oder angeschaut haben.

Mit dem Tool dia kann man Systeme uebrigens darstellen. Und es gibt dazu glaube ich noch Tools auf Linux, um so Dinge zu schalten. Ich bin schon in Gedanken beim Loetstift, aber das wird wohl ein Wunsch sein, den ich mir erst mit 40 erfuellen kann. :-)

Vektoren, Vektoren, Vektoren

(Für Anfänger)

In meiner neuen Datei mat.js findet sich eine andere Variante von Vec3 als vor ein paar Tagen in vecs.js.

function Vec3 (x,y,z) {
    "use strict";
    if (this instanceof Vec3 === false) return new Vec3(x,y,z);
    this.x = x || 0;
    this.y = y || 0;
    this.z = z || 0;
    return Object.seal(this);
}
Vec3.prototype = Object.freeze({
    magnitude: function () {
	return Math.sqrt(Math.pow(this.x, 2) + Math.pow(this.y, 2) + Math.pow(this.z, 2));
    },
    get length () { // ueberfluessiger doppelter eintrag aber kuerzer
	return this.magnitude();
    },
    dot: function (x,y,z) {
	if (x instanceof Vec3) {
	    y = x.y;
	    z = x.z;
	    x = x.x;
	}
	return this.x*x + this.y*y + this.z*z;
    },
    cross: function (x,y,z) {
	var x0, y0, z0;
	if (x instanceof Vec3) {
	    y = x.y;
	    z = x.z;
	    x = x.x;
	}
	x0 = this.y * z - this.z * y; // yzzy 
	y0 = this.z * x - this.x * z; // zxxz
	z0 = this.x * y - this.y * x; // xyyx
	return new Vec3(x0,y0,z0);
    },
    subtract: function (x, y, z) {
    	if (x instanceof Vec3) {
	    y = x.y;
	    z = x.z;
	    x = x.x;
	}
	return new Vec3(this.x - x, this.y - y, this.z - z);
    },
    add: function (x, y, z) {
    	if (x instanceof Vec3) {
	    y = x.y;
	    z = x.z;
	    x = x.x;
	}
	return new Vec3(this.x + x, this.y + y, this.z + z);
    }
});

var v1 = new Vec3(6,5,1);
var v2 = new Vec3(1,2,1);
var v3 =  v1.subtract(v2);
var v4 =  v1.add(v2);
console.log(v1.dot(v2));
console.log("length v1-v4");
console.log(v1.length);
console.log(v2.length);
console.log(v3.length);
console.log(v4.length);
console.log("v1 - v4");
console.dir(v1);
console.dir(v2);
console.dir(v3);
console.dir(v4);
console.log("cross");
var v5 =  v1.cross(v2);
console.dir(v5);
console.log(v5.length);
console.dir(v5.cross(v5)); // A x A ergibt Nullvektor
/*
17
length v1-v4
7.874007874011811
2.449489742783178
5.830951894845301
10.099504938362077
v1 - v4
{ x: 6, y: 5, z: 1 }
{ x: 1, y: 2, z: 1 }
{ x: 5, y: 3, z: 0 }
{ x: 7, y: 7, z: 2 }
cross
{ x: 3, y: -5, z: 7 }
9.1104335791443
{ x: 0, y: 0, z: 0 }
*/

6.01 Intro to Electroengineering and Computer Science

Genau mein Fach, was ich nie studieren konnte. Dank des MIT kann ich die Sachen, die ich in Lehrbüchern, über deren Anschaffung meine Mutter sich aufregte, las, endlich richtig lernen, weil mir der Tutor das automatisch abnickt, was richtig ist.

Cool ist die Einleitung in Signale und Systeme, aber alle anderen Teile sind es auch, auch wenn nur die Haelfte auf archive.org zu finden ist. Dazu gibt es Recitations. Die geben uebrigens bei Anwesenheit und Mitmachen Punkte, zum anderen ist es leicht, damit noch was dazuzulernen, oder sich es leichter zu machen.

6.00SC Introduction to Computer Science and Programming

Bald bin ich durch alle OpenCourseWare Kurse durch, dass ich mich auf meine konzentrieren kann. Hier ein Exempel aus Lektion 4. Ich fange mal mittendrin an, wo die Videos mit 6.6k in 5h/Stück (100MB) auf die Platte schleichen.


// Aus Kurs 6.00 Introduction to Computer Science and Programming Lecture 4
// Gerade angemacht und kurz aufgegriffen und ausprobiert zu Beginn der Stunde.
// Vom Bildschirm von Python nach JavaScript uebertragen

var x = 0.5; // Wurzel von 0.5 zu computen
var epsilon = 0.01;
var low = 0.0;
var high = Math.max(x, 1.0);	// ueberfluessige Zeile vom Bildschirm. high = 1.0, da x = 0.5
var ans = (high + low) / 2.0;
while (Math.abs(Math.pow(ans,2)-x) >= epsilon && ans <= x) {
    console.log("ans =", ans, ", low = ", low, ", high = ",high);
    if (Math.pow(ans,2) < x) {
	low = ans;
    } else {
	high = ans;
    }
    ans = (high + low) / 2.0;
}
console.log(ans, " is close to square root of ", x);
/*
ans = 0.5 , low =  0 , high =  1
0.75 ' is close to square root of ' 0.5
*/

Dieser Code kann sich Wurzeln naehern. Anders als "Newtons Methode", welche ich kurz aufgegriffen hatte, aber noch nicht weiter verstanden, kann diese nicht auf hohe Präzision, aber sich naehern und in der Tat...

Math.sqrt(0.5);
// 0.7071067811865476

Das gleiche Ergebnis 0.75 gibt das Python Programm in der Stunde aus.. ich denke aber, es wird im Laufe der Stunde noch optimiert. Sie sind gerade dabei. (Was aber klar wird, ist, dass es sich auch um eine "Programmieren für Leute, die noch nie eine Programmiersprache benutzt haben" Klasse handelt, was mich vielleicht mal langweilt. Wir werden sehen.

Fortschritt im Kleinen

Das hier ist mit xp = (d*x) / (z+d); yp = (d*y) / (z+d) erzeugt. Ob d fuer ax+by+cz=d steht? Oder doch fuer Distanz d? Ich weiss nicht. Ich darf diese Formel, weil sie dieses Ergebnis bringt, genauer untersuchen. In der Tat haben Aenderungen von d und z Auswirkungen auf die Darstellung des Dreiecks (der Canvas kennt aber nur x und y, bedenke). Wenn ich ein wenig hinterfrage, werde ich schon drauf kommen. Das hier sind beides die gleichen Koordinaten. Das Kleine ist umgerechnet und das Grosse original.
    var p0 = Point(10,10,250);
    var p1 = Point(10,250,250);
    var p2 = Point(100,100,250);
    var d = 250;
    var p0p = zp(p0.x,p0.y,p0.z, d);
    var p1p = zp(p1.x,p1.y,p1.z, d);
    var p2p = zp(p2.x,p2.y,p2.z, d);

dot product und cross product

Eine ganz schoen lehrreiche Woche.

Das ist so einfach, dass ich denke, dass man es in der Oberstufe schon hatte. Ich wuerde es der Hauptschule bereits zutrauen. Genauso wie das einfache Rechnen mit Matrizen. Dafuer muss man nicht unbedingt in die "Oberstufe". Wer die ueberspringt hat ja, wie ich keine Chance mehr im Leben. Es war keine Absicht. Aber die Strafe kassiere ich bis an mein Lebensende. Was fuer die Gesellschaft mehr als ein Armutszeugnis ist, was sie so bietet.

Jedenfalls ist es total einfach und macht Spass. Ich kann auf einmal ein wenig mit Vektoren rechnen. Seiten von Dreiecken. Flaechen in der Ebene, Volumen im Raum. Wenn ich jetzt die X-Achse als Vektor x sehe, und die Y-Achse als Vektor y, dann erhalte ich mit xxy einen Vektor z in den Raum. Das ist zwar keine Loesung fuer die Abbildung von 3D Objekten im 2D Raum, ich bin mit der Entfernung und der Skalierung noch zugange und weiss, dass ich zum Schluss genau das gleiche schreiben werde, wie die Graphikprogrammierung vorschreibt. Nur - werde ich es dann verstanden haben :-).

cos α = b2 + c2 - a2 2bc

Der Linear-Algebra Kurs mit Gilbert Strang ist uebrigens total geil. Seit dem Multivariabelcalculus kann ich det(A,B,C) erklaeren und was a1b2 - a2b1 bedeutet. Auf dem Weg zum Cross Product kam das erstmal dran. Auf die Art und Weise kann man naemlich Flaeche und Volumen berechnen.

Eine ganz schoen lehrreiche Woche. Ich finde die Idee, auf einmal auf OpenCourseWare zu stehen, und in alle Fakultaeten, die ich immer mal besucht haben wollte, mal reinzugucken, gut. Ich lerne durch eigene Anstrengung problemlos einige wichtige Sachen fuer mein weiteres Leben. Meine kommenden Source Codes werden es mir danken. Endlich mehr Operationen, in denen Math vorkommt :-)

{}[key] oder [].indexOf(key)

Was ist schneller? Nach keywords im Array suchen, oder das adressieren eines Objects per [subscript] Key?

    /* Das ist langsam, jedes | muss vgl. werden */
    
    var keywords = /if|else|while|do/;
    if (keywords.test("do")) {
    
    }

    /* Das ist langsam, der Array wird durchlaufen */

    var keywords = [ "if", "else", "while", "do" ];
    if (keywords.indexOf("do") > -1) {
    
    }
    
    /* Das ist besser, ein HashCode computed ergibt den [slot] */
    
    var keywords = {
	if: "if",
	else: "else",
	while: "while",
	do: "do"
    };
    if (keywords["do"] === "do") {
	// Moment == "do" kostet einen Vergleich
    }
    
    /* Das geht noch schneller, der Vergleich kann weg */
    var keywords = {
	if: "true,
	else: true,
	while: true,
	do: true
    };
    
    if (keywords["do"]) {
    }
    

Ein Ausflug in die Welt der Algorithmen laesst mich b) das Objekt begründen. Denn Wenn ich h(key) compute und dann objecthash[key] raussuche, komme ich mit JavaScripts O(1) davon. Wenn ich aber den keywords.indexOf(key) !== -1 nehme, wird der Array linear durchlaufen, was im unguenstigen Fall keywords.length = n ist, was wie gelaeufig O(n) fuer einen Array bedeutet.

syntax.js benutzt unter anderem noch Array Lookups (Update: und RegExp, moegl. quadratische Laufzeit!). An der Stelle denke ich mir, die Geschwindigkeit noch um einen sichtbaren Faktor verbessern zu koennen. Das heisst, alle keywords nochmal in ein Objekt stopfen und anstelle von indexOf (oder dem Regexp) absuchen. Ich glaube, eine function isKeyword (word) { return keywords.indexOf(word) !== -1; } nutzt den Array noch.

Update: keywordsRegExp.test(word) war es, was es auszutauschen gilt. Das Objekt wird auch faster als der Regulaere Ausdruck /if|else|while|do/ sein, der wahrscheinlich sogar schlimmer als der Array ist, weil er jeden Buchstaben neu ansetzen darf... Hier ist noch was rauszuholen.

Türme von Hanoi

Eigentlich wollte ich das Problem mal in Angriff nehmen. Ich erinnerte mich daran, dass es auch in Helmut Balzerts Lehrbüchern der Informaik vorkam, und ich es da das erste mal gelöst hatte. Wenn auch noch nicht graphisch programmiert. Jetzt hat die Wikipedia den Algorithmus bereits verraten.

    /* Die Saulen und die drei Scheiben */

    var a = [3,2,1];
    var b = [];
    var c = [];
    
    /* Die Moenche bei der Arbeit. */

    function bewege(i, a, b, c) {
	if (i > 0) {
	    bewege(i-1, a, c, b);
		var disc = a.pop();
		c.push(disc);
		console.log("["+a+"] ["+b+"] ["+c+"]");
	    bewege(i-1, b, a, c);
	}
    }
    
    console.log("["+a+"] ["+b+"] ["+c+"]");
    bewege(3, a, b, c);
    console.log("["+a+"] ["+b+"] ["+c+"]");
    
    
/*
[3,2,1] [] []
[3,2] [] [1]
[3] [1] [2]
[] [3] [2,1]
[] [2,1] [3]
[2] [3] [1]
[] [1] [3,2]
[] [] [3,2,1]
[] [] [3,2,1]
*/

Länge beliebiger Linien

Canvas-2D

Also ich habe eine schraege Linie L auf dem Bildschirm. Begrenzt durch P(2,1) und Q(7,4). Die Frage ist jetzt, wie lang ist die (in Pixeln)?

Habe ich es rausgefunden? Der Vektor PQ-> von PQ ist <5,3>. Und wenn man jetzt die Wurzel von 52 + 32 zieht, dass ist die Wurzel von 34, erhaelt man ein Ergebnis, |PQ->| ˜ 5.83. Das entspricht dem, was ich ungefaehr gemessen habe (mit Kuli skizziert) und ich denke das ist die Loesung.

Kurze Probe mit einer waagerechten P(1,1) und Q(6,1). Vektor PQ-> ist (6-1, 1-1) also <5,0>. (MathML Symbole muss ich noch ueben.) Und die Wurzel aus 25 ist 5. Die Laenge ist, ich habe es mit y = 1 einfach gemacht, auch 5, fuers Auge ablesbar. Scheint zu stimmen.

    // Berechne die Laengen der Seiten a, b, und c durch die Punkte A,B,C.
    // Als naechstes sind dann die Winkel und In- und Umkreis, Hoehen, p,q, etc. dran. ;-)
    a = Math.sqrt(Math.pow(C.x - B.x, 2) + Math.pow(C.y - B.y, 2)); 
    b = Math.sqrt(Math.pow(A.x - C.x, 2) + Math.pow(A.y - C.y, 2)); 
    c = Math.sqrt(Math.pow(B.x - A.x, 2) + Math.pow(B.y - A.y, 2)); 

Wikipedia: Vektor Weil ich nur amerikanisches Material lese, ich aber wissen muss, dass Sachen wie Dot Product und Skalarprodukt das Selbe sind. Die Wikipedia bietet viel perfekt gesetzte Mathematik in deutscher Sprache. Und seit ich Mathe für Informatiker geguckt habe, kann ich ∀, ∃ und einige andere Symbole endlich (und für immer) auch lesen und sprechen.

Differentialgleichungen

Zu Beginn des Unterrichts, in der 1. Lektion erklaert der Professor den Unterschied zwischen Computer und Mensch, wie sie die Gleichungen zeichnen.

Zeichnen von Differentialgleichungen:

Computer Mensch
1. Waehle (x,y) im gleichen Abstand 1. Waehle die Kurve c
2. berechne x,y 2. f(x,y) = c
3. Zeichne das Stueckchen Linie an x,y -|- (wiederhole 1.-3.) 3. Male c -|-|-|-|-|-|-|-|- (fertig)

Der Punkt ist, dass der Mensch lieber die Kurve zeichnet, waehrend der Computer problemlos jedes Lineelement berechnet kann. Was bedeutet bei jedem x,y einmal f(x,y) zu berechnen. Fuer einen Menschen sei das horrible, meint er.

syntax.js Parser

Jetzt habe ich zwei Monate nicht weiterprogrammiert an syntax.js. Im Februar waren nicht nur mein Schatz und eins unserer Kaninchen krank (gottseidank wurden sie auch nacheinander wieder gesund), nein, zum Ende des Monat habe ich mir dann CS61B angeguckt, weil mir der Datenstruktur und Algorithmuskurs auffiel, und das immer in meinem Interesse lag. Im Maerz habe ich dann selben Kurs nochmal vom MIT gezogen (6.006) und bei Richard Buckland (Australien) mal reingeguckt. Der hat aber zu volle Klassen und redet querbeet statt (nur) vom Thema der Stunde. Im April mache ich dann auf einmal mit MIT OpenCourseWare weiter. Nur irgendwie bin ich jetzt wohl vom Parser in syntax.js abgerutscht. Dabei habe ich mich nicht verprogrammiert, dass er nicht geht, der ist so flexibel, dass man ihn jederzeit weitermachen kann. Ich denke oft daran, denke oft an EcmaScript 6.

Ich lese gerade die Unterrichtsmaterialien für 6.035 Computer Language Engineering, wovon ich mir letzten Monat schon die erste Lektion angeguckt habe. Ich habe ueber Automatentheorie, Regulaere Ausdruecke und Komplexitaet ebenso ein Buch (Hopcroft, Ullman, Motwani) gehabt, wie Linux-Unix-Profitools (mit SED, AWK, LEXX, YACC, MAKE) von Helmut Herold. Das ist jetzt zehn Jahre her. Aber damals habe ich schon Parsetrees gesehen, und mit lex und yacc probiert, ebenso wie mit AWK (womit man kleine-mittelgrosse coole-komplexe Parsingskripte fuer die Bash schreiben kann), was zu generieren,

Im Januar habe ich den 99-Zeilen Syntaxhighlighter um weitere 4398 Zeilen erweitert, was Tokenizer (Lexer) und Scanner (Parse Tree), sowie die Primitiven erster UI Elemente (AST-Ausführung, Syntaxbaum, Tokenstatistik) beinhaltet. Aufgehoert hatte ich Anfang Februar halt, da hatte ich bereits Rest-Arguments und den Spread-Operator, sowie ein Destructuring Pattern vom kommenden EcmaScript 6 Standard eingebaut, sowie eine ToValue(ast) Funktion, die den AST ausfuehrt. Anstelle von ToValue(ast) muss noch eine ToByteCode(ast) und dann ToValue(bytecode) Stufe eingebaut werden.

Kurzum, 6.035 Computer Language Engineering behandelt genau das. Und nicht zu knapp. Irgendwann moechte ich mit dem Parser auch weitermachen, weil ich ihn gebrauchen kann.

Lineare Algebra

Ich habe Stift und Papier genommen und mitgerechnet und mitgezeichnet. 2x2 und 3x3 Gleichungen habe ich bereits geloest. Und ich kann jetzt die Vektoren der Spalten zeichnen. Das ist schonmal ein guter Start.

Computergraphik

Also xp = d*xz+d = x(z/d)+1 und yp = d * yz + d = x(z/d)+1 kommt mir schon bekannt vor. Ich glaube sowas in Linux 3D Grafikprogrammierung Band 1 vor zehn Jahren gelesen zu haben.

Noch ein Weilchen und ich werde jubeln.

RollingHash

Weil eine String-auf-String Suche geradezu quadratisch ist, oder halt O(s * n), auf jedem Buchstaben muss ein neuer Vergleich begonnen werden, der dann noch durchlaufen muss. Das kann bei grossen Texten lange dauern, ist irgendwann in den Neunziger Jahren ein neuer Algorithmus aufgetaucht. In 6.006 Einführung in Algorithmen gibt es eine Lektion, in der der Karp-Rabin Algorithmus vorgestellt wird. Ein Rolling Hash. Richtig implementiert laeuft er in O(s+n+m) wobei m noch der finale Vergleich zwischen den gematchten HashCodes sei. Also das geht so.

Urspruenglich denke ich, implementiert man ihn so, dass man mit den rh.skip() und rh.append() Operationen das erste Zeichen entfernt, oder ein letztes hinzufuegt. Die Struktur aktualisiert den Hashcode. Den vergleicht man laufen mit dem HashCode des Suchstrings. Wenn man eine Uebereinstimmung hat, muss man noch beide OHNE HASH vergleichen, weil im Hashing Kollisionen ueblich sind.

function RollingHash (input) {
    "use strict";
    
    var me = this;
    var frame = "",  framecode = null, framesize = 0;
    var search = "", searchcode = null;
    var base = 26, code_a =  ("a").charCodeAt(0);
    var pos = 0;

    function h (c) {
	var i = 0;
	var hashval = 0; 
	while (i < c.length) {
	    hashval += (c.charCodeAt(i) - code_a);
	    ++i;
	}
	return base * hashval; 
    }
    
    function skip () {
	var c = frame[0];
	frame = frame.slice(1);
	framecode -= h(c);
    }
    function append (c) {
	frame += c;
	framecode += h(c);
    }

    function compare (s) {
	if (s===undefined) throw "nothing to search for";
	search = s;
	searchcode = h(search);
	framesize = search.length;
	frame = input.substr(0, framesize);
	framecode = h(frame);
	pos = framesize-1;
	do {
	    if (searchcode === framecode) {
		if (input.substr(pos-framesize+1, search.length) === search) { 
		    return pos-framesize+1;
		}
	    } 
	    if (pos < input.length-1) {
		++pos;
		skip();
	        append(input[pos]);
	    } else break;
	    
	} while (1);
	return -1;
    }

    function reset () {
	frame = "";
	framecode = 0;
    }
    function update (v) { 
	input = v; reset(); 
    };
    
    if (me instanceof RollingHash === false) return new RollingHash(input);
    me.skip = skip;
    me.append = append;
    me.search = compare;
    me.reset = reset; 
    me.update = update; 
    Object.defineProperty(me, "hashcode", { get: function () { return framecode; }, configurable: false })
    if (!input) reset();
    
    return Object.freeze(me);
}

var input = "In diesem Text versuche ich jetzt was zu finden";
var rh = new RollingHash(input);

console.log("Ergebnisse vom HashCode Vergleich:");
console.log(rh.search("geht nicht"));
console.log(rh.search("find"));
console.log(rh.search("versuch"));
console.log("Ergebnisse von indexOf:");
console.log(input.indexOf("geht nicht"));
console.log(input.indexOf("find"));
console.log(input.indexOf("versuch"));

/*
Ergebnisse vom HashCode Vergleich:
-1
41
15
Ergebnisse von indexOf:
-1
41
15
*/

So wie ich das jetzt in JavaScript implementiert habe, gebe ich dem keine O(s+n+m), bin aber in etwa dran. .charCodeAt() gilt bestimmt als konstant. input.substr ist das, was ich unter +m verstanden habe. Ich vermute aber, dass frame.slice(1) auch O(frame) ist, und ich bei jedem skip O(c+frame) rechnen kann. Wenn ich falsch liege, auch gut. Was kostet frame.slice()? Anderseits bin ich aber auch so der Meinung, dass meine Arbeit ueber konstant liegt und ein bisschen laenger braucht.

Hier noch was ueber Unklarheiten oder Dummheiten im Design des Beispiels.

Die Operationen reset() und update() addressieren die Unstimmigkeiten mit mir, wie ich den ADT zu implementieren habe. Soll input und search wieder raus und nur skip und append und ein Code rauskommen? Dann muss man alles andere jedesmal selbst neu schreiben, oder sollte man die Variabeln input und frame einfach korrekt benennen und alle anderen Werte synchronisieren? Das ist alles Sache des Software-Designers und nicht mehr Sache des Algorithmus, auch wenn sich der Designer dabei wieder Gedanken um die Komplexität seines Designs machen muss.

Computergraphik

/* Die Magnitude eines Vektors ist das Dot Product des Vektors mit sich selbst. 
    Heraus kommt eine |A| = 
*/

function magnitude(a,b,c) {	
    if (c!==undefined) {
	return Math.sqrt( Math.pow(a,2) + Math.pow(b,2) + Math.pow(c, 2) ); 
    } else {
    	return Math.sqrt( Math.pow(a,2) + Math.pow(b,2) ); 	
    }
}

/* Dann gibt es da noch a*b = |a|*|b|*cos(Θ) und so Dinge, die wiederholen
sich alle. Das macht richtig Spass, sich nacheinander, wenn auch langsam, an 
Einzelheiten zu erinnern, die man gerade aufgegriffen hat. */

Waehrend ich als erste Übung aus der Mathematik Vektoren und Matrizen machen werde, und endlich mit dem Cross Product und dem Dot Product, Normalenvektoren und der Ebene, Matrizen und Einheitsvektoren arbeiten will, habe ich mir schonmal einige Lektionen besorgt. Ich denke, ich werde ein halbes Jahr lang mit 6.6k Videos saugen, waehrend ich meine Uebungen mache, oder mal nicht zuhause bin.

  • CS61B: Datenstrukturen und Algorithmen /Java (Berkeley) [komplett]
  • 6.006: Datenstrukturen und Algorithmen /Python (MIT) [komplett]
  • 6.042j: Mathematik fuer Informatiker (MIT) [komplett]
  • 6.035: Computer Language Engineering [nur die erste Lektion, werde ich wegen Ecma-262 und syntax.js aber ganz machen]
  • - Mathe -
  • 18.01/18.02: Single und Multivariable Calculus (MIT) [bis Examen 1]
  • 18.06: Lineare Algebra, [die ersten zwei Lektionen]
  • - Physik
  • 8.01: Physik I Klassische Mechanik (MIT) [die ersten Lektionen]
  • 8.02: Physik II Elektrizität (MIT) [die ersten Lektionen]
/* Beschleunigung - geht hier von einer Startgeschwindigkeit von 0 aus, denke ich. */
    
function accel(s, t) {
    return s / Math.pow(t, 2);
}

/* Geschwindigkeit */

function speed (s, t) {
    return s / t;
}

/* Ausprobieren */

var s = 1000;	// mm	
var t = 1000;	// ms	
console.log(accel(s, t));	// 0.001	
console.log(speed(s, t));	// 1

s = 10000;	// mm
t = 10000;	// ms
console.log(accel(s, t));	// 0.0001
console.log(speed(s, t));	// 1

s = 100;	// mm
t = 10000;	// ms
console.log(accel(s, t));	// 0.000001
console.log(speed(s, t));	// 0.01

s = 10000;	// mm
t = 100;	// ms
console.log(accel(s, t));	// 1
console.log(speed(s, t));	// 100

/*
0.001
1
0.0001
1
0.000001
0.01
1
100
*/

/* Jetzt muss ich noch umwandeln: Meter, Millisekunden, etc. */

convert.sizes = { "mm" : 1, "cm": 10, "dm": 100, "m": 1000 };
function convert(value, from, to) { 
    var sizes = convert.sizes;
    value *= sizes[from];
    value /= sizes[to];
    return value;
}

console.log(convert(13, "m", "mm")); // 13000 mm
console.log(convert(13, "mm", "m")); // 0.013 m

Als ich vor einem Monat OpenCourseWare entdeckte freute ich mich, auf einmal Zugriff auf die Elektrotechnik-Fakultät zu haben. Wenn ich mit Mathe einigermassen assimiliert bin, mache ich mit Circuits and Electronics, Signals and Systems weiter. Weil ich eine 5GB Traffic habe, kann ich die nicht einfach alle nacheinander abspeichern. Ich wuerde ja glatt meine Festplatte rasieren, um sie mit OpenCourseWare zu fuellen. Aber gucken und machen kann ich eh nur eine nach der anderen. Und dafuer habe ich genug.

  • 6.387: Computergraphik (keine Videos) - aber komplettes Material zum Lernen!!!
  • 6.838: Computergrafik (keine Videos)

Natürlich habe ich das Kursmaterial downgeloaded und mich mittlerweile mit der Bedienung angefreundet. Jetzt untersuche ich bereits die Problem Sets und werde mich darum kuemmern, auch Aufgaben zu machen. Damit ich den Lernerfolg auch verbuchen kann.

(Code entfernt)

Noch habe ich keine Ahnung (*), was ich da mache. Die Ebene hatte ich nicht mehr in der Schule. Gottseidank kommt das hier alles vielfach vor, dass ich in ein paar Wochen, nach einigen Aufgaben, dahintergestiegen sein werde. Ich kann uebrigens noch Gleichungen 2., 3., 4. Grades lösen, so wie es scheint. Jedenfalls mit ein wenig Praxis garantiert.

(*) Update: Kommt

Wer schreibt ein neues ls?

Leicht, kann aber anspruchsvoll gestaltet werden: Mit node.js kann man ja auch Systemtools fuer Unix (und sogar Windows) schreiben. Anstelle sie mit der Funktion print zu drucken kann man die files auch einzeln untersuchen und gruppieren. Manchmal haette ich gerne ein LS, was mir ausgibt, was ich will und wie ich es will. Und mir zum Beispiel mal meine .js Dateien durchzaehlt und nach was guckt. Ein wenig mehr als ls. Was man sich mit "ls | grep | diff | wc" (in abwechselnden Reihenfolgen) zusammenbauen kann. Ich mache gerade OpenCourseWare, dass ich nicht weiss, ob ich das selbst mache. Der Bildschirm und das Geraet sind erstmal ein paar Tage blockiert. Files einlesen, zaehlen, auswerten, ggf mit anderen Befehlen oeffnen und lesen. Auswerten und alles zusammengefasst ausgeben.

var fs = require("fs");
function print(str) {
    console.log(str);
}
function getfiles(err, files) {
    if (err) throw err;
    files.forEach(print); // anstelle von print -> analyze
}
function ls (dir, options) {
    fs.readdir(dir, getfiles);
}
function main() {
    ls((process.argv[2]||"."), null);
}
if (!module.parent) {
    main();
}

Einfach node ls.js /dir eigeben, und die Namen werden ausgegeben, wie wenn man einfach ls unter Linux eingibt.

Höhe, Tiefe, Groesse eines Binärbaumknotens

Die Groesse eines Knotens ist die Anzahl der Knoten, die er unter sich traegt, sich eingeschlossen. Die Hoehe ist die Anzahl der Level bis zum tiefsten Blatt. Die Tiefe ist die Anzahl der Level bis zur root Node. Es gibt die verschiedensten Methode das zusammenzuzaehlen.

Notes - Ein Baum mit n Level maximal 2n Nodes, wenn er komplett ist. Ein Baum mit n Leveln hat 2n/2 Nodes im Letzten Level, 2n/4, im Level darueber, 2n/8 im Level darueber, und 2n/2n Nodes in der Root. Im Array findet man die left und right Nodes an der Position 2i und 2i+1 und parent eben an Math.floor(i/2) (was mit floor 2 und 3 jeweils 1 ergibt). Die Binaerbaeume sind mit ihrem 2er-Logarithmischen Verhalten echt Oberklasse und sich weiter darin zu vertiefen ist ein Muss fuer jeden Softwaretechnik-Fan.


    /* Wie weit ist es bis zum tiefsten Blatt (zaehle umgekehrt runter) ? */

    function height (node) {
	if (!node) return 0;
	else return Math.max(height(node.left)+1, height(node.right)+1);
    }
    
    /* Wie viele Nodes hat der Subtree, einschliesslich der Node selbst ? */
    
    function size (node) {
	if (node) {
	    var l = size(node.left);
	    var r = size(node.right);
	    return l + r + 1;
        }
        return 0;
    }
    
    /* Wie viele Nodes tief bin ich von der Wurzel aus (zaehle umgekehrt rauf) ? */
    
    function depth (node) {
    	var d = 0;
	if (!node) return d;
	while (node) {
	    ++d;
	    node = node.parent;
	}
	return d;
    }
    

Die Namensgebung depth, height, size ist aus dem Algorithmuskurs. Der Code ist der, der mir fuer diese einfachen Funktionen einfiel. Wenn ich sehe, wie ich gerechnet habe, haette ich height und depth glatt andersrum benannt. Aber das ist Sache desjenigen, der es implementiert und die Anleitung zu schreibt, wie er es gemacht hat. Also da habt ihr ein wenig Freiheit, von Lehrstuhl zu Lehrstuhl zu Lehrbuch unterscheiden sich naemlich die Namen der Operationen, so heisst removeMin() zum Beispiel auch extract_min(), etc.

Newtons Methode

Habe das High Precision Number Computing Modul aus dem Algorithmuskurs angemacht, und dachte mir mal, auszuprobieren, wovon geredet wird. Diese Methode von Newton soll sich der Zahl naehern. Ich scheine es aber noch nicht richtig gemacht zu haben, denn sie naehert sich nicht viel weiter. Zum Beweis, dass es nicht der IEEE 754 sei, habe ich das gleiche in C++ geschrieben. Heraus kommt, dass ich noch ueben muss. Ich habe xi+1 = (xi + a/xi) / 2. wohl noch nicht ganz verstanden. Zumindest habe ich mit der Formel an der Tafel Pause gedrueckt. Ich sollte wohl mal zuende gucken :-). Cool ist, dass ich den Ableitungsteil mit den Tangenten langsam begreife, der kam hier kurz vor, weil es ja Newtons Methode ist. Man sieht also, wozu ich das anwenden kann, wenn ich diese Formel hier zum Rechnen kriege.

// mit C++ doubles
#include 
using namespace std;
int newton (int a, int prec) {
    double xi = 1, x = 1;
    for (int i=1; i <= prec; i++) {
	xi = x;
	x = (xi + (a / xi)) / 2;
	cout << x << endl;
    }
}
int main() {
    newton(2,10);
    newton(2,100);
}
/*
1.5
1.41667
1.41422
1.41421
1.41421
1.41421
1.41421
1.41421
1.41421
1.41421
1.5
1.41667
1.41422
1.41421
1.41421
1.41421
1.41421
1.41421
1.41421
1.41421
...
1.41421

*/

// Mit JavaScript Numbers
function newton (a, prec) {
    prec = prec || 10;
    var x = 1, xi = 1, z, n;
    for (var i = 1; i <= prec; i++) {
	xi = x;
	z = (xi + (a / xi));
	n = 2;
	x = z/n;
	console.log(x);
    }
}
newton(2, 10);
newton(2,100);

/*
1.5
1.4166666666666665
1.4142156862745097
1.4142135623746899
1.414213562373095
1.414213562373095
1.414213562373095
1.414213562373095
1.414213562373095
1.414213562373095
1.5
1.4166666666666665
1.4142156862745097
1.4142135623746899
1.414213562373095
1.414213562373095
1.414213562373095
1.414213562373095
1.414213562373095
1.414213562373095
1.414213562373095
1.414213562373095
1.414213562373095
1.414213562373095
1.414213562373095
1.414213562373095
...
1.414213562373095

*/

Auszug. Um die Tangente zu kriegen muss man mit der Ableitung rechnen. Die Formel y = f(xi) + f'(xi) * (x-xi) ist mir bereits mehrmals aufgefallen.

Neben der gerade ausprobierten Divisionsmethode mit a/xi gibt es eine Multiplikationsmethode mit 1/xi * a und einige andere Dinge zu lernen. Interessantes Thema, denn mit den Methoden kann man nicht nur sehr lange irrationale Zahlen ausrechnen, wie die Quadratwurzel von 2 &sqrt2;. Das ist vor allem fuer wissenschaftliche Berechnungen aber auch fuer Computing aller Art unwahrscheinlich wichtig, das zu erlernen.

Patterns

Weil pattern = canvas.createPattern(img, "repeat") mir nicht sagte, wie ich das pattern zeichne, habe ich das image, was ich als Pattern nahm, mit context.drawImage(img, 0,0, canvas.width, canvas.height); gezeichnet. Ist nur ein Bild von mir. Ich haette die Haare vorher kaemmen sollen. Es wurde der vor-letzte Schnappschuss aus der Kamera, die liegt heute noch auf dem Regal. Sie geht nicht mehr an. Von einer Sekunde zur anderen. Das passiert vielen elektrischen Geraeten, denke ich. Mein Laptop hatte ein aehnliches Problem und liegt bis heute daneben. Der alte Rechner hier geht noch.

Wie man sieht, sieht man noch context.fillRect(...); mit context.rotate(0.1), sowie einem context.translate(10, 0); vor dem letzten rotate. Der Stack den man saven und restoren kann, der haelt die Transformationmatrix, eine einfache SVGMatrix, und die strokeStyles und anderen Attribute. Dafuer ist das saven und restoren der Einstellungen. ist ganz nuetzlich. Gerade, weil die Matrix wieder runter gepoppt wird und man die nicht immer zurueckstellen muss. In dem Beispiel hier wird aber ohne restore() vor der naechsten Rotation weiter rotiert. Da sieht man, wie es ist, wenn man die Matrix nicht mit .save() auf den Stack pusht. Die Colors sind ebenfalls auf die zuletzt gewaehlte Farbe gegangen, man kann aber keine Auswirkungen beobachten.

Ein wenig Unsicherheit bei der ersten Verwendung der arcTo Funktion gehoert dazu. Die Abbildungen in der Spec verraten aber, wie der Winkel mit der aktuellen Position, einem Scheitelpunkt (x0,y0) und einem Punkt auf dem anderen Schenkel (x1,y1) aufgebaut ist, zwischen dessen Schenkeln man den arc mit dem radius r zeichnet. context.arcTo(x0,y0,x1,y1, r);.


OpenCourseWare ist cool. Jetzt habe ich Algorithmen und Datenstrukturen, Mathe fuer Informatiker, das erste Viertel vom Calculus und gucke bei Physics I + II rein. Was dann sein muss, sind die 6.xx Kurse fuer Elektroingenieure (Richtung Computerwissenschaften). Die TU kann nicht besser sein ;-) (nur live noch cooler) Und ich denke, ich werde ein Jahr lang bueffeln.

Canvas Spezifikation

Das Beispiel ist mit Copy und Paste aus der Canvas Spezifikation gekommen, ich wollte es mal ausprobieren.

Die 18.02 Multivariabelcalculus Klasse beginnt mit Vektoren und Matrizen. Es ist die ideale Einführung für mich in meine alten Computergrafikgrundlagen und -probleme. Der Matheunterricht animiert mich dazu, es diesmal programmiert zu kriegen.

Text Metrics

Hat nur width? Die Canvasspezifikation redet von mehr Attributen, mit denen man den Text ausmessen kann. Steht beim TextMetrics Objekt.

Canvas + Worker

Ich uebe gerade mit dem HTMLCanvasElement umzugehen. Ich habe bislang zwei Uhren programmiert, und das ist jetzt fast ein Jahr her. Das war zu Beginn meiner JavaScript-Phase (oder -berufung).

Ich hab auf 2ality (hat die besten JavaScript Artikel) bereits gelesen, dass Ian Hickson eine Schnittstelle fuer Canvas und WebWorker vorgeschlagen hatet. In den aktuellen Docs kommt sie bereits vor, scheint aber noch nicht zu funktionieren. Wer will, kann es hier testen (canwork.html).

Das Beispiel ist aus den Canvas Docs und sollte nur das Datum sekuendlich ausgeben. Der Clou war, dass die "Berechnung" im Worker stattfand. Und man mit context.commit() dem Proxy mitteilt, den Canvas die Bitmap zu bitBlten.


/* canwork.html */
window.addEventListener("DOMContentLoaded", function (e) {
    var canvas = document.querySelector("canvas");
    var proxy = canvas.transferControlToProxy();
    var worker = new Worker("canwork.js");
    worker.postMessage(proxy, [proxy]);
}, false);

/* canwork.js */
self.onmessage = init;

var context = new CanvasRenderingContext2d();

function draw () {
    context.clearRect(0,0, context.width, context.height);
    context.fillText(new Date(), 0, 100);
    context.commit();
}

function init (e) {
    e.data.setContext(context);
    setInterval(draw, 1000 / 60);
}

Anderseits. Die Malfunktionen funktionieren in jedem Fall. Da macht es nichts, wenn der Worker nicht geht. Wenn man doch sowieso nicht malen kann. Gell? Update: Mittlerweile habe ich ein paar Stunden Matheunterricht geguckt und Canvas geuebt und weiss, dass ich, wenn ich 3D Zeichnen will, die ueblichen Tools aus der Computergrafik brauche. Transformationsmatrizen, um die Projektion auszurechnen.

paint.html
window.addEventListener("DOMContentLoaded", function (e) {

    "use strict";

    var canvas = document.querySelector("#canvas");
    var context = canvas.getContext("2d");
    var brush = new Brush(5, "darkblue");

    function Brush(width, color) {
	return {
	    width: width,
	    color: color
	};
    }
    
    function paint (e) {
	context.save();
	context.strokeStyle = brush.color;
	context.strokeWidth = brush.width;
	context.lineTo(e.pageX, e.pageY);
	context.stroke();
	context.restore();
    }

    canvas.addEventListener("mousedown", paint, false);

}, false);

Single Variable Calculus

Edward stuermt die Mathefakultaet.

d dx xa = axa-1

Hier lernt man nicht nur allerhand fixe Loesungen, sondern auch mehrere Notationen und mehrere Umformungen des gleichen Terms. So macht Mathe wieder Spass.

dy dt = dy dx * dx dt bedeutet Δy Δt = Δy Δx * Δx Δt

Ich denke mir, bevor ich die 6.0xx Kurse vom MIT weitermache, mache ich erstmal die 18er Reihen zum Calculus. Damit ergaenze ich dann Mathe fuer Informatiker und mein grundlegendes Verstaendnis von Mathe. Ich werde mit dem Multivariable Calculus und damit mit Matrizen und Vektoren beginnen (*).

ax + by + cz = d // aus 18.02 - a,b,c ist gleichzeitig der Normalenvektor der Ebene.

Bevor ich dann zu 6.xx Circuits und Electronics, sowie Signals and Systems, komme, mache ich erstmal hier weiter und schreibe weiter Datenstrukturen.

ddxf' = ΔfΔd

Priority Queues

Priority Queues werden als Eventscheduling beispielsweise auf dem Flughafen eingesetzt. Die Struktur ist ein kompletter Binaerbaum oder ein Array, der nach der Minheap Property geordnet ist. Das bedeutet, die parentnodes haben einen kleineren Schluessel als ihre Childnodes. (Maxheap bedeutet das umgekehrt, BST hat links kleiner und rechts groesser als ihr Parent). Eine removeMin() Operation entfernt die Node mit dem kleinsten Schluessel aus dem Baum und gibt ihre Daten dabei noch zurueck. Also in dem Fall wird die root Node staendig erneuert, dazu muss left oder right anstelle der root Node treten und sein left oder right die entstehende Luecke wieder schliessen. Wenn man die Childpointer besetzt, sollte man erst den linken und dann den rechten nehmen, das ist einheitlich.

Inzwischen habe ich die Operationen zum Umwandeln des Baumes in einen Heap geschrieben. Um mir das Ordnen des Minheaps oder Maxheaps einfach zu machen, lege ich den Baum einfach flach in den Array, sortiere ihn mit Quicksort (!), und restrukturiere den Baum, indem ich die Nodes im Array enstprechend der Heapformel i/2 (parent), i (node), 2i (left child), 2i+1 (right child) wieder neu verknuepfe. Was vielleicht O(lg n+ n lg n+ n/2) fuer *heapify machen koennte. Ich bin da aber noch nicht so sicher drin, das auszurechnen. Aber uebe das nun auch bereits.

if (typeof exports !== "undefined") exports.PriorityQueue = PriorityQueue;

function PriorityQueue (options) {
    "use strict";
    var me = this;
    var root = null;
    var heap = null;

    function Node (k, v, p, l, r) {
	"use strict";
	var me = this;
	var o;
	if (typeof k === "object" && k !== null) {
	    o = k;
	    k = o.key;
	    v = o.value;
	    p = o.parent;
	    l = o.left;
	    r = o.right;
	}
	me.key = typeof k !== "undefined" ? k : null;
	me.value = typeof v !== "undefined" ? v : null;
	me.parent = p || null;
	me.left = l || null;
	me.right = r || null;
	return Object.seal(me);
    }
    
    
    function bst_find (k, node) {
	node = node || root;
	if (node) {
	    if (k === node.key) return node;
	    if (k < node.key) return find(k, node.left);
	    if (k > node.key) return find(k, node.right);
	}
	return null;
    }
        
    function bst_update(k, v, node) {
	return bst_insert(k, v, node, true);
    }
    
    function bst_insert (k, v, node, update) {
	var c;
	c = new Node(k,v, null, null, null);
	if (root === null) {
	    root = c;     
	    return c;
	} else {
	    node = node || root;
	    while (node) {
		if (node.key === k) {
		    if (update) {
			 node.value = v;
	    		return node;
	    	    } else {
	    		return null;
	    	    }
		} else if (k < node.key) {
		    if (!node.left) {
			c.parent = node;
			node.left = c;
			return c;
		    } else {
			node = node.left;
		    }
		} else if (k > node.key) {
		    if (!node.right) {
			c.parent = node;
			node.right = c;
			return c;
		    } else {
			node = node.right;
		    }
		}
	    }
	}
	return null;
    }
    
    function bst_removeMin () { 
	var node = root;
	var right;
	while (node) {
	    if (node.left) node = node.left;
	    else break;
	}
	if (node) {
	    if (node.left) throw "mistaken programming";
	    right = node.right;
    	    node.right = null;
    	    if (!node.parent && right) {
    		root = right;
    	    } else if (!node.parent && !right) {
    		root = null;
    	    }
	    if (right) {
		right.parent = node.parent;
		node.parent = null;
		if (right.parent) {
		    right.parent.left = right;
		}
	    } 
	    if (node.parent) {
	        node.parent.left = null;
	    } 
	}
	return node;
    }
    
    function removeMax () {
    
    }
    
    function inorder(visit, node) {
	node = node || root;
	if (node) {
	    if (node.left) inorder(visit, node.left);
	    var r = visit(node);
	    if (node.right) inorder(visit, node.right);
	    return r;
	} 
	return null;
    }
    
    function levelorder(visit, node) {
	var queue = [];
	node = node || root;
	queue.push(node);
	while (queue.length) {
	    node = queue.shift();
	    visit(node);
	    if (node.left) queue.push(node.left);
	    if (node.right) queue.push(node.right);
	}
    }
    
    function isMinOrder (node) {
	node = node || root;
	if (!node) return false;
	if (node.left) {
	    if (node.key > node.left.key) return false;
	    if (!isMinOrder(node.left)) return false;
	}
	if (node.right) {
	    if (node.key > node.right.key) return false;
	    if (!isMinOrder(node.right)) return false;
	}
	return true;
    }
    function isMaxOrder (node) {
	node = node || root;
	if (!node) return false;
    	if (node.left) {
	    if (node.key < node.left.key) return false;
	    if (!isMaxOrder(node.left)) return false;
	}
	if (node.right) {
	    if (node.key < node.right.key) return false;
	    if (!isMaxOrder(node.right)) return false;
	}
	return true;
    }
    function isBstOrder (node) {
	node = node || root;
	if (!node) return false;
	if (node) {
	    if (node.left) {
	        if (node.key < node.left.key) return false;
		if (!isBstOrder(node.left)) return false;
	    }
	    if (node.right) {
	        if (node.key > node.right.key) return false;
		if (!isBstOrder(node.right)) return false;
	    }
	}
	return true;
    }    
    
    function toTree (list) {
	var tree,  p, n, l, r;
	tree = list[0]; // root node
	tree.parent = null;
	
	// naechste 2er Potenz (aus Bithacks)
	var j = list.length;
	--j;
	j |= j >> 1;
	j |= j >> 2;
	j |= j >> 4;
	j |= j >> 8;
	j |= j >> 16;
	j |= j >> 32;
	++j;
	j = j / 2;  // so ist der Binaerbaum aeh Array genauer durchzulaufen
		    // ohne dass ich die letzte Reihe nochmal ablatsche usw.
	
	// var zweier = 2; while (list.length > zweier) { zweier = zweier * 2; } 

	for (var i = 1; i <= j; i++) {
	
	    // hole nodes
	    if (i > 1) { p = list[Math.floor(i/ 2)-1] || null; }  // i/2
	    else { p = null; }
	    n = list[i-1] || null;	// i
	    l = list[(2*i)-1] || null;// 2i
	    r = list[(2*i)] || null; // 2i+1
	
	    // verknuepfe nodes neu
	    if (n) {
		n.parent = p;
		n.left = l;
		n.right = r;
	    }
	    if (l) { 
		l.parent = n;
		l.left = null;
		l.right = null; 
	    }
	    if (r) {
		r.parent = n;
		r.left = null;
		r.right = null;	
	    }
	}
	return tree;
    }
    
    function toArray (node) {
	var a = [];
	levelorder(function (node) {
	    a.push(node);
	}, node);
	return a;
    }
    function minheapify () {
	// 1. mache array
	var array = toArray(root);
	// 2. sortiere array
	array = array.sort(function (a, b) {
	    if (a && b) {
		return (a.key < b.key);
	    }
	});
	// 3. mache baum.
	var tree = toTree(array);
	root = tree;
	heap = array;
    }
    function maxheapify () {
	var array = toArray(root);
    	array = array.sort(function (a, b) {
	    if (a && b) {
		return (a.key > b.key);
	    }
	});
	var tree = toTree(array);
	root = tree;
	heap = array;
    }
    
    function print () {
	var nodes = 0;
	inorder(function (node) {
	    ++nodes;
	    console.log("node "+nodes+ ": key="+node.key+", value="+node.value+ " (l="+(node.left && node.left.key)+",p="+(node.parent && node.parent.key)+",r="+(node.right && node.right.key)+")");
	});
    }
    
    var me = this;
    if (me instanceof PriorityQueue === false) return new PriorityQueue(options);
    me.insert = insert;
    me.find = bst_find;
    me.update = bst_update;
    me.removeMin = bst_removeMin;
    me.removeMax = null;
    me.minheapify = minheapify;
    me.maxheapify = maxheapify;

    me.ismin = isMinOrder;
    me.ismax = isMaxOrder;
    me.isbst = isBstOrder;
    me.print = print;
    return Object.freeze(me);
}

if (typeof module === "undefined" || (module && module.parent === null)) {

var pq = new PriorityQueue();

pq.insert(30, "Hallo Welt");
pq.insert(20, "Hallo Eddie");
pq.insert(10, "Hallo Queue");
pq.insert(40, "Hallo BSP");
pq.insert(1, "More");
pq.print();

function next () {
    var n;
    n=pq.removeMin();
    if (n) {
        console.log("removeMin().key == " +(n.key) + ", value=" +(n.value));
    } else { 
	console.log("removeMin() == null (Queue empty)"); 
    }
    pq.print();
}

next();
next();
next();
next();
next();
next();

for (var i = 0; i < 10; i++) {
    pq.insert(Math.random().toPrecision(3), "Zufallswert "+(i+1));
}

console.log("ismin = " +pq.ismin());
console.log("ismax = " +pq.ismax());
console.log("isbst = " +pq.isbst());

for (var i = 0; i < 10; i++) {
    next();
}

/*
node 1: key=1, value=More (l=null,p=10,r=null)
node 2: key=10, value=Hallo Queue (l=1,p=20,r=null)
node 3: key=20, value=Hallo Eddie (l=10,p=30,r=null)
node 4: key=30, value=Hallo Welt (l=20,p=null,r=40)
node 5: key=40, value=Hallo BSP (l=null,p=30,r=null)
removeMin().key == 1, value=More
node 1: key=10, value=Hallo Queue (l=null,p=20,r=null)
node 2: key=20, value=Hallo Eddie (l=10,p=30,r=null)
node 3: key=30, value=Hallo Welt (l=20,p=null,r=40)
node 4: key=40, value=Hallo BSP (l=null,p=30,r=null)
removeMin().key == 10, value=Hallo Queue
node 1: key=20, value=Hallo Eddie (l=null,p=30,r=null)
node 2: key=30, value=Hallo Welt (l=20,p=null,r=40)
node 3: key=40, value=Hallo BSP (l=null,p=30,r=null)
removeMin().key == 20, value=Hallo Eddie
node 1: key=30, value=Hallo Welt (l=null,p=null,r=40)
node 2: key=40, value=Hallo BSP (l=null,p=30,r=null)
removeMin().key == 30, value=Hallo Welt
node 1: key=40, value=Hallo BSP (l=null,p=null,r=null)
removeMin().key == 40, value=Hallo BSP
removeMin() == null (Queue empty)
removeMin().key == 0.251, value=Zufallswert 4
node 1: key=0.298, value=Zufallswert 7 (l=null,p=0.460,r=null)
node 2: key=0.460, value=Zufallswert 2 (l=0.298,p=0.608,r=0.582)
node 3: key=0.462, value=Zufallswert 9 (l=null,p=0.557,r=null)
node 4: key=0.557, value=Zufallswert 6 (l=0.462,p=0.582,r=null)
node 5: key=0.582, value=Zufallswert 3 (l=0.557,p=0.460,r=null)
node 6: key=0.608, value=Zufallswert 1 (l=0.460,p=null,r=0.838)
node 7: key=0.692, value=Zufallswert 8 (l=null,p=0.838,r=0.804)
node 8: key=0.804, value=Zufallswert 10 (l=null,p=0.692,r=null)
node 9: key=0.838, value=Zufallswert 5 (l=0.692,p=0.608,r=null)
removeMin().key == 0.298, value=Zufallswert 7
node 1: key=0.460, value=Zufallswert 2 (l=null,p=0.608,r=0.582)
node 2: key=0.462, value=Zufallswert 9 (l=null,p=0.557,r=null)
node 3: key=0.557, value=Zufallswert 6 (l=0.462,p=0.582,r=null)
node 4: key=0.582, value=Zufallswert 3 (l=0.557,p=0.460,r=null)
node 5: key=0.608, value=Zufallswert 1 (l=0.460,p=null,r=0.838)
node 6: key=0.692, value=Zufallswert 8 (l=null,p=0.838,r=0.804)
node 7: key=0.804, value=Zufallswert 10 (l=null,p=0.692,r=null)
node 8: key=0.838, value=Zufallswert 5 (l=0.692,p=0.608,r=null)
removeMin().key == 0.460, value=Zufallswert 2
node 1: key=0.462, value=Zufallswert 9 (l=null,p=0.557,r=null)
node 2: key=0.557, value=Zufallswert 6 (l=0.462,p=0.582,r=null)
node 3: key=0.582, value=Zufallswert 3 (l=0.557,p=0.608,r=null)
node 4: key=0.608, value=Zufallswert 1 (l=0.582,p=null,r=0.838)
node 5: key=0.692, value=Zufallswert 8 (l=null,p=0.838,r=0.804)
node 6: key=0.804, value=Zufallswert 10 (l=null,p=0.692,r=null)
node 7: key=0.838, value=Zufallswert 5 (l=0.692,p=0.608,r=null)
removeMin().key == 0.462, value=Zufallswert 9
node 1: key=0.557, value=Zufallswert 6 (l=null,p=0.582,r=null)
node 2: key=0.582, value=Zufallswert 3 (l=0.557,p=0.608,r=null)
node 3: key=0.608, value=Zufallswert 1 (l=0.582,p=null,r=0.838)
node 4: key=0.692, value=Zufallswert 8 (l=null,p=0.838,r=0.804)
node 5: key=0.804, value=Zufallswert 10 (l=null,p=0.692,r=null)
node 6: key=0.838, value=Zufallswert 5 (l=0.692,p=0.608,r=null)
removeMin().key == 0.557, value=Zufallswert 6
node 1: key=0.582, value=Zufallswert 3 (l=null,p=0.608,r=null)
node 2: key=0.608, value=Zufallswert 1 (l=0.582,p=null,r=0.838)
node 3: key=0.692, value=Zufallswert 8 (l=null,p=0.838,r=0.804)
node 4: key=0.804, value=Zufallswert 10 (l=null,p=0.692,r=null)
node 5: key=0.838, value=Zufallswert 5 (l=0.692,p=0.608,r=null)
removeMin().key == 0.582, value=Zufallswert 3
node 1: key=0.608, value=Zufallswert 1 (l=null,p=null,r=0.838)
node 2: key=0.692, value=Zufallswert 8 (l=null,p=0.838,r=0.804)
node 3: key=0.804, value=Zufallswert 10 (l=null,p=0.692,r=null)
node 4: key=0.838, value=Zufallswert 5 (l=0.692,p=0.608,r=null)
removeMin().key == 0.608, value=Zufallswert 1
node 1: key=0.692, value=Zufallswert 8 (l=null,p=0.838,r=0.804)
node 2: key=0.804, value=Zufallswert 10 (l=null,p=0.692,r=null)
node 3: key=0.838, value=Zufallswert 5 (l=0.692,p=null,r=null)
removeMin().key == 0.692, value=Zufallswert 8
node 1: key=0.804, value=Zufallswert 10 (l=null,p=0.838,r=null)
node 2: key=0.838, value=Zufallswert 5 (l=0.804,p=null,r=null)
removeMin().key == 0.804, value=Zufallswert 10
node 1: key=0.838, value=Zufallswert 5 (l=null,p=null,r=null)
removeMin().key == 0.838, value=Zufallswert 5
*/

DasEine Art EventScheduling habe ich dann mit einem EventQeue ausprobiert. Der Code nutzt die BST Property fuer einen Baum. Ein richtiger PriorityQueue verwendet nicht die BST, sondern die Minheap Property, und verzichtet direkt auf den Baum. Man benutzt nur noch den Array, und den logarithmischen Index (wenn array[key] < array[parent=floor(i/2)], dann swappen der keys und values).

Die Verbindung zum Begriff Queue beruht (vermute ich) im PriorityQueue eigentlich darauf, dass die Nodes nach der Minheap Property geordnet sind, und das kleinste Element damit das Erste ist. Und in einem Queue, da entfernt man immer das erste Element. Und ich denke, beim Original PQ kam auch ein Queue vor, der den Minheap Array unterstuetzte.

var PriorityQueue = require("./priority").PriorityQueue;

EventQueue.prototype = new PriorityQueue;
function EventQueue () {
    "use strict";
    var listeners = {};

    function on (event, listener) {
	if (!listeners[event]) listeners[event] = [];
	listeners[event].push(listener);
    }
    function off (event, listener) {
	var k, l;
	if (!(l=listeners[event])) return null;
	k = l.indexOf(listener);
	if (k > -1) l.splice(k,1);
	return k > -1;
    }

    function dispatch (event, value) {
	"use strict";
	var l=listeners[event], f, args;
	if (l) {
	    args = [].slice.call(arguments, 1);
	    for (var i=0; i < l.length; i++) {
		f = l[i];
		if (typeof f === "function") {
		    setTimeout(function () {
			f.apply(f, args);
		    },0);
		}
	    }
	}
    }
    
    function timerDemo() {
	setTimeout(function removeNext() {
	    var node = me.removeMin();
	    if (node) {
	        me.dispatch("removeMin", node.key, node.value);
		setTimeout(removeNext, 250);
	    }
	}, 250);
    }
    
    var me = this;
    if (me instanceof EventQueue === false) return new EventQueue;
    me.on = on;
    me.off = off
    me.dispatch = dispatch;
    me.timerDemo = timerDemo;
}

var host = new EventQueue();
var keys = [ 234,2526,26265,474574,23512,25234,2626,26245,6,2512,1123,122,13,5415 ];
var values = [ "a","b","c","d","e","f","g","h","i","j","k","l","m","n","o" ];
for (var i = 0; i < keys.length; i++) {
    host.insert(keys[i], values[i]);
}
host.on("removeMin", function (key, value) {
    console.log("-> event removeMin: Es wurde "+key+"="+value+" ausgeworfen.");
});

host.timerDemo();
/*
-> event removeMin: Es wurde 6=i ausgeworfen.
-> event removeMin: Es wurde 13=m ausgeworfen.
-> event removeMin: Es wurde 122=l ausgeworfen.
-> event removeMin: Es wurde 234=a ausgeworfen.
-> event removeMin: Es wurde 1123=k ausgeworfen.
-> event removeMin: Es wurde 2512=j ausgeworfen.
-> event removeMin: Es wurde 2526=b ausgeworfen.
-> event removeMin: Es wurde 2626=g ausgeworfen.
-> event removeMin: Es wurde 5415=n ausgeworfen.
-> event removeMin: Es wurde 23512=e ausgeworfen.
-> event removeMin: Es wurde 25234=f ausgeworfen.
-> event removeMin: Es wurde 26245=h ausgeworfen.
-> event removeMin: Es wurde 26265=c ausgeworfen.
-> event removeMin: Es wurde 474574=d ausgeworfen.
*/

Midterm bis Wahrscheinlichkeit

Ich habe in 6.042: Mathematik für Informatiker jetzt Induktionsbeweise, Numerische Theorie, Graphentheorie, Summen, Rekurrenzen und einiges mehr angeguckt. Fuer den Rest des Semesters geht es jetzt um Wahrscheinlichkeit. Als Grundlage verschiedenster Gebiete der Informatik.

    function mul(a,b) {
	var summe = 0;
	for (var i=1; i <= b; i++) {
	    summe += a;
	}
	return summe;
    }

Ein wenig gegrinst hatte ich, als der Professor Rekurrenzen mit dem Einsetzen von Alpha loeste und eine 1 + sqrt(5)2 und so aehnlich Loesung praesentierte. Ich bin nicht mehr so schnell wie in der Schule. Ich war eigentlich nie schlecht in Mathe. Aber ich bin heute begeisterte und verstehe das viel einfacher.

Loga-Irrtum

So berechnet man den Logarithmus nicht, das Ergebis ist auf jeden Fall das falsche. Dennoch hat mir der Monat, die eineinhalb Monate mit Datenstrukturen, Algorithmen und Mathe für Informatiker den näher gebracht, als je zuvor.

/* Falsche Impl. Die -Summe aus (minus x hoch k + 1) durch (k + 1). 
scheint es ja nicht so einfach direkt zu sein. Warum auch. Ist immer so.
Ich werde die Logarithmusdefinitionen mehrere Tag lesen muessen, 
bis ich "log xy = log x + log y" (multiplikation zur addition) kann.*/

function log (n) {
    var x = n - 1;
    var buf = new ArrayBuffer(Float64Array.BYTES_PER_ELEMENT);
    var r = new Float64Array(buf, 0);
    for (var k=0; k <= n; k++) {
	    r.set(0, r.get(0) + (Math.pow(-x, k+1) / (k + 1)));
    }
    return -r.get(0); 
}

/* Der Float64 hat hier nichts zu bedeuten, um es vorweg zu nehmen.
Der bringt gar nichts, wenn es um den IEE754 Rundungsfehler geht. 
Man kann binaere Files aber so entsprechend ihrer definierten Groesse 
lesen. Hier ist es mehr ein Fehlschlag, als ein nuetzliches Instrument,
um bei der Berechnung eines einfachen Logarithmusses zu helfen. 
Nebebei uebe ich gerade mit den TypedArrays umzugehen, darum das Mixing. */

console.log(log(1));
console.log(log(2));
console.log(log(3));
console.log(log(4));
console.log(log(5));
console.log(log(10));
function ln(n) {
    return Math.pow(Math.E, n);
}
console.log("-");
console.log(ln(1));
console.log(ln(2));
console.log(ln(3));
console.log(ln(4));
console.log(ln(5));
console.log(ln(10));
console.log("-");
console.log(Math.log(1));
console.log(Math.log(2));
console.log(Math.log(3));
console.log(Math.log(4));
console.log(Math.log(5));
console.log(Math.log(10));

/*
0
0.8333333134651184
-1.3333332538604736
35.849998474121094
-524.5333251953125
2542416128
-
2.718281828459045
7.3890560989306495
20.085536923187664
54.59815003314423
148.41315910257657
22026.465794806703
-
0
0.6931471805599453
1.0986122886681098
1.3862943611198906
1.6094379124341003
2.302585092994046
*/

Wie man eindeutig lesen kann, habe ich nicht die richtige Formel und nicht die richtige Implementation erwischt, sondern tappe noch im Dunkeln. Der gute alte Logarithmus, der mir in der Schule aber schon so viel Spass machte, und mich mein halbes Leben praktisch beim Denken begleitet, muss in seiner formalen Form halt neu eingeuebt werden. Damit mir auch so richtig schlecht wird, bevor ich mir noch YouTube konsultiere, habe ich mir schonmal die Wikipedia angeguckt. Logarithmus.

Die Fakultät n!

Die factorial function kennt jeder. Sie multipliziert alle i von 1 bis n { 1 < i < n } miteinander. Heraus kommt ein riesengrosses Produkt, da jeder weitere Zahl ein Faktor wird.

Wenn man eine Menge S hat, und die eine Sequenz s = {a,b,c}, dann hat sie, da |s| = 3 ist, 3! (= 6 moegliche) Permutationen. 10!2! = 1814400

function fac(n) {
    if (n < 2) return 1;
    return fac(n-1) * n;
}

function fac2(n) {
    var x;
    if (n < 2) return 1;
    if (x=fac2.prototype[n]) return x;
    return fac2.prototype[n] = fac(n-1) * n;
}

// Gebe die Ergebnisse der beiden Funktionen fuer die ersten 16 mal aus und nehme die benoetige Zeit auf
var start = Date.now();
for (var i=1; i < 17; i++) {
console.log("fac("+i+") = "+ fac(i));
}
console.log((Date.now() - start) + "ms");
start = Date.now();
for (var i=1; i < 17; i++) {
console.log("fac2("+i+") = "+ fac(i));
}
console.log((Date.now() - start) + "ms");

/*
fac(1) = 1
fac(2) = 2
fac(3) = 6
fac(4) = 24
fac(5) = 120
fac(6) = 720
fac(7) = 5040
fac(8) = 40320
fac(9) = 362880
fac(10) = 3628800
fac(11) = 39916800
fac(12) = 479001600
fac(13) = 6227020800
fac(14) = 87178291200
fac(15) = 1307674368000
fac(16) = 20922789888000
82ms
fac2(1) = 1
fac2(2) = 2
fac2(3) = 6
fac2(4) = 24
fac2(5) = 120
fac2(6) = 720
fac2(7) = 5040
fac2(8) = 40320
fac2(9) = 362880
fac2(10) = 3628800
fac2(11) = 39916800
fac2(12) = 479001600
fac2(13) = 6227020800
fac2(14) = 87178291200
fac2(15) = 1307674368000
fac2(16) = 20922789888000
10ms
*/

fac2 benutzt die Memoizing Technik und speichert alle berechneten Ergebnisse. Das reduziert bei mehrmaligen Zugriff auf die Funktion die benoetigte Zeit deutlich.

    function fac3 (n) {
    	    var x;
    	    if (x=fac3.prototype[n]) return x;
    	    else x = 1;
    	    for (var i=1; i<=n; i++) {
    		x *= i;
    		if (!fac3.prototype[i]) fac3.prototype[i] = x;
	    }
	return x;
    }

Das soll noch eine Bottom Up Loesung sein. Einfach zuerst das, was fehlt berechnen. Und dann das, was danach kommt. Ohne eine rekursive Funktion zu benutzen. Man geht Bottom Up oder von n-1 nach n und in der Programmiersprache mit for und while durch.

Maerz

Habe den letzten Monat archiviert. Habe die letzten zwei Wochen noch 6.042 Mathematik für Informatiker geguckt und mich bis Lektion 16 herangetastet.


Letzten Monat habe ich ein paar Algorithmen bereits gemacht, dann habe ich Mathe geguckt, darum ist die Sammlung weniger fertig als sie sein koennte. Ich mache einfach diesen und auch naechsten Monat weiter damit. Was aber diesmal kommt ist, dass ich wieder Wert auf WebGL (und nur WebGL) legen werde.


Archiv

  • Seit dem letzten Monat versuche ich: Datenstrukturen und Algorithmen zu lernen.
  • Die Einträge vom vorletzten Monat sind alle hier zu finden.
  • Die Einträge vom vorvorletzten Monat sind alle hier zu finden.
  • Die Einträge vom vorvorvorletzten Monat sind alle hier zu finden.
  • Die Einträge vom vorvorvorvorletzten Monat sind alle hier zu finden.
  • Die interessanten Sachen: spidermonkey | libuv | in den headern der anderen

Diese Seite erfordert JavaScript und einen aktuellen Browser, um zu funktionieren.