Lehrzeit

Schule & Informatik

Seite 2 von 142

Tiefensuche mit Processing

Basierend auf meinem letzten Beitrag habe ich jetzt noch die Tiefensuche mit Hilfe einer Adjazenzmatrix implementiert. Besuchte Knoten werden mit Gelb markiert und der aufspannenden Baum besteht aus gelben Kanten.

Die Knoten 1 und 7 wurden nicht besucht, was man an dem fehlenden gelben Punkt sieht. Ob ein Graph zusammenhängend ist, lässt sich daher mit der Tiefesuche feststellen.

Zum besseren Verständnis habe ich noch das in meinem Fall benötigte besucht[]:boolean – Feld ausgeben lassen, sowie den zu jedem Knoten gehörigen Vorgänger-Knoten, den ich in einem Feld vorgaenger[]:int speichere.

Die darüberstehenden Zahlen gibt die Durchlaufreihenfolge der Knoten wieder.

Den bisherigen Stand biete ich hier wieder zum Download an: ProcessingTiefensuche

Im nächsten Schritt möchte ich natürlich den schrittweisen Durchlauf animiert darstellen. Aber dazu muss ich die rekursive Implementierung des Algorithmus aufbrechen, damit bei jedem Durchlauf der draw()-Methode nur 1 Schritt gemacht wird.

Graphen und Processing

Angeregt durch die Videos von Daniel Shiffman möchte ich dieses Jahr das Implementieren der Graphenalgorithmen in der elften Jahrgangsstufe auf Basis von processing mit wie immer Java machen.

Hierzu habe ich jetzt in BlueJ ein Grundprojekt programmier, dass den Schüler als Vorlage zum Weitermachen dienen soll. Folgende Features habe ich dabei umgesetzt:

  1. Graphen werden per Zufall erzeugt.
    Hierzu werden 20 Knoten zufällig im Fenster erzeugt, Die Kanten werden ebenfalls zufällig erzeugt. Um nicht nur vollständige Graphen zu bekommen, habe ich zu folgender Implementierung gegriffen:

    for(int i=0; i < maxKnoten; i=i+1) {
        for(int j=0; j < maxKnoten; j=j+1) {
            if(i==j) { //Diagonale mit Nullen belegen
                adjazenzmatrix[i][j] = 0;
            } else {
                int zufallsGewicht = (int)random(1,60);
                 //Die 3 oder das == durch != ersetzen
                if (zufallsGewicht%3==0)
                    adjazenzmatrix[i][j] = zufallsGewicht;
                else
                    adjazenzmatrix[i][j] = 0;
            }
        }
    }
    

    Dadurch erhalte ich alle möglichen Graphen mit einer unterschiedlichen Anzahl an Kanten. Auch mal nicht zusammenhängende Graphen.

  2. Ist der Graph mal erzeugt können die Knoten mit der Maus noch verschoben werden. Hierzu muss der Graph aber im Verschiebmodus sein. Dieser ist standardmäßig aktiviert und kann durch Drücken der Taste ‚m‘ verändert werden.
  3. Durch Drücken der Taste ‚i‘ werden die Knotennamen eingeblendet. Die Kantengewichte werden durch Drücken der Taste ‚e‘ ausgegeben.
    Die erstmalige Anzeige der Knotennamen dauert am Anfang etwas. Warum weiß ich nicht.
  4. Durch Drücken der Taste ‚a‘ wird ein Algorithmus gestartet, wobei im Moment noch keiner implementiert ist.
  5. Durch Drücken der Taste ’s‘ und mit einem Mausklick wird ein möglicher Startknoten grün markiert oder entmarkiert.
  6. Durch Drücken der Taste ‚t‘ und mit einem Mausklick wird ein möglicher Zielknoten rot markiert oder entmarkiert.
  7. Durch Drücken der Taste ‚h‘ kann auch während der Benutzung des Programms die Hilfe angezeigt werden. Auch das dauert am Anfang etwas.

Hier noch die zip-Datei zum Runterladen und weiterentwickeln:  ProcessingAdjazenzMatrix.

Didaktisches Problem?

„Fremdsprachen wie Französisch und Englisch lernen, aber bei 3 Zeilen Java schon aussteigen.“, das ging mir durch den Kopf, als ich meinen aktuellen Zehnklässlern folgende kleine Aufgabe gab:

Aufgabe

Ergänze den Quelltext der GUI so, dass ein Vorschlag angezeigt wird.

