Informatik-Abitur-Wiederholung: Unterschied zwischen den Versionen
(→SQL) |
|||
(26 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
Zeile 26: | Zeile 26: | ||
==Zweidimensionale Arrays== | ==Zweidimensionale Arrays== | ||
===Aufgabe 1 | ===Aufgabe 1 === | ||
a) Implementiere die Methode <code>public int[][] dasEinmalEins()</code>. | a) Implementiere die Methode <code>public int[][] dasEinmalEins()</code>. | ||
Zeile 44: | Zeile 44: | ||
Die Methode gibt in einer Liste alle runtergenommenen Container zurück. | Die Methode gibt in einer Liste alle runtergenommenen Container zurück. | ||
=Vererbung= | |||
[[File:Klassendiagramm-Buch-Fachbuch-Hoerbuch.png|thumb|Klassendiagramm |717px]] | |||
''Mit der Methode info() erhält man alle Informationen über das Objekt der jeweiligen Klasse.'' | |||
'''Aufgaben:''' | |||
# gibt es in der Klasse Fachbuch die Methode gibTitel() ? Wenn ja: warum? Wenn nein: warum nicht? | |||
# Implementiere die Klasse Fachbuch. | |||
# Erkläre am Beispiel des Klassendiagramms den Begriff Polymorphie. | |||
=Modellierung= | =Modellierung= | ||
==PriorityQueue | ==PriorityQueue == | ||
Es soll eine Klasse <code>PriorityQueue</code> erstellt werden, in der Objekte nach einer Priorität gespeichert werden sollen. Die Klasse soll u.a. über die Methoden <code>public Object getFirst()</code> und <code>public void insert(Object pObject, int pPriority)</code> verfügen. Die Klasse <code>PriorityQueue</code> soll auf der Basis der Klasse <code>List</code> oder <code>Queue</code> implementiert werden. | Es soll eine Klasse <code>PriorityQueue</code> erstellt werden, in der Objekte nach einer Priorität gespeichert werden sollen. Die Klasse soll u.a. über die Methoden <code>public Object getFirst()</code> und <code>public void insert(Object pObject, int pPriority)</code> verfügen. Die Klasse <code>PriorityQueue</code> soll auf der Basis der Klasse <code>List</code> oder <code>Queue</code> implementiert werden. | ||
Zeile 56: | Zeile 68: | ||
#<code>PriorityQueue</code> hat ein Objekt vom Typ <code>Queue</code> | #<code>PriorityQueue</code> hat ein Objekt vom Typ <code>Queue</code> | ||
==Monopoly | ==Monopoly == | ||
Bei Monopoly gibt es 40 Felder. Das sind z.T Straßen (wie z.B. die Poststraße) und z.T. Bahnhöfe (wie z.B. der Westbahnhof). Die anderen Felder (wie z.B. Elektrizätswerk, Los, Frei Parken, Gemeinschaftsfeld) werden hier der Einfachheit halber nicht betrachtet. Wenn man auf ein Feld kommt, dann kann man es kaufen, wenn es noch nicht verkauft ist. Wenn man auf einen Bahnhof oder eine Straße eines anderen Spielerst tritt, dann muss man bezahlen. Bei den Straßen hängt das davon ab, wie viele Häuser schon gebaut wurden. Bei den Bahnhöfen hängt es davon ab, wie viele Bahnhöfe der Besitzer hat. Wenn man auf eine eigene Straße tritt, dann kann man ein Haus bauen und muss dafür bezahlen. | Bei Monopoly gibt es 40 Felder. Das sind z.T Straßen (wie z.B. die Poststraße) und z.T. Bahnhöfe (wie z.B. der Westbahnhof). Die anderen Felder (wie z.B. Elektrizätswerk, Los, Frei Parken, Gemeinschaftsfeld) werden hier der Einfachheit halber nicht betrachtet. Wenn man auf ein Feld kommt, dann kann man es kaufen, wenn es noch nicht verkauft ist. Wenn man auf einen Bahnhof oder eine Straße eines anderen Spielerst tritt, dann muss man bezahlen. Bei den Straßen hängt das davon ab, wie viele Häuser schon gebaut wurden. Bei den Bahnhöfen hängt es davon ab, wie viele Bahnhöfe der Besitzer hat. Wenn man auf eine eigene Straße tritt, dann kann man ein Haus bauen und muss dafür bezahlen. | ||
Zeile 76: | Zeile 88: | ||
'''Aufgabe''': | '''Aufgabe''': | ||
Entwerfen Sie ein Implementationsdiagramm. Begründen Sie Ihre Entscheidungen. Begründen Sie auch, ob Sie sich für <code>Stack</code>, <code>Queue</code> oder <code>List</code> entscheiden. | Entwerfen Sie ein Implementationsdiagramm. Begründen Sie Ihre Entscheidungen für die Beziehungen zwischen den Klassen. Begründen Sie auch, ob Sie sich für <code>Stack</code>, <code>Queue</code> oder <code>List</code> entscheiden. | ||
=lineare Datenstrukturen= | =lineare Datenstrukturen= | ||
==eine lineare Datenstruktur implementieren== | ==eine lineare Datenstruktur implementieren== | ||
[[ | [[Datei:Queue.png]] | ||
# '''Erläutere anhand des | # '''Erläutere anhand des Objektdiagramms eine Implementationsstrategie für die Methode <code>public void enqueue(ContentType pContent)</code> .''' | ||
# '''Implementiere die folgenden Methoden: ''' | # '''Implementiere die folgenden Methoden: ''' | ||
## <code>public boolean isEmpty()</code> | ## <code>public boolean isEmpty()</code> | ||
Zeile 89: | Zeile 101: | ||
## <code>public Object top()</code> | ## <code>public Object top()</code> | ||
# '''Die Klasse <code>Node</code> ist dabei ''transparent''. Erläutere, was das bedeutet.''' | # '''Die Klasse <code>Node</code> ist dabei ''transparent''. Erläutere, was das bedeutet.''' | ||
==eine Liste durchlaufen== | ==eine Liste durchlaufen== | ||
Zeile 107: | Zeile 118: | ||
Ein Beispiel dafür findet sich unter '''[[Quelltextanalyse_Java]]'''. | Ein Beispiel dafür findet sich unter '''[[Quelltextanalyse_Java]]'''. | ||
==Quicksort | ==Quicksort== | ||
# Erläutere das Quicksort-Verfahren anhand der Zeichenkette "S-C-H-U-L-E". | # Erläutere das Quicksort-Verfahren anhand der Zeichenkette "S-C-H-U-L-E". | ||
# Implementiere die Methode <code>public List quicksort(List pBuchstaben)</code>. | # Implementiere die Methode <code>public List quicksort(List pBuchstaben)</code>. | ||
Zeile 142: | Zeile 153: | ||
* Die SQL-Aufgaben beziehen sich auf die Datenbank Schule. | * Die SQL-Aufgaben beziehen sich auf die Datenbank Schule. | ||
* Testen kann man SQL-Abfragen auf der Datenbank Schule '''[http://sibi-wiki.de/informatikag/videodb/index.php hier]'''. <br/>Die Zugangsdaten gibt's bei Herrn Kaibel | * Testen kann man SQL-Abfragen auf der Datenbank Schule '''[http://sibi-wiki.de/informatikag/videodb/index.php hier]'''. <br/>Die Zugangsdaten gibt's bei Herrn Kaibel | ||
* '''BEVOR DU LOSLEGST :'''<br/>'''Überlege erst, welche der folgenden Prinzipien du anwenden kannst/musst:''' | |||
** Kartesisches Produkt mit Abgleich über einen Primär-/Fremdschlüssel | |||
** ''"Alle inklusive Drückeberger":'' LEFT JOIN bzw. RIGHT JOIN | |||
** ''"Nur die Drückeberger":'' LEFT JOIN bzw. RIGHT JOIN und IS NULL | |||
** Differenz (NOT IN) | |||
** Gruppierung (GROUP BY) | |||
** ''Zwei Objekte aus der selben Tabelle: Das "bekannte" Objekt und das "unbekannte" Objekt.'': Zwei Variablen für eine Entitätsmenge. | |||
** selbstdefinierte Tabelle (=innere Abfrage), auf die eine äußere Abfrage zugreift. | |||
[[Datei:Beispieldatenbank-schule.jpg]] | [[Datei:Beispieldatenbank-schule.jpg]] | ||
Zeile 149: | Zeile 168: | ||
# Eine Liste der Klassen mit der Anzahl der Schüler; sortiert nach der Anzahl der Schüler. | # Eine Liste der Klassen mit der Anzahl der Schüler; sortiert nach der Anzahl der Schüler. | ||
# "Lehrerraumprinzip": Eine Liste der Lehrer, in der für jeden Lehrer vermerkt ist, in welchem Raum er am meisten Stunden unterrichtet.<br/>''Hinweis: Man braucht ein GROUP BY für zwei Spalten: GROUP BY l.id, r.id'' | # "Lehrerraumprinzip": Eine Liste der Lehrer, in der für jeden Lehrer vermerkt ist, in welchem Raum er am meisten Stunden unterrichtet.<br/>''Hinweis: Man braucht ein GROUP BY für zwei Spalten: GROUP BY l.id, r.id'' | ||
# | # Eine Liste aller Schüler und Lehrer. | ||
# In welchen Räumen findet nie Sport statt? | # In welchen Räumen findet nie Sport statt? | ||
# Welche Schüler sind Klassenkameraden von Anne Ebert? | # Welche Schüler sind Klassenkameraden von Anne Ebert? | ||
Zeile 156: | Zeile 175: | ||
# Eine Liste aller Klassen, in der angezeigt wird, wieviel Prozent Sport sie haben. | # Eine Liste aller Klassen, in der angezeigt wird, wieviel Prozent Sport sie haben. | ||
=Automaten | =Automaten= | ||
==Deterministische / Nicht-Deterministische Endliche 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.''' | # 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.''' | # '''Erläutere den Unterschied zwischen einem nicht-deterministischen endlichen Automaten und einem deterministischen endlichen Automaten.''' | ||
Zeile 164: | Zeile 183: | ||
## '''Erläutere, warum die zugrunde liegende Sprache regulär ist.''' | ## '''Erläutere, warum die zugrunde liegende Sprache regulär ist.''' | ||
==Reguläre Grammatik | ==Reguläre Grammatik== | ||
# '''Welche Bedingungen muss eine Grammatik erfüllen, um regulär zu sein?''' | # '''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.''' | # 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.''' | ||
Zeile 172: | Zeile 191: | ||
## Akzeptiert werden nur Wörter, die am Anfang gleich viele a haben wie am Ende. | ## Akzeptiert werden nur Wörter, die am Anfang gleich viele a haben wie am Ende. | ||
= | ==Parser== | ||
Programmiere einen Parser für die folgende Sprache: | |||
Akzeptiert wird jedes Wort beliebiger Länge, das <u>genau</u> ein a und <u>mindestens</u> ein b enthält. | |||
''(Es lohnt sich, vorab einen Automaten zu zeichnen!)'' | |||
==Kellerautomat, kontextfreie Grammatik, Parser für Kellerautomat== | |||
# Warum gibt es für die Sprache L = {a<sup>n</sup>b<sup>n</sup>} keinen deterministischen endlichen Automaten? | |||
# Zeichne einen Kellerautomat für die Sprache | |||
# Notiere eine kontextfreie Grammatik für die Sprache. | |||
# Implementiere einen Parser für die Sprache. | |||
=Binärbäume= | |||
[[File:Ahnenbaum.png|thumb|Ahnenbaum: Justus und seine Vorfahren|300px]] | [[File:Ahnenbaum.png|thumb|Ahnenbaum: Justus und seine Vorfahren|300px]] | ||
==Preorder, Inorder und Levelorder | ==Preorder, Inorder und Levelorder== | ||
Gegeben ist der Ahnenbaum von Justus und seinen Vorfahren. | Gegeben ist der Ahnenbaum von Justus und seinen Vorfahren. | ||
# Gib die Elemente des Baumes in Preorder, Inorder und Levelorder an. | # Gib die Elemente des Baumes in Preorder, Inorder und Levelorder an. | ||
Zeile 182: | Zeile 214: | ||
# Wie kann man den Inorder-Durchlauf ganz einfach ablesen? | # Wie kann man den Inorder-Durchlauf ganz einfach ablesen? | ||
==rekursive Methoden | ==rekursive Methoden== | ||
# Erläutere den Standard-Aufbau rekursiver Methoden mithilfe der Fachbegriffe ''rekursiver Aufruf, Abbruchbedingung, Sachlogik''. | # Erläutere den Standard-Aufbau rekursiver Methoden mithilfe der Fachbegriffe ''rekursiver Aufruf, Abbruchbedingung, Sachlogik''. | ||
# Implementiere die Methode <code>public List preorder(BinaryTree pTree)</code>. | # Implementiere die Methode <code>public List preorder(BinaryTree pTree)</code>. | ||
==Pfaddurchlauf | ==Pfaddurchlauf== | ||
# Benenne für den Ahnenbaum (s. rechts) eine Methode, die sich mithilfe eines '''Pfaddurchlaufes''' realisieren lässt und implementiere sie. | # 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. | # Erläutere die Implementationsstrategie beim Pfaddurchlauf. | ||
==Levelorder | ==Levelorder== | ||
# Implementiere die Methode <code>public List levelorder(BinaryTree pTree)</code> für den Ahnenbaum. | # Implementiere die Methode <code>public List levelorder(BinaryTree pTree)</code> für den Ahnenbaum. | ||
# Erläutere die Strategie von Levelorder anhand der Implementierung. | # Erläutere die Strategie von Levelorder anhand der Implementierung. | ||
==Binäre Suchbäume | ==Binäre Suchbäume== | ||
# Erläutere die Struktur eines Binären Suchbaumes. | # Erläutere die Struktur eines Binären Suchbaumes. | ||
# Welche Rolle spielt Inorder in einem binären Suchbaum? | # Welche Rolle spielt Inorder in einem binären Suchbaum? | ||
# Die Klasse <code>BinarySearchTree</code> kann implementiert werden, indem man die (fertige!) Klasse <code>BinaryTree</code> verwendet. | |||
## Welche Beziehung besteht zwischen den beiden Klassen? Begründe. | |||
## Implementiere die Methoden <code>insert</code> und <code>search</code>. | |||
===Implementierung von binären Suchbäumen | ===Implementierung von binären Suchbäumen=== | ||
[[Datei:Klassendiagramm_Buch.png|405px|thumb|right|Klassendiagramm der Klasse Buch]] | [[Datei:Klassendiagramm_Buch.png|405px|thumb|right|Klassendiagramm der Klasse Buch]] | ||
Es soll eine Klasse <code>Bibliothek</code> realisiert werden, in der die Bücher in einem Attribut <code>buecherBaum</code> vom Typ <code>BinarySearchTree</code> gespeichert werden. | Es soll eine Klasse <code>Bibliothek</code> realisiert werden, in der die Bücher in einem Attribut <code>buecherBaum</code> vom Typ <code>BinarySearchTree</code> gespeichert werden. | ||
Zeile 210: | Zeile 245: | ||
=Graphen= | =Graphen= | ||
[[File:Deutschland-graph.png|thumb|Deutschlandkarte |400px]] | |||
==Tiefendurchlauf== | ==Tiefendurchlauf== | ||
'''Verständnisaufgabe:''' | |||
Der Startknoten sei Frankfurt. Gib die ersten 10 Städte eines Tiefendurchlaufs an. Wenn es mehrere Möglichkeiten gibt, dann soll die Stadt ausgewählt werden, die <u>weniger weit entfernt</u> ist. | |||
Welcher Traversierungsmethode beim Binärbaum entspricht der Tiefendurchlauf? Warum? Wie zeigt sich das an der Implementierung? | |||
'''Implementierungsaufgabe:''' | |||
Gesucht ist eine Liste aller Knoten, die sich vom Knoten <code>startKnoten</code> aus mit 3 Kanten erreichen lassen.<br/> | Gesucht ist eine Liste aller Knoten, die sich vom Knoten <code>startKnoten</code> aus mit 3 Kanten erreichen lassen.<br/> | ||
D.h. zu implementieren ist eine Methode | D.h. zu implementieren ist eine Methode | ||
<code>public List<Vertex>findeKnoten(Vertex pStart, int pAnzahl)</code> | # <code>public List<Vertex> findeKnoten(Vertex pStart, int pAnzahl)</code> | ||
Diese Methode wird dann wie folgt aufgerufen: | Diese Methode wird dann wie folgt aufgerufen: | ||
<code>List<Vertex>ergebnis = findeKnoten(startKnoten,3);</code> | <code>List<Vertex> ergebnis = findeKnoten(startKnoten,3);</code> | ||
(Der Graph soll in einem Attribut <code>graph</code> gespeichert sein.) | (Der Graph soll in einem Attribut <code>graph</code> gespeichert sein.) | ||
==Breitendurchlauf== | ==Breitendurchlauf== | ||
// | '''Verständnisaufgabe:''' | ||
Der Startknoten sei Frankfurt. Gib die ersten 10 Städte eines Tiefendurchlaufs an. Wenn es mehrere Möglichkeiten gibt, dann soll die Stadt ausgewählt werden, die <u>weniger weit entfernt</u> ist. | |||
Welcher Traversierungsmethode beim Binärbaum entspricht der Breitendurchlauf? Warum? Wie zeigt sich das an der Implementierung? | |||
'''Implementierungsaufgabe:''' | |||
Implementiere die Methode | |||
<code>public List<Vertex> breitendurchlauf(String pStadt)</code> | |||
''Beachte: Im Parameter wird ein <code>String</code> angegeben! | |||
==Dijkstra-Algorithmus== | |||
Ermittle mithilfe des Dijkstra-Algorithmus den kürzesten Weg von Kassel nach Bremen. | |||
=Netzwerkprogrammierung= | |||
Der GossipServer soll dazu dienen, Tratsch (=Gossip) zu speichern und weiter zu verbreiten. Es gelten die folgenden Anforderungen: | |||
Gossip schreiben: | |||
* '''Gossip schreiben:''' Man kann die Verbindung zum GossipServer herstellen und (anonym!) eine neue Nachricht hinterlassen. Die wird als Text mit Datum/Uhrzeit gespeichert. Es werden nur Nachrichten in SMS-Länge akzeptiert. Dafür soll auf der Client-Seite eine Klasse '''<code>GossipClient.java</code>''' entwickelt werden. | |||
* '''Gossip abonnieren:''' Mithilfe eines geeigneten Befehls kann man den Gossip abonnieren. Der GossipServer schickt dem Client dann jede neu eintreffende Nachricht. Das soll auf der Client-Seite die Klasse '''<code>GossipTicker.java</code>''' erledigen. | |||
* '''Gossip-Archiv lesen:''' Man kann alle Nachrichten vom GossipServer abrufen, indem man einen geeigneten Befehl an den GossipServer schickt. Der GossipServer schickt dann alle Nachrichten mit Datum zurück. | |||
* '''Abmelden:''' Mithilfe eines geeigneten Befehls kann man die Verbindung zum GossipServer trennen. | |||
* '''Gossip speichern und die Abonnentenliste verwalten:''' Der <code>GossipServer</code> speichert die Nachrichten und die Abonnenten in Listen und reagiert auf die o.g. Anforderungen des <code>GossipClient</code> und des <code>GossipTicker</code>. | |||
'''Aufgaben:''' | |||
# Erstelle aus den Anforderungen ein geeignetes Netzwerk-Protokoll. Das Protokoll soll auf fehlerhafte Anforderungen angemessen reagieren können. | |||
# erstelle ein Implementationsdiagramm mit den Klassen GossipServer, Server, Abonnent, Nachricht und List. | |||
# implementiere die Klasse GossipServer: | |||
## Konstruktor | |||
## die Teile der Methode processMessage, mit denen man Gossip schreiben und das Archiv lesen kann. | |||
=Backtracking= | =Backtracking= | ||
// | '''Das Rucksackproblem''' | ||
In einen Container können 500kg gepackt werden. Es gibt folgende Gewichte: | |||
47.347, 55.734, 33.878, 11.321, 99.960, 42.316, 20.764, 52.945, 65.182, 83.339, 94.084, 68.415, 50.309, 70.037, 85.085 | |||
Jetzt sollen Gewichte so ausgewählt werden, dass die 500kg möglichst gut ausgenutzt werden, ohne dass die 500kg überschritten werden.<br/>''Die optimale Lösung ist in diesem Fall übrigens 499.983, d.h. ziemlich nah dran...'' | |||
* Erläutere, wie man das Problem mit Backtracking lösen kann.<br/>Gib dabei auch an, welche Informationen man in Attributen speichern muss. | |||
=Kryptographie= | =Kryptographie= | ||
==Diffie-Hellmann-Verfahren== | ==Diffie-Hellmann-Verfahren== | ||
//TODO | <font color='red'>//TODO</font> | ||
''Diffie-Hellmann soll man ja auch mathematisch durchrechnen können. <br/>Wenn das kommt, dann wird dafür wird eine Liste von geeigneten Primzahlen / Primitivwurzeln angegeben.'' | |||
==RSA-Verfahren== | ==RSA-Verfahren== | ||
// | Das RSA-Verschlüsselungsverfahren verwendet Zahlen. | ||
* Welche Zahlen braucht man, um eine Nachricht zu verschlüsseln? | |||
* Welche Zahlen braucht man, um eine Nachricht zu entschlüsseln? | |||
* Warum kann jemand, der eine Nachricht mit RSA verschlüsselt, diese nicht wieder entschlüsseln? | |||
Es soll jetzt eine Java-Klasse <code>RSA</code> programmiert werden, mit der man Nachrichten verschlüsseln und entschlüsseln kann. | |||
In der Klasse soll es eine Methode <code>verschluessele(...)</code> und eine Methode <code>entschluessele(...)</code> geben. | |||
* Welche Parameter und Rückgabetypen müssen diese Methoden haben? | |||
* Welche Attribute muss die Klasse <code>RSA</code> haben? | |||
=Datenschutz= | =Datenschutz= |
Aktuelle Version vom 27. Februar 2020, 16:39 Uhr
Auf dieser Seite werden Fragen zusammengestellt, die auf die "Basics" im Informatik-Abitur abzielen.
Die Lösungen finden sich hier: Informatik-Abitur-Wiederholung-Lösungen
Keine Garantie für Vollständigkeit!
Arrays
Standardmethoden für einfache Arrays
Eine Klasse NamensVerwaltung
enthalte als Attribut ein Array namen
:
Index | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
Wert | "Meier" | "Schmidt" | "Müller" | "Franzen" | "Altenburg" |
- Implementiere die Methode
public int anzahl()
. - Implementiere die Methode
public boolean enthaelt(String pName)
. - Implementiere die Methode
public void sortiere()
. Die Methode soll das Array mit einer für Arrays geeigneten Sortiermethode sortieren. Implementiere auch die notwendigen Hilfsmethoden.
Zweidimensionale Arrays
Aufgabe 1
a) Implementiere die Methode public int[][] dasEinmalEins()
.
Die Methode soll die Tabelle des kleinen EinmalEins zurückgeben.
b) Implementiere die Methode public int summe(int[][] tabelle)
Aufgabe 2
Die Beladung eines Containerschiffs wird durch ein zweidimensinales Array von Stacks abgebildet:
private Stack<Container>[][] beladung;
Jetzt soll von jedem Stack der oberste Container (wenn es einen gibt) runtergenommen und auf einen Güterzug verladen werden. Implementiere dafür die Methode
private List<Container> obersteContainerRunterNehmen();
Die Methode gibt in einer Liste alle runtergenommenen Container zurück.
Vererbung
Mit der Methode info() erhält man alle Informationen über das Objekt der jeweiligen Klasse.
Aufgaben:
- gibt es in der Klasse Fachbuch die Methode gibTitel() ? Wenn ja: warum? Wenn nein: warum nicht?
- Implementiere die Klasse Fachbuch.
- Erkläre am Beispiel des Klassendiagramms den Begriff Polymorphie.
Modellierung
PriorityQueue
Es soll eine Klasse PriorityQueue
erstellt werden, in der Objekte nach einer Priorität gespeichert werden sollen. Die Klasse soll u.a. über die Methoden public Object getFirst()
und public void insert(Object pObject, int pPriority)
verfügen. Die Klasse PriorityQueue
soll auf der Basis der Klasse List
oder Queue
implementiert werden.
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
Monopoly
Bei Monopoly gibt es 40 Felder. Das sind z.T Straßen (wie z.B. die Poststraße) und z.T. Bahnhöfe (wie z.B. der Westbahnhof). Die anderen Felder (wie z.B. Elektrizätswerk, Los, Frei Parken, Gemeinschaftsfeld) werden hier der Einfachheit halber nicht betrachtet. Wenn man auf ein Feld kommt, dann kann man es kaufen, wenn es noch nicht verkauft ist. Wenn man auf einen Bahnhof oder eine Straße eines anderen Spielerst tritt, dann muss man bezahlen. Bei den Straßen hängt das davon ab, wie viele Häuser schon gebaut wurden. Bei den Bahnhöfen hängt es davon ab, wie viele Bahnhöfe der Besitzer hat. Wenn man auf eine eigene Straße tritt, dann kann man ein Haus bauen und muss dafür bezahlen.
- 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.
Medienplayer
Szenario:
Ein Medienplayer kann die Titel, die man hören möchte, in Wiedergabelisten verwalten. Folgende typische Operationen sollen im Modell enthalten sein:
- Für einen Titel werden der Name, der Interpret und die Länge in Sekunden gespeichert. (Um die Speicherung der Audio-Daten kümmert sich diese Modellierung nicht.)
- Ein Titel kann an einer beliebigen Position der Wiedergabeliste (d. h. am Anfang, am Ende oder an einer Stelle innerhalb der Liste) eingefügt werden. Ebenso kann ein beliebiger Titel aus der Liste gelöscht werden.
- Das Abspielen der Wiedergabeliste beginnt beim ersten Titel. Dann werden alle Titel nacheinander abgespielt. Man kann das Abspielen stoppen. Und man kann wieder an den Anfang der Wiedergabeliste gehen.
- In einem Medienplayer werden beliebig viele Wiedergabelisten verwaltet. Jede Wiedergabeliste hat einen Namen. Der Medienplayer kann immer nur eine aktive Wiedergabeliste haben. Die aktive Liste kann abgespielt werden.
- Im Medienplayer kann man eine Wiedergabeliste auswählen, indem man ihren Namen angibt. Man kann auch neue Wiedergabelisten anlegen, indem man einen Namen angibt. Und man kann die gerade aktive Wiedergabeliste löschen.
- Beim Abspielen einer Wiedergabeliste fragt der Medienplayer immer den nächsten Titel von der aktiven Wiedergabeliste an.
Aufgabe:
Entwerfen Sie ein Implementationsdiagramm. Begründen Sie Ihre Entscheidungen für die Beziehungen zwischen den Klassen. Begründen Sie auch, ob Sie sich für Stack
, Queue
oder List
entscheiden.
lineare Datenstrukturen
eine lineare Datenstruktur implementieren
- Erläutere anhand des Objektdiagramms eine Implementationsstrategie für die Methode
public void enqueue(ContentType pContent)
. - Implementiere die folgenden Methoden:
public boolean isEmpty()
public void enqueue(Object pObject)
public void dequeue()
public Object top()
- Die Klasse
Node
ist dabei transparent. Erläutere, was das bedeutet.
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.
eine Methode erläutern
Erläutere die Methode einfuegen
(s.o.) unter Verwendung der wesentlichen Fachbegriffe.
Ein Beispiel dafür findet sich unter Quelltextanalyse_Java.
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?
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.
Berücksichtige, dass in der Datenbank auch Reservierungen für die Zukunft gespeichert werden sollen.
Relationales Datenmodell
- Übertrage das Modell rechts in ein relationales Datenmodell.
- Erläutere, wie die Relation
belegt
in das relationale Datenmodell übertragen wird. Verwende die wesentlichen Fachbegriffe. - Was wäre die Konsequenz, wenn die Tabelle
belegt
als Primärschlüssel ein Attributid
hätte?
Normalisierung
- Benenne die Anforderungen der 1., 2. und 3. Normalform.
- Erläutere, wie man Verstöße gegen die 1., 2. und 3. Normalform feststellt.
Gegeben ist die folgende Modellierung:
- Kurs(id, bezeichnung, schuljahr, halbjahr, lehrer_kuerzel, lehrer_name)
- Leistung(↑kurs_id, schueler_id, name, vorname, note)
- Erläutere, ob sich die Modellierung in 1., 2. oder 3. Normalform befindet.
- Überführe nötigenfalls schrittweise in 3. Normalform.
SQL
- Die SQL-Aufgaben beziehen sich auf die Datenbank Schule.
- Testen kann man SQL-Abfragen auf der Datenbank Schule hier.
Die Zugangsdaten gibt's bei Herrn Kaibel - BEVOR DU LOSLEGST :
Überlege erst, welche der folgenden Prinzipien du anwenden kannst/musst:- Kartesisches Produkt mit Abgleich über einen Primär-/Fremdschlüssel
- "Alle inklusive Drückeberger": LEFT JOIN bzw. RIGHT JOIN
- "Nur die Drückeberger": LEFT JOIN bzw. RIGHT JOIN und IS NULL
- Differenz (NOT IN)
- Gruppierung (GROUP BY)
- Zwei Objekte aus der selben Tabelle: Das "bekannte" Objekt und das "unbekannte" Objekt.: Zwei Variablen für eine Entitätsmenge.
- selbstdefinierte Tabelle (=innere Abfrage), auf die eine äußere Abfrage zugreift.
- Eine Liste aller Unterrichtsfächer, in der steht, wieviele Stunden sie jeweils unterrichtet werden; die Unterrichtsfächer mit vielen Stunden sollen oben stehen.
- Eine Liste der Räume, in denen die 8B Unterricht hat.
- Eine Liste der Klassen mit der Anzahl der Schüler; sortiert nach der Anzahl der Schüler.
- "Lehrerraumprinzip": Eine Liste der Lehrer, in der für jeden Lehrer vermerkt ist, in welchem Raum er am meisten Stunden unterrichtet.
Hinweis: Man braucht ein GROUP BY für zwei Spalten: GROUP BY l.id, r.id - Eine Liste aller Schüler und Lehrer.
- In welchen Räumen findet nie Sport statt?
- Welche Schüler sind Klassenkameraden von Anne Ebert?
- 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.
- Eine Liste der Schüler, die keine Klasse haben.
- Eine Liste aller Klassen, in der angezeigt wird, wieviel Prozent Sport sie haben.
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.
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.
Parser
Programmiere einen Parser für die folgende Sprache:
Akzeptiert wird jedes Wort beliebiger Länge, das genau ein a und mindestens ein b enthält.
(Es lohnt sich, vorab einen Automaten zu zeichnen!)
Kellerautomat, kontextfreie Grammatik, Parser für Kellerautomat
- Warum gibt es für die Sprache L = {anbn} keinen deterministischen endlichen Automaten?
- Zeichne einen Kellerautomat für die Sprache
- Notiere eine kontextfreie Grammatik für die Sprache.
- Implementiere einen Parser für die Sprache.
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?
rekursive Methoden
- Erläutere den Standard-Aufbau rekursiver Methoden mithilfe der Fachbegriffe rekursiver Aufruf, Abbruchbedingung, Sachlogik.
- Implementiere die Methode
public List preorder(BinaryTree pTree)
.
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.
Levelorder
- Implementiere die Methode
public List levelorder(BinaryTree pTree)
für den Ahnenbaum. - Erläutere die Strategie von Levelorder anhand der Implementierung.
Binäre Suchbäume
- Erläutere die Struktur eines Binären Suchbaumes.
- Welche Rolle spielt Inorder in einem binären Suchbaum?
- Die Klasse
BinarySearchTree
kann implementiert werden, indem man die (fertige!) KlasseBinaryTree
verwendet.- Welche Beziehung besteht zwischen den beiden Klassen? Begründe.
- Implementiere die Methoden
insert
undsearch
.
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.
Graphen
Tiefendurchlauf
Verständnisaufgabe:
Der Startknoten sei Frankfurt. Gib die ersten 10 Städte eines Tiefendurchlaufs an. Wenn es mehrere Möglichkeiten gibt, dann soll die Stadt ausgewählt werden, die weniger weit entfernt ist.
Welcher Traversierungsmethode beim Binärbaum entspricht der Tiefendurchlauf? Warum? Wie zeigt sich das an der Implementierung?
Implementierungsaufgabe:
Gesucht ist eine Liste aller Knoten, die sich vom Knoten startKnoten
aus mit 3 Kanten erreichen lassen.
D.h. zu implementieren ist eine Methode
public List<Vertex> findeKnoten(Vertex pStart, int pAnzahl)
Diese Methode wird dann wie folgt aufgerufen:
List<Vertex> ergebnis = findeKnoten(startKnoten,3);
(Der Graph soll in einem Attribut graph
gespeichert sein.)
Breitendurchlauf
Verständnisaufgabe:
Der Startknoten sei Frankfurt. Gib die ersten 10 Städte eines Tiefendurchlaufs an. Wenn es mehrere Möglichkeiten gibt, dann soll die Stadt ausgewählt werden, die weniger weit entfernt ist.
Welcher Traversierungsmethode beim Binärbaum entspricht der Breitendurchlauf? Warum? Wie zeigt sich das an der Implementierung?
Implementierungsaufgabe:
Implementiere die Methode
public List<Vertex> breitendurchlauf(String pStadt)
Beachte: Im Parameter wird ein String
angegeben!
Dijkstra-Algorithmus
Ermittle mithilfe des Dijkstra-Algorithmus den kürzesten Weg von Kassel nach Bremen.
Netzwerkprogrammierung
Der GossipServer soll dazu dienen, Tratsch (=Gossip) zu speichern und weiter zu verbreiten. Es gelten die folgenden Anforderungen: Gossip schreiben:
- Gossip schreiben: Man kann die Verbindung zum GossipServer herstellen und (anonym!) eine neue Nachricht hinterlassen. Die wird als Text mit Datum/Uhrzeit gespeichert. Es werden nur Nachrichten in SMS-Länge akzeptiert. Dafür soll auf der Client-Seite eine Klasse
GossipClient.java
entwickelt werden. - Gossip abonnieren: Mithilfe eines geeigneten Befehls kann man den Gossip abonnieren. Der GossipServer schickt dem Client dann jede neu eintreffende Nachricht. Das soll auf der Client-Seite die Klasse
GossipTicker.java
erledigen. - Gossip-Archiv lesen: Man kann alle Nachrichten vom GossipServer abrufen, indem man einen geeigneten Befehl an den GossipServer schickt. Der GossipServer schickt dann alle Nachrichten mit Datum zurück.
- Abmelden: Mithilfe eines geeigneten Befehls kann man die Verbindung zum GossipServer trennen.
- Gossip speichern und die Abonnentenliste verwalten: Der
GossipServer
speichert die Nachrichten und die Abonnenten in Listen und reagiert auf die o.g. Anforderungen desGossipClient
und desGossipTicker
.
Aufgaben:
- Erstelle aus den Anforderungen ein geeignetes Netzwerk-Protokoll. Das Protokoll soll auf fehlerhafte Anforderungen angemessen reagieren können.
- erstelle ein Implementationsdiagramm mit den Klassen GossipServer, Server, Abonnent, Nachricht und List.
- implementiere die Klasse GossipServer:
- Konstruktor
- die Teile der Methode processMessage, mit denen man Gossip schreiben und das Archiv lesen kann.
Backtracking
Das Rucksackproblem
In einen Container können 500kg gepackt werden. Es gibt folgende Gewichte:
47.347, 55.734, 33.878, 11.321, 99.960, 42.316, 20.764, 52.945, 65.182, 83.339, 94.084, 68.415, 50.309, 70.037, 85.085
Jetzt sollen Gewichte so ausgewählt werden, dass die 500kg möglichst gut ausgenutzt werden, ohne dass die 500kg überschritten werden.
Die optimale Lösung ist in diesem Fall übrigens 499.983, d.h. ziemlich nah dran...
- Erläutere, wie man das Problem mit Backtracking lösen kann.
Gib dabei auch an, welche Informationen man in Attributen speichern muss.
Kryptographie
Diffie-Hellmann-Verfahren
//TODO
Diffie-Hellmann soll man ja auch mathematisch durchrechnen können.
Wenn das kommt, dann wird dafür wird eine Liste von geeigneten Primzahlen / Primitivwurzeln angegeben.
RSA-Verfahren
Das RSA-Verschlüsselungsverfahren verwendet Zahlen.
- Welche Zahlen braucht man, um eine Nachricht zu verschlüsseln?
- Welche Zahlen braucht man, um eine Nachricht zu entschlüsseln?
- Warum kann jemand, der eine Nachricht mit RSA verschlüsselt, diese nicht wieder entschlüsseln?
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?
- Welche Attribute muss die Klasse
RSA
haben?
Datenschutz
Eine gemeinnützige Studienstiftung bietet Stipendien für besonders gute Abiturienten an.
Um den Abiturienten fächerspezifisch geeignete Angebote machen zu können, hätte die Studienstiftung gerne eine Liste der besonders guten Abiturienten (Schnitt: besser als 1,3) mit folgenden Einträgen:
- Name
- Vorname
- Adresse
- Englisch-Note
- Deutsch-Note
- Mathematik-Note
- Informatik-Note
- Durchschnittsnote
Erörtern Sie diese Anfrage unter datenschutzrechtlichen Aspekten.
Schlagen Sie ggf. ein datenschutzrechtlich besseres Verfahren vor. (Das Verfahren sollte pragmatisch sein.)