Lehrzeit

Schule & Informatik

Was bislang passiert ist

In den vergangenen Wochen war es hier ein wenig ruhiger: Schule & Privatleben waren ein wenig turbulenter, wobei hier zweiteres nichts zur Sache tut.

Informatikabitur 2017

Das diesjährige, schriftliche Informatikabitur verlief problemlos. Die gestellten Aufgaben war recht unterschiedlich im Aufbau, so dass eine Auswahl leicht fiel. Gefragt wurden alle Standarddiagramme (Klassendiagramm, Objektdiagramm, Sequenzdiagramm, Zustandsdiagramm), wobei ich mir gewünscht hätte, dass die Aufgabenformulierung hie und da noch eindeutiger hätte sein können.

So unterscheide ich zwischen „Klassendiagrammen“, in denen nur die Klassennamen und Kardinalitäten vorkommen, das Kompositum-Entwurfsmuster stelle ich immer so dar und auch in der Angabe war es so gezeichnet. Ein „erweitertes Klassendiagramm“ umfasst dann auch Attribute und Methoden mit Datentypen und Sichtbarkeiten (public, private, protected). Meist wird eine Mischung angegeben (Aufgabe 2), was ich nicht für glücklich halte. Auch die Tatsache, dass man sich nicht konsequent an UML hält, finde ich fragwürdig. Wofür gibt es denn einen Standard, wenn man ihn nicht benutzt? Das hat dann auch in meinen Augen nichts mit didaktischer Reduktion zu tun.

P-Seminar

Mein diesjähriges P-Seminar befindet sich auf einem, wie ich finde, spannenden Weg. Vom ursprünglichen Ziel „Kurzfilme, die Informatik-Themen“ problematisieren, ist nur wenig übrig geblieben. Dafür wurde die Ausstellung des örtlichen Energie-Solar-Vereins digitalisiert. Diese benutzen immer noch Plakate in den Ausstellungen, was nun nicht mehr nötig ist. Ein Teil der Schüler haben hierfür die Inhalte der Plakate als Website umgesetzt, welche nun mit Hilfe eines Tablets (unten) und rollbaren Fernsehers interaktiv präsentiert werden kann.

Zum Glück wollten aber nicht alle programmieren, so dass noch einige tolle Kurzfilme rund ums Thema alternative Energie entstanden sind bzw. entstehen. Ich hoffe, dass ich hier einige zeigen kann, denn ich finde es wirklich großartig, was die Schüler geleistet haben.

Das das P-Seminar im Übrigen eine andere Wendung nahm, finde ich im Nachhinein nicht so schlimm. In meinen Augen sollte es im P-Seminar vor allem darum gehen, dass die Schüler sich einfach mal frei, aber dennoch zielgerichtet ausprobieren können. Denn nur so können sie sich selbst besser kennenlernen und einen sinnvollen nächsten Schritt bei ihrer Berufswahl treffen.

Die kommenden P-Seminare

Im nächsten Schuljahr werde ich meine 3D-Drucker wieder mehr aktivieren und Quadrokopter mit den Schülern bauen. Das wird nicht ganz billig (ca. 150 Euro pro Modell), aber dafür gehört das Modell dann auch den Schülern. Allerdings werden wir gehörig auf die rechtliche Seite aufpassen müssen, hat sich da doch, dank einiger Spinner, die Lage doch sehr verschärft. Einfach so rumfliegen ist nicht mehr. Dennoch hoffe ich, dass wir tolle Flugrennen haben werden oder interessante Flugaufnahmen der Schule.

Beim Lesen meiner diversen abonnierten Blogs stieß ich auf den Hinweis, dass der Faust nun auch in Handschrift vorliegt. Hierzu haben 229 Personen jeweils einen Teil des Werks abgeschrieben, das Ganze wurde gebunden und kann nun beim X47-Verlag gekauft werden.Der Verlag bietet für den ein oder anderen Leser vielleicht noch weitere interessante Werke. Einfach mal vorbeischauen.

