Dienstag, Juni 26, 2007

Kann man Programmieren lernen?

Kann man das Programmieren erlernen? Sicher! Aber kann es jeder erlernen?

Ich bin über einen Blog auf einen interessanten Artikel gestossen ("The camel has two humps (working title)" von Saeed Dehnadi und Richard Bornat). Darin berichten die Autoren von den vielen vergeblichen Versuchen, die es gegeben hat, das Programmieren erfolgreich zu unterrichten. Denn zwischen 30 und 60 Prozent der Studierenden an Universitäten und Hochschulen scheitern regelmäßig am ersten Programmierkurs. Bei allen Bemühungen: Die hohen Durchfallquoten scheinen unabänderlich zu sein.

Die Autoren behaupten, die Programmierbegabung mit einem Test ermitteln und damit vorhersagen zu können, ob ein Kandidat bzw. eine Kandidatin das Programmieren erfolgreich erlernen wird. Ich halte die durchgeführte Studie für methodisch kritisch, darum sind die Aussagen und Spekulationen mit großer Vorsicht zu genießen. Dennoch lassen Sie uns einmal anschauen, was Dehnadi und Bornat da untersucht haben.

Die beiden gehen davon aus, dass sich dem Programmierunerfahrenen, dem Novizen, beim Umgang mit imperativen Sprachen drei Hürden stellen -- und zwar in der angegebenen Reihenfolge:

  • Zuweisungen und Zuweisungsfolgen

  • Rekursion und Iteration

  • Nebenläufigkeit


In einem Test stellen Dehnadi und Bornat den Studierenden vor dem ersten Kontakt mit einer Programmiersprache einige Fragen zu Zuweisungen bzw. zu Folgen von Zuweisungen; sie testen also lediglich die erste Hürde. Die Probanden müssen via Multiple Choice erraten, welche Werte nach den Zuweisungen gültig sind.

Nach den Tests unterscheiden Dehnadi und Bornat drei Gruppen. Die Annahme ist, dass sich die Probanden ein mentales Modell von der Arbeitsweise von Zuweisungen machen. Versuchen die Probanden, sich bei der Suche nach Lösungen strikt an Regeln zu halten, seien die Ergebnisse auch noch so unsinnig oder seltsam? Oder versuchen sie, etwas sinnvolles aus jeder einzelnen Aufgabe zu holen und entsprechend zu antworten? Oder verweigern sie die Antwort, da diese Zuweisungen wenig Sinn zu machen scheinen? Eine Gruppe, die Konsistenten, beantwortet die meisten bis alle Fragen mit dem gleichen mentalen Modell; das sind die, die sich einer Maschine gleich an ein Regelwerk halten. Die Inkonsistenten sind die, die bei verschiedenen Fragen verschiedene mentale Modelle anwenden; es sind die, die versuchen, jede Zuweisungsaufgabe für sich genommen sinnhaft zu beantworten. Die Blanken verweigern die Antwort auf die meisten oder alle Fragen; sie mögen nicht rätseln, was diese ganze Kryptik für einen Sinn machen soll.

Obwohl jede der drei Gruppen eine absolut vernünftige Strategie für ihr Handeln verfolgt, die durchaus als intelligent bezeichnet werden kann, kommt lediglich das Vorgehen der Konsistenten der Arbeitsweise eines Rechners gleich. Ein Rechner befolgt Regeln der Ausführung und wendet diese stur an. Ob die Ergebnisse Sinn machen oder nicht, hinterfragt ein Rechner nicht.

Interessant ist nun, wie sich die Probanden im Laufe der Zeit entwickeln. Alle belegten einen Programmierkurs und schlossen den Kurs mit einer Prüfung ab. Dehnadi und Bornat wollen nun festgestellt haben, dass einzig die Konsistenten zu bemerkenswert guten oder mittelmäßigen Programmierern werden. Die Inkonsistenten und Blanken bleiben bemerkenswert programmierschwach. Es will fast so scheinen, als lege der frühe Test als Novize die Zukunft in Ketten: einem Inkonsistenten bzw. Blanken scheint der Eintritt in die Programmierwelt verwehrt. Die Autoren schreiben:


[...] it is extremely difficult to teach programming to the inconsistent and blank groups. It might be possible to teach them, if we concentrated on trying to persuade them to see a programming language as a system of rules ([...]).


