Veröffentlicht am

Cory Doctorow, Little Brother (incl. epub)

Ich bin ein Schüler an der Cesar Chavez High in San Franciscos sonnigem Mission-Viertel, und damit bin ich einer der meistüberwachten Menschen der Welt.

doctorow_little_brother

Little Brother ist ein Roman für Jugendliche, 2008 erschienen. Der Autor Cory Doctorow (Wikipedia) ist in Internetkreisen bekannt als Aktivist, Autor, Blogger und Journalist und für ein rotes Cape.

Das Buch spielt in einer so nahen Zukunft, dass sie fast schon Gegenwart ist. Schüler in San Francisco haben Laptops statt Schulbüchern, mit einem Betriebssystem, das auf den Schulgebrauch ausgerichtet ist und den Benutzern wenig Kontrolle über den Rechner gibt und gleichzeitig ihre Benutzung kontrolliert. Videokameras mit Gesichtserkennung auf den Schulfluren sind kürzlich verboten worden, als Ersatz experimentiert die Schule mit Schritterkennungs-Software, um den Aufenthalt der Schüler zu überwachen. Computerversierte Schüler wissen allerdings, wie man diese Systeme austrickst.
Dann verüben Terroristen einen Angriff auf San Francisco, in der Größenordnung vergleichbar dem Angriff auf New York 2001. Die staatliche Heimatschutzbehörde ergreift Maßnahmen, die nach und nach zu einem immer größeren Überwachungsstaat in Kalifornien führen, bis hin zu Guantanamo-artigen Geheimgefängnissen. Eine Reihe von Jugendlichen, allen voran der 17-jährige Marcus, wehren sich gegen die Beschneidung ihrer Bürgerrechte – sie wehren sich vor allem mit kleinen digitalen Sabotagemaßnahmen und Happenings.

Der Titel des Buches – eine Anspielung auf George Orwells 1984, in der der Große Bruder die personifizierte Überwachung darstellt – bezieht sich auf eine Stelle, an der nach Namen für die lose Verbindung aufmüpfiger Jugendlicher gesucht wird. Dabei fällt auch „Little Brothers“, sozusagen als die kleinen Brüder des großen Überwachers, die sich gegen dessen Methoden wehren.

Ich halte das Buch für Science Fiction im besten Sinn, nämlich mit der Betonung auf dem ersten Wort. Denn die Geschichte selber ist eher dünn. Der Überwachungsstaat entsteht eben nicht nach und nach, auch wenn ich das oben geschrieben habe – sondern er ist sofort da. Gleich am Anfang werden Marcus und seine Freunde von der Heimatschutzbehörde festgehalten und misshandelt, einfach weil sie zufällig zu einer ungünstigen Zeit an einem ungünstigen Ort waren. Das ging ein bisschen arg schnell. Und die Charaktere sind schon sehr zweidimensional. Von Erwachsenen ist man das in Jugendbüchern gewöhnt, aber auch die Jugendlichen sind holzschnittartig. Viel telling, wenig showing.

Dafür werden Konzepte und Erkenntnisse vorgestellt, wenn auch nicht immer besonders elegant. „Erlaubt mir an dieser Stelle eine kleine Abschweifung, um das zu erklären“ schreibt der Ich-Erzähler, und das macht der dann auch. Alan Turing wird vorgestellt, die Entschlüsselung des Enigma-Codes, RFID-Chips und wie man sie unbrauchbar macht, Bayessche Filter und Histogramme, das Falsche-Positivergebnisse-Paradoxon, Internet-Protokolle und asymmetrische Verschlüsselung nach öffentlichen Algorithmen. Außerdem schadet es gar nicht, dass Schüler mal von Linux hören, von LARP (einschließlich Vampirrollenspiel im Hotel, wie ich es aus Erzählungen kenne), von Alternate Reality Games.

Hier werden Technik und Populärkultur ernst genommen; übliche Lektüre im Deutschunterricht ist dagegen Level 4 – Die Stadt der Kinder von Andreas Schlüter für die zugegeben etwas jüngeren Schüler: Dort werden die Kinder auf magische Weise in die Welt des Computerspiels befördert und müssen sich dort ohne Erwachsene zurechtfinden.

Ist Little Brother als Schullektüre geeignet oder nicht? Man kann auf jeden Fall tolle Sachen damit machen:

  • Das englische Original hat Doctorow unter der Creative-Commons-Lizenz BY-NC-SA freigegeben. Das heißt, solange man den a) Autor nennt und b) das ganze nicht kommerziell ist, darf man mit dem Buch machen, was man will (eine Verfilmung, ein Comic, eine gekürzte oder erweiterte Ausgabe), solange man c) das entstandene Produkt unter den gleichen Bedingungen auch anderen zur Verfügung stellt. Man braucht weder die Erlaubnis des Autors noch eines Verlages dazu. Über CC-Lizenzen sollten Schüler Bescheid wissen.
  • Das Buch gibt es als rororo-Taschenbuch in einer Übersetzung von Uwe-Michael Gutzschhahn. Rowohlt hat für die Rechte am Buch sicher bezahlt, es handelt sich ja um eine kommerzielle Verwendung. Ich habe das Buch allerdings in der Übersetzung von Christian Wöhrl gelesen. Der hat das Buch auch übersetzt und stellt seine Version als pdf öffentlich zur Verfügung, natürlich ebenfalls unter der CC-BY-NC-SA, wie es die Lizenz ja vorsieht. Man kann Schüler die Übersetzungen vergleichen lassen; mir selber gefallen an der Wöhrl-Übersetzung etliche Sachen nicht. Deshalb habe ich mir an über hundert Stellen kurze Notizen in mein pdf-Dokument gemacht (am Tablet gelesen, dort geht das mit einfachem Daumendruck). Nur zwei davon betreffen Schreibfehler, der Rest sind Stellen, die ich erst mit dem Original vergleichen möchte, bevor ich sie beurteile. Wenn ich das Buch mit Schüler lese, würde ich auf jeden Fall eventuell vorher und sicher nachher eine verbesserte Übersetzung davon erstellen, die ich dann der nächsten Klasse zur Lektüre anbieten könnte.
  • Weil man das ja darf, hat jemand die Wöhrl-Übersetzung auch in das eBuch-Format .epub umgewandelt, aber wohl automatisiert aus der pdf-Datei, jedenfalls sind die Dateien, die ich gefunden habe, unbrauchbar. Deshalb habe ich die pdf-Datei überarbeitet und mache das Buch hiermit als sauber formatierte .epub-Datei zugänglich.
    Ich würde natürlich die Schüler überreden, ihr Tablet oder Smartphone mal als Lesegerät auszuprobieren. Von selber kommt sicher kaum einer auf die Idee, Romane dort zu lesen, da ist die Schullektüre doch ein guter Anlass.
  • Mit der Übersetzung von Wöhrl darf man ja alles machen, was man mit dem Original auch darf, also hat Fabian Neidhardt das Buch als Hörbuch aufgenommen und stellt es zum öffentlichen Gebrauch zu Verfügung.
  • Tvtropes.org ist ein riesiges Wiki, auf dem man Stunden verbringen kann. Dort wird etwas gesammelt, das eigentlich nicht Trope, sondern Topos heißt. Topoi sind feste – vielleicht sogar vorformulierte – Bilder und Motive der Literatur (später auch: in Film, Fernsehen, Comics, Computerspielen und anderen Medien). Die gibt es schon sehr lange. Tvtropes kennt die Kategorien „Older Than Dirt“ (vor dem griechischen Alphabet), „Older Than Feudalism“ (von dort bis zum Fall Roms), „Older Than Print“ (von dort bis zum Buchdruck) und so weiter. Die Bezeichner der Topoi sind meist etwas alberner als „locus amoenus“ oder andere traditionelle Toposnamen.
    Auf der Tvtropes-Seite von Little Brother sind über 50 Topoi aufgezählt, die sich im Buch finden lassen: Von „Adults Are Useless“ und „Anti-Hero“ und „Blonde Republican Sex Kitten“ bis „Would Hurt a Child“, „Your Terrorists Are Our Freedom Fighters“ und „Your Radio Hates You“. Die kann man Schüler suchen lassen, oder man kann sie diskutieren, anzweifeln, erklären, Beispiele aus anderen Büchern finden. Eine deutschsprachige Sammlung von Schullektüren-Topoi ist übrigens auch ein Projekt, das ich im Hinterkopf habe.
  • Referat oder Diskussionsrunde zu der Fortsetzung des Buchs, Homeland.
  • Vergleich mit anderen Dystopien.
  • Als Basis für Diskussion und – je nach Altersstufe – Erörterungen. In einer Unterrichtsstunde im Buch wird selbst diskutiert:

    „Unter welchen Umständen sollte die Regierung bereit sein, die Bill of Rights außer Kraft zu setzen?“, fragte sie und drehte sich dabei an die Tafel, um die Zahlen von eins bis zehn untereinanderzuschreiben.

Und dann ist natürlich die Aktualität des Romans. 2010 gab es einen Skandal um eine Schule in Philadelphia (Zeitungsartikel): die Schule spionierte die Schüler mit den in die Schülerlaptops eingebauten Kameras zu Hause aus, ohne deren Wissen natürlich. Und gestern lese ich, dass eine Schülerin aus Texas vom Unterricht suspendiert wurde, weil sie sich weigerte, den Schülerausweis mit eingebautem RFID-Chip zu tragen. (Tatsächlich war das schon im Januar, aber sie kehrt dieser Tage zur Schule zurück; das Gericht gab der Schule Recht, trotzdem benutzt die Schule das Überwachungsprogramm inzwischen nicht mehr.) Dazu noch die aktuellen gesellschaftlichen Themen Vorratsdatenspeicherung, NSA-Bespitzelung, Handy-Rasterfahndung. Lesenswert auch das Interview zu Trusted Computing: Windows 8 macht sich auf den Weg, Hardware zu propagieren, die das Installieren von Linux erschwert macht und die Kontrolle der installierten Programme ermöglicht.

Was gegen das Buch als Schullektüre spricht:

  • Es ist nicht wirklich gut geschrieben. Vielleicht lag’s an der Übersetzung, vermutlich eher an den zweidimensionalen Figuren. Andererseits weiß ich nicht, ob das Schüler stören würde. In dem Alter habe ich auch recht platte Sachen gelesen und genossen.
    Was mir übrigens fehlt: eine Demonstration echter Zusammenarbeit. Schön wäre eine Erzählung vom Wachsen eines Wikis oder anderer Zusammenarbeit; hier wird das nur behauptet und nicht gezeigt. Und ich hätte gerne einen glaubwürdigen Vertreter des Themas Sicherheit und Überwachung, als ernst zu nehmenden Gegenspieler der Jugendlichen.
  • In welcher Jahrgangsstufe soll man das lesen? Auf Englisch frühestens in der 10. Klasse, denke ich, vorher ist nicht genug Sprache da. Oder doch schon in 9? Besteht dann die Gefahr, dass die ganze Technik überlesen wird? Im Deutschunterricht… am liebsten in der 8., so was das Niveau des Buchs betrifft. In dem Alter muss man sie auch das Interesse an Technik und Informatik etwas fördern, und der Inhalt dürfte die Schüler in diesem Alter sehr interessieren. Andererseits ist ein bisschen Sex drin, einmal Geschlechtsverkehr offstage, einmal heftiges Fummeln. (Ist das Rummachen unmittelbar vor der Pressekonferenz, die sie dadurch fast verpassen, unrealistisch oder sind rebellische Teenager wirklich so planlos? Die Frauenfiguren sind in Ordnung, aber jede einzelne der Jüngeren steht auf den Helden. Na ja.)
  • Einige Male wird positiv die Piratenpartei genannt – in Schweden. Dass die deutsche Piratenpartei damit nicht gemeint ist, muss man den Schülern sagen, trotzdem ist das manchen Eltern vielleicht schon zu politisch. Wir erinnern uns: wenn man irgendwas mit Hexen und Zauberern liest, gibt es häufiger aus religiösen Gründen Protest, als man denkt.
  • Irgendein Elternteil arbeitet immer bei Microsoft. Wenn der Internet Explorer als „Microsofts Crashware-Dreck, den kein Mensch unter 40 freiwillig benutzte“ bezeichnet wird, und wenn Firmen, die die Lizenz erworben haben, für Microsoft-Spielekonsolen zu schreiben, „Blutgeld an Microsoft gezahlt“ haben, dann muss man sich auf etwas Ärger vorbereiten.
  • Jugendsprache zu lesen ist meistens etwas peinlich; bei der Beschreibung von Stadtvierteln in San Francisco ist von „Nutten“ und „Transen“ und „pissen“ die Rede, aber das dürfte kein Problem sein.
  • Das Buch zitiert mehrfach die amerikanische Unabhängigkeitserklärung: wenn ein Volk nicht mehr will, was die Regierung tut, darf das Volk sich wehren. Hm.
    Erstmal ist die Bevölkerung von San Francisco mit dem Vorgehen der Heimatschutzbehörde ja voll einverstanden. (Die Presse erfüllt ihre Rolle der Aufklärung aber auch nicht.) Trotzdem reklamiert Marcus das Recht für sich, aktiven Widerstand zu leisten. Das hätte ich gerne etwas differenzierter. Andererseits, vielleicht ist das ein guter Anlass zur Diskussion.