Den Quelltext kann man hier herunterladen: Ratgeber2

Die Klasse TippGeber hatte ich mit den Schülern zusammen erstellt und dabei Felder und die Zählwiederholung eingeführt:

import java.util.*; 

public class TippGeber {
    private String[] tipp;

    public TippGeber() {
        tipp = new String[] {
            "Essen",
            "Schlafen",
            "Lernen",
            "Kino",
            "Freunde treffen",
            "Aufrauemen",
            "Lesen",
            "Musik machen"
        };
    }
    
    public String getZufallsEintrag() {
        //Wuerfel definieren
        Random wuerferl = new Random();
        //Wuertfel werfen
        int wurfErgebnis = wuerferl.nextInt(tipp.length);
        //tipp zurueckgeben
        return tipp[wurfErgebnis];
    }
    
    public void tippsAusgeben() {
        for (int index=0; index<tipp.length; index++) {
            System.out.println("tipp["+index+"]="+tipp[index]);
        }
    }
}

Ergänzt werden sollte also nur die folgende Methode in der GUI, die ich wie immer mit dem Java-Editor erstellt habe:

public void jButton_zeigeTipp(ActionEvent evt) {
    //TippGeber initialisieren

    //zufallsEintrag holen
   
    //Tipp anzeigen

}

Da dieses Zusammenspiel zwischen einer Oberfläche und einem Backend bereits gemacht wurde (Quader), dachte ich, dass sei kein Problem. Falsch gedacht. Von 30 Schüler wusste es keiner! Ein paar wenige konnte zwar aus dem alten Projekt die paar nötigen Zeilen rüber kopieren und anpassen. Als aber einer am Lehrercomputer vorprogrammieren sollte, kam er ungefähr soweit:

public void jButton_zeigeTipp(ActionEvent evt) {
    //TippGeber initialisieren
    new TippGeber tipps
    //zufallsEintrag holen
    ??????
    //Tipp anzeigen
    ??????
}

Welche Vorstellung oder Nicht-Vorstellung liegt da vor? Ich stelle mal ein paar Vermutungen auf:

  1. Es ist immer noch nicht klar, dass Programmierzeilen oder zumindest Zuweisungen in der Regel von Rechts nach Links gelesen werden, ähnlich wie in der Mathematik: y=2*5+1
  2. Der Konstruktor ist eine besondere Methode und benötigt daher Klammern… wurde nicht gemacht,
  3. Erkannt wurde, dass Objekte Namen haben müssen… Immerhin
  4. Erkannt wurde, dass komplexe Objekte mit new erzeugt werden… auch schon mal gut.
  5. Anweisungen werden in Java mit einem Semikolon beendet… wurde nicht gemacht, wäre aber, wenn es nicht so gehäuft wie oben auftritt, auch nicht so schlimm.

Aber nicht nur, dass wir das fast schon mal so gemacht hatten. Ich hatte in meiner Grundwissens-Zusammenfassung das alles auch schon stehen::

 Ein Objekt im Quelltext erzeugen können:
 new – Konstruktorname – ( - Werteliste - )
 Beispiel: 
 Hausaufgabe neueHA = new Hausaufgabe("M", "20161101", "B: S 12/1");

Das „-“ verbindet dabei die Token wie ’new‘ und steht für ein Leerzeichen. Ein eingerahmter Begriff bzw, Token kann vom Programmierer frei gewählt werden. Wie im folgenden Beispiel:

public – class – EigenerName – { – }

Hier ist nur das Token „Eigene Name“ frei wählbar. „public“, „class“ und die Klammern müssen so genau an dieser Stelle und genau in dieser Schreibweise stehen.

Was ist nun also schief gelaufen? War die Abstraktion mit den Token zu groß? War der Lerndruck zu gering, was ich vermute? Wie erklärt ihr das?

Kennt ihr auch solche Probleme? Wie löst ihr das? Hat jemand das Programmieren-Lernen über Token irgendwie verbessert? Oder hat einen ganz anderen Ansatz?

Gibt es einen Erklär- und/oder Trainingsansatz ohne Computer? Ich denke da an Spielkarten.

Der Vollständigkeit halber sei erwähnt, dass es in der Parallelklasse mindestens 1 Schüler gibt, der kein Problem damit hatte und das, obwohl er ohne Programmiervorkenntnisse in die 10. Klasse gekommen ist.

« Ältere Beiträge Neuere Beiträge »

© 2017 Lehrzeit

Theme von Anders NorénHoch ↑