Informatik-Abitur-Wiederholung-Lösungen

Auf dieser Seite finden sich die Lösungen für die Aufgaben der folgenden Seite:

Informatik-Abitur-Wiederholung

Arrays

Standardmethoden für einfache Arrays

1. Implementiere die Methode public int anzahl().
2. Implementiere die Methode public boolean enthaelt(String pName).
3. 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-ein Buch.
• 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 Typ Fachbuch zu erzeugen, muss erst der Konstruktor von Buch aufgerufen werden; das ist auch inhaltlich wichtig, denn nur so können titel und autor richtig eingetragen werden.
• Mit super.info() greifen die Subklassen auf die Methode info() 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:

1. PriorityQueue erbt von List
2. PriorityQueue erbt von Queue
3. PriorityQueue hat ein Objekt vom Typ List
4. PriorityQueue hat ein Objekt vom Typ Queue

Queue bietet nicht ausreichend Funktionalität, denn man muss ein neues Element gemäß seiner Priorität einsortieren können. Das ist bei Queue 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

1. Entscheide dich begründet für eine Datenstruktur für die 40 Felder des Monopoly-Spiels.
2. Zeichne ein Klassendiagramm mit den Klassen MonopolyFeld, Strasse und Bahnhof und einer weiteren sinnvollen Klasse, die du selber einführst. Gib für die Klassen Strasse, 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 und Titel.
• Medienplayer ist die "oberste" Klasse und damit der Ausgangspunkt der Modellierung.
• Medienplayer hat eine Liste mit Inhaltsobjekten vom Typ Wiedergabeliste. List eignet sich besser als Queue oder Stack, weil damit das Auswählen der Wiedergabeliste nach dem Titel einfacher realisiert werden kann.
• Medienplayer hat ein Attribut aktiveWiedergabeliste vom Typ <Wiedergabeliste, in dem die jeweils aktive Wiedergabeliste gespeichert wird.
• WiedergabeListe kann nicht von List erben, weil sie sonst die Methode concat(List pList) zur Verfügung hätte, die im Szenario nicht vorgesehen ist.
• Stattdessen: WiedergabeListe hat eine List mit Inhaltsobjekten vom Typ Titel. Queue oder Stack 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

1. 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 und tail auf newNode zeigen.
• Vom letzten Node den Verweis next auf newNode setzen.
• Den Verweis von tail auf newNode setzen.

1. Implementiere die folgenden Methoden:
   siehe Queue_ab_Abi_2017#Implementierung
2. 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

Klassendiagramm der Klasse Buch

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.

1. public Bibliothek(): Der Konstruktor erzeugt eine Bibliothek; die buecherListe ist zu Anfang leer. Das hat nichts mit Listendurchlauf zu tun, ist aber trotzdem wichtig...
2. public boolean enthaelt(String pTitel)
3. public void einfuegen(Buch pBuch): Fügt pBuch 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

1. Erläutere das Quicksort-Verfahren anhand der Zeichenkette "S-C-H-U-L-E".
2. Implementiere die Methode public List quicksort(List pBuchstaben).
3. 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

1. 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
2. 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.
3. 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
4. "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.id
   SELECT 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
5. Eine Liste aller Lehrer und Schüler.
   SELECT l.name
FROM lehrer l
UNION
SELECT s.name
FROM schueler s
6. 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'
)
7. 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'
)
8. 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
9. 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
10. 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

1. 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.
2. Erläutere den Unterschied zwischen einem nicht-deterministischen endlichen Automaten und einem deterministischen endlichen Automaten.
3. Gesucht wird ein endlicher Automat, der erkennt, ob eine eingegebene Zeichenkette das Wort LOL enthält.
   1. Zeichne dafür den Übergangsgraph eines Nicht deterministischen endlichen Automaten.
   2. Erläutere, warum die zugrunde liegende Sprache regulär ist.

//TODO

Reguläre Grammatik

1. Welche Bedingungen muss eine Grammatik erfüllen, um regulär zu sein?
2. 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.
   1. Akzeptiert wird jedes Wort beliebiger Länge, das mindestens 2 a und 2 b enthält.
   2. Akzeptiert wird jedes Wort beliebiger Länge, das mehr a als b enthält.
   3. Akzeptiert werden nur Wörter, die höchstens 6 Zeichen haben.
   4. Akzeptiert werden nur Wörter, die am Anfang gleich viele a haben wie am Ende.

//TODO

Binärbäume

Ahnenbaum: Justus und seine Vorfahren

Preorder, Inorder und Levelorder

Gegeben ist der Ahnenbaum von Justus und seinen Vorfahren.

1. Gib die Elemente des Baumes in Preorder, Inorder und Levelorder an.
2. Inwiefern ergibt Levelorder eine sinnvolle Reihenfolge?
3. Für welche Bäume ergibt Inorder eine sinnvolle Anordnung?
4. Wie kann man den Inorder-Durchlauf ganz einfach ablesen?

//TODO

rekursive Methoden

1. Erläutere den Standard-Aufbau rekursiver Methoden mithilfe der Fachbegriffe rekursiver Aufruf, Abbruchbedingung, Sachlogik.
2. Implementiere die Methode public List preorder(BinaryTree pTree).

//TODO

Pfaddurchlauf

1. Benenne für den Ahnenbaum (s. rechts) eine Methode, die sich mithilfe eines Pfaddurchlaufes realisieren lässt und implementiere sie.
2. Erläutere die Implementationsstrategie beim Pfaddurchlauf.

//TODO

Levelorder

1. Implementiere die Methode public List levelorder(BinaryTree pTree) für den Ahnenbaum.
2. Erläutere die Strategie von Levelorder anhand der Implementierung.

siehe Binärbaum#Levelorder-Traversierung_(nur_LK)

Binäre Suchbäume

1. Erläutere die Struktur eines Binären Suchbaumes.
2. Welche Rolle spielt Inorder in einem binären Suchbaum?

//TODO

Implementierung von binären Suchbäumen

Klassendiagramm der Klasse Buch

Es soll eine Klasse Bibliothek realisiert werden, in der die Bücher in einem Attribut buecherBaum vom Typ BinarySearchTree gespeichert werden.

1. Zeichne ein Implementationsdiagramm mit den Klassen Bibliothek, Buch und der Schnittstelle Item
2. Welche Funktion erfüllt die Schnittstelle Item in diesem Zusammenhang?
3. Implementiere die Klasse Buch.
4. Implementiere für die Klasse Bibliothek die folgenden Methoden:
   1. public void einfuegen(Buch pBuch)
   2. 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 und processClosedConnection ü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.