Vor diesem Hintergrund scheint es besonders fragwürdig, so die Autoren, Java als erste Programmiersprache zu unterrichten. Java wird nicht über ein einfaches Regelwerk definiert, sondern über einen mehrere Hundert Seiten umfassenden Standard.

Mich machen diese Ergebnisse nachdenklich. Was sind die Konsequenzen daraus? Sollten manche Studierenden lieber die Finger von der Informatik lassen, weil ihre Hirne nicht so regelbasiert wie Computer tickern? Andererseits: Nicht jeder Software Engineer muss ein Programmierstar sein. Oder haben wir schlicht noch nicht das richtige Unterrichtsmodell für Programmiersprachen gefunden? Ich hoffe sehr, dass dieser Untersuchung weitere Studien folgen, die besser und erkenntnisreicher sind.

Montag, Juni 18, 2007

Suchen mit Strategie

In den vergangenen Wochen habe ich mich viel mit XML befasst. Für die Verarbeitung eines XML-Dokuments habe ich mir ein Python-Programm geschrieben, das die XML-Darstellung direkt in einen Objektbaum abbildet -- alle weiteren Bearbeitungsschritte führe ich dann in dem Objektmodell aus. Jedes Objekt in diesem Baum hat einen Vorgänger (parent) und keinen oder mehr Nachfolger (childs). Das ist sehr ähnlich zu DOM.

Bei der Verarbeitung einer solchen Baustruktur tritt ein Problem immer wieder auf: Sie suchen Knoten (= Objekte) in dem Baum, die einem oder mehreren Kriterien genügen. Für diese Aufgabe kann man eine sehr flexible query-Funktion programmieren:

def query(criteria):
assert callable(criteria)
result = []
for element in allElements():
try:
if criteria(element) == True:
result.append(element)
except: pass
return result