Das Konzept des Abschreibens erinnerte mich an irgendeine Religionslehrerin oder -lehrer, der als „Zusatzaufgabe bei Unterrichtsstörungen“ in seinem / ihren Unterricht immer eine Seite der Bibel abschreiben ließ. Am Ende seiner Schullaufbahn hatte er oder sie eine komplett handschriftliche Bibel. Eine schöne Idee. Schade, dass es so etwas nicht auch in Informatik gibt: DAS eine grundlegende Werk, das man kennen sollte. Mir würden zwar einige in Frage kommenden Werke einfallen, aber keines spielt im Unterrichtsgeschehen die eine Rolle, wie sie die Bibel oder ein Faust spielt.

Graphologie hat mich auch schon immer interessiert. Und bei der Menge an gefundene Handschriften in dem Buch, hätte man geügend Übungsmaterial. Schade, dass die Graphologie nicht für ein ganzes P-Seminar reicht im Fach Informatik reicht…. oder …. einen Roboter bauen, der handschriftlich schreibt?

Die andere Seite

Und dann ist da noch die andere Seite des Unterrichts, nämlich die des Vaters. Mein ältester Sohn ist selbst in der 11. Klasse und es für mich spannend zu erleben, wie Kollegen einer anderen Schule Unterricht P-Seminare gestalten:

  • Wieso muss man auf drei Berufsinformationsmessen gehen, wenn man weiß, was man mal studieren will?
  • Wieso muss jetzt mit Gewalt eine Sponsor gesucht werden, wenn es keinen gibt, den das Thema das P-Seminars interessiert?
  • Wieso müssen die Schüler alles in der Schule machen, wenn es manchmal besser ist, wenn Sie mal ein ganzes Wochenende oder wenigstens eine Tag an dem Thema zu Hause durcharbeiten?

Ich muss realisieren, dass viele Wege durch ein P-Seminar führen und „viel zu lernen ich noch habe“.

Informatik 11. Klasse

Inzwischen habe ich mein Graphen-Programmieren auf Basis mit Processing verbessert und die Tiefensuche kann nun schrittweise „durchgeklickt“ werden. Hierzu habe ich den Tiefensuche-Algorithmus nicht mehr rekursiv wie bisher implementiert, sondern – was ich bis jetzt noch gar nicht wusste, mit Hilfe eines Stacks. Auf diesem Stack liegen die als nächstes zu untersuchenden Knoten.

Ein ähnliches Konzept gibt es auch für die Breitensuche: Hier werden die noch zu untersuchenden Knoten allerdings in einer Queue verwaltet. Schade, dass ich diese Zusammenhänge erst jetzt entdeckt habe, denn so habe ich einen logischen Zusammenhang zwischen dem ersten Halbjahr und dem zweiten Halbjahr bislang noch gar nicht genutzt.

Hier also das BlueJ-Projekt: TiefensucheProcessingAnim

Einfach das Programm mit BlueJ oä starten, dann einen Knoten mit ’s’+Mausklick als Startknoten grün markieren. Dann ‚a‘ drücken, um den Algorithmus zu starten und anschließend ’s‘  für jeden Algorithmus-Schritt. Im Hintergrund wird der Stack jeweils mitausgegeben.

Die Breitensuche habe ich noch nicht umgesetzt, da wir im Unterricht jetzt beim Dijkstra sind. Danach noch Projektmanagement und das finale Endprojekt.