Das Buch ist aber so schön aktuell und würde den Schülern gut gefallen. Nächstes Jahr habe ich wohl eine 8. und eine 10. Klasse in Deutsch. In 10 ist keine Zeit dafür, da muss man sich mit dem 18. Jahrhundert beschäftigen. Ist 8 zu früh? Ein Referat ist natürlich immer drin. (Rowohlt empfiehlt ab 14 Jahren – im Lauf der 8. werden die meisten Schüler 14, einige sind es schon vorher, sehr selten erst später.)

Links:

Fußnote:

Von Wired gibt es die 12-teilige Videoserie Codefellas (Youtube). Darin spionieren Special Agent Henry Topple, der noch sehr an den Verkleidungen und Geheimoperationen des kalten Kriegs hängt, und die junge Hackerin – bald seine Vorgesetzte – Nicole Winters im Auftrag der Regierung den Menschen hinterher.

Der Inhalt ist nicht verfügbar.
Bitte erlaube Cookies, indem du auf Übernehmen im Banner klickst.

Veröffentlicht am

Kryptographie 2: Asymmetrische Verschlüsselung bei E-Mails

Wenn einer einem eine E-Mail schreibt, kann so ziemlich jede Zwischenstation auf dem Weg vom Sender zum Empfänger mitlesen, was darin steht. Schlimmer noch, eventuell kann der sogar den Inhalt der Mail verändern. Deshalb dürfen wir Lehrer auch keine personenbezogenen Daten via E-Mail versenden, und deshalb ist E-Mail auch nicht als amtliches Kommunikationsmittel mit Behörden zugelassen.

Aus diesem Grund hat sich das Innenministerium schon vor einiger Zeit etwas einfallen lassen, das gerade beworben wird: Die De-Mail. Das ist eine Ergänzung zur herkömmlichen E-Mail, die unter anderem von der Telekom angeboten wird, und die das Innenministerium als Kommunikation akzeptieren will. Dabei wird die Kommunikation zwischen zwei zertifizierten De-Mail-Anbietern verschlüsselt. Zumindest standardmäßig wird die Nachricht aber vom Empfänger-Anbieter entschlüsselt und, uh, auf Schadsoftware untersucht, und dann wieder verschlüsselt weitergeleitet. Zwischendrin liegt die Nachricht also in entschlüsselter Form vor, und damit kann sie gelesen oder manipuliert werden. Das soll natürlich verboten sein, technisch bleibt es aber möglich. Zur Zeit gilt dieses Verfahren deshalb laut Gesetz als nicht sicher, weshalb laut Spiegel Online die Regierung das Gesetz ändern will. Auch weitere Kritikpunkte gibt es am De-Mail-Konzept.

Verschlüsselte E-Mails kann man aber bereits jetzt mit wenig Aufwand verschicken, ganz ohne zusätzliches De-Mail, ohne zusätzliche Kosten, und ganz ohne die Offenlegung der Nachricht auf dem Transport. Das geht zum Beispiel mit einem Plugin für Thunderbird, aber erst will ich erklären, wie das Verschlüsseln im Prinzip funktioniert.

1. Symmetrische Verschlüsselung

So kennt man das: Sender und Empfänger machen einen Schlüssel aus. Das kann ein komplizierter sein, mit Nachschlagen in einem Buch oder mit Schablonen, was man so aus Krimis kennt. Als Beispiel nehme ich hier einen ganz simplen, nämlich wieder die Verschiebung um 1 nach rechts: Aus „a“ wird „b“, aus „b“ wird „c“, aus „z“ wird „a“. So chiffrierte Nachrichten lassen sich leicht knacken, aber darum geht es hier erst einmal nicht. Der Empfänger entschlüsselt die Nachricht, indem er sie wieder in die Gegenrichtung verschiebt: Aus „b“ wird „a“, aus „c“ wird „b“, aus „a“ wird „z“.

Dieser Schlüssel besteht eigentlich aus zwei Teilen, der Verschiebung um 1 nach rechts, und der Verschiebung um 1 nach links. Mit dem einen verschlüsselt man, mit dem anderen entschlüsselt man. (Oder umgekehrt.) Wenn man den einen Teil kennt, kennt man automatisch auch den anderen Teil: Das heißt symmetrische Verschlüsselung. Man verschlüsselt den Nachrichtentext mit dem einen Schlüssel und entschlüsselt ihn dann mit dem symmetrischen Gegenstück:

krypto_schluessel2-text krypto_schluessel2-codierung krypto_schluessel2-decodierung
Der Klartext „text“. Dessen Verschlüsselung. Sieht dann so aus: „ufyu“. Der Originaltext ist geschickt verborgen. Wird in dieser Form übermittelt. Die Entschlüsselung der Verschlüsselung. Sieht dann wieder so aus: „text“.

Der Nachteil dieses symmetrischen Verfahrens: Der Sender muss den Schlüssel erst einmal auf sicherem Weg zum Empfänger bringen. Und dann muss dieser Schlüssel geheim gehalten werden. (Und außerdem darf der Schlüssel nicht so leicht zu knacken sein wie in meinem Beispiel, aber darum geht es hier nicht.)

2. Asymmetrische Verschlüsselung

Die wird zum Beispiel für E-Mail-Verschlüsselung benutzt. Als Benutzer lege ich mir für meine E-Mail-Adresse (etwa lehrerzimmer@herr-rau.de) ein Schlüsselpaar an, das ähnlich funktioniert wie oben:

krypto_schluessel3

Auch hier besteht der Schlüssel aus zwei Teilen. Der eine Teil ist öffentlich (public). Den veröffentliche ich auf meiner Webseite (etwa 0x78549FB2), sende ihn an öffentlich einsehbare Verzeichnisse, schicke ihn meinen Freunden. Der andere Teil des Schlüssel ist privat. Den veröffentliche ich nirgendwo, den kenne nur ich. Ganz wichtig: wer einen Teil des Schlüssels, insbesondere den öffentlichen, hat, kann von diesem aus nicht auf den anderen schließen. Das ist grundlegend anders als beim symmetrischen Verfahren, wo ja letztlich die beiden Teile des Schlüssels ziemlich ähnlich sind. Wie das geht, und wieso man den privaten Schlüssel nicht so leicht knackt, selbst wenn man Klartext, codierten Text und öffentlichen Schlüssel dazu hat, ist ein anderes Thema.

Wenn jetzt A eine Nachricht an B schicken will, und zwar so verschlüsselt, dass sie außer B niemand sonst lesen kann, dann geht das so:

krypto_verschluesselung
krypto_verschluesselung2

A verschlüsselt den Text mit dem öffentlichen Schlüssel des Empfängers. Das kann er, weil der Schlüssel öffentlich ist. Damit ist der Originaltext erst einmal verborgen. Das Paket schickt A dann an B. Der wendet seinen privaten Schlüssel darauf an und löst den Originaltext wieder heraus.

Allerdings könnte diese Mail immer noch von irgend jemandem geschickt worden sein, nicht unbedingt von A. Manchmal möchte man aber nicht nur den Inhalt verschlüsseln, sondern auch dem Empfänger versichern können, dass die Mail wirklich von der Adresse kommt, von der sie zu kommen vorgibt. Das geht ebenfalls mit dem Schlüsselpaar, nur eben andersherum:

krypto_authentifizierung
krypto_authentifizierung2

A verschlüsselt den Text mit seinem eigenen privaten Schlüssel. Das kann er, weil er den ja selber verwaltet. Das Paket schickt A dann an B. Der wendet den öffentlichen Schlüssel des Senders darauf kann (das kann er, weil der ja öffentlich ist) und entpackt so die Nachricht. Wenn die Mail nicht von A kam, hilft einem der ganze öffentliche Schlüssel von A nichts, der Paketinhalt wird nicht zu öffnen sein.

Man kann natürlich auch beides gleichzeitig tun, eine Mail signieren und ihren Inhalt verschlüsseln.

Der Vorteil dieses Vorgehens: (1) Das ganze Verfahren ist öffentlich und damit überprüfbar. (2) Ich kann jemandem eine Nachricht schicken, ohne dass der Empfänger erst auf einem zu findenden Weg einen Schlüssel von mir bekommen muss. (3) Der einzige, der etwas geheim halten muss, bin ich selber, nämlich meinen privaten Schlüssel.

Fußnote 1: Aus Effizienzgründen wird beim Signieren (zur Authentifizierung) häufig nicht die ganze Mail verschlüsselt, sondern nur deren Hashwert.
Fußnote 2: Aus Effizienzgründen wird beim Verschlüsseln oft die Nachricht mit einem herkömmlichen, spontan erzeugten symmetrischen Schlüssel verschlüsselt. Dieser wird dann asymmetrisch verschlüsselt und zusammen mit der symmetrisch verschlüsselten Nachricht verschickt, worauf der Empfänger den symmetrischen Schlüssel auspacken und anwenden kann.
Fußnote 3: Der private Schlüssel ist ebenso wie der dazu gehörende öffentliche Schlüssel eine Funktion. Wenn ich beide nacheinander auf einen Text anwende, und nur dann, kommt wieder der Text heraus, und zwar egal, in welcher Reihenfolge ich die Funktionen angewendet habe. Beim Verschlüsseln der Nachricht verschlüsselt man zuerst mit dem öffentlichen Schlüssel (des Empfängers) und entschlüsselt mit dem privaten Schlüssel; beim Authentifizieren der Nachricht verschlüsselt man zuerst mit dem privaten Schlüssel (des Senders) und entschlüsselt mit dem anderen.

Anwendung:

Wenn ich mir das Thunderbird-Add-on „Enigmail“ installiere, kann ich mir so ein Schlüsselpaar generieren lassen. Das Add-on benutzt seinerseits die Software GnuPG, die dem Verschlüsselungsstandard OpenPGP entspricht. Den privaten Schlüssel merkt sich Thunderbird, den öffentlichen verteilt es an bestimmte dafür zuständige Server.

Woher weiß man, dass sich hinter lehrerzimmer@herr-rau.de wirklich Herr Rau befindet? Damit hat diese Verschlüsselung erst mal nichts zu tun, obwohl es Zertifizierungsmöglichkeiten gibt. Woher weiß man, dass der öffentliche Schlüssel, den man in meinem Impressum herunterladen kann, nicht gehackt und ersetzt worden ist durch den öffentlichen Schlüssel eines Angreifers? Weiß man gar nicht. Aber das ist eine andere Geschichte. Wer sicher gehen will, ruft mich an fragt. :-)

Veröffentlicht am

Kryptographie 1: Verschlüsselung von Passwörtern

Ein allgemeinbildender Überblick.

Bei vielen Rechnern zu Hause oder in der Schule ist es so, dass man sich mit einem Benutzernamen und einem Passwort anmelden muss, um damit arbeiten zu können. Auch wenn man in einem Onlinegeschäft etwas einkauft, muss man meist diese Daten eingeben. In beiden Fällen überprüft das System daraufhin, ob Passwort und Benutzername korrekt sind, und lässt den Benutzer erst danach weiter arbeiten.

Damit das funktioniert, muss der Rechner zu Hause – oder der Rechner im Onlinegeschäft – irgendwo eine Liste von Benutzernamen und Passwörtern gespeichert haben, entweder in einer Datenbankdatei oder als einfache Textdatei:

Benutzer:        Passwort:
admin            admin1234
rau              password
huber            geHeim!
mueller          password

Das Problem ist dabei, dass jeder, der auf das System Zugriff hat – also mindestens der Systembetreuer – diese Passwörter einsehen und missbrauchen kann. Und wenn diese Liste gar gestohlen wird, kann der Dieb sie ebenso missbrauchen. Um so schlimmer, wenn die Benutzer das gleiche Passwort bei anderen Systemen auch noch einsetzen!
Wer die Passwortliste also in dieser Form speichert, handelt äußerst fahrlässig und leichtfertig. Besser ist es, wenn man die Passwörter in verschlüsselter Form speichert, etwa so:

Benutzer:        Passwort:
admin            benjo2345
rau              qbttxpse
huber            hfIfjn"
mueller          qbttxpse

Der Benutzer „admin“ tippt beim Anmelden immer noch sein altes Passwort „admin1234“ ein, vor dem Vergleich mit dem verschlüsselt gespeicherten Passwort wird es aber erst verschlüsselt. Aus „admin1234“ wird – bei der Verschlüsselung, die ich verwendet habe – „benjo2345“, und das wiederum passt zu der Information in der Datei, also wird die Anmeldung akzeptiert.

Dieses System hat aber ebenfalls Nachteile. Natürlich muss man den verwendeten Schlüssel geheim halten. Außerdem sieht man, dass die Benutzer „rau“ und „mueller“ das gleiche Passwort haben, selbst wenn man es noch nicht kennt. Am schlimmsten: Wenn man die Passwortdatei analysiert, kann man den Schlüssel knacken – der ist nämlich in meinem Fall nicht sehr gut, beim Verschlüsseln wird lediglich jeder Buchstabe ums eins verschoben: Aus „a“ wird „b“ und so weiter. Natürlich gibt es bessere Verschlüsselungsverfahren als diese Verschiebechiffren. Aber auch die sind nicht so viel schwerer zu knacken, wenn man nicht als Kryptographieexperte eine eigene Chiffriermethode entwickelt und diese dann erfolgreich geheim hält. Es kann aber nicht jeder Systembetreuer ein Kryptographieexperte sein, und das Geheimhalten von Schlüsseln ist auch schwierig.

Also greift man zu einer anderen Lösung, nämlich einer kryptographischen Hash-Funktion. Das ist eine veröffentlichte Verschlüsselungsfunktion, die man also nicht geheimhalten muss, und die trotzdem schwer zu knacken ist. Davon gibt es einige, etwa MD5 oder SHA-1 oder SHA-256; meine Beispiele sind alle SHA-1.

Wenn der Benutzer „rau“ erstmalig sein Passwort eingibt, wendet man die Funktion SHA-1 darauf an (das ist die Verschlüsselung), und speichert das entstandene neue Passwort. Dann sieht meine Passwortdatei so aus:

Benutzer:        Passwort:
admin            7b902e6ff1db9f560443f2048974fd7d386975b0
rau              5baa61e4c9b93f3f0682250b6cf8331b7ee68fd8
huber            da5245eadd0e7be84735101f013eaea400e0ad43
mueller          5baa61e4c9b93f3f0682250b6cf8331b7ee68fd8

Wenn sich der Benutzer „rau“ dann erneut anmeldet, gibt er sein Passwort ein. (Wir erinnern uns, das war „password“.) Das wird wieder mit SHA-1 verschlüsselt, wieder kommt „5baa61e4c9b93f3f0682250b6cf8331b7ee68fd8“ heraus, und *das* wird dann mit den gespeicherten Daten verglichen.

Die so gespeicherte Datei bringt einem Dieb erst einmal gar nichts. Auch der Administrator kann aus der Datei das ursprüngliche Passwort nicht so einfach ablesen. Das liegt an einen wichtigen Eigenschaften dieser kryptographischen Hashfunktion:

  • Jeder Hash ist gleich lang.
  • Und zwar egal, wie lange das zu verschlüsselnde Passwort war.
  • Man kann also von der Länge des Hashwerts nicht auf die Länge des Originalpasswort schließen.
  • Man kann auch sonst von dem Hashwert nicht auf irgendwelche andere Eigenschaften des Originalpassworts schließen. Man kann daran zum Beispiel nicht erkennen, ob es darin viele Vokale gibt, oder wie viele Sonderzeichen, oder ob manche Zeichen mehrfach vorkommen oder nicht.
  • Das impliziert auch, dass Hashwerte für ähnliche Wörter trotzdem unvorhersagbar verschieden sind. Der Hash für „password“ ist ein ganz anderer als für „passwort“.
  • (Für später mal: Es folgt auch aus all dem, dass es zu einem gegebenen Hashwert bei einer gegebenen Hashfunktion nicht nur ein Originalpasswort gibt, das diesen Hashwert erzeugt, sondern beliebig viele davon. Klar: Es gibt nur endlich viele Hashwerte, aber im Prinzip unendlich viele, weil beliebig lange, Passwörter. Der Fachausdruck heißt „Kollision“, und davon hätte man gerne möglichst wenige.)

Die SHA-1-Hashes in meiner Tabelle sind übrigens alle genau 40 Zeichen lang, aber nicht irgendwelche beliebigen Zeichen. Tatsächlich besteht jeder Hash aus 20 Zahlen, wobei sich jede Zahl im Bereich von 0-255 befindet. Man könnte den „password“-Hash also auch so schreiben: 091.170.097.228.201.185.063.063.006.130.037.011.108.248.051.027.126.230.143.216 – aber man schreibt das besser im Hexadezimalsystem, also eben: 5baa61e4c9b93f3f0682250b6cf8331b7ee68fd8. Das ist für Informatiker lesbarer. Man sagt, der Hash ist 20 Byte lang – ein Byte entspricht einer Zahl von 0-255 und ist die Universaleinheit beim Computern.

Wie genau diese Hashfunktionen funktionieren, gehört nicht mehr zur Allgemeinbildung, also nicht hierher. Der Knackpunkt ist, dass es relativ leicht ist, aus einem Eingabewert (etwa dem Passwort) den Hashwert zu berechnen, aber sehr, sehr schwer, zu einem gegebenen Hashwert ein Wort zu finden, das diesem entspricht.

Warum sind diese Funktionen öffentlich und kein streng gehütetes Geheimnis? Zum einen führt das dazu, dass jeder sie verwenden kann. Vor allem ermöglicht das auch der ganzen Welt, zu testen, ob die Funktionen auch halten, was sie versprechen. Gerade diese Öffentlich- und Überprüfbarkeit führt zu Sicherheit. Und außerdem neigen streng gehütete Geheimnisse dazu, früher oder später ohnehin herauszukommen, so dass man sich nicht auf sie verlassen sollte, wenn es um Sicherheit geht.

Was man mit einer gestohlenen Passwortdatei anfangen kann, auch wenn die Daten verschlüsselt sind.

Selbst wenn die Passwörter mit SHA-1 oder einer anderen kryptographischen Hashfunktion verschlüsselt sind, kann man noch einiges damit anfangen. Man kann versuchen, die Passwörter zu knacken. Dazu gibt es mehrere Möglichkeiten:

  1. Brute Force: Man probiert einfach alle theoretisch denkbaren Passwörter der Reihe nach aus und vergleicht deren Hashwert mit dem gespeicherten Wert. Früher oder später führt das zum Erfolg, vor allem bei kurzen Passwörtern. Bei langen Passwörtern dauert das aber lange, so dass man mit Brute Force nicht weit kommt. Bei einem Alphabet von 70 Zeichen (groß, klein, Ziffern) gibt es immerhin schon 580.000 Milliarden Passwörter der Länge 8. Aber auch das schafft ein Rechner in zwei Wochen. Wenn man nur auf Kleinbuchstaben testet, reduziert sich die Zahl auf 208 Milliarden – eine Sache von Minuten.
  2. Wörterbuchangriff: Statt Passwörter zu raten, geht man einfach ein Wörterbuch durch. So ein Wörterbuch hat vieleicht eine halbe Million Wörter. Das Wörterbuch erweitert man dann um eine Liste bekannter und beliebter Passwörter. Dazu nimmt man ein paar typische Ersatzregeln – eine „1“ statt einem „i“, eine „3“ statt einem „E“ und noch ein paar Varianten. Damit wächst das Wörterbuch auf einige Milliarden Einträge an, aber die durchzugehen ist für einen Rechner gut machbar.
  3. Wäre es nicht schön, wenn es irgendwo eine Liste von häufigen Hashes mit Klartextlösungen dazu gäbe, und man tippte nur den Hashwert ein, und in der Liste würde dann nach dem entsprechenden Klartext gesucht? Gibt es natürlich. Das Passwort „password“ wäre schon bei einem Wörterbuchangriff geknackt worden, aber ohnehin hat es sich herumgesprochen, dass der SHA1-Hash „5baa61e4c9b93f3f0682250b6cf8331b7ee68fd8“ diesem Passwort entspricht. Es gibt Listen solcher bekannter Hashes, und wenn man ein Passwort verwendet, das irgendwer sonst auf der Welt noch verwendet, und dessen Passwort wird bekannt, dann landet der entsprechende Hash vielleicht auf diesen Listen. Systematisch werden Hashes außerdem in sogenannten Rainbow Tables gesammelt. Ganz einfach ist das nicht, da es 256^20 verschiedene SHA1-Hashes gibt. Milliarden ist kein Ausdruck dafür, die Zahl hat 48 Nullen hinten dran. Die kann man nicht einfach mal alle speichern oder durchsuchen.

Wie man seine Passwortdatei sicherer machen kann.

Bekanntlich ist das Passwort „password“ nicht sicher, weil dessen Hash bekannt ist. Das gleiche gilt für „admin“ und viele andere häufig verwendete Passwörter. Also gibt es das Konzept des „salting“.

Dabei wird jedes Benutzerpasswort (ohne dass der Benutzer das mitkriegt) automatisch um einige Zeichen ergänzt, das sogenannte „salt“. Nimmt man als salt „Ab!4“, wird das dämliche Benutzerpasswort „password“ automatisch vor dem Umwandeln zu „passwordAb!4“ ergänzt, dessen Hash dann eben nicht das altbekannte „5baa61e4c9b93f3f0682250b6cf8331b7ee68fd8“ ist. Das salt muss man natürlich jedesmal ergänzen, wenn ein Benutzer sich mit seinem Passwort anmeldet. Natürlich sollte ein besseres salt gewählt werden als in meinem Beispiel.

Außerdem kann man für jeden Benutzer ein individuelles salt speichern. Gut, in beiden Fällen darf das salt natürlich nicht bekannt werden. Aber man gewinnt dadurch echt unbekannte Hashes, und die individuellen Salts führen dazu, dass für zwei Benutzer mit dem gleichen Passwort trotzdem unterschiedliche Hashes gespeichert werden – eben weil zu dem Passwort noch die individuellen salts dazu gehören.

Ich führe das übrigens nur wegen der Etymologie an. Laut einer Theorie heißt salt so, weil man das bei der Umwandlung des Originals in den Hashtext hinzufügt. Und „hash“ ist ein Gericht aus Kartoffeln und Hackfleisch oder Corned Beef, bei dessen Zubereitung man natürlich auch Salz hinzufügt. Vielleicht kommt das Wort auch aus dem Konzept „salting a mine“. Dem bin ich mal in einem alten Perry-Mason-Krimi begegnet. Dabei platziert man, sagen wir, ein paar Stücke Golderz in einer ansonst wertlosen Mine, um einem prospektiven Käufer vorzugaukeln, es handle sich um eine produktive Mine, in der es noch Erz abzubauen gibt.

Wie man an Passwortdateien kommt

Weiß ich nicht. Diebstahl? Social Engineering? An die Datei mit den verschlüsselten Benutzerpassworten von Windows heranzukommen ist jedenfalls nur mäßig schwer, wenn man Zugang zum Rechner hat. Fürs Entschlüsseln gibt es dann hilfreiche Programme, etwa John the Ripper, das automatisch Wörterbuch- und Brute-Force-Angriffe ausführt. Die Verbreitung dieser Programme ist in Deutschland rechtlich problematisch – man darf sie nur zum Guten weitergeben und verwenden.

(Ganz einfach kommt man an Passwörter, wenn diese unverschlüsselt übertragen werden, also via http statt https. Dann kann ein Rechner im örtlichen Netzwerk oder eine Zwischenstation auf dem Weg zum Empfänger das mitlesen.)

Wie man sein Passwort sicher macht.

Der Vollständigkeit halber: Für jeden Dienst ein anderes Passwort verwenden. Kein kurzes Passwort nehmen, das durch Brute Force geknacht werden kann. Kein Passwort, das eine Wörterbuchattacke nicht übersteht. Kein Passwort, das andere Leute auch verwenden. Darauf hoffen, dass der Onlinedienst die Passwörter ordentlich verschlüsselt.

Veröffentlicht am

Serious Text Games

