Problem: Klausur ist schlecht ausgefallen. Man kann vermuten, dass auch die Nicht-Klausurschreiberinnen nicht alles gekonnt hätten. Offenbar kommen so einige Dinge, die wir im Unterricht behandeln, nicht so bei Euch an, wie ich mir das wünsche. Andererseits bin ich natürlich an den Lehrplan gebunden.
Was meines Erachtens bei Euch nur schlecht funktioniert:(*)
• Zu einem Problem ein eigenes Vorgehen entwerfen und programmieren (z.B. "ermittle die zweitgrößte Zahl aus einem Array" oder "ermittle, wie oft jedes Arrayelement im Array vorkommt")
• bestehenden Java-Programmcode lesen und verstehen.
Bitte bearbeitet die folgenden zwei Aufgaben über mein Rückmeldeformular:
Aufgabe 3:
Lies bzw. überfliege noch einmal mein Java-Einführungsskript. 20220114_TOE_Java_Einfuehrung.pdf Notiere alle Begriffe oder Konzepte, die deiner Meinung in einer "Vokabelliste für Informatik" erklärt werden müssten. Erstelle dazu eine einfache Textdatei und sortiere die Begriffe (nur ein Begriff pro Zeile!) danach, wie wichtig Du Sie findest (wichtigste Begriffe zuerst!).
Beispiel: Liste von Maxi Mustermann:
• Objekt
• if
• Reset
• Unterschied Array und Liste
• Referenz
Aufgabe 4 (ggf. Hausaufgabe)
Informiere Dich in der Wikipedia über die Datenstruktur "Stapelspeicher" und beantworte folgende Fragen:
a) Wie funktioniert ein Stapelspeicher?
b) Welche Operationen stellt die Datenstruktur zur Verfügung und was bewirken sie?
Informiere Dich in der Wikipedia über die Datenstruktur "Warteschlange (Datenstruktur)" und beantworte folgende Fragen:
c) Wie funktioniert ein Warteschlange?
d) Welche Operationen stellt die Datenstruktur zur Verfügung und was bewirken sie?
19.11.2022
Lieber IF-Q1-Kurs,
Für die letzte Stunde vor den Ferien bereitet ihr bitte Folgendes vor:
Informiere Dich in der Wikipedia über die Datenstruktur "Stapelspeicher" und beantworte folgende Fragen:
a) Wie funktioniert ein Stapelspeicher? b) Welche Operationen stellt die Datenstruktur zur Verfügung und was bewirken sie?
Informiere Dich in der Wikipedia über die Datenstruktur "Warteschlange (Datenstruktur)" und beantworte folgende Fragen:
c) Wie funktioniert ein Warteschlange? d) Welche Operationen stellt die Datenstruktur zur Verfügung und was bewirken sie?
Klausurthemen Grundlagen
• Konzepte Objekt, Klasse, Eigenschaft, Methode verstehen
• einfache Algorithmen (z.B. Primzahltest, Mittelwert oder Spannweite eines Arrays, größtes Element eines Arrays, Sortieren mit Bubble-Sort), selbst schreiben und "auf Papier" ausführen können.
• Zu Programmen bzw. Objektbeziehungen ein Diagramm des Speicherlayouts zeichnen ("Wölkchen") und umgekehrt.
Neue Themen:
• Komplexität von Algorithmen
• Sortierverfahren: "in place" und "stabil"
• Prinzip "Rekursion" verstehen. Z.B. Fibonaccizahlen oder Fakultät selbst schreiben können.
• Idee hinter "rekursivem Array-Reverse" verstehen.
• Mergesort: Verfahren verstehen und kleinere Teile davon selbstständig ergänzen können oder Fehler finden können
• Sowohl beim "rekursivem Array-Reverse" als auch bei "Mergesort" wird intensiv mit Arrays und trickreicher Indexmanipulation gearbeitet. Da sollte man einen Überblick behalten.
• Konzept "verkettete Liste" am Beispiel unserer Klasse StringListe verstehen. Einzelne Methoden (wie z.B. insertAfterCurrent) selbst schreiben können.
Hier die gesamte Klasse, die Mergesort enthält und testet.
import java.util.Arrays;
public class StartklasseSuS {
public static int zahlen[] = new int[8];
public static void main() {
populate(zahlen);
if(zahlen.length < 60) {
System.out.println("Das Array sieht anfangs so aus: "+Arrays.toString(zahlen));
} else {
System.out.println("Das Array hat eine Länge von "+zahlen.length);
}
System.out.println("Ist das array sortiert? "+isSorted(zahlen));
long start = System.currentTimeMillis();
boolean doMergesort = true;
if(doMergesort) {
System.out.println("Es wird nun mit Mergesort sortiert!");
zahlen = mergesort(zahlen);
} else {
System.out.println("Es wird nun mit Bubblesort sortiert!");
zahlen = bubblesort(zahlen);
}
long end = System.currentTimeMillis();
System.out.println("Benoetigte Zeit in ms: "+(end-start));
if(zahlen.length < 60) {
System.out.println("Das Array sieht am Ende so aus: "+Arrays.toString(zahlen));
} else {
System.out.println("Das Array hat eine Länge von "+zahlen.length+" und eine sortierte Version wird daher nicht mehr ausgegeben.");
}
System.out.println("Ist das array sortiert? "+isSorted(zahlen));
int suchElem = 30;
int idx = binSearch(suchElem);
System.out.println("Das Element "+suchElem+" besitzt den Index "+idx);
}
public static boolean isSorted(int[] a) {
boolean result = true;
for(int i = 0; i < a.length-1; i++) {
if(a[i] > a[i+1]) {
result = false;
}
}
return result;
}
public static void populate(int[] z) {
for(int i = 0; i < z.length; i++) {
z[i] = (int) (Math.random()*3000);
}
}
// Gibt den Index der ersten Vorkommens des Elementes e zurück. Bei nicht-gefundenem Element wird -1 zurückgegeben
public static int binSearch(int e) {
int start = 0;
int ende = zahlen.length-1;
int mitte = (ende+start)/2;
while(true) {
if(e == zahlen[mitte]) {
return mitte;
}
if(e < zahlen[mitte]) {
// untere Hälfte benutzen
ende = mitte-1;
mitte = (ende+start)/2;
} else {
// obere Hälfte benutzen
start = mitte+1;
mitte = (ende+start)/2;
}
if(start>ende) {
break;
}
}
return -1;
}
public static int[] bubblesort(int[] a) {
for(int i = 0; i < a.length; i++) {
for(int j = 0; j < a.length-1; j++) {
if(a[j] > a[j+1]) {
int hilf = a[j];
a[j] = a[j+1];
a[j+1] = hilf;
}
}
}
return a;
}
public static int[] mergesort(int[] a) {
int[] b = new int[a.length];
// left begin, left end, right begin, right end
int lb = 0, le = a.length/2 -1, rb = le+1, re = a.length-1;
mergesort(a,b,lb,le,rb,re);
return a;
}
/*
* mergesort sortiert das teilarray von lb bis re, dabei wird array b als
* hilfsspeicher genutzt.
* @param a zu sortierendes Array
* @param b hilfsarray mit gleicher größe wie a
* @param lb "left begin" index
* @param le "left end" index
* @param rb "right begin" index
* @param re "right end" index
*/
public static void mergesort(int[] a, int[] b, int lb, int le, int rb, int re) {
// Diagnosetools
System.out.println("------------------------");
System.out.println("Mergesortaufruf mit lb="+lb+"; le="+le+" und rb="+rb+"; re="+re);
String teilarr1 = arrToString(a,lb,le);
String teilarr2 = arrToString(a,rb,re);
System.out.println("Teil 1: "+teilarr1+" Teil 2: "+teilarr2);
if(lb < le) {
int mitte = (lb+le)/2;
mergesort(a,b,lb,mitte,mitte+1,le);
}
if(rb < re) {
int mitte = (rb+re)/2;
mergesort(a,b,rb,mitte,mitte+1,re);
}
// Diagnosetools
System.out.println("------------------------");
System.out.println("Start der Zusammenführung zweier Teile mit lb="+lb+"; le="+le+" und rb="+rb+"; re="+re);
teilarr1 = arrToString(a,lb,le);
teilarr2 = arrToString(a,rb,re);
System.out.println("Teil 1: "+teilarr1+" Teil 2: "+teilarr2);
// ###################
// ###################
// ###################
// Merge-phase fehlt!
// ###################
// ###################
// ###################
//for(int i = lb; i <= re; i++) { // Dummy-Schleife, die nur provisorisch das Hilfsarray füllt. Hier muss gearbeitet werden!
// b[i] = a[i];
//}
int indexLinks = lb;
int indexRechts = rb;
int indexNeu = lb;
while(( indexLinks <= le ) && (indexRechts <= re)) {
if(a[indexLinks] < a[indexRechts]) {
b[indexNeu] = a[indexLinks];
indexLinks++;
} else {
b[indexNeu] = a[indexRechts];
indexRechts++;
}
indexNeu++;
}
// feststellen, welcher reststapel noch übertragen werden muss
if(indexLinks<=le) { // im linken Stapel sind noch Elemente
for(int i = indexLinks; i <= le ; i++) {
b[indexNeu] = a[indexLinks];
indexNeu++;
indexLinks++;
}
}
if(indexRechts<=re) { // im rechts Stapel sind noch Elemente
for(int i = indexRechts; i <= re ; i++) {
b[indexNeu] = a[indexRechts];
indexNeu++;
indexRechts++;
}
}
// ###################
// ###################
// ###################
// Ende der Merge-phase!
// ###################
// ###################
// ###################
// Rückkopie nach array a:
for(int i = lb; i <= re; i++) {
a[i] = b[i];
}
// Diagnosetools
System.out.println("Nach der Mergephase sieht das Array von lb="+lb+" bis re="+re+" so aus:");
String teilarr = arrToString(a,lb,re);
System.out.println("Zusammengeführter Teil: "+teilarr);
return;
}
// Stringdarstellung eines Teilarrays von index b bis einschließlich index e
public static String arrToString(int[] arr,int b, int e) {
String result = "[ ";
for(int i = b; i <= e; i++) {
result += ""+i+": "+arr[i];
if(i != e) { // noch nicht letzter durchgang
result += " | ";
}
}
result += " ]";
return result;
}
}
24.10.2022
Hausaufgabe und "EVA zu Hause":
Beantworte folgende Fragen:
- was bedeutet "in place" und "stabil" bei Sortierverfahren?
- wie arbeiten BubbleSort und Mergesort (in place? stabil?)
- Verschaffe dir einen Überblick über die Landau-Symbole (Stichwort Komplexität)
Grober Pseudocode für rekursiv implementierten Mergesort (mit angedeutetem Aufruf bei 8 Elementen):
mergesort(array, von 1 , bis 8) {
falls array teilbar
aufruf mergesort(array, 5 bis 8)
aufruf mergesort(array, 1 bis 4)
ansonsten
return
// zusammenführungsphase:
betrachte "obere" Elemente der Teilstapel
if(linkes Element < rechtes Element) {
linkes Element in neues Array einfügen
} else {
linkes Element in neues Array einfügen
}
Sonderfall: linke oder rechte Liste leer:
Rest der rechten oder linken Liste übernehmen
}
Komplexitätsbetrachtungen zum Problem "Spannweite"
public class Haupt {
public static void spannweite() {
int[] arr = {9,2,6,3,77,43};
int minElem = sucheMinElem(arr);
int maxElem = sucheMaxElem(arr);
int ergebnis = maxElem - minElem;
}
public static int sucheMinElem(int[] arr){
int min = arr[0];
for(int i=0; i<arr.length;i++) {
if(arr[i] < min) {
min = arr[i];
}
}
return min;
}
public static int sucheMaxElem(int[] arr){
int max = arr[0];
for(int i=0; i<arr.length;i++) {
if(arr[i] > max) {
max = arr[i];
}
}
return max;
}
}
// Problemgröße n=6
// Hauptprogramm: 4 Schritte
// Erster Methodenaufruf: 20
// Zweiter Methodenaufruf: 20
// Insgesamt: 44 Schritte
//
// Problemgröße n=7
// Hauptprogramm: 4 Schritte
// Erster Methodenaufruf: 23
// Zweiter Methodenaufruf: 23
// Insgesamt: 50 Schritte
//
// Problemgröße n=8
// Hauptprogramm: 4 Schritte
// Erster Methodenaufruf: 26
// Zweiter Methodenaufruf: 26
// Insgesamt: 56 Schritte
//
// Problemgröße n=9
// Insgesamt: 62 Schritte
//
// Problemgröße n:
// Insgesamt: 4 + 3·n+2 + 3·n+2
// = 4+2(3n+2)
// = 4+6n+4
// = 6n+8
//
// Das Spannweitenproblem liegt also in der
// Komplexitätsklasse n.
// (Man spricht auch von "lineare Komplexität")
27.09.2022
Link zu den Security-Rätseln: https://0xf.at/
Gebt eure Ergebnisse über folgendes Rückmeldeformular ein:
20.09.2022
Klausurthemen:
• Konzepte Objekt, Klasse, Eigenschaft, Methode verstehen
• einfache Algorithmen (z.B. Primzahltest, Mittelwert oder Spannweite eines Arrays, größtes Element eines Arrays, Sortieren mit Bubble-Sort), selbst schreiben und "auf Papier" ausführen können.
• Zu Programmen bzw. Objektbeziehungen ein Diagramm des Speicherlayouts zeichnen ("Wölkchen") und umgekehrt. (siehe Aufgabe unten)
Decke jeweils eines der beiden verdeckten Elemente auf und generiere daraus das andere:
Ereuge ein Speicherdiagramm für das Ende der Main-Methode:
public class Auto {
int baujahr;
String kennzeichen;
public static void main() {
Auto[] arr = new Auto[5];
Auto z = new Auto(2003,"N-AB 333");
arr[1] = new Auto(2002,"D-FM 222");
arr[2] = new Auto(2006,"M-AT 666");
arr[3] = z;
arr[4] = z;
// Zeichne die bis hier aufgebaute
// Datenstruktur in einem Diagramm
}
}
Schreibe ein Programm, welches folgendes Speicherdiagramm erzeugen könnte:
Aufgabe: Versuche vorherzusagen, welche Ausgabe die folgende (ziemlich sinnlose) Funktion erzeugt. Erst das Ergebnis notieren, dann ausführen! Sage das Ergebnis auch für andere Wörter als "hey" voraus!
private void increaseDBSize() {
Device[] oldDevices = this.devices;
this.devices = new Device[oldDevices.length + 10];
for(int i = 0; i < oldDevices.length; i++) {
this.devices[i] = oldDevices[i];
}
}
public String getDeviceList() {
String result = "";
for(int i = 0; i < numDevices; i++) {
result += devices[i].devName+" - "+devices[i].type+" \n";
}
return result;
}
public String getAllDevicesFromLocation(String loc) {
String result = "";
for(int i = 0; i < numDevices; i++) {
if(devices[i].loc.equals(loc)) {
result += devices[i].devName+" - "+devices[i].type+" \n";
}
}
return result;
}
public int numberOfDevicesInRoom(String loc) {
int result = 0;
for(int i = 0; i < numDevices; i++) {
if(devices[i].loc.equals(loc)) {
result++;
}
}
return result;
}
}
29.08.2022
Miniprojekt für die nächsten Stunden
public class Haupt {
public static void main(String[] args) {
gbgIT = new InventarTool();
// Gerät SerienNr Raum Art Anschaffungsjahr
// device sn location type year
gbgIT.add("Dell Optiplex 7010", "AO802310","E35" , "DesktopPc" , 2014);
gbgIT.add("Dell Optiplex ABCD", "XY620382","R135", "DesktopPc" , 2022);
gbgIT.add("Terra 2220W" , "TNsi922" ,"E35" , "19'' Monitor", 2015);
System.out.println("Geräte aus R35: \n" + gbgIT.getAllDevicesFromLocation("E35"));
System.out.println("Geräteliste nach Raum: \n" + gbgIT.numberOfDevicesInRoom("E35"));
gbgIT.sortByRoom();
System.out.println("Geräteliste nach Raum: \n" + gbgIT.getDeviceList() );
}
}
15.08.2022
• Begrüßung, Leistungsbewertung, Themen im Schuljahr
• Welche Rechner und welche Programme habt ihr benutzt?
• Wer programmiert hobbymäßig?
Programmgerüst zum 15.08.2022
Wir kümmern uns zunächst um ein paar Informatikprobleme, die immer wieder auftauchen. Füge den folgenden Quelltext in ein neues Projekt ein und schreibe die angedeuteten Methoden.
public class Haupt {
public static void main() {
int[] a = {10,20,30,40,50,60,70,80};
zufallsbelegung(a);
printArray(a);
// Linksrotation des Arrays:
// alle Elemente werden eine Position nach links geschoben.
// Das Element beim Index 0 wird an die letzte Position gesetzt
// Beispiel: Array {2,4,9,5,6} -> {4,9,5,6,2}
a = rotiereLinks(a);
printArray(a);
// Entscheidung, ob ein Element existiert
// Beispiel: im Array {2,4,9,5,6} liefert der Aufruf hatElement(a,4) das Ergebnis "true"
// System.out.println("Array enthaelt Element 4: "+hatElement(a,4));
// Berechnung des Mittelwerts des Array:
// Der Mittelwert eines Arrays kann man folgendermaßen berechnen:
// (Summe aller Elemente) ÷ (Anzahl der Elemente)
// Beispiel: Array {2,4,9,5,6} hat den Mittelwert 5,2
// System.out.println("Mittelwert "+mittelwert(a));
// Feld umkehren
// Beispiel: Array {2,4,9,5,6} ist umgekehrt {6,5,9,4,2}
// a = arrayUmkehren(a);
// printArray(a);
// Berechnung der Spannweite des Arrays:
// Die Spannweite ist die Differenz zwischen dem größten und kleinsten Element
// Beispiel: Array {2,4,9,5,6} hat die Spannweite 7
// System.out.println("Spannweite "+spannweite(a));
// Enthält Mehrfachwerte
// Beispiel: Array {2,4,9,5,6} enthält keine mehrfachen Elemente
// Beispiel: Array {2,6,9,5,6} enthält Elemente mehrfach! (in diesem Fall die 6)
// System.out.println("Array enthaelt Mehrfachwerte: "+hatMehrfachwerte(a));