5 Kommentare

  1. Hallo Ingo! Beim Dijkstra und A* und ähnlichen Verfahren benutzt du für die open list dann eine priority queue. Immer das gleiche Prinzip. Sehr schön das alles – genau wie dein Projekt!

    • Das mit der Priority-Queue beim Dijkstra ist aber nicht so optimal, da durch die ständige Änderung der Entfernung die Queue immer wieder neusortiert werden müsste.

      • Deswegen implementiert man die priority queue ja als min heap und nicht als Liste o.ä. Dann geht einfügen in O (log n) und das kleinste Element steht immer vorne bzw in der Wurzel des heaps, dh auslesen in O (1). Kannst es ja mal mit der pq in der Java Standardbibliothek ausprobieren. Meiner Erfahrung aus der KI nach ist aber oft gar nicht die Implementierung der open list der entscheidende zeitfaktor sondern das Such verfahren bzw die Heuristik. Die beste Datenstruktur nützt nichts wenn sich das Verfahren im suchraum verrennt. (Sorry für Tippfehler. Auf Handy geschrieben)

        • Einfügen und Löschen in O(log n) ist klar. Aber ich sehe tatsächlich noch nicht, warum es insgesamt deutlich besser wird. Bei Start des Algorithmus habe ich alle noch nicht besuchten Knoten im Heap, oder? Wenn ich jetzt die Entfernung der verbleibenden n-1 Knoten im Heap aktualisiere, muss ich doch den gesamten Heap neu sortieren und das müsste doch O(n log n) sein. Denn einen Knoten zu verschieben müsste O(log n) sein und das für im worst case n-1 Knoten ergäbe doch O(n log n). In der Regel muss man wahrscheinlich nicht alle Knoten ändern, aber man weiß ja nie.

          • (Alles Folgende ist mit extremer Vorsicht zu genießen. Ist bei mir mittlerweile auch über zehn Jahre her, dass ich mal wirklich von Grund auf diese Datenstrukturen implementiert habe.)

            „Aber ich sehe tatsächlich noch nicht, warum es insgesamt deutlich besser wird“. Die Frage ist erstmal: Besser als was? Du musst für Dijkstra, A* und Co. auf jeden Fall in jedem Schritt den *bestbewerteten* Suchknoten expandieren. D.h. im Gegensatz zur Tiefen- oder Breitensuche werden neu expandierte Knoten *irgendwo* in die open list eingefügt. Deren Reihenfolge ändert sich also in jedem Fall.

            Ich weiß nicht, wie du es machen würdest, aber eine Möglichkeit wäre natürlich komplettes Neusortieren der Liste (dann auch als Liste oder Array realisiert), macht O(n log n). Oder man hält die Liste sortiert und macht aus dem Einfügen der Nachfolgeknoten so ne Art Bubblesort, d.h. man lässt sie mit der neuen Bewertung „durchperlen“. Das ist dann aber jedesmal linear in der Länge der Liste. Und genau da ist die Heap-Struktur effizienter, würde ich sagen, weil du beim binary heap eine Baumstruktur hast und nur die Heap-Eigenschaft wieder herstellst, in logarithmischer Zeit.

            Wichtig ist auch: Nur die Bewertung der m Knoten, die du im vorigen Schritt expandiert hast (d.h. deren Nachfolger du untersucht hast), können überhaupt ihre Bewertung verändern. Das sind normalerweise ganz wesentlich weniger als als die Gesamtzahl der Knoten n . In der Praxis hast du sogar oft eine konstante Obergrenze (siehe: branching factor). D.h. du hast bei m neuen Knoten und einer Liste mit n Elementen zwar O(m log n) für das Einfügen, aber da m << n ist, praktisch doch logarithmische Laufzeit, während (sortiererhaltendes) Einfügen in die Liste O(m * n) wäre.

            Und als letztes: Für richtig riesige PQs (aber nur da!) gibt es natürlich die echt coolen Implementationsvarianten: Fibonacci Heap z.B. wo man in O(1) amortisierter Zeit einfügen bzw. Kosten anpassen kann. Das hab ich so ca. im Jahr 2000 mal programmiert – nur um zu merken, dass es für meine Anwendung absolut null Performance-Vorteile gebracht hat. Interessanterweise (auch gerade ergoogelt) benutzt auch die Implementation in java.util anscheinend keine Fibonacci heaps: https://stackoverflow.com/questions/6273833/is-there-a-standard-java-implementation-of-a-fibonacci-heap

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.

*

© 2017 Lehrzeit

Theme von Anders NorénHoch ↑