Dieser query-Funktion übergibt man ein Kriterium in Form eines Lambda-Ausdrucks (das ist eine anonyme, sprich namenlose Funktion; so etwas gibt es jetzt auch in C# 3.0). Zum Beispiel:

query(lambda e: e.tag == "page")

Dieser Aufruf sucht aus dem Objektmodell alle Objekte raus, die in der XML-Darstellung das Tag "page" tragen.

Ein Nachteil dieser Suchabfrage ist, dass alle Elemente (allElements()) durchgegangen werden. Optimiert werden könnte das durch eine Suchstrategie, die nur relevante Elemente nach einem bestimmten Verfahren der Suche zum Test vorlegen würde. Hier die optimierte Version:

def query(criteria,strategy=yieldElements):
assert callable(criteria) and callable(strategy)
result = []
for element in strategy():
try:
if criteria(element) == True:
result.append(element)
except: pass
return result

Dazu zwei Strategien. Die erste Strategie (yieldElements) generiert wie gehabt alle Elemente. Die zweite Strategie (yieldInnerElements) generiert alle Elemente, die im Sinne einer XML-Darstellung "innerhalb" eines gegebenen Elements liegen. Die Strategie ist also parametrisiert.

def yieldElements():
for klass in elementClasses:
for element in klass.instances:
yield element


def yieldInnerElements(element):
def _yieldInnerElements():
def yieldInnerNodes(node):
for n in node.childs:
yield n
for child in yieldInnerNodes(n):
yield child
return yieldInnerNodes(element)
return _yieldInnerElements

Wieder ein Beispiel für eine Abfrage:

query(lambda e: e.tag == "page",yieldInnerElements(chapterOne))

Jetzt werden lediglich die Objekte mit dem Tag "page" herausgesucht, die als Kinder bzw. Kindskinder etc. innerhalb eines chapterOne-Objekts des Objektmodells zu finden sind.

Eine interessante Einsicht ist, dass jede Strategie auch als Teil eines Kriteriums in criteria verstanden werden kann. Die explizite Formulierung einer Strategie optimiert lediglich die Vorlage von Elementen zum Kriteriumstest und beschleunigt das Suchverfahren. Strukturwissen um die Organisation der Daten kann so effizient ausgenutzt werden. Die Parallelen zum Constraint Programming sind kein Zufall!

Donnerstag, Juni 07, 2007

Maschinelles 3D-Sehen

Bislang hat es viele Versuche gegeben, Computern (bzw. Robotern) das Sehen beizubringen -- mit mäßigem Erfolg. Basis für eine erfolgreiche Orientierung im Raum ist die Fähigkeit, die Welt dreidimensional wahrzunehmen. Wir Menschen bekommen das mit unseren zwei Augen hervorragend hin. Und deshalb hat man versucht, das Erfolgsmodell aus der Natur, das "Stereosehen", zu imitieren.

Allerdings ist man damit nicht weit gekommen. Es ist schon bei einem Bild extrem aufwendig und schwierig, aus den zahllosen Bildpunkten abzuleiten, wo Objektgrenzen entlang verlaufen. Bei zwei Bildern wird es nicht weniger einfach, zumal die zwei Bilder in Bezug gesetzt werden müssen und daraus mehr oder weniger präzise eine Information über die Raumtiefe gewonnen werden muss. Das ist so schwierig, dass man es bis heute nicht wagt, autonome Fahrersysteme am "normalen" Straßenverkehr teilnehmen zu lassen. Es gibt auch keine kleinen staubsaugenden oder rasenmähenden Roboter zu kaufen, die sich sicheren Auges zügig durch Wohnung oder Garten bewegen.

Ein Teil des Problems liegt daran, dass unser Stereosehen nur im Nahbereich sehr gut arbeitet. Unsere Augen liegen nur ein paar Zentimeter auseinander, zu wenig, um sehr genaue Entfernungsinformationen daraus berechnen zu können. Information über die Entfernung von etwas wird zu einem großen Teil von unserem Gehirn aus Erfahrungswissen über Größenverhältnisse, Bewegungsverhalten etc. abgeleitet. Das alles zusammen gibt uns die Illusion einer räumlichen Orientierungsfähigkeit, wie sie faktisch durch unseren reinen Sehapparat nicht gegeben ist.

Es ist also fraglich, ob das Stereosehen als Vorlage für maschinelles 3D-Sehen taugt. Müssen wir uns vielleicht nach gänzlich anderen Techniken umschauen? Es gibt sie, die neue Technik des 3D-Sehens, entwickelt von Prof. Dr. Schwarte aus Siegen. Mit Hilfe der PMD-Technologie (PMD steht für "Photonic Mixer Device") liefert eine PMD-Kamera zu jedem Pixel eine Tiefeninformation -- und das bei nur einem Kameraauge! Die Technik ist faszinierend. Sie wird fraglos unsere Zukunft verändern. Können Sie sich das vorstellen? Ein Blick in die Zukunft: In ein paar Jahren halten Sie Ihre Handykamera auf ein Motiv und Sie bekommen ein Raumbild der Szene! Damit ist es für eine Bildverarbeitung ganz einfach, Objektgrenzen in einer Szene zu ermitteln. Denn es wird gesehen, dass das eine Objekt vor oder hinter dem anderen Objekt liegt.

Ich bin sehr gespannt, was diese Zukunft bringen wird. Es werden neue Algorithmen für diese Technik entwickelt werden müssen. Man wird diese neue Technik zu nutzen lernen müssen. Bei aller Begeisterung, die ich dafür aufbringe, es wird sicher 10 oder 15 Jahre dauern, bis diese Technik unseren Alltag zu durchdringen beginnt.

Nehmen wir einmal an, wir sind 20 Jahre weiter und die Maschinen haben keine Probleme mehr beim 3D-Sehen. Dann gibt es immer noch viel zu tun. Was unterscheidet einen Profi-Tennisspieler von einem normalen Tennisspieler? Weder ist es die Fähigkeit zum 3D-Sehen bei der Ballerkennung, noch Reaktionsschnelligkeit. Wenn ein Roboter in der Profi-Liga mitspielen möchte, so muss er lernen zu sehen, was mit dem Ball wahrscheinlich passieren wird, bevor der Ball den Schläger des Gegners verlässt und die Flugbahn berechnet werden kann.

Ähnliches gilt im Straßenverkehr. Gute Autofahrer ahnen vorher, was passieren könnte und verhalten sich entsprechend. Auch hier ist unser Gehirn in der Einschätzung von Verkehrsituationen technischen Lösungen weit voraus. Wir werden das Problem mit Computern anders lösen müssen, analog zum 3D-Sehen: nicht das Vorbild imitieren, sondern technische Lösungen finden, die qualitativ ähnliches leisten, aber die Stärken der Technik ausnutzen.