„The Republia Times“ ist ein schönes Spiel, das sich vielleicht auch für das rasche Leseverstehen (skimming) im Englischunterricht eignet. Flashbasiert, im Browser zu spielen; man kann die Flashdatei aber auch einfach lokal speichern. (Via Aaron A. Reed.)

Das Spiel ist einfach, aber reizvoll: Man spielt den eben ernannten Redakteur der Republia Times, einer Zeitung im diktatorisch regierten Republia. Die Presse dort ist alles andere als frei; die Familie des Redakteurs befindet sich in Geiselhaft der Regierung. Man muss zehn Tage als Redakteur überstehen: In den ersten Tagen muss man die Loyalität der Leserschaft auf einen gegebenen Wert erhöhen, indem man regimefreundliche Propagandaartikel platziert. Danach muss man die Anzahl der Leser erhöhen, indem man Artikel veröffentlicht, die den Lesern gefallen. (Der Loyalitätswert darf dabei aber nicht unter eine bestimmte Grenze sinken.) Und danach wiederum hat man etwas freiere Hand… bis sich der Untergrund meldet und sowohl eine hohe Auflage als auch eine niederige Loyalität der Leserschaft zu einem bestimmten Termin fordert.

So sieht der Bildschirm aus:

republia

Von links unten kommen auf einem Ticker nach und nach die Nachrichten des Tages herein, mal früher mal später. Aus diesen Nachrichten kann man seine Zeitung füllen: Man macht aus dieser Nachricht eine kleine Notiz, einen gewöhnlichen Artikel oder einen großen Dreispalter. Man kann auch nichts auswählen, dann bleibt die Zeitung halt leer, und das kostet natürlich Leser. Um die Zeitung zu füllen hat man nur einen Arbeitstag Zeit; am Rand läuft eine Uhr unerbittlich mit, die einen in den späteren Phasen des Spiels unter Druck setzt. Ganz wird die Zeitung ohnehin nie voll, die Größen der Artikel und der Seite sind so gewählt, das immer mindestens ein kleines frustrierendes Kästchen frei bleibt.

Der Knackpunkt beim Spiel ist die Auswahl der Nachrichten und die Entscheidung, wie groß man sie in die Zeitung setzt:

  • Es gibt Artikel, die für höhere Leserzahlen sorgen: Sport, Militär, Unterhaltung, Wetter. Bei diesen Themen kommt es nicht auf die Größe der Artikel an, sondern nur darauf, dass es sie gibt. Die bringen Leser. Zu viel politische Propaganda und zu wenig Unterhaltung lässt die Leserzahl sinken.
  • Es gibt Artikel, die die Loyalität der Leserschaft beeinflussen, positiv oder negativ: Negative Informationen über die Regierung, Erfolge des feindlichen Nachbarstaats. Hier haben größere Artikel mehr Einfluss auf die Loyalität der Leserschaft als kleinere. Das Wetter ist immer neutral, andere Nachrichten können positiv oder negativ sein.
  • Gibt es zu viel freien Platz, dann sinken Leserzahlen. Drei große Geschichten reichen, um die Zeitung zu füllen

Nach dem zehnten Tag ist das Schicksal von Republia entschieden und es kommt zu einem Ende, sozusagen.

Für den Englischunterricht nutzbar ist das Spiel, weil man die – allerdings sehr kurzen – Nachrichten schnell überfliegen und beurteilen muss: Sind sie interessant ist oder nicht und, unabhängig davon, politisch neutral, positiv oder negativ?

Außerdem lernt man:

  • Eine Zeitung füllt sich nicht von selbst, es gibt immer jemanden, der auswählt, was hineinkommt.
  • Selbst wenn eine Nachricht gebracht werden muss, kann man sie groß herausbringen oder klein halten.
  • An manchen Tagen kommen einfach keine brauchbaren Nachrichten. Aber auch dann muss die Zeitung voll werden.
  • Es gibt mehr Nachrichten, als in einer Zeitung Platz haben. Manches erfährt der Leser also nicht.

Ein anderes flashbasiertes Spiel, das ich schon mal mit Sechtsklässlern gespielt habe, ist „The Big Scan“. Ich habe das vor Jahren schon mal erwähnt, deshalb nur kurz: Das Spiel ist – anders als Republia Times – für Lerner gedacht. Man spielt einen Privatdetektiv, der einen (nicht ganz unblutigen) Fall lösen muss. Dabei übt man, Texte gezielt nach bestimmten Informationen durchzugehen.

Kaum für die Schule geeignet sind die folgenden Spiele, aber ich will sie erwähnen, weil sie für mich reizvoll waren (alles reine Textspiele):

Whom the Telling Changed von Aaron A. Reed. (Auf der verlinkten Seite ist auch eine Möglichkeit, das Spiel im Brwoser zu spielen.) Die Mitglieder einer Stammesgruppe sitzen in vor- oder frühgeschichtlicher Zeit um ein Lagerfeuer und hören sich die rituell erzählte, altbekannte Geschichte an, die der Erzähler vorträgt. Sehr aktiv in herkömmlicher Weise ist man als Spieler nicht: in jeder Erzählpause kann man dan Erzähler bitten, bestimmte Aspekte der Geschichte zu erklären oder zu betonen. Allerdings macht das der Gegenspieler genauso, ein anderer Angehöriger der Gruppe mit anderen politischen Zielen. Beide lenken die Stimmung der Gruppe durch ihre Zwischenfragen, denn die Situation ist hoch politisch: Soll man gegen einen Nachbargruppe in den Krieg ziehen oder nicht? Stellt sie eine Gefahr dar oder nicht?
Die Geschichte, die erzählt wird, ist außerdem eine Episode aus dem Gilgamesch-Epos. Wer sich die mal am virtuellen Lagerfeuer erzählen lassen möchte, kann sich „Whom The Telling Changed“ anschauen.

Auf einem Originaltext eines anderen Autors basiert auch The Tempest von Graham Nelson und, uh, William Shakespeare. (Online spielbar via der verlinkten Seite.) Man spielt den Luftgeist Ariel; die Handlung ist die von Shakespeares Sturm. Die Texte sind weitgehend Originalsprache, und zwar – laut eigenen Angaben – der fast vollständige Text der Folioausgabe von 1623. Also Blankvers. Das macht das Lesen macnhmal etwas schwer, und ganz leicht ist das Spiel auch nicht, das macht es weniger reizvoll für Leute, die weder mit frühem Neuenglisch noch mit Interactive Fiction vertraut sind. Aber reizvoll schon, das könnte ich mir auch gut mit einem allerdings gekürzten Sommernachtstraum vorstellen.

Unter der Seite Literary Worlds der Western Michigan University gibt es einen Link zu virtuellen literarischen Welten, die im Rahmen eines Projekts der Uni dort angelegt wurden. Das sind letztlich MUDs, multi-user dungeons, Textadventures für mehrere Spieler. Leider funktionieren einige der Links nicht mehr, auch wenn dann doch alle Welten – und es sind viele – von innerhalb eines jeden Spiels aus betreten werden können. Design und Interface sind nicht sehr ansprechend oder benutzerfreundlich. Ich habe mal The Tempest ausprobiert: Links textbasiert, rechts mit Bildern; navigieren kann man nur rechts, weil der Text bei Richtungsvariablen keinen sauberen Angaben ausgibt; agieren kann man nur links mit Texteingabe. Und alles recht umständlich. Eine schöne Idee, aber nicht mehr zeitgemäß. Auch die Kombination Text-Bild halte ich eher für irritierend als für nützlich – entweder ein reines Textspiel, oder Point-and-Click.

Fußnote: Ich habe schon mal ein eigenes Inform-7-Textadventure auf einen Server hochgeladen, der das Spiel multi-user-fähig macht. Funktioniert auch. Nächster Schritt: Mit Schülern eine Welt anlegen und sich dann dort treffen, textbasiert.

Veröffentlicht am

Ein Taschenrechner mit Java in der 10. Klasse (1)

Mit meiner 10. Klasse habe ich im ersten Halbjahr einen Taschenrechner programmiert, ziemlich bald, als Einstieg in die Algorithmik, die ich dafür dieses Jahr vorgezogen habe. Als BlueJ-Projekt sieht der Rechner so aus:

taschenrechner_bluej_rot

Objektorientiert programmieren heißt, dass man die Programmieraufgabe auf verschiedene, relativ unabhängige Einheiten verteilt. Der Bauplan für diese Einheiten heißt „Klasse“, und eben diese programmiert man.

1. Die Klasse GUI

Die Klasse GUI kann ein guter Schüler machen. Sie übernimmt das, was vom Programm äußerlich sichtbar ist. (GUI steht für Graphical User Interface.) Das ist quasi das Plastik-und-Alu-Gehäuse des Rechners. Den hat ein freiwilliger Schüler schon gleich am Anfang programmiert, und zwar mit dem Java-Editor. Dieses Programm von Gerhard Röhner ist eigens für Schulen und Schüler entwickelt, um leichter diese grafischen Benutzeroberflächen zu erstellen, die in Java, ehrlich gesagt, recht umständlich sind.

Die Klasse GUI braucht einen Bereich, in dem man die Ergebnisse anzeigen lassen kann (im Java-Editor-JFrame-Projekt: JLabel oder JTextField), und viele Knöpfe mit unterschiedlichen Beschriftungen (JButton). Nach diesen Angaben hat ein Schüler folgendes Taschenrechner-GUI angelegt, nachdem wir vorher noch ausgemacht hatten, welche Knöpfe es geben soll:

taschenrechner_gui_ansicht_leer

Ich hätte die Knöpfe anders platziert und benannt, aber hey, es ist nicht mein Taschenrechner. Und hier ist auch ein Vorteil des objektorientierten Programmierens: Wem dieses GUI nicht gefällt, der kann es einfach durch ein anderes, eigenes ersetzen, ohne dass die anderen am Programm beteiligten Klassen geändert werden müssen.

Noch passiert allerdings nichts, wenn man auf die Knöpfe drückt. Viel soll auch gar nicht passieren: für das Innenleben des Taschenrechners sind wieder andere Klassen zuständig. Der Taschenrechner muss nur Bescheid geben, welche Taste gedrückt ist, und zwar einem Objekt der Klasse Steuerung. Damit das geht, muss man die mit dem Java-Editor erstellte GUI-Klasse etwas ergänzen:

1. Ein GUI-Objekt muss ein Steuerung-Objekt kennen, dem es die Benachrichtigung schicken soll (Referenzattribut auf ein Objekt der Klasse Steuerung); das geht in einer Zeile:

Steuerung steuerung;

2. Wenn eine Taste gedrückt wird, muss an die Steuerung eine Nachricht gesendet werden. Die Vorarbeit dazu erledigt der Java-Editor, man muss nur – nach dem TODO-Kommentar – eine einzige Zeile in jeder Knopfgedrückt-Methode ergänzen (es gibt für jeden Knopf eine solche Methode):

private void jButton1_ActionPerformed(ActionEvent evt) {
  // TODO hier Quelltext einfügen
  senden ("1");
} // end of jButton1_ActionPerformed

Der Einfachheit halber benutzen alle diese Knopfdruckmethoden die ebenfalls zu ergänzende Sendemethode der Klasse GUI:

void senden(String s) {
  steuerung.empfangen(s);
}

Das war es fast. Damit das GUI auch Text ausgeben kann, muss man nur diese Methode ergänzen:

void ausgeben(String s) {
  ausgabefeld.setText(s);
}

Und damit ist die Klasse GUI fertig. Wenn eine Taste gedrückt wird, wird eine Nachricht an die verbundene Steuerung geschickt, und wenn man das GUI-Objekt anweist, Text auszugeben, dann macht es das. Mehr erwartet man von einer Taschenrechnerhülle nicht.

2. Die Klasse Steuerung

Diese Klasse sollte man den Schülern fertig vorgeben. Sie macht eigentlich gar nicht so viel, ist aber umständlicher zu programmieren, als man meint. Sie macht zwei Dinge: Erstens nimmt sie in Empfang, welche Nachrichten, also Tastendrucke, vom GUI gesendet werden. Und gleich darauf sagt sie der Steuerung, was diese anzeigen soll. Wenn am Anfang die Taste 1 gedrückt wird, soll das GUI „1“ anzeigen. Wenn danach die Taste 2 gedrückt wird, soll das GUI „12“ anzeigen. Wenn dann die Mal-Taste gedrückt wird, soll das GUI „*“ anzeigen. (Die bisher eingegebene Zahl 12 muss sich die Steuerung aber merken.) Und so weiter, bis es nach dem Eingeben der zweiten Zahl ans eigentliche Rechnen geht. Dieses Rechnen übernimmt dann wieder eine dritte Klasse, nämlich die Klasse Calculator.

