Anmerkung: In dieser Jahrgangsstufe geht es vor allem um die Programmierung mit Java. Zum Erlernen eignet sich unter anderem das Programm BlueJ.
Inhaltsverzeichnis
[Anzeigen]
[Verbergen]
- Objekte und Klassen
- Klassen
- Objekte
- JAVA-Quelltext mit Erklärungen am Beispiel eines Programmes
- Datentypen
- Kommentierung
- Zugriffsrechte
- Rückgabewerte
- Wertzuweisung
- Kurzformen
- Verzweigungen und Schleifen
- Verzweigungen
- if-Anweisung
- Vergleichsoperatoren
- Mehrfachverzweigungen: Switch-Case-Anweisungen
- Schleifen
- for-Schleife
- while-Schleife
- Arrays (Felder)
- Einleitung
- Deklaration eines Arrays
- Eindimensionale und mehrdimensionale Arrays
- Vererbung und Polymorphie
- Sortierverfahren
- Allgemeines
- Selectionsort, Insertsort, Bubblesort
- Selectionsort
- Grundlagen
- Beispiel
- Insertsort
- Grundlagen
- Beispiel
- Bubblesort
- Grundlagen
- Beispiel mit dem Feld der Abfolge „5, 37, 13, 21, 2, 13“
- 1. Durchlauf
- 2. Durchlauf
- 3. Durchlauf
- 4. Durchlauf
- 5. Durchlauf
- Endliche Automaten
- Einführung
- Beispiel: Schwimmbadautomat
- Zustandsübergangstabelle
- Implementierung von endlichen Automaten
- Literatur und Quellen
- Literatur
- Quellen
Objekte und Klassen
Klassen
Eine Klasse besteht aus Name, Attributen und Methoden. Nach Konventionen wird der Klassenname groß und die Attribute sowie die Methoden klein geschrieben. Besteht der Begriff aus mehreren „Teilen“, werden die weiteren Wörter groß geschrieben.
| KREIS |
| durchmesser xPosition yPosition farbe istSichtbar |
| sichtbarMachen() horizontalBewegen(int entfernung) farbeAendern(String neueFarbe) groesseAendern(int neuerDurchmesser) |
Objekte
Von einer Klasse können ein oder mehrere Objekte geschaffen werden und mit unterschiedlichen Namen versehen werden. Allen Attributen muss ein Wert zugewiesen werden. Mit Hilfe von Methoden sendet der Benutzer an ein Objekt eine Botschaft, die es veranlasst, die entsprechende Änderung seiner Attribute durchzuführen.
JAVA-Quelltext mit Erklärungen am Beispiel eines Programmes
Klassendefinition: Die Beschreibung der Klasse
public class KREIS {
Definition der Attribute durch Zugriffsrecht (private oder public), Bezeichner und Datentyp (z.B. int, String, boolean).
private int radius;
private int xPosition;
private int yPosition;
private String farbe;
private boolean istSichtbar;
Konstruktor: Hier werden die Anfangswerte der einzelnen Attribute festgelegt.
public KREIS() oder public KREIS(int r, int x, int y) {
Wertzuweisungen
radius = 15 oder r;
xPosition = 20 oder x;
yPosition = 60 oder y;
farbe = "blau";
istSichtbar = false;
Definition einer Methode durch Zugriffsrecht, Rückgabewert (hier void: keine Rückgabe), Bezeichner und ggf. anzugebender Parameter
public void zeichnen() {
...
}
Aufrufen einer weiteren Methode
public void sichtbarMachen() {
istSichtbar = true;
zeichnen();
}
Methode mit nötiger Parametereingabe und Wertzuweisung
public void horizontalBewegen(int entfernung) {
loeschen();
xPosition = xPosition + entfernung;
zeichnen();
}
}
Datentypen
| Datentyp | Beschreibung | Werte | Speicherbedarf |
| boolean | Wahrheitswert | true oder false | 1 Bit |
| int | ganze Zahl | (z.B.) -3; 0; 5 | 32 Bit (4 Byte) |
| double | Dezimalzahl | (z.B.) 3.27; -0.05 | 64 Bit (8 Byte) |
| char | einzelnes Zeichen | 'a'; '5' | 16 Bit (2 Byte) |
Der Datentyp „String“ ist ein zusammengesetzter Datentyp, der sich aus einzelnen Daten vom Typ „char“ zusammensetzt, z.B. "Abc" = 'A' + 'b' + 'c'.
Kommentierung
Jede Methode sollte vorher kommentiert werden, damit der Leser des Quelltextes eine Chance hat zu verstehen, was mit dieser Methode bewirkt werden soll. Bei einer Zeile verwendet man die Zeichenfolge //.
Bei mehreren Zeilen wird Folgendes benutzt:
/**Diese Methode soll zeigen,
* dass sie sinnlos ist.
*/
Zugriffsrechte
Beim Definieren der Attribute durch Zugriffsrechte gibt es zwei Möglichkeiten:
- private: Attribute oder Methoden, auf die nur Objekte dieser Klasse zugreifen (lesen oder verändern) können.
- public: Attribute oder Methoden, auf die auch Objekte anderer Klassen zugreifen können.
Im Sinne der Datenkapselung (Objekte sollen nicht direkt auf Attributwerte anderer Objekte zugreifen dürfen) werden Attribute üblicherweise als "private" deklariert. Soweit eine Änderung des Attributwerts zugelassen werden soll, wird eine Methode mit dem Zugriffsmodifikator public zur Verfügung gestellt, die diese Änderung (i.d.R. nach Prüfung auf sinnvolle Werte, z.B. Altersangabe zwischen 0 und 100) durchführt.
Rückgabewerte
Verwendet man „void“, ist keine Rückgabe eines Wertes vorgesehen (ein ggf. geändeter Wert ist nur über den Objektinspektor einsehbar). Bei „int“ wird eine integer-Zahl zurückgegeben und kann von einem anderen Objekt weiterverarbeitet werden bzw. über die Konsole betrachtet werden. Analog dazu funktionieren „double, String, boolean“.
Wertzuweisung
Eine Wertzuweisung an eine Variable geschieht durch einen Ausdruck der Form
x = 50;
y = x + 25;
y = (2*x + 3) - 5
Dabei wird der Variablen auf der linken Seite die Zahl oder das Ergebnis des Rechenausdrucks auf der rechten Seite zugewiesen, z.B. y = 5; x = 12; y = 3*x - 6; danach ist y = 30 und x = 12.
Der Ausdruck y = x%3 (sprich: x modulo 3) bedeutet, dass y der Rest zugewiesen wird, der sich bei der Division von x durch 3 ergibt. Mit x = 13; y = x%3; wird y der Wert 1 zugewiesen.
Kurzformen
y++; bedeutet dasselbe wie y = y + 1; und y-- dasselbe wie y = y - 1;.
Möchte man y = y + 3 oder y = y - 3 abkürzen, verwendet man y += 3 bzw.
y -=3.
Verzweigungen und Schleifen
Verzweigungen
if-Anweisung
Die Syntax für eine if-Anweisung lautet wie folgt:
if(Bedingung) {Anweisungen} else {Anweisungen}
Der else-Teil kann auch entfallen, falls man keine Anweisung definieren möchte, wenn die Bedingung nicht erfüllt ist. Erfolgt zudem nur eine Anweisung, können die geschweiften Klammern weggelassen werden:
if(n > 0) x = x/n;
Vergleichsoperatoren
Folgende Vergleichsoperatoren können verwendet werden:
| Bedeutung | Beispiel | |
| == | gleich | x == 3 |
| != | ungleich | x != y |
| > | größer | 4 > 3 |
| >= | größer oder gleich | x >= y |
| < | kleiner | x+1 < 0 |
| <= | kleiner oder gleich | x <= y |
Es gibt zusätzlich noch diese zusammengesetzten Vergleiche:
- &&: und-Verknüpfung
- ||: oder-Verknüpfung
if(x >= 0 && x <= 10) y = x;
Mehrfachverzweigungen: Switch-Case-Anweisungen
Die Syntax sieht so aus (erklärt an einem Programm zur Ermittlung der Tagesanzahl eines Monats):
switch (monat) {
case 1: case 3: case 5: case 7: case 8: case 10: case 12: tage = 31; break;
case 4: case 6: case 9: case 11: tage = 30; break;
case 2: {if(jahr%4 == 0) tage = 29; else tage = 28;}; break;
}
Der Grundgedanke bei dieser Methode ist der, dass der Rechner zur passenden case-Marke springt und die dort angegebene Anweisung ausführt; passt keine Marke, springt er an das Ende der switch-Anweisung und führt keine Anweisung aus.
Der switch-Ausdruck muss vom Typ integer oder char sein. Die case-Marken müssen Konstanten, d.h. Zahl oder Zeichen, sein (keine Rechenausdrücke). Der Typ der case-Marke muss zum switch-Ausdruck passen, case-Marken müssen voneinander verschieden sein und müssen mit einem break beendet werden.
Schleifen
for-Schleife
Die Syntax sieht wie folgt aus:
for(int i = 0; i <= n; i = i +1) {Anweisungen}
Dabei werden die Laufvariablen durch int i = 0 initialisiert, durch i <= n eine Abbruchbedingung definiert und durch i = i +1 oder i++ die Laufvariable verändert. Statt i kann der Bezeichner anders genannt werden.
Es ist auch möglich abwärts zu zählen, also i = i - 1 oder i--. Die Abbruchbedingung muss dementsprechend angepasst werden. Außerdem kann die Schrittweite beliebig verändert werden, z.B. i = i + 5.
while-Schleife
while(Bedingung) {Anweisungen}
Solange die Bedingung erfüllt ist, führt das Programm die zwischen den geschweiften Klammern aufgelisteten Anweisungen aus.
Arrays (Felder)
Einleitung
Häufig kommt es vor, dass man mehrere gleichartige Elemente, wie z. B. Zahlen, Zeichen oder booleschen Werten speichern möchte. Hierbei kann bereits zu Beginn gesagt werden, dass es eine bestimmte Anzahl an Elementen gibt; genauso ist es aber möglich, dass die Anzahl der Elemente noch nicht abgesehen werden kann.
Die einzelnen Elemente können zwar mit jeweils einer eigenen Variable beschrieben werden.
Einfacher ist hingegen die Verwendung eines Arrays, also eines Felds. In diesem Array wird jedem Element ein Wert von 0 bis zum Endwert zugewiesen. Dieser Wert wird auch als Index bezeichnet. Über den Aufruf des Index kann somit das Element selbst aufgerufen werden.
Deklaration eines Arrays
Die Deklaration eines Arrays erfolgt in Java durch die Angabe, dass es ein Array ist, durch die Angabe des Datentyps für alle Feldwerte und durch die Angabe des Bezeichner des Array. Die Deklaration sieht damit wie folgt aus:
int[] a;
float[] b;
boolean[] c;
a, b, c sind hierbei die Namen des Arrays. Hier ist seine Länge noch nicht festgelegt.
Es kann daher noch nicht damit gearbeitet werden. Es hat den Wert null. Um die maximale Länge des Arrays
festzulegen, wird der gewünschte Wert in die eckigen Klammern geschrieben:
int[5] a;
float[2] b;
boolean[20] c;
Somit hat a nun Platz für 5 Integer-Werte, b Platz für 10 Float-Werte und c Platz
für 20 Bool-Werte. Ohne Zuweisung eines Werts zu einem Index hat ein Element den Wert null.
Die einzelnen Werte können sodann mit a[0], a[1], ... , a[4] angesprochen werden. Wichtig ist dabei, dass
nicht ab der ersten Stelle gezählt wird, sondern ab der „nullten“.
Um das Array gleich bei der Erzeugung mit Werten zu füllen, können die sofort in einer geschweiften Klammer angegeben werden. In diesem Fall sähe das Array beispielsweise wie folgt aus:
a = new int[] {1, 4, 9, 16, 25};
b = new float[] {0.8, 4.2}
Das Element a[3] hätte dann den Wert 16.
Eindimensionale und mehrdimensionale Arrays
Oben wurde lediglich das eindimensionale Array behandelt. Es ist allerdings auch denkbar, dass einem Feld mehrere Werte zugewiesen werden. In diesem Fall spricht man von mehrdimensionalen Arrays.
Vererbung und Polymorphie
Eine Fluglinie könnte ihre Mitarbeiter in Piloten, Flugbegleiter und Bodenpersonal aufteilen. Alle Attribute und Methoden, die alle Mitarbeiter gemeinsam haben, wie z.B. persnr, name, kuendigen() werden in der Oberklasse PERSONAL festgelegt.
Attribute und Methoden, die nur einen Teil der Mitarbeiter betreffen, werden dagegen in der betreffenden Unterklasse aufgenommen (z.B. das Attribut abteilung in BODENPERSONAL). Die Unterklasse erbt sämtliche Attribute und Methoden der Oberklasse. In Java wird der Bezug zur Oberklasse mittels des Schlüsselwortes extends hergestellt, also z.B. class BODENPERSONAL extends PERSONAL. Das zugehörige Klassendiagramm könnte also folgendermaßen aussehen:
Im Beispiel werden die Methoden befoerdern(), gehaltBerechnen() von allen Objekten der drei Unterklassen verstanden, da sie von der gemeinsamen Oberklasse PERSONAL geerbt wurden, allerdings werden diese Methoden z.T. überschrieben. Erst zur Laufzeit dieses Programms entscheidet sich je nach Zugehörigkeit zu einer der drei Unterklassen, welche der verschiedenen Ausprägungen ausgeführt wird.
Da hierbei der gleiche Methodenaufruf bei Objekten verschiedener Klassen eine unterschiedliche Ausführung bewirkt, spricht man von Polymorphie (griech. „Vielgestaltigkeit“). In dem Beispiel bekommt ein Pilot zum Grundgehalt eine Zulage abhängig vom Rang, während das Bodenpersonal für geleistete Überstunden zusätzlich entlohnt werden. Flugbegleiter haben keine Zusätze. Ähnliches gilt für die Methode befoerdern().
Sollten von einer Oberklasse keine Objekte erzeugt werden, z.B. weil jeder Mitarbeiter einer der drei Unterklassen angehört, verwendet man eine abstrakte Oberklasse PERSONAL, die im Diagramm durch {abstract} kenntlich gemacht wird. In Java erhalten abstrakte Klassen das Schlüsselwort abstract. In einer solchen Klasse muss eine Methode wie befoerdern() nicht ausformuliert werden, sondern kann ebenfalls als abstrakt deklariert werden. Das ist quasi nur eine Ankündigung, dass diese Methode existiert und in allen Unterklassen ausformuliert wird.
Sortierverfahren
Allgemeines
Das Sortieren von Daten nach bestimmten Kriterien gehört zu den wichtigsten Problemen der Informatik. Bei großen Datenmengen ist es sehr wichtig, dass effiziente Algorithmen zur Verfügung stehen, die möglichst wenig Zeit zum Sortieren benötigen. Im Folgenden werden „einfachere“ Algorithmen betrachtet, die recht verständlich zu impletieren sind, aber eine relativ lange Laufzeit haben.
Die drei Algorithmen Insertsort (Sortieren durch Einfügen), Selectionsort (Sortieren durch Auswählen) und Bubblesort (Sortieren durch Vertauschen) werden beschrieben und an einem Beispiel erläutert. Auf weitere Algorithmen wie Mergesort oder Quicksort werden dagegen nicht besprochen.
Selectionsort, Insertsort, Bubblesort
Selectionsort
Grundlagen
Selectionsort arbeitet nach dem Prinzip, das kleinste Element des Feldes zu suchen, und dieses dann mit dem ersten Element des zu betrachteten Teils zu tauschen.
Zu Beginn sucht man im ganzen Feld nach dem kleinsten Element und tauscht es mit dem ersten Element. Danach sucht man im Restfeld ohne erstes Element nach dem kleinsten Element und tauscht mit dem zweiten Element bzw. mit dem ersten Element des zu betrachtenden Teils. Dies wiederholt man, bis das zweitgrößte Element an den korrekten Platz Platz gebracht wurde.
Beispiel
Insertsort
Grundlagen
Insertsort arbeitet nach dem Prinzip, das Feld in einen sortierten und einen unsortierten Teil zu teilen und dann das erste Element des unsortierten Teils an die richtige Stelle im sortierten Teil zu schieben. Zunächst besteht der sortierte Teil aus dem ersten Element. Das erste Element des unsortierten Teils ist damit das zweite. Dieses wird solange mit dem vorherigen vertauscht, solange es kleiner als dieses ist oder das Element noch nicht das erste Element des Feldes ist.
Somit vergrößert sich der sortierte Teil jeweils um eins, während sich der unsortierte um eins verringert. Dies wird wiederholt, bis der unsortierte Teil null wird und somit das ganze Feld sortiert vorliegt.
Beispiel
Bubblesort
Grundlagen
Der Sortieralgorithmus Bubblesort (Blasensortierung) arbeitet nach dem Prinzip, dass das Feld durchlaufen wird und dabei so getauscht wird, dass das größte bzw. kleinste Element an der richtigen Stelle steht. Nachfolgend wird die aufsteigende Variante beschrieben, so dass das größte Element nach oben wandert.
Man beginnt dazu am Anfang des Feldes und tauscht benachbarte Elemente aus, wenn das rechte Element kleiner als sein Vorgänger ist. Somit steht das größte Element nach einem Durchlauf am Ende des Feldes. Diese Sortierung wird wiederholt, ohne dass dabei der letzte bereits sortierte Feldteil betrachtet wird. Damit erhält man ein sortiertes Feld.
Beispiel mit dem Feld der Abfolge „5, 37, 13, 21, 2, 13“
1. Durchlauf
2. Durchlauf
3. Durchlauf
4. Durchlauf
5. Durchlauf
Endliche Automaten
Einführung
Programme können in Zustandsdiagrammen dargestellt werden. Darin werden Übergänge und Aktionen dargestellt. Wird eine Aktion zeitgleich mit dem Übergang gestartet, spricht man von ausgelösten Aktionen.
Die verschiedenen Aktionen führen wiederum zu verschiedenen Zuständen. Ist die Anzahl der Zustände begrenzt, also endlich, spricht man von einem endlichen Automat. Mithilfe eines solchen endlichen Automaten lassen sich viele (aber nicht alle) Systeme modellieren.
Ein endlicher Automat ist eine Art „Black Box“. Befindet sich diese Black Box nach Abarbeitung der Eingabefolge in einem ausgezeichneten Zustand, dem sogenannten Endzustand, so handelt es sich um eine akzeptierte Folge, ansonsten hat sie die Eingabe nicht akzeptiert.
Beispiel: Schwimmbadautomat
Der Eintritt in ein Schwimmbad kostet 2€. Nach Eingabe von Münzen im Gesamtwert von mindestens 2€ öffnet der Automat die Schranke, sonst nicht. Er akzeptiert lediglich Münzen im Wert von 0,50€, 1€ und 2€.
Das zugehörige Zustandsdiagramm sieht so aus, wobei q Zustand beschreibt:
Zustandsübergangstabelle
Das Zustandsdiagramm lässt sich auch tabellarisch darstellen. Diese Tabelle wird als Zustandsübergangstabelle bezeichnet. Hierbei steht in der Kopfzeile die Aktion, die den Übergang auslöst, in der linken Spalte der Aggregatszustand des Übergangs und in der Zelle die ausgelöste Aktion sowie den Zielüberstand des Übergangs[1]Informatik 3, S. 83..
Beim Schwimmbadautomaten sähe die Tabelle etwa wie folgt aus:
| 0,5 | 1,0 | 2,0 | |
| start | q0,5 | q1 | q2 |
| q0,5 | q1 | q1,5 | q2 |
| q1 | q1,5 | q2 | q2 |
| q1,5 | q2 | q2 | q2 |
| q2 | q2 | q2 | q2 |
Häufig werden in der Informatik „Wörter“ als Zeichenketten (häufig nur Zeichen a und b) oder auch „Zahlen“ als Ziffernketten eingegeben und daraufhin untersucht, ob sie eine bestimmte Bedingung erfüllen.
Implementierung von endlichen Automaten
Endliche Automaten werden durch ein spezielles Objekt implementiert. Dabei wird der Zustand des Objekts durch eine konkrete Kombination der Attributswerte definiert. Häufig werden allerdings nicht alle Attributswerte benötigt. Aus diesem Grund kann ein spezieller Zustand verwendet werden, dessen Wert den Zustand des simulierten Automaten beschreibt[2]Informatik 3, S. 83..
Literatur und Quellen
Literatur
- Informatik 3 , Ernst Klett Verlag GmbH, Stuttgart, 1. Auflage, 2008
ISBN: 978-3-12-731768-8.