Die Buchhandlung SCHMIDT & CO verwaltet ihre Bücher mit Hilfe von Karteikarten, von den im Folgenden einige abgebildet sind.
Dabei repräsentiert eine Karteikarte ein Buch, von dem es aber mehrere Buchexemplare geben kann (vgl. Attribut „Anzahl“). Die ISBN-Nummer ist eine eindeutige Kennzeichnung eines Buches.
Der Buchhändler möchte diese Buchdatei mit Hilfe eines Computerprogramms verwalten.
Sie sollen in dieser Aufgabe Teile der Buchverwaltung modellieren und implementieren. Dabei ist das Prinzip der Vererbung zu benutzen. Alle Bücher werden erst einmal in einer Liste verwaltet.
In dieser Liste werden die Bücher nach Autoren sortiert alphabetisch aufsteigend angeordnet. Alle Bücher desselben Autors stehen so hintereinander, wie sie aufgenommen wurden. Aus Gründen der Vereinfachung wird auf eine Anordnung z. B. nach Titel verzichtet.
Entwerfen Sie ein Klassendiagramm für eine Klasse Buch und ihre Unterklassen (inklusive aller benötigten Attribute mit Datentypen, Methoden mit Parametern und Beziehungen).
Erläutern und begründen Sie das Konzept der Vererbung und konkretisieren Sie es an diesem Beispiel.
Ein Objekt der Klasse Buchverwaltung verwaltet alle Bücher in einer Liste buecher.
Analysieren Sie die nachfolgende Methode buchEinfuegen(Buch pBuch), indem Sie die auf den oben angegebenen Karteikarten mit den beschriebenen Büchern in der dort angegebenen Reihenfolge mit Hilfe dieser Methode in die vorher leere Liste buecher einfügen.
public void buchEinfuegen(Buch pBuch) {
if (buecher. isEmpty()) {
buecher.append(pBuch);
} else {
buecher.toFirst();
boolean gefunden = false;
while (buecher.hasAccess() && !gefunden) {
Buch aktuellBuch = buecher.getContent();
if (aktuellBuch.gibAutor().compareTo(pBuch.gibAutor()) <= 0) {
buecher.next();
} else {
gefunden = true;
buecher.insert(pBuch);
}
}
if (!gefunden) {
buecher.append(pBuch);
}
}
}
Erläutern Sie die Funktionsweise der Methode.
Bei der vorliegenden Implementierung werden gleiche Bücher (Autor, Titel) in die Liste einfügt und nicht die Anzahl der Exemplare erhöht.
Implementieren Sie die Methode buchEinfuegen_neu(Buch pBuch), so dass beim Einfügen eines Buches, das bereits in der Liste vorhanden ist, nur das Attribut Anzahl erhöht wird.
Die Buchdatei soll mit Hilfe eines Objektes der Klasse BinaySearchTree verwaltet werden.
Begründen Sie, warum von den vorhandenen Kriterien nur die ISBN als Ordnungskriterium für einen BinarySearchTree geeignet ist.
Bei der Erfassung der Daten wurde der Verlag nicht mit aufgenommen, da er sich aus der ISBN erschließen lässt.
Die ISBN-Nummer zu einem Buch ist aus einem Präfix für den Warentyp, einer Länderkennung, einer Verlagskennung und einer verlagsinternen Nummerierung zusammengesetzt. Außerdem kann noch eine Prüfziffer angehängt werden. So ist in 978-3-12-738800-4 die Ziffernfolge 978 das Präfix für Bücher, 3 die Länderkennung für Deutschland und 12 die Kennung für einen bestimmten Verlag.
Alle Bücher dieses Verlages fangen also mit 978-3-12 an.
Die Buchhandlung möchte wissen, welche Bücher des Bestandes vom gleichen Verlag stammen. Deshalb sollen die Bücher der Buchhandlung nun nach ISBN aufsteigend angeordnet werden. In dieser Liste werden die Bücher eines Verlages hintereinanderstehen.
Dazu sollen die vorhandenen Bücher in ein Objekt der Klasse BinarySeachTree eingefügt und anschießend als geordnete Liste zur Verfügung gestellt werden.
Erläutern Sie, welche Änderungen und Erweiterungen in den bereits vorhandenen Klassen notwendig sind.
Implementieren Sie die Methode public List gibListeGeordnetNachISBN() und eventuell notwendige Hilfsmethoden der Klasse Buchverwaltung.
In einer Ahnentafel werden die Vorfahren eines Individuums, des sogenannten Probanden, dargestellt. Da jedes Individuum zwei Elternteile hat, lässt sich die Ahnentafel als Binärbaum darstellen, wobei der Proband in der Wurzel des Baumes steht. Die Ebenen des Baumes enthalten die Individuen einer Generation. Der Proband hat die Generationsnummer Null
Jedes Individuum in der Ahnentafel wird durch die eindeutige Kekulé-Zahl (nach Dr. Stephan Kekulé, 1904) gekennzeichnet, die nach folgenden Regeln gebildet wird:
Der Proband (Ausgangsperson) erhält immer die Kekulé-Zahl 1.
Hat ein Individuum die Kekulé-Zahl n, so erhält sein Vater die Nummer 2∙n und seine Mutter die Nummer 2∙n + 1
Die folgende Abbildung zeigt die Ahnentafel des Probanden Johann Sebastian Bach als Binärbaum.
Da in der Ahnenforschung nicht immer alle Vorfahren bekannt sind, gibt es Lücken im Ahnenbaum.
Geben Sie die Kekulé-Zahlen der Individuen an, die nicht in dem Baum dargestellt sind.
Geben Sie die verwandtschaftlichen Beziehung an, die zwischen dem Individuum mit der Kelkulé-Zahl 5 und Johann Sebastian Bach besteht.
Die Verwaltung einer Ahnentafel soll mit dem Rechner erfolgen. Dazu wird die Ahnentafel durch eine Klasse Ahnentafel repräsentiert, die einen Binärbaum ahnenbaum beinhaltet. Im Baum werden die Individuen gespeichert. Die Merkmale eines Individuums werden in der Klasse Individuum festgehalten.
Entwickeln Sie ein Implementationsdiagramm für die beiden Klassen Ahnentafelund Individuum, bei dem auch die Beziehungen dargestellt werden. Bei den Klassen Ahnentafel und Individuum reicht die Angabe der Attribute und der Konstruktoren.
Gegeben ist die Methode gibIndividuum:
public Individuum gibIndividuum(int pKekule) {
if (pKekule > 0) {
Stack<Boolean> pfadZumIndividuum = new Stack<Boolean>();
int tempKekule = pKekule;
while (tempKekule > 1) {
pfadZumIndividuum.push(new Boolean(tempKekule % 2 == 0));
tempKekule = tempKekule / 2;
}
BinaryTree<Individuum> aktTeilbaum = gibAhnenbaum();
while (!pfadZumIndividuum.isEmpty() &&
!aktTeilbaum.isEmpty()) {
if ((pfadZumIndividuum.top()).booleanValue()) {
aktTeilbaum = aktTeilbaum.getLeftTree();
} else {
aktTeilbaum = aktTeilbaum.getRightTree();
}
pfadZumIndividuum.pop();
}
if (!aktTeilbaum.isEmpty()) {
return aktTeilbaum.getContent();
} else {
return null;
}
} else {
return null;
}
}
Analysieren Sie die Methode, indem Sie den Ablauf der Methode für den Aufruf gibIndividuum(12), angewandt auf den Ahnenbaum von Johann Sebastian Bach,simulieren. Dokumentieren Sie hierzu die Änderung der Variablenwerte in den beiden while-Schleifen. Erläutern Sie die Idee des Algorithmus.
Die Klasse Ahnentafel soll um die Methode gibAnzahlGenerationen mit dem Methodenkopf
public int gibAnzahlGenerationen() {
erweitert werden, die die Anzahl der in der Ahnentafel gespeicherten Generationen zurückgibt. Die Generationen müssen dabei nicht unbedingt vollständig gespeichert sein. Implementieren Sie die Methode gibAnzahlGenerationen und gegebenenfalls weitere Hilfsmethoden.
In Büchern ist die Darstellung einer umfangreichen Ahnentafel wie etwa die von Bach in Form eines Baumes unpraktisch. In diesem Fall stellt man die Ahnentafel als Liste dar, die nach aufsteigender Kekulé-Zahl sortiert ist. Die Kekulé-Zahl muss mit abgespeichert werden, da der Ahnenbaum nicht in jedem Fall vollständig ist.
Die Klasse Ahnentafel soll um die Methode gibAhnentafelAlsListe mit dem Methodenkopf
public List<IndividuumKNr> gibAhnentafelAlsListe() {
erweitert werden, die die Individuen des Ahnenbaums zusammen mit ihrer Kekulé-Zahl in eine nach aufsteigender Kekulé-Zahl sortierten Liste schreibt. Die Klasse IndividuumKNr ist eine Unterklasse der Klasse Individuum, die als zusätzliches Attribut die Kekulé-Zahl verwaltet.
Entwickeln Sie eine Lösungsidee und implementieren Sie die Methode gibAhnentafelAlsListe und gegebenenfalls weitere Klassen und Hilfsmethoden.
Ein Unternehmen, das über verschiedene Standorte verfügt, möchte über die Nummernschilder der Dienstfahrzeuge kennzeichnen, zu welchen Standort das Fahrzeug gehört. Dazu werden zwei Buchstaben nach dem Ortskürzel und vor der Zahl benutzt.
Bei diesem Beispiel kennzeichnet AB den Standort.
Bei der Modellierung der Kennzeichenverwaltung entscheidet man sich, die Kennzeichen in einem Suchbaum zu verwalten. Der Suchbaum ist nach den Standortkennzeichen sortiert. Es werden die Kreiskürzel weggelassen.
Der Baum speichert die Kennzeichen sortiert nach dem mittleren Buchstabenteil. Die Zahlenteile zu einem Buchstabenteil werden in den Inhaltsobjekten der Baumknoten in aufsteigender Reihenfolge gespeichert.
Zwei neue Autos mit den Kennzeichen BQ MT 73 und ZQ QQ 13 sollen zugelassen werden. Erweitern Sie den Suchbaum aus Abbildung 1 entsprechend. Erläutern Sie Ihre Lösung.
Zur Verwaltung der Kennungen soll ein Computerprogramm benutzt werden, das zwei Klassen benutz:
Die Klasse Kennungsverwaltung
In einem Objekt der Klasse Kennungsverwaltung werden die Standortkennungen der Kennzeichen in einem binären Suchbaum mit dem Namen kennungsbaum verwaltet.
Die Klasse Standortkennung
In einem Objekt der Klasse Standortkennung werden neben den Standortkürzeln die zugehörigen Nummern (Zahlen) aufsteigend sortiert in einem Objekt einer generischen Liste mit Namen kennungsZahlen verwaltet.
Objekte dieser Klassen werden als Inhaltsobjekte der Knoten in dem binären Suchbaum benutzt. Entwerfen Sie ein Implementationsdiagramm. Zu den Standardklassen müssen keine Attribute und Methoden angegeben werden.
In der Klasse Kennungsverwaltung gibt es die folgende Methode:
public int wasLiefereIch(String pText)
{
Standortkennung num1 = new Standortkennung(pText,-1);
// Ortskennzeichen mit leerem Zahlenteil
Standortkennung num2 = kennungsbaum.search(num1);
if (num2 == null) {
return -1;
} else {
List werte = num2.gibZahlen();
werte.toFirst();
int ergebnis = 0;
while (werte.hasAccess()) {
ergebnis++;
werte.next();
}
return ergebnis;
}
}
Geben Sie an, welchen Wert die Methode für den dargestellten Baum und den Methodenparameter pText = "PS" zurückliefert.
Analysieren Sie die Methode und beschreiben Sie, nach welcher allgemeinen Strategie der Rückgabewert berechnet wird.
Erläutern Sie, welche Funktion die Methode im Sachzusammenhang hat.
Um neue Kennzeichen aufzunehmen, benötigt man folgende Methoden:
In der Klasse Standortkennung die Methode fuegeZahlHinzu mit der Kopfzeile:
public void fuegeZahlHinzu(int pZahl)
In die Liste kennungszahlen wird pZahl unter Berücksichtigung der Sortierung eingefügt, sofern sie dort noch nicht vorhaben ist.
In der Klasse Kennungsverwaltung die Methode fuegeHinzu mit der Kopfzeile:
public void fuegeHinzu(String pText, int pZahl)
Ein Kennzeichen, das sich aus pText und pZahl zusammensetzt, wird dem binären Suchbaum hinzugefügt, sofern es noch nicht vorhanden ist. Ansonsten geschieht nichts.
Implementieren Sie die beiden Methoden.
Als Lösungsalternative sollen die Kennungen mit Hilfe einer relationalen Datenbank verwaltet werden.
Entwerfen Sie dazu eine ER-Diagramm und geben Sie dazu das Relationenschema an.
In einigen Kreisen kann man bei der Kennzeichenwahl auch das Ortkürzel wählen.)
Dieses hat Auswirkung auf die Modellierung des Verwaltungsprogramm.
Erläutern Sie, welche Probleme bei der bestehenden Modellierung entstehen können und entwickeln Sie, durch welche Änderungen die Modellierung angepasst werden kann.
Die Firma Hotel-Hotel vermittelt verschiedene Hotels an vielen Standorten auf der ganzen Welt, wobei die Anzahl vermittelter Hotels an den Standorten unterschiedlich ist.
Mit einem Hotelbewertungssystem möchte Hotel-Hotel ihren Kunden eine Entscheidungshilfe anbieten, denn immer häufiger ziehen Interessierte vor der Buchung von Hotelaufenthalten Bewertungen anderer Gäste als Grundlage ihrer Entscheidung für oder gegen ein Hotel heran.
Die Gäste werden aus diesem Grund nach ihrem Aufenthalt in einem Hotel gebeten, dieses mit einer ganzzahligen Punktezahl zu bewerten (0 = sehr schlecht bis 10 = sehr gut). Die Bewertungszahl eines Hotels entsteht dann als Durchschnitt (arithmetisches Mittel) aller abgegebenen Bewertungen.
Zur Vereinfachung der Aufgabenstellung gehen wir davon aus, dass die Standortnamen eindeutig sind und nur dann im Datenbestand vorkommen, wenn auch schon mindestens ein Hotel an diesem Standort in das Bewertungssystem aufgenommen wurde. Es gibt an einem Standort keine Hotels mit gleichem Namen.
Eine Softwarefirma hat in einem ersten Arbeitsschritt ein noch vereinfachtes Entwurfsdiagramm für eine Softwarelösung erstellt (siehe Abbildung 1).
In der weiteren Diskussion mit dem Auftraggeber Hotel-Hotel ergibt sich für die Softwarefirma, dass die Standorte in einem binären Suchbaum nach ihrem Namen geordnet verwaltet werden sollen.
Abbildung 1
In den zu Anfang leeren Suchbaum werden die Standorte ”Berlin”, ”Aachen”, ”München”, ”Kopenhagen”, ”Wien”, ”Salzburg”, der Reihe nach eingefügt.
Die Hotels an diesen Standorten sollen in dieser Teilaufgabe zunächst noch nicht berücksichtigt werden.
Stellen Sie den resultierenden binären Suchbaum grafisch dar.
Erläutern Sie, wie innerhalb des binären Suchbaumes die richtige Einfügestelle für den zuletzt einzufügenden Standort ”Salzburg” gefunden wird.
Die Softwarefirma bereitet die Implementation des Hotelbewertungssystems vor und hat sich dafür entschieden, ergänzend zu dem binären Suchbaum für die Standorte die Hotels eines Standortes jeweils in einer linearen Liste zu verwalten.
Entwickeln Sie ein Implementationsdiagramm zum Entwurfsdiagramm (Abbildung 1), in dem die Klassenbeziehungen zur linearen Liste und zum Suchbaum dargestellt werden. In den Klassendiagrammen müssen keine weiteren Attribute und Methoden angegeben werden.
Wandeln Sie das Entwurfsdiagramm der Klasse Standortin ein Implementationsdiagramm um. Geben Sie hier alle Attribute und Methoden an.
Im Folgenden soll die Methode bewerteHotel der Klasse Hotelbewertungssystem entwickelt werden. Dabei dürfen die Methoden aus den Klassendokumentationen (wie z. B. die Methode bewerteHotel der Klasse Standort) verwendet werden.
Implementieren Sie die Methode bewerteHotel.
In der Klasse Hotelbewertungssystem wurden folgende Methoden implementiert.
Das Attribut orte ist eine Referenz auf den binären Suchbaum.
public Hotel gibMirEtwas() {
return gibMirEtwasIntern(orte);
}
private Hotel gibMirEtwasIntern(BinarySearchTree<Standort> pBaum) {
Hotel erg = null;
if (!pBaum.isEmpty()) {
List<Hotel> hotels = pBaum.getContent().gibHotelliste();
hotels.toFirst();
while (hotels.hasAccess() && hotels.getContent().gibBewertungszahl() > 0) {
erg = hotels.getContent();
hotels.next();
}
Hotel links = gibMirEtwasIntern(pBaum.getLeftTree());
if ((links != null) && (links.gibBewertungszahl() < erg.gibBewertungszahl())) {
erg = links;
}
Hotel rechts = gibMirEtwasIntern(pBaum.getRightTree());
if ((rechts != null) && (rechts.gibBewertungszahl() < erg.gibBewertungszahl())) {
erg = rechts;
}
}
return erg;
}
Die Angabe bei den Listenobjekten sind: Hotelname, Anzahl der Bewertungen, Bewertung.
Bestimmen Sie die in der privaten Methode gibMirEtwasIntern angewendete Traversierungsvariante.
Erläutern Sie im Sachzusammenhang, was die Methode gibMirEtwas leistet und wozu sie im Hotelbewertungssystem eingesetzt werden könnte.
Bislang kann die Bewertung anonym erfolgen. Das hat zu Folge, dass das System missbraucht werden kann, indem Kunden beliebig oft ihre Bewertung eingeben können. Um das zu erschweren, möchte das Unternehmen neben der Bewertung die E-Mailadresse mit abspeichern und für jede E-Mailadresse nur eine Bewertung zulassen.
Beschreiben Sie, wie die Modellierung geändert werden müsste. Neben Sie Stellung zur der Frage, was bei diesem Vorgehen aus Datenschutzsicht in beachten ist. Beschreiben Sie hierzu drei Aspekte.
Eine Möglichkeit, Freundschaftsbeziehungen in einer Gruppe von Personen (z. B. einem sozialen Netzwerk) zu veranschaulichen, besteht in der Darstellung aller Freundschaftsbeziehungen in Form eines Graphen. Dabei entspricht jeder Knoten des Graphen einer Person innerhalb der Gruppe, und eine Kante repräsentiert das Freundschaftsverhältnis zwischen den durch die Kante verbundenen Personen. Die Intensität des Freundschaftsverhältnisses wird mithilfe des Kantengewichts modelliert je kleiner das Kantengewicht, desto enger/ stärker ist die Freundschaft der miteinander verbundenen Personen. Besitzt das Kantengewicht einen Wert aus dem Intervall [0 ; 1], so sprechen wir hier von einer dicken Freundschaft.
Kennen sich zwei Personen der Gruppe überhaupt nicht, so existiert auch keine Kante zwischen den beiden Personen, das Freundschaftsverhältnis hat somit den Wert unendlich. Das Freundschaftsverhältnis einer Person zu sich selbst hat stets den Wert 0. Gegeben sei nun die folgende Darstellung der Freundschaftsbeziehungen innerhalb einer Gruppe:
Abbildung 1
Stellen Sie den Graphen aus der obigen Abbildung 1 als Adjazenzmatrix dar. Kürzen Sie in Ihrer Darstellung die Vornamen durch den jeweiligen Anfangsbuchstaben ab. Stellen Sie den Graphen auch als Adjazenzliste dar. Erläutern Sie, inwiefern die Modellierung des Graphen mit einer Adjazenzliste im Vergleich zur Modellierung mit einer Adjazenzmatrix im gegebenen Sachzusammenhang sinnvoll ist.
Der Freundschaftsgraph soll in der Datenstruktur eines Graphen gespeichert werden, um ihn mit informatischen Methoden auswerten zu können. Es sind die Klassen Graph, Vertex und Edge gegeben. Im folgenden Implementationsdiagramm werden die Klassenbeziehungen verdeutlicht. Der Name einer Person werde in dem Namensattribut des Knotens gespeichert.
Abbildung 2
Erläutern Sie die beiden dargestellten Beziehungen zwischen den Klassen. Implementieren Sie die Klasse Personvollständig. Implementieren Sie die Methode initialisiereBeispielgraph der Klasse Freundschaftsgraph für den folgenden Teilgraphen:
Gegeben ist die die folgende Methode der Klasse Freunschaftsgraph.
public List<Person> gibGruppenmitglieder(Person pPerson)
{
pPerson.setMark(true);
List<Person> ergebnis = new List<Person>();
ergebnis.append(pPerson);
List<Vertex> freundeListe = personenGraph.getNeighbours(pPerson);
freundeListe.toFirst();
while (freundeListe.hasAccess()) {
Person freund = (Person) freundeListe.getContent();
if (!freund.isMarked()) {
List<Person> gruppenmitglieder = gibGruppenmitglieder(freund);
ergebnis.concat(gruppenmitglieder);
}
freundeListe.next();
}
return ergebnis;
}
Stellen Sie den Ablauf der Methode am Beispiel des Aufrufs mit der Person mit dem Namen „Carla“ geeignet dar, indem Sie die Belegung der Variablen ergebnis, freundeListeund freundprotokollieren.
Erläutern Sie, weshalb eine Markierung der Personen/Knoten des Graphen für die Terminierung des Algorithmus wichtig ist.
Erläutern Sie, weshalb die oben angegebene Methode eine Liste entsprechend der Dokumentation der Klasse Freundschaftsgraph im Anhang erzeugt und zurückgibt.
Implementieren Sie die Methode existierenDickeFreunde der Klasse Freundschaftsgraph.
Dokumentieren Sie Ihre Lösung durch geeignete Kommentare.
Henri und Carla werden dicke Freunde, genauso Dana und Felix. Henri lernt außerdem Emil kennen und befreundet sich mit ihm. Der neue Freundschaftsgraph hat dann folgendes Aussehen:
Je besser zwei Personen befreundet sind, desto schneller wird eine Neuigkeit zwischen den beiden Personen ausgetauscht. Die Zeit, die für den Austausch der Neuigkeit benötigt wird, soll hier vereinfacht dem Wert des Freundschaftsverhältnisses entsprechen.
Aron hat die Neuigkeit erfahren, dass der Informatiklehrer erkrankt ist, und verbreitet diese in der in obigen Abbildung dargestellten Personengruppe.
Bestimmen Sie mithilfe des Verfahrens von Dijkstra die Wege, auf denen die Neuigkeit am schnellsten bis zu Henri und bis zu Emil übermittelt wird und geben Sie diese an. Stellen Sie dabei die Schritte zur Bestimmung der kürzesten Wege geeignet dar. Beurteilen Sie die dargestellte Modellierung von Freundschaftsbeziehungen innerhalb einer Personengruppe als Graph im Allgemeinen und die Anwendbarkeit des Verfahrens von Dijkstra für die Lösung dieser Aufgabenstellung im Speziellen.
Freunschaftsbeziehungen können auch in einer Datenbank verwaltet werden.
Entwickeln Sie eine Datenbankmodellierung in Form eines Entity-Relationship-Diagramms, welche die Speicherung aller Personen und deren Freundschaftsbeziehungen zueinander ermöglicht.
Erläutern Sie Ihre Modellierung. Entwickeln Sie eine Datenbankabfrage, die auf Grundlage Ihrer Datenbankmodellierung alle Personenpaare ausgibt, die "dicke Freunde" sind.
Quelle: https://nwm2.net-schulbuch.de/index.php