Die Klasse Steuerung kann man sicher sauberer programmieren, als ich das getan habe. Sie muss sich im Prinzip zwei Zahlen merken können, eine erste und eine zweite. Dazu muss sie wissen, ob sie jetzt schon rechnen soll oder erst auf die Eingabe einer zweiten Zahl warten muss. Manchmal muss sie auch schon nach der Eingabe einer einzigen Zahl rechnen, nämlich bei allen Operationen mit nur einem Operanden – Quadratwurzel, Fakultät, Betrag und so weiter.

Ein Grund dafür, dass die Steuerung so arbeitet, ist folgender: Die Rechenarbeit soll ganz von der Klasse Calculator übernommen werden. Denn da schlägt die Stunde der Schüler.

3. Die Klasse Calculator und Unterklassen dazu

Die Klasse Calculator – beziehungsweise eine eigene Unterklasse dazu – ist die Klasse, mit der Schüler fast ausschließlich arbeiten. Sie enthält alle Rechenmethoden, die der Taschenrechner beherrscht. Über die muss man sich natürlich vorher verständigen, schon mal, damit es genügend Knöpfe dafür gibt. Da wären die Grundrechenarten, aber auch Wurzel, Potenzierung, Prozent, Betrag, Kehrwert und was es noch alles gibt. Ich habe auch noch ein paar exotische Sachen ergänzt (Collatz, Fibonacci, Primzahltest, größter gemeinsamer Teiler), auch wenn wir erst später im Schuljahr darauf zurückkommen werden:

taschenrechner_calculator

Im Klassendiagramm sind die Methoden alphabetisch sortiert, den Schülern muss man eine Liste mit einer anderen Reihenfolge vorgeben! Meine Liste war – leider erst am Ende der Sequenz – sortiert nach:

  • Einfach: Grundrechenarten (addieren, subtrahieren, multiplizieren, dividieren)
  • Leicht: negation, kehrwert, hochDrei, quadrat, prozent (wobei wir uns erst mal einigen mussten, was diese Prozenttaste bewirken soll)
  • Mit bedingter Anweisung: betrag
  • Mit while-Schleife: potenz. modulo, fakultaet, summeVonBis

Und so weiter. Die Schüler arbeiteten dann in ihrem eigenen Tempo und in ihrer eigenen Geschwindigkeit an diesen Methoden. Denn darum ging es eigentlich vor allem: Einführung in die Algorithmik und Kontrollstruktoren. Nur: ohne den graphischen Taschenrechnerkrimskrams drumherum macht das den Schülern viel weniger Spaß. Einige kamen nicht sehr weit über die Grundrechenarten hinaus, die meisten kamen bis Fakultät/Potenz, andere schlugen bei Wikipedia nach und fanden Lösungen für Wurzel und Sinus/Cosinus heraus. Die hatte ich nur aufgenommen, weil der GUI-Programmierer die vorgegeben hatte. Später im Jahr werde ich dann noch auf einige der exotischeren Methoden zurückkommen.

(Zur Klasse Taschenrechner: Die Klasse Calculator enthält zwar alle Methoden, aber sie funktionieren noch nicht richtig. Standardmäßig kommt dabei immer 99 heraus. Aufgabe der Schüler ist es, eine Unterklasse zu Calculator zu programmieren und die Methoden der Oberklasse durch ihre eigenen, verbesserten Methoden zu überschreiben. Sinnvoller wäre es natürlich gewesen, die Klasse Calculator als Interfache anzulegen. Aber dann müssten die Schüler immer wieder in den Code des Interface, um auszukommentieren, was sie noch nicht verbessert haben. Deshalb habe ich mich für diese eigentlich unelegante Lösung entschieden.)

4. Der Rest

Die Klasse Starter legt je ein Objekt der Klassen GUI, Steuerung und Calculator-Unterklasse an und macht sie miteinander bekannt. Sie enthält außerdem die main-Methode, mit der man den Taschenrechner auch außerhalb von BlueJ als echtes kleines Java-Programm unter Windows, Mac oder Linux laufen lassen kann.

Ziel der Sequenz: Einführung in Algorithmik und Programmierung. Daneben schon mal ein Vorgeschmack auf Vererbung und Referenzattribute. Außerdem sehen die Schüler bereits das objektorientierte Prinzip der Arbeitsteilung in Klassen angewendet. Gute Schüler können sich an ein GUI wagen, alle machen die algorithmisch interessanten Rechenmethoden, und der Verwaltungskram der Steuerung bleibt den Schülern verborgen.

Download des ganzen BlueJ-Projekts mit zwei Arbeitsblättern dazu.

(Fortsetzung morgen.)

Veröffentlicht am

Lange Sätze in der Schule, und Satzzeichen zweiter Klasse

(Ich weiß nicht, ob ich das schon mal geschrieben habe. Das wird in letzter Zeit immer mehr ein Problem. Ich mache das jetzt seit achteinhalb Jahren, manchmal fällt mir nichts mehr ein; andere Male stelle ich fest, dass ich meine Gedanken schon mal früher aufgeschrieben habe.)

Es geht um die Sprache in Aufsätzen ab der 10. Jahrgangsstufe bis hin zum Abitur. Die zeichnet sich aus durch Nominalisierungen, umständlichen Satzbau und Phrasen.

Nominalisierungen

Ein paar Beispiele aus Aufsätzen:

  • Man kann eine Reduzierung der Verse pro Strophe feststellen.
  • Auch ist eine Erleichterung seinerseits zu hören, denn…
  • Das Treffen der beiden Personen geschieht, nachdem…
  • …löst einen Verwirrungszustand in dem Leser aus.
  • Zu beachten ist, dass die Abiturienten eine sehr starke Kompetenzsteigerung erfahren.

Besser sind hier Nebensätze und Verben: Es werden weniger Verse pro Strophe; jemand ist erleichert; Personen treffen sich einfach und der Leser wird verwirrt.

An den Nominalisierungen sind wir teilweise selber schuld. Wir drillen die armen Schüler in den Aufsatz-Gliederungen zum Nominalstil, bis sie nicht mehr anders können.

Satzbau

Es gibt Schüler, die erst einmal nicht anders können als ihre Gedanken in einen einzigen Satz (genauer: eine einzige Periode) zu packen. Das geschieht automatisch, fast zwanghaft. Und spätestens ab dieser Jahrgangsstufe haben die Schüler schon recht komplexe Gedanken. Wenn man die in eine Periode packt, wird die recht umständlich:

Gerade in der heutigen Zeit in der westlichen Welt, wo viele Leute nahe beieinander leben, die einerseits an einen hohen Lebensstandard gewohnt sind, sich andererseits an eine Methode, diesen zu erreichen, nämlich immer an den größtmöglichen eigenen Profit zu denken, gewöhnt haben, was wiederum der Gesellschaft schadet, sind die so genannten Tugenden, wie zum Beispiel Bescheidenheit, Rücksicht und Verantwortungsbewusstsein, allen voran jedoch Mitgefühl, um so wichtiger.

In Deutsch fürs Leben von Wolf Schneider gibt es eine schöne Anleitung zur „Satzzertrümmerung“, wie er das nennt, mit Beispielen, wie man solcher Ungetüme Herr wird. Die teile ich gerne mal meinen Schülern aus. Danach verbesserte ein Schüler meiner 10. Klasse den Satz oben so, wobei bewusst nichts an Inhalt und Wortwahl geändert wurde:

Heutzutage leben in der westlichen Welt viele Menschen nahe beieinander. Diese sind an einen hohen Lebensstandard gewöhnt und versuchen immer, diesen zu erreichen. Hierbei denken sie stets an den größtmöglichen eigenen Profit, was jedoch der Gesellschaft schadet. Deshalb sind heute Tugenden wie zum Beispiel Bescheidenheit, Rücksicht und Verantwortungsbewusstsein, aber vor allem Mitgefühl sehr wichtig.

Wenn man solche Sätze verständlich macht, versteht man sie auch leichter. Das birgt die Gefahr, dass man auch eventuelle Schwächen im Gedankengang leichter erkennt. Zum Üben ein weiterer Satz aus einem Schüleraufsatz:

Im Gegensatz dazu steht seine Frau Jokaste, die erst erfreut über die Meldung des Boten, dass Polybos, der Ziehvater von Ödipus, verstorben sei und somit die Angst ihres Mannes, den eigenen Vater zu töten, unbegründet ist, ist, dann jedoch durch die Schilderung des Boten über seine Bekanntschaft mit Ödipus bemerkt, dass sie durchaus eine weit engere Beziehung zu ihrem Mann haben könnte, als sie es zunächst vermutet hatte.

Ganz ernsthaft: Meine Schüler waren geradezu entrüstet darüber, dass plötzlich ein Lehrer weniger umständliche Sätze fordert. Ich bin mir einigermaßen sicher, dass keine Lehrkraft der Jahre zuvor das so erklärt hat, aber bei den Schülern hängen geblieben ist trotzdem: Ich soll umständliche Sätze machen. Hauptsätze are for sissies.
Das ist zum Teil eine ganz natürliche Entwicklung. Die Schüler wollen anspruchsvolle Texte schreiben, sind auch stolz darauf, so etwas zu können, und schießen dabei über das Ziel hinaus. Und jetzt müssten sie lernen, wieder einfachere Sätze zu bauen. (Manche Erwachsene verlassen nie dieses Stadium.)

Satzzeichen

Der erste Schritt zur Satzzertrümmerung ist, ab und zu mal einen Punkt zu machen. Oder ein anderes Satzzeichen. Meine Schüler (10. Klasse) waren geschockt, als ich ihnen sagte, sie dürften auch einen Doppelpunkt zur Verbindung zweier Sätze verwenden. Einen DOP-pel-PUNKT! (Tumult im Klassenzimmer.) Oder ein Semikolon. Auch mal, für ganz verwegene, einen Gedankenstrich – auch wenn Frau Rau und ich, die wir beide dieses Satzzeichen schätzen, unterschiedliche Ansichten dazu haben, wie angebracht es in welchen Textsorten ist. Gedankenstriche führen gerne mal zu Parenthesen – und wir wissen alle, wie schwer man die Finger davon lassen kann, wenn man erst einmal auf den Geschmack gekommen ist.

Welche Unterschiede Satzzeichen zwischen zwei Sätzen machen, kann man bei diesen Sätzen ausprobieren:

  1. Formal ist der Kopf deines Briefes nicht korrekt; die Betreffzeile fehlt. (Korrekturbemerkung)
  2. Es besteht nur aus natürlichen Substanzen. Es ist völlig ungefährlich. (Dauerwerbesendung)
  3. Das ist mit Fruchtsaft gemacht, da sind viele Vitamine drin. (Werbung für Süßigkeit)
  4. Mutter feierte bis 4 Uhr früh. Ihre Kinder erstickten. (Schlagzeile)

Meistens ist es noch besser, den Zusammenhang zwischen zwei Sätzen nicht durch ein Satzzeichen anzudeuten, sondern ihn explizit zu machen, indem man Konjunktionen benutzt (weil, so dass, obwohl, während) oder Adverbien (deshalb, gleichzeitig, trotzdem). Zur Not gehen auch Präpositionen (durch), aber die führen automatisch zu Nominalstil, und mit dem übertreiben es viele Schreiber ja ohnehin.

Phrasen

„Ebenfalls nicht zu vernachlässigen ist der Punkt, dass…“ So beginnen gerne mal Argumente in der Erörterung. Das ist einmal problematisch, weil da etwas ganz und gar Nebensächliches im Hauptsatz steht. Das eigentlich Wichtige muss sich in einer Nebensatzkonstruktion ein Plätzchen einrichten, und da kann es eng werden. (Nichts gegen Nebensätze. Einige meiner besten Sätze sind Nebensätze.) Schlimmer ist das aber, weil das so eine leere Phrase ist. Und daran, fürchte ich, sind tatsächlich nur wir Lehrer schuld.

Wir bringen den Schülern nämlich bei, Überleitungen zu machen. Und legen ihnen dazu oft genug eine Liste von Phrasen vor, die sie verwenden sollen. Ich glaube, man sollte Schülern mal probeweise Überleitungen verbieten; vielleicht kämen dann zusammenhängendere Texte heraus.

Anhang 1: Zum Üben.

