Informatik-Abitur-Wiederholung-Lösungen: Unterschied zwischen den Versionen
(2 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
Zeile 15: | Zeile 15: | ||
# Implementiere die Methode <code>public void sortiere()</code>. | # Implementiere die Methode <code>public void sortiere()</code>. | ||
<code> | <code> | ||
'''public int anzahl(){''' | '''public int anzahl(){''' | ||
return namen.length; | return namen.length; | ||
} | } | ||
</code> | </code> | ||
<code> | <code> | ||
'''public boolean enthaelt(String pName){''' | '''public boolean enthaelt(String pName){''' | ||
for(int i=0; i<namen.length; i++){ | for(int i=0; i<namen.length; i++){ | ||
Zeile 32: | Zeile 32: | ||
return false; | return false; | ||
} | } | ||
</code> | </code> | ||
''Das Sortieren macht man am besten mit Bubblesort - das geht für Arrays am einfachsten:'' | ''Das Sortieren macht man am besten mit Bubblesort - das geht für Arrays am einfachsten:'' | ||
<code> | <code> | ||
'''public void sortiere(){''' | '''public void sortiere(){''' | ||
for(int i=0; i<namen.length; i++){ | for(int i=0; i<namen.length; i++){ | ||
Zeile 59: | Zeile 59: | ||
namen[b] = name_a; | namen[b] = name_a; | ||
} | } | ||
</code> | </code> | ||
==Zweidimensionale Arrays== | ==Zweidimensionale Arrays== | ||
Zeile 65: | Zeile 65: | ||
a) Implementiere die Methode <code>public int[][] dasEinmalEins()</code>. | a) Implementiere die Methode <code>public int[][] dasEinmalEins()</code>. | ||
<code> | <code> | ||
'''public int[][] dasEinmalEins(){''' | '''public int[][] dasEinmalEins(){''' | ||
int[][] ergebnis = new int[10]10]; | int[][] ergebnis = new int[10]10]; | ||
for(int i=0; i<10; i++){ | for(int i=0; i<10; i++){ | ||
for(int j=0; j<10; j++){ | for(int j=0; j<10; j++){ | ||
ergebnis[i][j] | ergebnis[i][j] = i*j; | ||
} | } | ||
} | } | ||
return ergebnis; | |||
} | } | ||
</code> | </code> | ||
b) Implementiere die Methode <code>public int summe(int[][] tabelle)</code> | b) Implementiere die Methode <code>public int summe(int[][] tabelle)</code> | ||
<code> | <code> | ||
'''public int summe(int[][] tabelle){''' | '''public int summe(int[][] tabelle){''' | ||
int ergebnis = 0; | int ergebnis = 0; | ||
Zeile 88: | Zeile 89: | ||
return ergebnis; | return ergebnis; | ||
} | } | ||
</code> | </code> | ||
===Aufgabe 2=== | ===Aufgabe 2=== | ||
<code> | <code> | ||
'''private List<Container> obersteContainerRunterNehmen()''' | '''private List<Container> obersteContainerRunterNehmen()''' | ||
{ | { | ||
Zeile 109: | Zeile 110: | ||
} | } | ||
} | } | ||
</code> | </code> | ||
=Vererbung= | =Vererbung= | ||
Zeile 120: | Zeile 121: | ||
'''Implementiere die Klasse Fachbuch.''' | '''Implementiere die Klasse Fachbuch.''' | ||
<code> | <code> | ||
'''public class Fachbuch <u>extends Buch</u>'''{ | '''public class Fachbuch <u>extends Buch</u>'''{ | ||
private String kategorie; | private String kategorie; | ||
Zeile 144: | Zeile 145: | ||
} | } | ||
} | } | ||
</code> | </code> | ||
'''Erläuterungen:''' | '''Erläuterungen:''' | ||
Zeile 159: | Zeile 160: | ||
Das kann man an folgendem Beispiel sehen: | Das kann man an folgendem Beispiel sehen: | ||
<code> | <code> | ||
List<Buch> buecher = new List<Buch>(); | List<Buch> buecher = new List<Buch>(); | ||
buecher.append(new Buch("The Hobbit", "Tolkien"); | buecher.append(new Buch("The Hobbit", "Tolkien"); | ||
Zeile 167: | Zeile 168: | ||
System.out.println(b.info()); | System.out.println(b.info()); | ||
} | } | ||
</code> | </code> | ||
An die Konsole wird dadurch folgendes ausgegeben: | An die Konsole wird dadurch folgendes ausgegeben: | ||
<code> | <code> | ||
Autor: Tolkien; Titel: The Hobbit | Autor: Tolkien; Titel: The Hobbit | ||
Autor: Lambacher; Titel: Differentialgleichungen; '''Kategorie: Mathematik''' | Autor: Lambacher; Titel: Differentialgleichungen; '''Kategorie: Mathematik''' | ||
</code> | </code> | ||
Zeile 189: | Zeile 190: | ||
#<code>PriorityQueue</code> hat ein Objekt vom Typ <code>Queue</code> | #<code>PriorityQueue</code> hat ein Objekt vom Typ <code>Queue</code> | ||
<code>Queue</code> bietet nicht ausreichend Funktionalität, denn man muss ein neues Element <u>gemäß seiner Priorität</u> einsortieren können. Das ist bei <code>Queue</code> sehr mühsam. | <code>Queue</code> bietet nicht ausreichend Funktionalität, denn man muss ein neues Element <u>gemäß seiner Priorität</u> einsortieren können. Das ist bei <code>Queue</code> sehr mühsam. | ||
''<code>PriorityQueue</code> erbt von <code>List</code> '' ist nicht möglich, denn <u>es gibt Methoden der Klasse <code>List</code>, die die Struktur des <code>PriorityQueue</code> zerstören würden!</u> Diese Methoden würde <code>PriorityQueue</code> erben.<br/> | ''<code>PriorityQueue</code> erbt von <code>List</code> '' ist nicht möglich, denn <u>es gibt Methoden der Klasse <code>List</code>, die die Struktur des <code>PriorityQueue</code> zerstören würden!</u> Diese Methoden würde <code>PriorityQueue</code> erben.<br/> | ||
Zeile 253: | Zeile 254: | ||
# <code>public void einfuegen(Buch pBuch)</code>: Fügt <code>pBuch</code> an der richtigen Stelle in die Bibliothek ein. | # <code>public void einfuegen(Buch pBuch)</code>: Fügt <code>pBuch</code> an der richtigen Stelle in die Bibliothek ein. | ||
<code> | <code> | ||
public class Bibliothek{ | public class Bibliothek{ | ||
Zeile 285: | Zeile 286: | ||
} | } | ||
} | } | ||
</code> | </code> | ||
==eine Methode erläutern== | ==eine Methode erläutern== | ||
Zeile 422: | Zeile 423: | ||
''Bei diesem Problem markiert man die Knoten besser nicht, denn es könnte sein, dass man mit einem späteren Nachbarn eine kürzere Strecke zu einem Knoten findet!''<br/> | ''Bei diesem Problem markiert man die Knoten besser nicht, denn es könnte sein, dass man mit einem späteren Nachbarn eine kürzere Strecke zu einem Knoten findet!''<br/> | ||
''Der klassische Tiefendurchlauf wäre inklusive der durchgestrichenen Zeilen.'' | ''Der klassische Tiefendurchlauf wäre inklusive der durchgestrichenen Zeilen.'' | ||
<code> | <code> | ||
'''public List<Vertex>findeKnoten(Vertex pStart, int pAnzahl){''' | '''public List<Vertex>findeKnoten(Vertex pStart, int pAnzahl){''' | ||
List<Vertex> ergebnis = new List<Vertex>(); | List<Vertex> ergebnis = new List<Vertex>(); | ||
Zeile 442: | Zeile 443: | ||
} | } | ||
return ergebnis; | return ergebnis; | ||
</code> | </code> | ||
==Breitendurchlauf== | ==Breitendurchlauf== | ||
Zeile 511: | Zeile 512: | ||
<code> | <code> | ||
'''//GossipServer erbt von Server!''' | '''//GossipServer erbt von Server!''' | ||
<b>public class GossipServer extends Server </b> | <b>public class GossipServer extends Server </b> | ||
Zeile 582: | Zeile 583: | ||
} | } | ||
} | } | ||
</code> | </code> | ||
=Backtracking= | =Backtracking= | ||
Zeile 599: | Zeile 600: | ||
Der Algorithmus kann so funktionieren: | Der Algorithmus kann so funktionieren: | ||
<code> | <code> | ||
rucksackBacktracking(pStufe) | rucksackBacktracking(pStufe) | ||
wenn man eine bessere Lösung gefunden hat: | wenn man eine bessere Lösung gefunden hat: | ||
Zeile 610: | Zeile 611: | ||
rufe rucksackBacktracking(pStufe+1) auf. | rufe rucksackBacktracking(pStufe+1) auf. | ||
''Jetzt ist nichts mehr rückgängig zu machen, weil man das Gewicht ja schon rausgenommen hat.'' | ''Jetzt ist nichts mehr rückgängig zu machen, weil man das Gewicht ja schon rausgenommen hat.'' | ||
</code> | </code> | ||
=Kryptographie= | =Kryptographie= | ||
Zeile 641: | Zeile 642: | ||
D.h. die Methodenköpfe können so aussehen: | D.h. die Methodenköpfe können so aussehen: | ||
<code> | <code> | ||
public int verschluessele(int N, int M) | public int verschluessele(int N, int M) | ||
public int entschluessele(int p, int q, int C) | public int entschluessele(int p, int q, int C) | ||
</code> | </code> | ||
''(In der Praxis nimmt man nicht <code>int</code>, weil der Zahlenbereich von <code>int</code> bei Weitem nicht ausreicht!<br/>Stattdessen nimmt man Objekte der Klasse <code>BigInteger</code> - die können beliebig lange ganze Zahlen speichern.)'' | ''(In der Praxis nimmt man nicht <code>int</code>, weil der Zahlenbereich von <code>int</code> bei Weitem nicht ausreicht!<br/>Stattdessen nimmt man Objekte der Klasse <code>BigInteger</code> - die können beliebig lange ganze Zahlen speichern.)'' |
Aktuelle Version vom 23. Januar 2022, 18:03 Uhr
Auf dieser Seite finden sich die Lösungen für die Aufgaben der folgenden Seite:
Informatik-Abitur-Wiederholung
Arrays
Standardmethoden für einfache Arrays
- Implementiere die Methode
public int anzahl()
. - Implementiere die Methode
public boolean enthaelt(String pName)
. - Implementiere die Methode
public void sortiere()
.
public int anzahl(){
return namen.length;
}
public boolean enthaelt(String pName){
for(int i=0; i<namen.length; i++){
String derName = namen[i];
if(derName.equals(pName)){
return true;
}
}
return false;
}
Das Sortieren macht man am besten mit Bubblesort - das geht für Arrays am einfachsten:
public void sortiere(){
for(int i=0; i<namen.length; i++){
durchlauf();
}
}
public void durchlauf(){
for(int i=0; i<namen.length-1; i++){
String name = namen[i];
String naechsterName = namen[i+1];
if(name.compareTo(naechsterName) > 0){
tausche(i,i+1);
}
}
}
public void tausche(int a, int b){
String name_a = namen[a];
String name_b = namen[b];
namen[a] = name_b;
namen[b] = name_a;
}
Zweidimensionale Arrays
Aufgabe 1
a) Implementiere die Methode public int[][] dasEinmalEins()
.
public int[][] dasEinmalEins(){
int[][] ergebnis = new int[10]10];
for(int i=0; i<10; i++){
for(int j=0; j<10; j++){
ergebnis[i][j] = i*j;
}
}
return ergebnis;
}
b) Implementiere die Methode public int summe(int[][] tabelle)
public int summe(int[][] tabelle){
int ergebnis = 0;
for(int i=0; i<tabelle.length; i++){
for(int j=0; j<tabelle[i].length; j++){
ergebnis += tabelle[i][j];
}
}
return ergebnis;
}
Aufgabe 2
private List<Container> obersteContainerRunterNehmen()
{
List<Container> ergebnis = new List<Container>();
for(int i=0; i < beladung.length; i++){
for(int j=0; j < beladung[i].length; j++)
{
Stack<Container> aktuellerStapel = beladung[i][j];
if( ! aktuellerStapel.isEmpty() )
{
Container oberster = aktuellerStapel.top();
ergebnis.append(oberster);
aktuellerStapel.pop();
}
}
}
}
Vererbung
gibt es in der Klasse Fachbuch die Methode gibTitel() ? Wenn ja: warum? Wenn nein: warum nicht?
Ja, es gibt diese Methode; Fachbuch erbt die Methode von Buch, da die Methode in der Klasse Buch public ist.
Implementiere die Klasse Fachbuch.
public class Fachbuch extends Buch{
private String kategorie;
public Fachbuch(String pAutor, String pTitel, String pKategorie){
// den Konstruktor von Buch aufrufen!
super(pAutor, pTitel);
kategorie = pKategorie;
}
public String gibKategorie(){
return kategorie;
}
/**
* info() ist eine polymorphe Methode
*/
public String info(){
// erst mal die info der Klasse Buch abfragen!
String ergebnis = super.info();
ergebnis += "; Kategorie: "+kategorie;
return ergebnis;
}
}
Erläuterungen:
Fachbuch
ist-einBuch
.- Das Schlüsselwort für Vererbung ist
extends
; damit wird eine Klasse zur Subklasse. - Im Konstruktor der Subklassen muss zuerst mit dem Schlüsselwort
super(...)
der Konstruktor der Superklasse aufgerufen werden.- D.h. zum Beispiel für
Fachbuch
: Um ein Objekt vom TypFachbuch
zu erzeugen, muss erst der Konstruktor vonBuch
aufgerufen werden; das ist auch inhaltlich wichtig, denn nur so könnentitel
undautor
richtig eingetragen werden.
- D.h. zum Beispiel für
- Mit
super.info()
greifen die Subklassen auf die Methodeinfo()
der Superklasse zu. - Dass die Methode
info()
in der Superklasse und in den Subklassen vorkommt, liegt an der Polymorphie.
Erkläre am Beispiel des Klassendiagramms den Begriff Polymorphie.
Die Methode info() ist eine polymorphe Methode, denn sie ist sowohl in der Superklasse Buch als auch in deren Subklassen enthalten. Java ruft dann immer die "richtige" Methode auf - je nachdem, ob es sich bei dem Objekt um ein Buch oder z.B. um ein Fachbuch handelt.
Das kann man an folgendem Beispiel sehen:
List<Buch> buecher = new List<Buch>();
buecher.append(new Buch("The Hobbit", "Tolkien");
buecher.append(new Fachbuch("Differentialgleichungen", "Lambacher", "Mathematik"));
for(buecher.toFirst(); buecher.hasAccess(); buecher.next()){
Buch b = buecher.getContent();
System.out.println(b.info());
}
An die Konsole wird dadurch folgendes ausgegeben:
Autor: Tolkien; Titel: The Hobbit
Autor: Lambacher; Titel: Differentialgleichungen; Kategorie: Mathematik
Modellierung
PriorityQueue
Entscheide dich für eine der folgenden Möglichkeiten und begründe:
PriorityQueue
erbt vonList
PriorityQueue
erbt vonQueue
PriorityQueue
hat ein Objekt vom TypList
PriorityQueue
hat ein Objekt vom TypQueue
Queue
bietet nicht ausreichend Funktionalität, denn man muss ein neues Element gemäß seiner Priorität einsortieren können. Das ist beiQueue
sehr mühsam.
PriorityQueue
erbt von List
ist nicht möglich, denn es gibt Methoden der Klasse List
, die die Struktur des PriorityQueue
zerstören würden! Diese Methoden würde PriorityQueue
erben.
Ein Beispiel dafür ist die Methode append
: Damit könnte man ein Objekt - unabhängig von seiner Priorität! - einfach hinten anhängen.
Monopoly
- Entscheide dich begründet für eine Datenstruktur für die 40 Felder des Monopoly-Spiels.
- Zeichne ein Klassendiagramm mit den Klassen
MonopolyFeld
,Strasse
undBahnhof
und einer weiteren sinnvollen Klasse, die du selber einführst. Gib für die KlassenStrasse
,Bahnhof
und die von dir eingeführte Klasse auch die Attribute und Methoden an.
//TODO
Medienplayer
Entwerfen Sie ein Implementationsdiagramm. Begründen Sie Ihre Entscheidungen. Begründen Sie auch, ob Sie sich für Stack
, Queue
oder List
entscheiden.
Analyse
Bei der Analyse schreibt man formelhaft Begründungen für die Beziehungen der Klassen:
- Aus dem Szenario ergeben sich die Klassen
Medienplayer
,Wiedergabeliste
undTitel
. Medienplayer
ist die "oberste" Klasse und damit der Ausgangspunkt der Modellierung.Medienplayer
hat eine Liste mit Inhaltsobjekten vom TypWiedergabeliste
.List
eignet sich besser alsQueue
oderStack
, weil damit das Auswählen der Wiedergabeliste nach dem Titel einfacher realisiert werden kann.Medienplayer
hat ein AttributaktiveWiedergabeliste
vom Typ <Wiedergabeliste, in dem die jeweils aktive Wiedergabeliste gespeichert wird.WiedergabeListe
kann nicht vonList
erben, weil sie sonst die Methodeconcat(List pList)
zur Verfügung hätte, die im Szenario nicht vorgesehen ist.- Stattdessen:
WiedergabeListe
hat eineList
mit Inhaltsobjekten vom TypTitel
.Queue
oderStack
eignen sich nicht, weil man an beliebigen Stellen einfügen können muss.
Implementationsdiagramm: Beziehung der Klassen
Zuerst werden nur die Beziehungen zwischen den Klassen in einem Diagramm dargestellt.
Attribute und Methoden werden noch nicht dargestellt. Das erleichtert WESENTLICH die Modellierung und das Zeichnen!
Implementationsdiagramm: Die einzelnen Klassen
Jetzt werden die einzelnen Klassen mit Attributen und Methoden dargestellt.
lineare Datenstrukturen
eine lineare Datenstruktur implementieren
- Erläutere anhand des Objektdiagramms eine Implementationsstrategie für die Methode
public void enqueue(ContentType pContent)
.
Queue verfügt über zwei Attribute vom Typ Node, eins für den Anfang des Queues, eins für das Ende.
In jedem Node ist als value ein Objekt gespeichert. Jeder Node verweist wieder auf den nächsten Node.
Die Methode public void enqueue(ContentType pContent)
kann jetzt so realisiert werden:
- Einen neuen Node erzeugen:
newNode
- Wenn der Queue leer ist, dann lässt man den
head
undtail
aufnewNode
zeigen. - Vom letzten Node den Verweis
next
aufnewNode
setzen. - Den Verweis von
tail
aufnewNode
setzen.
- Implementiere die folgenden Methoden:
siehe Queue_ab_Abi_2017#Implementierung - Die Klasse
Node
ist dabei transparent. Erläutere, was das bedeutet.
Wenn man Queues verwendet, muss man über die Klasse Node gar nichts wissen - man weiß ggf. noch nicht einmal, dass es sie gibt. Als Nutzer der Klasse Queue schaut man gewissermaßen durch die Klasse Node hindurch direkt auf die Objekte, die in den Nodes gespeichert sind.
eine Liste durchlaufen
Die Klasse Bibliothek
hat ein Attribut buecherListe
vom Typ List
. In buecherListe
sind die Bücher gespeichert und zwar alphabetisch nach Titel sortiert.
Implementiere die folgenden Methoden. Verwende, wenn möglich, eine for-Schleife.
public Bibliothek()
: Der Konstruktor erzeugt eine Bibliothek; diebuecherListe
ist zu Anfang leer. Das hat nichts mit Listendurchlauf zu tun, ist aber trotzdem wichtig...public boolean enthaelt(String pTitel)
public void einfuegen(Buch pBuch)
: FügtpBuch
an der richtigen Stelle in die Bibliothek ein.
public class Bibliothek{
private List<Buch> buecherListe;
public Bibliothek(){
buecherListe = new List<Buch>();
}
public boolean enthaelt(String pTitel){
boolean ergebnis = false;
for(buecherListe.toFirst(); buecherListe.hasAccess(); buecherListe.next()){
Buch b = buecherListe.getContent();
if(b.getTitel().equals(pTitel)){
ergebnis = true;
}
}
return ergebnis;
}
public void einfuegen(Buch pBuch){
for(buecherListe.toFirst(); buecherListe.hasAccess(); buecherListe.next()){
Buch b = buecherListe.getContent();
if(pBuch.getTitel().compareTo(b.getTitel() < 0){
buecherListe.insert(pBuch);
return;
}
}
// die Liste wurde komplett durchlaufen und das Buch nirgendwo eingefuegt!
buecherListe.append(pBuch);
}
}
eine Methode erläutern
Erläutere die Methode einfuegen
(s.o.) unter Verwendung der wesentlichen Fachbegriffe.
Die Fachbegriffe sind im folgenden unterstrichen.
Die Methode einfuegen
hat einen Parameter vom Typ Buch
und gibt nichts zurück.
Zuerst wird die buecherListe
mit einer for
-Schleife komplett durchlaufen.
Dabei wird das jeweils aktuelle Buch in der lokalen Variable b
gespeichert und sein Titel mit dem Titel von pBuch
verglichen.
Wenn der Titel von pBuch
im Alphabet VOR dem Titel von b
ist, dann wird pBuch
VOR b
in die buecherListe
eingefügt und die Methode verlassen
Nach dem Ende der Schleife wird pBuch
hinten an buecherListe
angehängt. Das ist richtig so, denn offensichtlich konnte pBuch
in der ganzen Schleife nie eingefügt werden, d.h. pBuch
ist das alphabetisch letzte Buch.
Quicksort
- Erläutere das Quicksort-Verfahren anhand der Zeichenkette "S-C-H-U-L-E".
- Implementiere die Methode
public List quicksort(List pBuchstaben)
. - Welchen Vorteil hat Quicksort gegenüber einfachen Sortierverfahren wie Selectionsort oder Bubblesort?
//TODO
Datenbanken
Entity-Relationship-Modellierung
Eine Firma möchte die Ausleihe der Dienstwagen mit einer Datenbank verwalten. Für Mitarbeiter wird Name, Vorname und Telefon gespeichert. Von den Dienstwagen das Kennzeichen und die Anzahl der Sitzplätze. Immer wenn ein Mitarbeiter einen Dienstwagen benötigt, werden das Startdatum und das Enddatum für die Ausleihe gespeichert.
Zeichne ein ER-Modell für die folgenden zwei Fälle. Begründe jeweils die Kardinalitäten.
Beachte: In der Datenbank sollen auch Reservierungen für die Zukunft gespeichert werden.
//TODO
Relationales Datenmodell
Die Lösung findet sich hier:
Relationales_Datenmodell
Das endgültige Modell sich hier: Relationales_Datenmodell#n:m-Beziehungen_übertragen
Was wäre die Konsequenz, wenn die Tabelle belegt
als Primärschlüssel ein Attribut id
hätte?
Dann könnte ein Schüler einen Kurs mehrfach belegen. Das ist aber nicht gewünscht.
Normalisierung
Die Lösung hierzu (mit ausführlichen Erklärungen) findet sich hier:
Normalisierung
SQL
- Eine Liste aller Unterrichtsfächer, in der steht, wieviele Stunden sie jeweils unterrichtet werden; die Unterrichtsfächer mit vielen Stunden sollen oben stehen.
SELECT u.fach AS fach, SUM(u.stunden) AS stunden
FROM unterricht u
GROUP BY u.fach
ORDER BY stunden DESC - Eine Liste der Räume, in denen die 8B Unterricht hat.
SELECT r.nummer
FROM raum r
JOIN unterricht u
ON u.raum_id = r.id
JOIN klasse k
ON k.id = u.klasse_id
WHERE k.name = '8B'
Es geht auch ein kartesisches Produkt aus 3 Tabellen mit zwei Abgleichen zwischen den Tabellen. - Eine Liste der Klassen mit der Anzahl der Schüler; sortiert nach der Anzahl der Schüler.
SELECT k.name, COUNT(s.id) AS anzahl
FROM klasse k, schueler s
WHERE k.id = s.klasse_id
GROUP BY k.id
ORDER BY anzahl DESC - "Lehrerraumprinzip": Eine Liste der Lehrer, in der für jeden Lehrer vermerkt ist, in welchem Raum er am wieviele Stunden unterrichtet.
Hinweis: Man braucht ein GROUP BY für zwei Spalten: GROUP BY l.id, r.idSELECT l.name, r.nummer, SUM(u.stunden) AS anzahl
FROM lehrer l JOIN unterricht u
ON l.id = u.lehrer_id
JOIN raum r
ON r.id = u.raum_id
GROUP BY l.id, r.id
ORDER BY l.name, r.nummer - Eine Liste aller Lehrer und Schüler.
SELECT l.name
FROM lehrer l
UNION
SELECT s.name
FROM schueler s - In welchen Räumen findet nie Sport statt?
SELECT r.nummer
FROM raum r
WHERE r.id NOT IN
( SELECT u.raum_id
FROM unterricht u
WHERE u.fach = 'Sport'
) - Welche Schüler sind Klassenkameraden von Anne Ebert?
SELECT s.name
FROM schueler s
WHERE s.klasse_id IN
( SELECT s2.klasse_id
FROM schueler s2
WHERE s2.name = 'Ebert' AND s2.vorname = 'Anne'
) - Eine Liste ALLER Schüler, aus der hervorgeht, in welcher Klasse sie jeweils sind. Auch Schüler ohne Klasse (z.B. Wiesenhoff) sollen aufgeführt werden.
SELECT s.name AS schueler, k.name AS klasse
FROM schueler s LEFT JOIN klasse k
ON s.klasse_id = k.id - Eine Liste der Schüler, die keine Klasse haben.
SELECT s.name
FROM schueler s LEFT JOIN klasse k
ON s.klasse_id = k.id
WHERE k.id IS NULL - Eine Liste aller Klassen, in der angezeigt wird, wieviel Prozent Sport sie haben.
Danke an Luca und Jan!
Man braucht hier zwei innere Abfragen: eine für den Sportunterricht und einen für allen Unterricht.SELECT k.name, (B.sport/A.gesamt)*100
FROM
( SELECT u.klasse_id as id, SUM(u.stunden) as gesamt
FROM unterricht u
GROUP BY u.klasse_id
) AS A ,
( SELECT u.klasse_id as id, SUM(u.stunden) as sport
FROM unterricht u
WHERE u.fach = 'Sport'
GROUP BY u.klasse_id
) AS B , klasse k
WHERE A.id = B.id AND k.id = A.id
Automaten
Deterministische / Nicht-Deterministische Endliche Automaten
- Ein deterministischer endlicher Automat erhält Zahlen als Eingabe. Er soll überprüfen, ob die Zahl durch drei teilbar ist. Dafür überprüft er die Quersumme der Zahl: Ist die Quersumme durch drei teilbar, dann ist auch die Zahl selber durch drei teilbar. Zeichne den Übergangsgraph für diesen deterministischen endlichen Automaten.
- Erläutere den Unterschied zwischen einem nicht-deterministischen endlichen Automaten und einem deterministischen endlichen Automaten.
- Gesucht wird ein endlicher Automat, der erkennt, ob eine eingegebene Zeichenkette das Wort LOL enthält.
- Zeichne dafür den Übergangsgraph eines Nicht deterministischen endlichen Automaten.
- Erläutere, warum die zugrunde liegende Sprache regulär ist.
//TODO
Reguläre Grammatik
- Welche Bedingungen muss eine Grammatik erfüllen, um regulär zu sein?
- Das Alphabet der folgenden Sprachen besteht nur aus den Buchstaben a und b. Welche der folgenden Sprachen ist regulär? Begründe. Gib ggf. eine reguläre Grammatik an.
- Akzeptiert wird jedes Wort beliebiger Länge, das mindestens 2 a und 2 b enthält.
- Akzeptiert wird jedes Wort beliebiger Länge, das mehr a als b enthält.
- Akzeptiert werden nur Wörter, die höchstens 6 Zeichen haben.
- Akzeptiert werden nur Wörter, die am Anfang gleich viele a haben wie am Ende.
//TODO
Binärbäume
Preorder, Inorder und Levelorder
Gegeben ist der Ahnenbaum von Justus und seinen Vorfahren.
- Gib die Elemente des Baumes in Preorder, Inorder und Levelorder an.
- Inwiefern ergibt Levelorder eine sinnvolle Reihenfolge?
- Für welche Bäume ergibt Inorder eine sinnvolle Anordnung?
- Wie kann man den Inorder-Durchlauf ganz einfach ablesen?
//TODO
rekursive Methoden
- Erläutere den Standard-Aufbau rekursiver Methoden mithilfe der Fachbegriffe rekursiver Aufruf, Abbruchbedingung, Sachlogik.
- Implementiere die Methode
public List preorder(BinaryTree pTree)
.
//TODO
Pfaddurchlauf
- Benenne für den Ahnenbaum (s. rechts) eine Methode, die sich mithilfe eines Pfaddurchlaufes realisieren lässt und implementiere sie.
- Erläutere die Implementationsstrategie beim Pfaddurchlauf.
//TODO
Levelorder
- Implementiere die Methode
public List levelorder(BinaryTree pTree)
für den Ahnenbaum. - Erläutere die Strategie von Levelorder anhand der Implementierung.
siehe Binärbaum#Levelorder-Traversierung_(nur_LK)
Binäre Suchbäume
- Erläutere die Struktur eines Binären Suchbaumes.
- Welche Rolle spielt Inorder in einem binären Suchbaum?
//TODO
Implementierung von binären Suchbäumen
Es soll eine Klasse Bibliothek
realisiert werden, in der die Bücher in einem Attribut buecherBaum
vom Typ BinarySearchTree
gespeichert werden.
- Zeichne ein Implementationsdiagramm mit den Klassen
Bibliothek
,Buch
und der SchnittstelleItem
- Welche Funktion erfüllt die Schnittstelle
Item
in diesem Zusammenhang? - Implementiere die Klasse
Buch
. - Implementiere für die Klasse
Bibliothek
die folgenden Methoden:public void einfuegen(Buch pBuch)
public Buch finde(String pTitel)
: Findet ein Buch nach dem Titel; gibt das Buch bzw. null zurück.
//TODO
Graphen
Tiefendurchlauf
Gesucht ist eine Liste aller Knoten, die sich vom Knoten startKnoten
aus mit 3 Kanten erreichen lassen.
Bei diesem Problem markiert man die Knoten besser nicht, denn es könnte sein, dass man mit einem späteren Nachbarn eine kürzere Strecke zu einem Knoten findet!
Der klassische Tiefendurchlauf wäre inklusive der durchgestrichenen Zeilen.
public List<Vertex>findeKnoten(Vertex pStart, int pAnzahl){
List<Vertex> ergebnis = new List<Vertex>();
if(pStart.isMarked() == true){
return ergebnis;
}
pStart.setMark(true);
ergebnis.append(pStart);
// die folgende Abbruchbedingung prueft,
// ob man ueberhaupt noch eine Kante zur Verfuegung hat.
if(pAnzahl == 0){
return ergebnis;
}
List<Vertex> nachbarn = graph.getNeighbours(pStart);
for(nachbarn.toFirst(); nachbarn.hasAccess(); nachbarn.next()){
Vertex n = nachbarn.getContent();
List<Vertex> ergebnisN = findeKnoten(n, pAnzahl - 1);
ergebnis.concat(ergebnisN);
}
return ergebnis;
Breitendurchlauf
//TODO
Dijkstra-Algorithmus
Ermittle mithilfe des Dijkstra-Algorithmus den kürzesten Weg von Kassel nach Bremen.
- Die rote Liste' ist fett geschrieben und ist von oben nach unten zu lesen.
- Die gelbe Liste ist jeweils von links nach rechts zu lesen.
- Veränderungen in der gelben Liste sind unterstrichen.
In der gelben Liste wird in Klammern die aktuelle Distanz zum Startknoten und der Vorgängerknoten (als Nummernschild) angegeben.
- Kassel (0, --): Dortmund (160, KS), Hannover (167, KS), Frankfurt (193, KS), Wuerzburg (209, KS), Leipzig (250, KS)
- Dortmund (160, KS): Hannover (167, KS), Frankfurt (193, KS), Wuerzburg (209, KS), Leipzig (250, KS), Koeln (253, DO), Bremen (394, DO)
- Hannover (167, KS): Frankfurt (193, KS), Wuerzburg (209, KS), Leipzig (250, KS), Koeln (253, DO), Bremen (289, H), Hamburg (317, H), Berlin (457, H)
- Frankfurt (193, KS): Wuerzburg (209, KS), Leipzig (250, KS), Koeln (253, DO), Bremen (289, H), Hamburg (317, H), Karlsruhe (340, F), Berlin (457, H)
- Wuerzburg (209, KS): Leipzig (250, KS), Koeln (253, DO), Bremen (289, H), Hamburg (317, H), Nuernberg (319, WÜ), Karlsruhe (340, F), Berlin (457, H)
- Leipzig (250, KS): Koeln (253, DO), Bremen (289, H), Hamburg (317, H), Nuernberg (319, WÜ), Berlin (438, L)
- Koeln (253, DO): Bremen (289, H), Hamburg (317, H), Nuernberg (319, WÜ), Karlsruhe (340, F), Berlin (438, L)
- Bremen (289, H)
D.h. der kürzeste Weg von Kassel nach Bremen ist:
Kassel -> Hannover -> Bremen. Der Weg ist 289km lang.
Netzwerkprogrammierung
Protokoll
Client sendet | Server antwortet (einem Client) |
Server an alle |
---|---|---|
Client meldet sich an | +OK Willkommen beim GossipServer | |
Gossip schreiben: NEU <nachricht> |
+OK Nachricht akzeptiert -ERR Nachricht zu lang |
an alle Abonennten: NEU <zeit>--<nachricht> --- |
Gossip abonnieren: ABO |
+OK Abo akzeptiert | --- |
Gossip-Archiv lesen: ARCHIV |
+OK GossipArchiv <zeit 1>--<nachricht 1> ... <zeit n>--<nachricht n> . -ERR Datum falsch |
--- |
QUIT | +OK Tschuess Trennt die Verbindung |
--- |
<unbekannter Befehl> | -ERR unbekannter Befehl | --- |
<Parameter fehlt> | -ERR Parameter fehlt | --- |
Erstelle ein Implementationsdiagramm...
- GossipServer erbt von Server.
- GossipServer muss die Methoden
processMessage
,processNewConnection
undprocessClosedConnection
überschreiben.processMessage
ist notwendig, um Nachrichten von Clients gemäß Protokoll verarbeiten zu können.processNewConnection
ist notwendig, um neue Clients begrüßen zu können.processClosedConnection
ist notwendig, um Clients aus der Abonnentenliste streichen zu können, wenn sie sich abmelden
- GossipServer muss Nachrichten und Abonnenten verwalten können; dafür braucht er jeweils eine Liste.
- Die privaten Methoden sind vorteilhaft, damit die Methode
processMessage
nicht völlig aufgebläht wird.
Implementierung
//GossipServer erbt von Server!
public class GossipServer extends Server
{
private int port = 5555;
//Attribute fuer die Listen
private ListWithViewer<Abonnent> abonnentenListe;
private ListWithViewer<Nachricht> nachrichtenListe;
//Konstruktor
public GossipServer()
{
//den Konstruktor der Super-Klasse Server aufrufen
super(port);
System.out.println("GossipServer wird gestartet");
//die Listen als leere Listen erzeugen
abonnentenListe = new ListWithViewer<Abonnent>();
nachrichtenListe = new ListWithViewer<Nachricht>();
}
public void processNewConnection(String pClientIP, int pClientPort)
{
send(pClientIP, pClientPort, "+OK Willkommen beim Gossipserver");
//weiter ist hier nichts zu tun.
//denn Abonennten werden erst in die Liste geschrieben, wenn sie sich registriert haben.
}
public void processMessage(String pClientIP, int pClientPort, String pMessage)
{
if(pMessage.startsWith("NEU")){
String nachricht = pMessage.substring(4);
send(pClientIP, pClientPort, "+OK Nachricht akzeptiert");
nachrichtHinzufuegen(pClientIP, pClientPort, nachricht);
nachrichtAnAbonnentenWeiterleiten(nachricht);
return;
}
if(pMessage.equals("ARCHIV")){
sendeNachrichten(pClientIP, pClientPort);
return;
}
// weitere Befehle, die nicht zur Aufgabenstellung gehören
// kein Befehl trifft zu!
send(pClientIP, pClientPort, "-ERR unbekannter Befehl: "+pMessage);
}
private void nachrichtHinzufuegen(String pClientIP, int pClientPort, String pNachricht)
{
Nachricht neueNachricht = new Nachricht(pNachricht);
this.nachrichtenListe.append(neueNachricht);
}
private void sendeNachrichten(String pClientIP, int pClientPort)
{
send(pClientIP, pClientPort, "+OK GossipArchiv");
for(nachrichtenListe.toFirst(); nachrichtenListe.hasAccess(); nachrichtenListe.next()) {
Nachricht dieNachricht = nachrichtenListe.getContent();
send(pClientIP, pClientPort, dieNachricht.getZeit()+" "+dieNachricht.getText());
}
this.send(pClientIP, pClientPort, ".");
}
private void nachrichtAnAbonnentenWeiterleiten(String pMessage)
{
for(abonnentenListe.toFirst(); abonnentenListe.hasAccess(); abonnentenListe.next()){
Abonnent derAbonnent = this.abonnentenListe.getContent();
this.send(derAbonnent.getIp(),derAbonnent.getPort(), "+OK NEU "+pMessage);
abonnentenListe.next();
}
}
}
Backtracking
Das Rucksackproblem
Folgende Informationen muss man in Attributen speichern:
- die Gewichte, die aktuell im Rucksack sind:
aktuelleGewichte
- die Gewichte, die zur bisher besten Lösung gehören:
bisherBesteLösung
Bei diesem Backtracking-Problem entspricht jedes der Gewichte einer Stufe.
Für jedes Gewicht (d.h. auf jeder Stufe) hat man zwei Möglichkeiten:
- Das Gewicht in den Rucksack packen,
- Das Gewicht nicht in den Rucksack packen.
Für beide Möglichkeiten muss die Backtracking-Methode rekursiv aufgerufen werden.
Der Algorithmus kann so funktionieren:
rucksackBacktracking(pStufe)
wenn man eine bessere Lösung gefunden hat:
dann kopiere aktuelleGewichte in bisherBesteLösung u
wenn pStufe größer ist als die Anzahl der Gewichte:
dann verlasse die Methode (denn es kann nicht weiter gehen.)
packe das Gewicht pStufe in den Rucksack (d.h. füge das Gewicht zu aktuelleGewichte hinzu.)
rufe rucksackBacktracking(pStufe+1) auf.
nimm das Gewicht pStufe wieder aus dem Rucksack (d.h. entferne das Gewicht aus aktuelleGewichte.)
rufe rucksackBacktracking(pStufe+1) auf.
Jetzt ist nichts mehr rückgängig zu machen, weil man das Gewicht ja schon rausgenommen hat.
Kryptographie
Diffie-Hellmann-Verfahren
//TODO
RSA-Verfahren
Welche Zahlen braucht man, um eine Nachricht zu verschlüsseln?
Man braucht das Produkt zweier großer Primzahlen, d.h. N = p * q , wobei p und q Primzahlen sind. N ist der sogenannte öffentliche Schlüssel.
Die Primzahlen p und q selber braucht man zum Verschlüsseln nicht zu kennnen!
Außerdem braucht man noch eine weitere Zahl e, auf die sich Sender und Empfänger einigen müssen, die aber öffentlich sein kann. (Für e wird häufig 65537 gewählt.)
Welche Zahlen braucht man, um eine Nachricht zu entschlüsseln?
Man braucht die oben genannten Primzahlen p und q. Diese sind der sogenannte private Schlüssel.
Außerdem braucht man die oben genannte Zahl e.
Warum kann jemand, der eine Nachricht mit RSA verschlüsselt, diese nicht wieder entschlüsseln?
Um die Nachricht zu entschlüsseln, müsste er den öffentlichen Schlüssel N in die beiden Primfaktoren p und q (d.h. den privaten Schlüssel) zerlegen können. Das dauert aber bei großen Primzahlen (d.h. 500stellig) selbst mit dem schnellsten Computer mehr als 50 Jahre, d.h. es ist quasi unmöglich.
Es soll jetzt eine Java-Klasse RSA programmiert werden, mit der man Nachrichten verschlüsseln und entschlüsseln kann.
In der Klasse soll es eine Methode verschluessele(...) und eine Methode entschluessele(...) geben.
Welche Parameter und Rückgabetypen müssen diese Methoden haben?
Beim Verschlüsseln muss man den öffentlichen Schlüssel N und die Nachricht M als Parameter übergeben und erhält als Rückgabe die verschlüsselte Nachricht C.
Beim Verschlüsseln muss man die beiden privaten Schlüssel p und q und die verschlüsselte Nachricht C als Parameter übergeben und erhält als Rückgabe die Nachricht M.
D.h. die Methodenköpfe können so aussehen:
public int verschluessele(int N, int M)
public int entschluessele(int p, int q, int C)
(In der Praxis nimmt man nicht int
, weil der Zahlenbereich von int
bei Weitem nicht ausreicht!
Stattdessen nimmt man Objekte der Klasse BigInteger
- die können beliebig lange ganze Zahlen speichern.)
Welche Attribute muss die Klasse RSA haben?
Die Zahl e, auf die man sich geeinigt hat, kann als Attribut gespeichert werden.
Datenschutz
Erörtern Sie diese Anfrage unter datenschutzrechtlichen Aspekten.
Auf der einen Seite kann man vermutlich davon ausgehen, dass alle Schüler an einem Stipendium interessiert sind.
Andererseits werden hier aber personenbezogene Daten und Leistungsdaten abgefragt, ohne dass es dafür eine gesetzliche Grundlage gibt. Deswegen greift hier das Prinzip des Erlaubnisvorbehalts: Solche Daten dürfen nur weitergegeben werden, wenn die betroffenen Personen dem zustimmen - eine solche Zustimmung liegt aber nicht vor.
Deswegen muss die Schule die Anfrage der Studienstiftung ablehnen.
Schlagen Sie ggf. ein datenschutzrechtlich besseres Verfahren vor. (Das Verfahren sollte pragmatisch sein.)
Die Studienstiftung kann der Schule eine Email schicken, die diese an besonders gute Schüler weiterreicht. In der Mail kann ein Link zu einem Online-Formular der Studienstiftung sein, in das der Schüler seine Daten einträgt, seine Zustimmung gibt (und ggf. auch einen Scan des Abiturzeugnisses hochlädt). Die Studienstiftung sollte den Schüler auch um Zustimmung bitten, dass sie seine Angaben der Schule zur Überprüfung vorlegen darf.