Es darf daher getrost, was auch von allen, deren Sinne, weil sie unter Sternen, die, wie der Dichter sagt: „versengen, statt leuchten“, geboren sind, vertrocknet sind, behauptet wird, enthauptet werden, daß hier einem sozumaßen und im Sinne der Zeit, dieselbe im Negativen als Hydra gesehen, hydratherapeutischen Moment ersten Ranges – immer angesichts dessen, daß, wie oben, keine mit Rosenfingern den springenden Punkt ihrer schlechthin unvoreingenommenen Hoffnung auf eine, sagen wir, schwansinnige oder wesentielle Erweiterung des natürlichen Stoffgebietes zusamt mit der Freiheit des Individuums vor dem Gesetz ihrer Volksseele zu verraten sich zu entbrechen den Mut, was sage ich, die Verruchtheit haben wird, einem Moment, wie ihm in Handel, Wandel, Kunst und Wissenschaft allüberall dieselbe Erscheinung, dieselbe Frequenz den Arm bieten, und welches bei allem, ja vielleicht gerade trotz allem, als ein mehr oder minder modulationsfähiger Ausdruck einer ganz bestimmten und im weitesten Verfolge excösen Weltauffasseraumwortkindundkunstanschauung kaum mehr zu unterschlagen versucht werden zu wollen vermag – gegenübergestanden und beigewohnt werden zu dürfen gelten lassen zu müssen sein möchte.

Christian Morgenstern, aus der Vorrede zu den Galgenliedern.

Anhang 2:

Jeder Intellektuelle hat eine ganz spezielle Verantwortung. Er hat das Privileg und die Gelegenheit, zu studieren. Dafür schuldet er es seinen Mitmenschen (oder ‚der Gesellschaft‘), die Ergebnisse seines Studiums in der einfachsten und klarsten und bescheidensten Form darzustellen. Das Schlimmste – die Sünde gegen den heiligen Geist – ist, wenn die Intellektuellen es versuchen, sich ihren Mitmenschen gegenüber als Propheten aufzuspielen und sie mit orakelnden Philosophien zu beeindrucken. Wer’s nicht einfach und klar sagen kann, der soll schweigen und weiterarbeiten, bis er’s klar sagen kann.

Karl Popper, „Wider die großen Worte“, ein Brief des Philosophen Karl Popper, der 1971 in der Zeit erschien. Dieser Brief enthält auch die vielzitierten Übersetzungen (jedenfalls sind sie mir oft begegnet), in denen Popper die seiner Meinung nach schwülstigen und unklaren Äußerungen von Adorno und Habermas in verständliches Deutsch übersetzt.

Veröffentlicht am

Interactive Fiction in der Schule

Ich glaube, ich habe da etwas entdeckt, das mir viel Spaß machen wird. Über Text Adventures/Interactive Fiction habe ich ja vor ein paar Tagen geschrieben. Im Englischunterricht habe ich auch schon gelegentlich eine Zork-Stunde eingeschoben, und mit einer Unterstufenklasse, die ich in Informatik und Englisch hatte, habe ich selber mit dem Schreiben experimentiert.

Aber da geht noch mehr.

Einmal für den Literatur- und Fremdsprachenunterricht. Es gibt tolle Spiele: Manchmal muss man viele Rätsel lösen; bei anderen Spielen geht es darum, das historische New York kennenzulernen. Man schlüpft in die Rollen von Papageien oder Kleinkindern im Krabbelalter, mit entsprechend eingeschränkten Möglichkeiten, die Umwelt zu beeinflussen. Andere Werke sind Kurzgeschichten, paradoxe Parabeln und Verwirrspiele, avantgardistische Textexperimente. Auf Deutsch ist die Auswahl an Texten geringer, aber prinzipiell ist das gleiche möglich.

(Bald merkt man: Die Spiele leben nicht von den Rätseln, sondern von der Atmosphäre. Die wird anders erzeugt als in herkömmlicher Epik, ein paar Sätze reichen meist zur Beschreibung. Die Qualität des Schreibens zeigt sich auch darin, wie sehr die Erwartungen und Vermutungen des Spieler-Lesers vorausgeahnt werden; hier wird gleich unmittelbar auf die Reader-Response reagiert.)

Zum anderen kann man das Schreiben solcher Texte – vielleicht – für den Informatikunterricht nutzen. Geschrieben wird Interactive Fiction meist in eigenen, objektorientierten Programmiersprachen. In Inform 6 legt man ein Objekt so an:

Object Staff_Room "Staff Room"
     with
          description "A room for all the staff to meet and sit 
                and get a cup of coffee.",
          n_to hallway,
     has light;

Das sieht doch schon mal nach einer richtigen Programmiersprache aus. Aber in der Informatik geht es ja gar nicht so ums Programmieren. Es gibt auch Ansätze, informatische Konzepte ohne Programmiersprache zu lehren, zum Beispiel in einer Programmierumgebung, die ganz ohne Code und die entsprechenden Syntaxfehler auskommt, in der die Lernenden nur mit Drag-and-Drop arbeiten.

Eine andere Möglichkeit könnte Inform 7 sein. Da sehen die Zeilen Code, mit denen man den gleichen Raum wie oben erzeugt, so aus:

The Staff Room is a lighted room. "A room for all the staff to meet and sit and get a cup of coffee." North of the Staff Room is the Hallway.

Einfacher Inform-7-Code ist leicht zu schreiben, weil Inform 7 der natürlichen Sprache Englisch so nahe kommt wie wohl keine andere Programmiersprache. Deswegen lässt sich der Code auch sehr leicht lesen. Anspruchsvoller Inform-7-Code ist aus genau diesem Grund wohl schwerer zu schreiben, als man denkt. Zu sehr ist man versucht, einfach normales Englisch zu verwenden und übersieht dabei, dass Inform 7 trotz allem vielen Beschränkungen unterliegt. Aber dafür kann man sehr knapp und elegant formulieren:

Instead of a suspicious person (called the suspect) burning something which is evidence against the suspect when the number of people in the location is at least two, try the suspect going a random valid direction.

(Beispiel aus der pdf-Fassung von Ron Newcombs Inform 7 for Programmers.)

So komplexe Regeln für das Verhalten der Spielwelt wird man in der Schule kaum brauchen. Aber Zustandsautomaten gehen ganz schön, und die macht man zum Beispiel in der 10. Klasse. Da programmiert man zum Beispiel einen Aufzug mit drei Stockwerken/Zuständen. In Inform 7 legt man zuerst den Aufzug und die Knöpfe an, damit man in der Spielwelt auch etwas tun kann:

The elevator is an enterable, transparent container in the basement. It is not portable. The description is "An elevator with an up and a down button."
The up button is a thing in the elevator. It is scenery. The description is "An arrow pointing upwards."
The down button is a thing in the elevator. It is scenery. The description is "An arrow pointing downwards."
The elevator has a number called zustand. The zustand of the elevator is 1.

Und dann kommen die Regeln für die Zustandsübergänge:

Instead of pushing the up button when the player is in the elevator:
if the zustand of the elevator is 0:
now the zustand of the elevator is 1;
say "Going up. (Ground floor.)";
now the elevator is in the ground floor;
otherwise if the zustand of the elevator is 1:
now the zustand of the elevator is 2;
say "Going up. (First floor.)";
now the elevator is in the first floor;
otherwise:
say "Nothing happens."

Instead of pushing the down button when the player is in the elevator:
if the zustand of the elevator is 2:
now the zustand of the elevator is 1;
say "Going down. (Ground floor.)";
now the elevator is in the ground floor;
otherwise if the zustand of the elevator is 1:
now the zustand of the elevator is 0;
say "Going down. (Basement.)";
now the elevator is in the basement;
otherwise:
say "Nothing happens."

Eigentlich müssten die Knöpfe nicht nur im Aufzug sein, sondern auch außen. Aber das ist ja erst mal nur ein einfaches Modell.

Was auch noch gut geht mit Inform: Objekte, Attribute, Klassen, Vererbung, Datentypen; Modellierung, Relationen. Was vermutlich nicht so gut geht: Algorithmik, aber da bin ich noch am Herumprobieren.

Ich habe mal ein paar Seiten erstellt, die ich als Ausgangspunkt für meine Untersuchung von Inform 7 für die Schule nehmen möchte. Dort auch Links zu allem möglichen.

Bislang habe ich mit einer 10. Klasse zwischendurch mal Spiele in Inform 7 geschrieben; bisher ist nur ein kurzes Spiel online, von mir redigiert; ich hoffe, dass die anderen vor dem Schuljahresende auch fertig werden (von den Schülern selber noch redigiert).

Veröffentlicht am

Das P-NP-Problem, Teil 3: P=NP?

Executive summary: Die Fragen vom letzten Mal sind sich alle irgendwie ähnlich: Wenn man für eine davon einen effizienten Lösungsweg gefunden hat, kann man den auf die anderen übertragen. Wird man je einen finden?

Hier zur Erinnerung noch einmal der Ausschnitt aus den Komplexitätsklassen vom letzten Mal:

  1. In P, da liegen die relativ einfachen Aufgaben.
  2. In NP (aber außerhalb von P), da liegen die schweren Aufgaben, bei denen sich die Lösung wenigstens leicht überprüfen lässt. Die Zeichnung geht davon aus, dass P eine echte Teilmenge von NP ist, was nicht unbedingt stimmen muss.
  3. In EXPTIME (aber außerhalb von NP), da liegen die schweren Aufgaben, bei denen sich die Lösung auch nur schwer überprüfen lässt.

Der Handlungsreisende

Viele der Aufgaben aus (2) spielen in der Praxis eine große Rolle. Ein Beispiel dafür ist das Problem des Handlungsreisenden (Travelling Salesman). Das geht von einer Reihe von Orten aus, die zum Teil durch Straßen miteinander verbunden sind, etwa so:

Die Buchstaben stehen für die Ortsnamen, die Verbindungen dazwischen sind die Straßen. Das Ziel des Handlungsreisenden ist es, alle Orte zu besuchen, und zwar derart, dass er insgesamt möglichst wenig Entfernung zurücklegt und am Schluss wieder an seinem Ausgangspunkt ankommt. Die Aufgabe für ein Programm lautet etwa: Nenne mir eine solche Rundreise (wenn es sie denn gibt), die höchstens die Länge 9 hat. Wenn man erst einmal die Lösung hat, kann man recht einfach überprüfen, ob sie stimmt. Einfach heißt: in höchstens polynomieller Zeit. In diesem Beispielgraphen ist das sowieso sehr leicht. Dass es eine Lösung gibt, ist auch klar: zur Not probiert man einfach alle möglichen Kombinationen aus und schaut, ob eine geeignete dabei ist. Allerdings steigt der Aufwand dafür exponentiell mit der Anzahl an Orten und Verbindungen, wenn man eine allgemeine Lösungsweg hat. (Näherungsweise Lösungen gibt es sehr gute für dieses Problem.)

Die Freundesclique

Ein weiteres Beispiel für ein Problem aus (2) ist das Cliquenproblem. Da geht es um einen Haufen von Schülern, die sich mögen können oder nicht. Eine Clique ist dabei eine Gruppe von Schülern, von denen jeder jeden anderen in der Clique mag. Die Aufgabe dazu heißt: Nenne mir eine solche Clique (wenn es sie denn gibt), in der mindestens vier Schüler sind. Hier ist so ein Haufen von Schülern:

Die Buchstaben stehen für die Schüler (Anna, Bernd, Charlie, Denise…), die Verbindungen bedeuten, dass die sich mögen. Bei einer Handvoll Schüler geht das schnell, aber sobal die Zahlen größer werden, wird das aufwendiger: der Aufwand steigt nämlich exponentiell.
Die Antwort lautet übrigens: ja, es gibt eine 4er-Clique, nämlich {A, C, D, F}.

Logikrätsel

Auch Logikrätsel liegen in diesem Bereich. Damit meine ich beliebige Aufgaben wie

(x oder y) und (nicht (z) oder x)

Dabei sind x, y, z jeweils wahr oder falsch, und die Frage ist: gibt es eine Möglichkeit, dass diese logische Formel insgesamt wahr ist? Man kann das immer durch Ausprobieren aller Möglichkeiten überprüfen, aber bei n Variablen gibt es 2n Möglichkeiten, der Aufwand steigt exponentiell, und das ist nicht praktikabel.
Im Beispiel geht das noch, da kann man die 23=8 Möglichkeiten ausprobieren, und ja, es sind sogar 5 richtige dabei.

Zerlegung in Primfaktoren

Ein viertes Beispiel für ein Problem aus (2) ist die Primfaktorenzerlegung. Bei manchen Verschlüsselungstechniken nutzt man gerade das aus, dass diese Aufgabe so schwer ist – wäre sie es nicht, wäre das nicht sicher. (Zugegeben, ich kürze hier etwas ab – die NP-Probleme sind nämlich eigentlich Entscheidungsprobleme.)

Ähnlichkeit all dieser Aufgaben

Der Knackpunkt ist jetzt der, dass die verschiedene Aufgaben in (2) sich ähnlicher sind, als man meint, und das in zweierlei Hinsicht.

  • Erst mal hat man für keine davon allgemeinen Lösungen in polynomieller Zeit gefunden, sondern nur welche mit exponentiellem Aufwand. Das heißt aber nicht, dass es keine schnelleren Lösungen gibt! Vielleicht findet man ja noch welche.
  • Zweitens sind sie sich so ähnlich, dass, wenn man für eines davon eine solche effizientere Lösung gefunden hat, diese Lösung auch für alle anderen gilt. Und das ist das eigentlich Interessante an diesen Aufgaben, aber dazu werde ich kurz etwas ausholen.
  • Wenn man sicher sein wollte, dass es keine solche effiziente Lösung gibt, dann müsste man beweisen, dass es Probleme gibt, die in NP liegen, aber nicht in P – anders gesagt, dass P ungleich NP. Das ist das P=NP-Problem. Und das konnte noch keiner beweisen oder widerlegen. Wer’s tut, dem winken eine Million Dollar. So viel ist für die Lösung eines der Millenium-Probleme ausgesetzt. Man geht davon aus, dass P tatsächlich ungleich NP ist, dass man also nie eine effiziente Lösung finden wird.

— Wer jetzt noch dabei ist, verträgt ein paar Definitionen:

Zurückführen auf einen anderen Aufgabentyp (Reduktion)

Nehmen wir an, ich wäre bereits in der Lage, zwei beliebige Zahlen miteinander zu multiplizieren.
Dann bin ich auch in der Lage, Quadratzahlen zu berechnen.
Denn das Quadrieren einer Zahl lässt sich auf das Multiplizieren zweier Zahlen reduzieren. (Ich muss nur zusätzlich darauf achten, dass die beiden Faktoren gleich sind.)
Wenn der zusätzliche Aufwand bei der Reduktion vertretbar, also höchstens polynomiell ist, heißt das polynomielle Reduktion.

Genau genommen gilt das für die Reduktion und P und NP nur für formale Sprachen und Entscheidungsprobleme und nicht für meine meist salopp formulierten Aufgaben. Aber ich lasse das jetzt alles mal so stehen.

Wenn ich Problem A auf Problem B in vertretbarer Zeit zurückführen kann, und ich eine vertretbar schnelle Lösung für Problem B habe, dann kann ich auch Problem A in vertretbarer Zeit lösen.

NP-schwer/NP-hart

Ein Problem ist NP-schwer, wenn ich jedes Problem aus NP in polynomieller Zeit darauf zurückführen kann, insbesondere natürlich die besonders schwierigen. Ein NP-schweres Problem kann also selber in NP (aber gleichzeitig nie in P) liegen. Es kann aber noch schwerer sein, also zum Beispiel echt in EXPTIME liegen.

NP-vollständig

Ein Problem ist NP-vollständig, wenn es erstens in NP liegt, also wenn die Lösung in polynomieller Zeit auf Richtigkeit überprüft werden kann.
Und zweitens muss jedes andere Problem in NP (also insbesondere die schwierigen davon) mit polynomiellem Aufwand darauf zurückführbar sein. Ein NP-vollständiges Problem liegt also in NP und ist NP-schwer.
Alle Aufgaben oben sind NP-vollständig.

Beweise

Dass ein Problem NP-vollständig ist, erforderte zuerst einmal viel Beweisaufwand. Aber wenn man erst einmal ein solches Problem gefunden hat, dann lässt sich das mit weniger Aufwand für weitere beweisen. Wenn ich das Problem des Handlungsreisenden polynomiell reduzieren kann auf das Problem des ungerichteten Hamilton-Kreises, und wenn ich weiß, dass das NP-vollständig ist, dann ist auch der Handlungsreisende NP-vollständig.
Und das mit dem Hamilton-Kreis weiß ich, weil man den auf einen gerichteten Hamilton-Kreis polynomiell reduzieren kann, von dem man weiß, dass er NP-vollständig ist.
Und das weiß man, weil man den auf das Problem 3KNF-SAT polynomiell reduzieren kann, von dem man weiß, dass es NP-vollständig ist.
Und das weiß man, weil man es auf das Problem SAT polynomiell reduzieren kann, von dem man weiß, dass es NP-vollständig ist.
Und das weiß man – weil es mal bewiesen wurde.

Zusammenfassung

Jedes NP-vollständige Problem auf jedes andere NP-vollständige Problem polynomiell reduzieren. Das heißt, wenn man für ein Problem in NP einen effizienten (polynomiellen, nicht exponentiellen) Lösungsweg gefunden hat, dann kann man plötzlich alle Probleme in NP in polynomieller Zeit lösen, weil zur ursprünglichen Lösung dann allenfalls noch polynomieller Reduktionsaufwand hinzukommt.

Deswegen wäre es so wichtig, zu wissen, ob P=NP oder nicht. Wenn nicht, dann ist klar, dass es nie eine effiziente Lösung für irgendein NP-vollständiges Problem geben wird. (Für Spezialfälle und Näherungen natürlich schon.) Davon geht man aus, dass also P ungleich NP. Aber bewiesen ist es halt noch nicht.

Beispiel

Dazu ein Beispiel aus dem Staatsexamen Informatik, Frühjahr 2007, Theoretische Informatik, Thema 2, Aufgabe 4:

Das Partyveranstaltungsproblem ist das folgende. Gegeben ist eine Menge B von Bekannten und eine Menge H ⊆ B × B von (Paaren von) Bekannten, die sich nicht leiden können. Es ist festzustellen, ob eine Auswahl U ⊆ B von k Bekannten (|U| = k) existiert (die Gästeliste), sodass in dieser keine zwei Bekannten enthalten sind, die sich nicht leiden können. Man zeige, dass das Partyveranstaltungsproblem NP-vollständig ist.

Dass das Partyproblem NP-vollständig ist, beweist man so:
Man beweist erstens, dass es in NP ist und zweitens, dass es in polynomieller Zeit auf ein NP-hartes Problem zurückgeführt werden kann – zum Beispiel auf ein bereits bekanntes anderes NP-vollständiges Problem. Dann ist es selber NP-vollständig. Und da gibt es eines, das heißt Independent Set-Problem und ist eigentlich das gleiche wie das Party-Problem.

Fußnote

Wissenschaftler des Queen Mary and Westfield College der Universität London fanden heraus, dass Hummeln bei der Nahrungssuche in der Lage sind, das Problem des Handlungsreisenden besser und effizienter zu lösen, als dies mit den bislang bekannten mathematischen Computerverfahren möglich ist. Wie Hummeln diese Ergebnisse erzielen können, ist dabei noch nicht geklärt.

(Wikipedia zum Handlungsreisenden)

Veröffentlicht am

Das P-NP-Problem, Teil 2: P und NP

Executive summary: Es gibt eine besondere Art von Fragen, die schwer zu beantworten sind, aber wenn man die Antwort hat, kann man relativ leicht überprüfen, ob sie auch wirklich stimmt.

(Fortsetzung vom letzten Mal.) Als grobe Faustregel – und wir sind ja hier nur am Groben interessiert – kann man sagen:

  • alle Fragen, für die sich mit linear steigendem Aufwand eine Antwort finden lässt, sind in der Praxis gut beantwortbar (und bei konstantem Aufwand sowieso)
  • alle Fragen, für die sich mit polynomiell steigendem Aufwand eine Antwort finden lässt, sind in der Praxis gut beantwortbar
  • alle Fragen, für die sich nur mit exponentiell steigendem Aufwand eine Antwort finden lässt, sind in der Praxis nur schwer zu beantworten (allerdings gibt es für manche dieser Aufgaben schnellere Lösungsverfahren, die zwar nicht das perfekte, aber immerhin ein halbwegs brauchbares Ergebnis liefern)

Faustregel deshalb, weil eine exponentielle Lösung bei sehr kleinem Exponenten und kleinen Ausgangswerten schneller sein kann als eine polynomielle Lösung hoher Ordnung. Soll uns jetzt nicht kümmern.

Die Klasse aller Aufgaben mit höchstens polynomiell steigendem Aufwand für das Lösen einer Aufgabe nennt man P. Das schließt die ersten der drei Fälle oben ein. Aufgaben in P sind in der Praxis gut machbar, auch wenn P nicht für „Praxis“ steht, sondern für „polynomiell“. Typische Aufgaben in P sind das Sortieren und Durchsuchen von Listen und das Finden kürzester Wege auf einer Straßenkarte.

Und dann gibt es noch eine andere Klasse von Aufgaben, die heißt NP. Da sind die Aufgaben drin, für die man mit höchstens polynomiellem Aufwand überprüfen kann, ob eine Lösung die richtige ist, wenn man sie denn einmal hat. (Das schließt alle Aufgaben aus P mit ein.)

Daneben gibt es noch weitere Klassen, also zum Beispiel die Klasse EXPTIME. Da sind die Aufgaben drin, für die man mit höchstens exponentiellem Zeitaufwand eine Lösung finden kann. (Das schließt alle Aufgaben aus NP ein, und dann natürlich P sowieso. Aber dazu eben auch die Aufgaben, für die selbst das Überprüfen einer vorgeschlagenen Lösung sehr viel Arbeit macht.) Dazwischen und davor und dahinter und drumherum gibt es noch weitere Klassen, aber diese drei reichen uns hier. Ihr Verhältnis zueinander sieht man in diesem Diagramm:

Was gibt es denn für Aufgaben, die schwer zu lösen, aber relativ leicht oder auch sehr leicht zu überprüfen sind, also diejenigen Aufgaben, die in NP liegen, aber außerhalb von P?

Aus Im Laybrinth des Denkens von William Poundstone habe ich folgende schöne Idee. Da geht es um ein allwissendes Orakel, das beweisen soll, dass es allwissend ist. Man kann ihm solche Fragen stellen wie: „Was ist die zweibillionste Dezimalstelle von Pi?“, und es wird die Antwort ausspucken. Leider kann man die Antwort nicht so ohne Weiteres überprüfen, weil man das nirgendwo nachschlagen kann und das noch niemand ausgerechnet hat und das auch nicht so einfach auszurechnen ist – also wird die Antwort niemanden davon überzeugen, dass das Orakel wirklich allwissend ist.
Man kann das Orakel auch fragen: „Was ist die Quadratwurzel von 622521?“, und die Antwort wird ausgespuckt. Aber da könnten Zweifler sagen, dass das Orakel irgendwo einen Taschenrechner oder einen Spickzettel hat oder einfach ziemlich gut rechnen kann. Die Frage ist also zu leicht, als dass sie ein Beweis für die Allwissenheit des Orakel wäre.
Was man braucht, ist eine Frage, bei der es sehr, sehr schwer ist, die Antwort herauszufinden, selbst mit einem Taschenrechner oder Spickzettel oder Assistenten – aber wenn man sie einmal hat, kann man die Richtigkeit der Lösung schnell überprüfen. Und das sind eben die Aufgaben in NP, die außerhalb von P sind.

Dazu gehört zum Beispiel die Primfaktorenzerlegung. Es sieht auf den ersten Blick vielleicht nicht so aus, aber die Aufgabe, eine beliebige Zahl in Primfaktoren zu zerlegen, wächst exponentiell zur Größe der Zahl. Die fünfstellige Zahl 95477 in ihre zwei Primfaktoren zu zerlegen, das macht schon einigen Aufwand. Für einen Computer ist das aber noch leicht. Die doppelt so lange Zahl 3620188223 in ihre beiden Faktoren zu zerlegen, das macht aber nicht doppelt so viel Aufwand, und nicht zehnmal so viel Aufwand, sondern exponentiell mehr Aufwand. Und irgendwann, ab ein paar hundert Dezimalstellen, wird das auch für Computer praktisch nicht mehr berechenbar. Die Lösung zu überprüfen, das ist aber wieder einfach – das ist dann ja nur eine Multiplikation zweier Primzahlen.

Und mit diesen Primfaktoren funktioniert zumindest zum Teil auch die Verschlüsselung vieler Seiten und Nachrichten im Internet. Man schreit sozusagen heraus: „Huhu, ich habe hier ein seeeehr großes Produkt zweier Primzahlen. Dürft ihr euch alle anschauen, und wenn ihr die Zahl in ihre Faktoren zerlegen könnt, dann könnt ihr auch meine verschlüsselten Nachrichten lesen. Aber ellebätsch, das schafft ihr nicht!“

Mehr Beispiele für diese Art Aufgaben kommen im nächsten Teil dieser Eintragserie. Eigentlich gehören nur Fragen, die sich mit ja/nein beantworten lassen („Entscheidungsprobleme“) in die Kategorie P/NP; ich war beim Formulieren oben da nicht immer exakt.

Der Vollständigkeit halber: Was gibt es denn für Aufgaben, die schwer zu lösen sind (exponentieller Aufwand), und wo die Überprüfung ebenfalls schwer ist (exponentieller Aufwand)?

Ein richtig schönes Beispiel habe ich nicht gefunden. Wenn ein Schüler für n Vergehen 2n mal den Satz schreiben muss „Ich werde das nie wieder tun“, dann erfordert die Kontrolle, ob er seine Strafaufgabe gemacht hat, ebenfalls exponentiellen Aufwand (des Zählens). Vielleicht kommt hier irgendwann mal ein schöneres Beispiel hin.

Und zum Schluss und als Ausblick für eventuelle spätere Blogeinträge:

(1) Es gibt Aufgaben, die man nie berechnen können wird, weil man weiß, dass man das prinzipiell nicht berechnen kann. Zum Beispiel kann man kein Computerprogramm schreiben, dass zwei beliebige andere Programme unter allen Umständen und immer zum gleichen Ergebnis kommen.
(2) Es gibt Aufgaben, die man nie berechnen können wird, weil sie zwar eine Lösung haben, man das aber nie beweisen kann. Ein Beispiel dazu kann man nicht geben, weil, ja, weil man das ja nicht wissen kann.
(3) Es gibt Aufgaben, die garantiert eine Lösung haben, was man auch beweisen kann, die man aber nie wird berechnen können (Busy-Beaver-Funktion), weil – hm, das ist schwer zu erklären.

(Und insgesamt kürze ich ein ein bisschen ab. Mit Aufgaben meine ich immer: Fragen, und mit Lösungen: Antworten. Ist hier nicht so wichtig.)

(Fortsetzung folgt.)

Veröffentlicht am

Das P-NP-Problem, Teil 1: Was schwierig ist

Executive summary: Der Schwierigkeitsgrad mancher Aufgaben bleibt bei wachsender Problemgröße konstant, bei anderen steigt er linear, polynomiell (z.B. quadratisch) oder exponentiell an.

Die Informatik beschäftigt sich unter anderem damit, welche Aufgaben schwierig sind und welche leicht. Es gibt nämlich schwierige und leichte Aufgaben. Eine Deutschstunde vorzubereiten, das ist leicht; eine Deutschklausur zu korrigieren, das ist schwer. Oder war das doch umgekehrt? Wie misst man die Schwere von Aufgaben?

Bei einem gängigen Ansatz in der Informatik (es gibt noch andere) interessiert man sich dafür, wie lange man für eine Aufgabe braucht. Das heißt dann Zeitkomplexität.
Allerdings misst man diese Länge nicht in Sekunden oder Minuten oder Jahren, denn wie schnell eine Lösung gefunden wird, hängt ja auch vom individuellen Arbeitstempo eines Menschen oder eines Computers ab. Stattdessen nimmt man also die Anzahl der dazu nötigen Arbeitsschritte als Maßeinheit.
Und außerdem interessiert einen nicht so sehr, wie viele Arbeitsschritte man für eine konkrete Aufgabe braucht (das Durchsuchen eines unsortierten Stapels von zwanzig Deutschklausuren nach der Arbeit eines bestimmten Schülers etwa), sondern wie viele Arbeitsschritte man für eine Aufgabe allgemein braucht (das Durchsuchen eines Stapels von Deutschklausuren nach einer Arbeit im Prinzip).

Wieviel Schritte man für das Durchsuchen eines Stapels von Deutschklausuren im Prinzip braucht, das hängt vor allem von einem ab: der Anzahl der Klausuren. Man braucht mehr Arbeitsschritte, wenn es mehr Klausuren sind. Und zwar ist es immer so, dass man bei einem doppelt so hohen unsortierten Klausurenstapel doppelt so viel Zeit braucht, um eine bestimmte Klausur zu finden. (Das gilt allerdings nur, wenn man nicht dem verbreiteten Glauben anhängt, dass es ohnehin immer die letzte Arbeit ist. Glückskinder könnten natürlich die gesuchte Arbeit immer als erste ziehen, deshalb interessiert uns hier vor allem der durchschnittliche Aufwand bei einer Aufgabe.)

Und dieser Aufwand – die Anzahl der Arbeitsschritte – wächst beim Durchsuchen eines Stapels linear. Das ist ein Fachausdruck für die Erscheinung „doppelt so viel Klausuren machen doppelt so viel Arbeit“ und heißt so, weil das eine lineare Funktion ist, die als Kurve so aussieht, nämlich gar nicht kurvig, sondern gerade:

Die x-Achse enthält die wachsende Problemgröße (die Anzahl der Klausuren), an der y-Achse kann man den Aufwand ablesen. Es gibt absichtlich keine Einheiten, weil die uns ja nicht interessieren.

Jetzt könnte man argumentieren, das Bearbeiten einer Klausur seien in Wirklichkeit drei Arbeitsschritte, nämlich das In-die-Hand-Nehmen, das Lesen des Namens und das Ablegen auf einen Nachbarstapel. Das ändert aber nichts an dem Prinzip „doppelt so viel Klausuren machen doppelt so viel Arbeit“, die Kurve ist vielleicht etwas steiler, aber immer noch linear.
Und das gilt ungefähr auch noch, wenn man sich zehn Arbeitsschritte dafür anrechnet, den Stapel erst einmal aus der Schultasche zu ziehen, unabhängig von dessen Größe. Wenn es nur genügend Klausuren sind, spielt so ein einmaliger Zusatzaufwand, egal wie hoch er ist, keine große Rolle mehr. Wir in der Informatik sind da rechnerisch großzügig und pädagogisch pessimistisch und gehen von beliebig anwachsenden Klassengrößen aus.

Festgehalten: der Aufwand für das Durchsuchen eines unsortierten Klausurenstapels wächst linear (in diesem Fall: zur Anzahl der Klausuren).

Andere Aufgabenarten sind einfacher. Wenn ich beispielsweise eine Stapel von Deutsch-Schülerarbeiten zur Respizienz kriege, dann liegen obenauf zwei Kopien der Aufgabenstellung. Eine davon nehme ich und lege sie zur Seite, um sie – später mal – in einen Ordner zu tun. Dieser Aufwand ist für mich konstant, was die Anzahl der Arbeiten betrifft. Die Funktion dazu sieht so aus:

Ob man den Aufwand jetzt in einen oder drei oder zehn Arbeitsschritte zerlegt: er bleibt konstant (also unabhängig von der Anzahl der Klausuren).

Wir haben jetzt also schon Aufgaben mit konstantem Aufwand und welche mit linear wachsendem Aufwand. Der Aufwand kann aber auch noch schneller ansteigen, zum Beispiel beim Sortieren von Schüleraufsätzen. Da ist es nämlich so, dass das Sortieren von dreißig Aufsätzen nicht doppelt so viel Arbeit macht wie das Sortieren von fünfzehn, sondern mehr als doppelt so viel. (Aber: siehe unten.) Und bei einer Klasse von dreißig Schülern gibt es auch nicht doppelt so viele Chancen für Feindschaften, Tritte, Streit, Tratschereien, sondern mehr als doppelt so viel. Der Aufwand steigt mehr oder weniger quadratisch, und das sieht als Funktion so aus:

Beim Sortieren der Arbeiten hängt der Aufwand übrigens von der Sortiermethode ab. Nur bei den eher ungeschickten Methoden wächst der Aufwand quadratisch, bei anderen Methoden wächst er langsamer. Also sind die anderen Methoden in der Praxis sinnvoller. (In Wirklichkeit kommt bei Klausuren auch noch dazu, dass man ja weiß, dass die Arbeit von einer „Alexandra Abel“ wohl recht weit vorne zu liegen kommen wird, und die von „Zacharias Zuser“ ziemlich am Ende, selbst wenn man keine Ahnung hat, wie die Schüler in der Klasse sonst heißen. Und das erlaubt dann schon wieder noch schnellere Sortierstrategien.)

Festgehalten: Bei manchen Aufgaben steigt der Aufwand (abhängig von einer Eingangsgröße) quadratisch. Wir vernachlässigen wie oben schon andere konstante oder linear wachsende Arbeitsschritte, die eventuell noch dazu kommen – wenn die Zahl nur groß genug ist, läuft das auf quadratisch hinaus.

Ich stelle jetzt noch eine vierte Art von Aufgaben vor, bei der Art von Aufwand noch schneller wächst, nämlich exponentiell. Schon der quadratisch steigende Aufwand steigt ziemlich steil, aber der exponentiell steigende noch viel mehr, nämlich so:

Wenn man zum Beispiel eine Zahl in Primfaktoren zerlegen möchte, dann steigt der Aufwand exponentiell zur Größe der Zahl. (Oder sagen wir: zumindest ist bisher keine bessere Lösung bekannt als eine mit exponentiell steigendem Aufwand. Wenn mal jemand eine finden sollte, wird der sehr berühmt werden.) Exponentielles Wachstum heißt: wenn eine Zahl x-mal so groß wird, dann ist der Aufwand für die Primfaktorzerlegung nicht etwa x-mal so groß (das wäre lineares Wachstum), und auch nicht x2-mal so groß (quadratisches Wachstum), sondern etwa 2x-mal so groß. Das klingt gar nicht so dramatisch, aber erinnern wir uns an die Sache mit den Reiskörnern auf dem Schachbrett. Im jeweils einfachsten Fall hat man bei linearem Wachstum am Schluss 64 Körner, bei quadratischem Wachstum 4096 Körner und bei exponentiellem Wachstum eine Zahl mit zwanzig Stellen.

Man sieht den Unterschied, wenn man alle vier Funktionen nebeneinander betrachtet:

Jede linear steigende Aufgabe wird irgendwann mal größer als jede konstante, jede quadratische überholt irgendwann mal die lineare, und die exponentiell steigende Kurve, selbst wenn sie mal langsam anfangen sollte, übersteigt irgendwann jede quadratische.

Wenn die Grafik nur ein bisschen weiter nach rechts gehen würde, dann wäre die grüne Kurve sehr weit oben, und alle anderen, die gelbe eingeschlossen, so weit unten, dass man die Unterschied dazwischen nicht mehr gut erkennen könnte.

Exponentiell steigt schon sehr steil, aber es gibt natürlich auch noch steileres Wachstum, aber dazu vielleicht später mal. (Blogeintrag zur Ackermann-Funktion.)

— Als Zusammenfassung kommen jetzt ein paar mathematischer formulierte Beispiele für Steigungsverhalten. Dabei ist x jeweils die Eingangsgröße – Anzahl der Klausuren oder was auch immer. Dann ist f(x) der Aufwand in Arbeitsschritten, abhängig von dieser Eingangsgröße.

Konstant z.B.:
f(x) = 1
f(x) = 100
(Konstant ist etwa der Aufwand für das Suchen des kleinsten Elements in einer sortierten Liste.)

Linear z.B.:
f(x) = x
f(x) = 3*x
f(x) = 3*x + 100
(Linear wächst zum Beispiel der Aufwand für das Suchen in einer unsortierten Liste.)

Quadratisch z.B.:
f(x) = x2
f(x) = x2 + 100
f(x) = x2 + 3*x + 100
(Quadratisch wächst zum Beispiel der Aufwand für das Sortieren einer Liste, wenn man mit einem nicht besonders guten Sortierverfahren arbeitet.)

Polynomiell* z.B.:
f(x) = x4
f(x) = x4 + x3
f(x) = x4 + x3 + x2 + 3000*x + 9000

Exponentiell z.B.:
f(x) = 2x
f(x) = 20x
f(x) = 2x + x4 + x3 + x2 + 3000*x + 9000
(Exponentiell wächst zum Beispiel der Aufwand bei der Primfaktorzerlegung.)

*Polynomiell ist eine Art Überbegriff zu quadratisch: x2 ist polynomiell, und x3 auch und x5 auch und so weiter – also immer dann, wenn es um xirgendwasgrößer1 geht. Das kann quadratisch sein oder nicht, mit der dem Informatiker eigenen Großzügigkeit sagen wir polynomiell dazu und gut ist.

(Fortsetzung folgt.)