UE AlgoDat1 - Angabe SS 99 (TU Wien)

Inhalt
Allgemeine Hinweise zu den Übungsbeispielen
A1 Mengenlehre
A2 Zahlenliste
A3 Wortliste
A4 Gruppeneinteilung
A5 Hörsaalreservierung
B1 Filmdatenbank
B2 Interpreter
B3 CD-Verwaltung
B4 Stücklistenverwaltung
B5 Dateisystem
C1 Tabellenkalkulation
C2 Flugplaner
C3 Scheduling

 

Allgemeine Hinweise zu den Übungsbeispielen

Beispielzuteilung

Im Laufe des Semesters sind drei Programmieraufgaben am Computer auszuarbeiten. In jeder Beispielgruppe gibt es mehrere Beispiele, von denen Ihnen jeweils eines entsprechend Ihrer Matrikelnummer wie folgt zugeteilt ist:

• Beispielgruppe A: (letzte Stelle der Matrikelnummer mod 5) + 1
  (z.B.: Matrikelnummer xxxxxx7: (7 mod 5) + 1 = 3 -> Beispiel A3)
• Beispielgruppe B: (vorletzte Stelle der Matrikelnummer mod 5) + 1
  (z.B.: Matrikelnummer xxxxx5x: (5 mod 5) + 1 = 1 -> Beispiel B1)
• Beispielgruppe C: (Matrikelnummer mod 3) + 1
  (z.B.: Matrikelnummer 3333334: (3333334 mod 3) + 1 = 2 -> Beispiel C2)

Zur Erinnerung: Für natürliche Zahlen n und m versteht man unter "n mod m" den Rest, den man bei Division von n durch m erhält.

Achtung: Die Beispielzuteilung ist obligatorisch!
Vergewissern Sie sich rechtzeitig, daß Sie aus jeder Gruppe das richtige Beispiel programmieren. Bei der Abgabe werden ausnahmslos nur solche Beispiele angenommen, die Ihnen zugeteilt sind! Wenn Sie mit einem falschen Beispiel bei der Abgabe erscheinen, gilt das Beispiel als nicht abgegeben.

Abgaberichtlinien

Ein Beispiel wird von den Tutoren nur angenommen, wenn es den folgenden Anforderungen genügt.

Beachten der Übungsangabe

Alle in den Übungsangaben geforderten Eigenschaften und Funktionen des Programms müssen einwandfrei funktionieren und auf jene Art und Weise implementiert werden, wie es in den Angaben gefordert wird.

Funktionsfähigkeit:

Das Programm muß die gestellte Aufgabe funktionsfähig implementieren. Testen Sie Ihr Programm daher mit möglichst vielen verschiedenartigen Eingabedaten, um sicherzustellen, daß auch Sonderfälle korrekt funktionieren!

Verwenden Sie nicht zu viele maschinenspezifische Fähigkeiten Ihres Compilers. Das Programm muß auf den Abgabegeräten (Turbo Pascal 6.0) compilierbar sein. Probieren Sie daher Programme, die Sie auf dem eigenen Computer entwickelt haben, rechtzeitig vor der Abgabe auch auf den Computern im Übungsraum aus!

Ordentlicher Programmierstil:

Dazu gehört unter anderem:

• strukturierte Programmierung, erkennbare Strukturen
• modularer Aufbau
• klar definierte Funktionalität von Programmteilen
• nachvollziehbare Gedankengänge bei Algorithmen
• klare Begriffe der Variablen
• prägnante Bezeichner für selbstdefinierte Datenstrukturen und Prozeduren bzw. Funktionen
• Funktionen ohne Nebenwirkungen
• keine undurchschaubaren Programmtricks, keine Sprünge, etc.
• Verwendung von Einrückungen entsprechend den Programmstrukturen
• Leerzeilen zur klaren Trennung von Abschnitten im Programmtext

Kommentare:

Ein Kommentar ist eine Dokumentation des Programms innerhalb des Quelltextes und ist immer in natürlicher Sprache abzufassen. Schreiben Sie Kommentare unbedingt immer schon während der Programmerstellung und nicht im nachhinein.

Am Anfang eines Programms (Programmkopf) muß mindestens folgendes kommentiert werden: Name des Autors, Matrikelnummer, Studienkennzahl, Datum der Ersterstellung und Datum der letzten Änderung.

Selbstdefinierte Datentypen und Variablen sollten dann kommentiert werden, wenn sie wesentliche Bedeutung für das Programm haben und/oder ein komplexe Struktur aufweisen.

Bei Prozedur- und Funktionsdefinitionen sollte die Aufgabe der Routine, die Bedeutung der Eingangs- und Ausgangsparameter und die verwendeten globalen Variablen angeführt werden, eventuell verwendete besondere Algorithmen sollten ebenfalls festgehalten werden.

Absturzsicherheit:

Bei jeder Eingabemöglichkeit (auch von Dateien), die Sie in Ihrem Programm für den Benutzer vorsehen, sollte überlegt werden, welche Möglichkeiten es gibt, das Programm zu Fehlverhalten oder gar zum Absturz zu bringen und wie dies vermieden werden kann. Beispielsweise sollten falsche Eingaben mit Fehlermeldungen quittiert werden und angezeigt werden, welche Eingaben zulässig sind.

Sachlichkeit:

Bunt blinkende Bildschirme und den Yankee-Doodle piepsende Sortierprogramme beeindrucken keinen Abgabetutor und schon gar nicht den Übungsbetreuer. Auch die Verwendung des TurboVision-Systems von Turbo Pascal ist weder nötig noch zielführend.

Deshalb: Implementieren Sie einfache, sachliche und vor allem durch ihre Leistungsfähigkeit beeindruckende Programme. Und: Piepsen Sie nicht!

Kenntnis von Programm und Thema:

Bei der Abgabe des Programms stellt Ihnen der Tutor Fragen über das Thema der Vorlesung, das dem Programm zugrunde liegt. Das Vorweisen eines korrekten Programms allein genügt keinesfalls für eine erfolgreiche Abgabe.

Keine Teamwork:

Die Übung ist als Einzelübung konzipiert; Teamwork ist nicht zulässig. Aus diesem Grund werden Beispiele, die offensichtlich kopiert und nicht selbst ausgearbeitet sind, ausnahmslos nicht angenommen!

Programmierhinweise

Menüsteuerung:

Dem Benutzer soll (sofern nicht anders angegeben) bei jedem Beispiel ein (zeilenorientiertes) Menü zur Verfügung gestellt werden, das ihn wiederholt zwischen den verschiedenen angebotenen Programmfunktionen wählen läßt. Auf jeden Fall muß auch ein Menüpunkt für das Programmende vorgesehen sein.

Weitere Informationen

Sehr wichtige Informationen werden in der Vorlesung bekanntgegeben. Sehr viel effizienter werden Sie jedoch über das Internet informiert. Dazu müssen Sie zunächst in den Benutzerräumen des EDV-Zentrums einen eigenen Account beantragen, sofern Sie dies nicht schon getan haben. Mit diesem Account können Sie die elektronischen Aushänge (WWW, News) lesen, und per email mit uns kommunizieren, was Ihnen unter Umständen einen Besuch in der Sprechstunde erspart. Sollten Sie - warum auch immer - keinen Account in den Benutzerräumen haben/bekommen, stehen Ihnen im großen Übungsraum des Informatiklabors (Hauptgebäude, Stiege 5, 1. Stock) einige PCs zur Verfügung, um auf die Web-Seiten des Instituts zugreifen zu können.

Folgende URLs sind für Sie wichtig:

Informationen zur AlgoDat1-Laborübung:

http://www.apm.tuwien.ac.at/teaching/LVA/186428.html

AlgoDat1-Übungsaufgaben:

http://www.apm.tuwien.ac.at/teaching/LVA/AlgoDat1/

Informationen zur AlgoDat1-Vorlesung:

http://www.cg.tuwien.ac.at/courses/AlgoDat1/VO.html

Anmerkung: Alle Personenbezeichnungen sind geschlechtsneutral zu verstehen, auch wenn in dieser Beispielsammlung aus Gründen der leichteren Lesbarkeit die männliche Bezeichnung verwendet wird.

A1 Mengenlehre

Gegeben seien bis zu 10 Mengen, deren Elemente Zahlen sind. Schreiben Sie ein Programm, welches die Anwendung von Mengenoperatoren auf diese Mengen erlaubt. Die Mengen sind in einer Datei gespeichert, die pro Zeile eine Menge enthält. Die Elemente sind durch Leerzeichen voneinander getrennte Zahlen (Integer) in beliebiger Reihenfolge. Es sind keine doppelten Elemente in einer Menge erlaubt. Es ist aber möglich, daß eine Menge leer ist (nur Zeilenvorschub).

Beispiel für das Dateiformat:

     15 34 5 2

     45
     56 29 36
     ...

Das Programm soll menügesteuert folgende Funktionen bieten:

• Definieren einer Menge: Der Benutzer hat die Nummer der Menge (1...10) und alle ihre Elemente (Integer-Zahlen in beliebiger Reihenfolge) anzugeben.
• Vereinigung zweier Mengen: Menge1 ODER Menge2
• Durchschnitt zweier Mengen: Menge1 UND Menge2
• Differenz zweier Mengen: Menge1\Menge2
• Ausgabe aller Mengen: Alle Mengen sind fortlaufend numeriert auszugeben. Die Elemente sollen dabei aufsteigend sortiert sein. Auch die leeren Mengen sollen angezeigt werden und einen entsprechenden Vermerk bekommen.
• Laden und Speichern aller Mengen (beliebig wählbare Datei).

Bei der Vereinigung, dem Durchschnitt und der Differenz zweier Mengen sollen drei Mengen durch Eingabe ihrer Nummern gewählt werden können. Auf die ersten beiden soll die Operation angewendet werden, in die dritte soll das Ergebnis geschrieben werden. Danach sollen alle drei Mengen am Bildschirm ausgegeben werden.

Datenstruktur

Die 10 Mengen sind in einem Feld zu verwalten. Jede Menge soll durch eine aufsteigend sortierte lineare Liste repräsentiert werden. Beachten Sie, daß auch das Ergebnis einer Mengenoperation wieder eine aufsteigend sortierte Liste sein muß.

A2 Zahlenliste

Schreiben Sie ein Programm, das eine Folge von ganzen Zahlen im Bereich [-32000, 32000] verwaltet. Die Zahlen sind in einer Textdatei gespeichert (nicht notwendigerweise sortiert), jede Zahl steht in einer eigenen Zeile. Beispiel für das Dateiformat:

     15
     2048
     111
     ...

Das Programm soll menügesteuert folgende Funktionen bieten:

• Einfügen einer Zahl in eine absteigend sortierte Folge.
• Löschen einer Zahl aus der absteigend sortierten Folge (wenn die Zahl mehr als einmal vorkommt, soll sie nur genau einmal entfernt werden).
• Invertierung der Folge (d.h. die Reihenfolge der Elemente in der Folge soll umgekehrt werden), wobei das Ergebnis der Invertierung in eine zweite Liste geschrieben und anschließend ausgegeben werden soll.
• Ausgabe der gesamten sortierten Folge.
• Zählen, wie oft eine vom Benutzer angegebene Zahl in der Folge vorkommt.
• Ausgabe der Anzahl der verschiedenen Zahlen in der Folge (d.h., mehrfach vorkommende Zahlen werden nur einmal gezählt).
• Laden und Speichern der Zahlenfolgen (beliebig wählbare Datei).

Datenstruktur

Die Zahlen sollen in einer absteigend sortierten linearen Liste gespeichert werden. Als Schlüssel eines Listeneintrags dient die Zahl selbst.

A3 Wortliste

Schreiben Sie ein Programm, das eine Wortliste verwaltet. Die Wörter sind in einer Textdatei gespeichert, jedes Wort (max. 70 Zeichen, nur Buchstaben) steht in einer eigenen Zeile.

Beispiel für das Dateiformat:

     schreiben
     Programm
     Wortliste
     ...

Das Programm soll menügesteuert folgende Funktionen bieten:

• Einfügen eines Wortes in die sortierte Wortliste.
• Löschen eines Wortes aus der sortierten Wortliste.
• Ausgabe der gesamten Wortliste in alphabetischer Sortierung (nach Rückfrage aufsteigend oder absteigend).
• Ausgabe der gesamten Wortliste nach der Wortlänge (nach Rückfrage aufsteigend oder absteigend).
• Ausgabe einer aufsteigend sortierten Liste von Wortlängen und der entsprechenden Anzahl der Wörter mit dieser Länge, z.B.:

       8 Zeichen: 2 Woerter
       9 Zeichen: 1 Wort
       ...

• Laden und Speichern der Wortliste (beliebig wählbare Datei).

Datenstruktur

Die Wörter sollen in einer mehrfach verketteten Liste gespeichert werden, die nach zwei Suchkriterien sortiert ist:

• alphabetisch
• nach der Anzahl der Zeichen in einem Wort

Für jedes Suchkriterium soll die Liste doppelt verkettet werden, d.h. es soll jeweils einen Vorwärts- und einen Rückwärtszeiger geben.

Es sollen keinesfalls zwei sortierte Listen verwendet werden!

A4 Gruppeneinteilung

Die Teilnehmer an der Übung AlgoDat 1 sollen in verschiedene Gruppen eingeteilt werden. Entwerfen Sie ein Programm, das eine solche Gruppeneinteilung nach verschiedenen Kriterien erlaubt.

Die Teilnehmerdaten sind in Form einer Textdatei gespeichert. Jede Zeile enthält, mit Leerzeichen getrennt, die Matrikelnummer und den Namen (max. 22 Zeichen) eines Teilnehmers.

Beispiel für das Dateiformat:

     3333333 Muster Max
     4444444 Beispiel Birgit
     ...

Dem Benutzer sollen menügesteuert folgende Funktionen zur Verfügung gestellt werden:

• Einlesen von Teilnehmerdaten aus einer beliebig wählbaren Datei in eine lineare Liste.
• Abbilden einer Matrikelnummer auf eine Gruppennummer, wobei der Benutzer aus drei verschiedenen Kriterien (Abbildungsfunktionen) eines wählen kann.
• Ausgabe einer Statistik mit Gesamtzahl der Teilnehmer und Anzahl der Teilnehmer jeder Gruppe. Beachten Sie, daß je nach Wahl des Unterteilungskriteriums verschiedene Gruppenzahlen auftreten können!
• Zuweisen der Teilnehmer an die Gruppen und anschließende Ausgabe einer nach Namen sortierte Liste für jede Gruppe.

Zur Realisierung des Programms schreiben Sie bitte neben geeigneten Funktionen bzw. Prozeduren, die die obengenannten Aufgaben erledigen, die folgenden zwei Funktionen:

• Abbilden einer Matrikelnummer auf eine Gruppennummer: Schreiben Sie folgende drei Abbildungsfunktionen. Jede Abbildungsfunktion soll auf die Matrikelnummer i eines Teilnehmers angewandt werden können und als Rückgabewert die Gruppennummer liefern, die dem betreffenden Teilnehmer zugewiesen wird.
  1. f1(i):= (i mod 5) + 1
  2. f2(i):= ((i+2) mod 4) + 1
  3. f3(i):= (i mod 3) + 1
• Zuweisen der Teilnehmer an die Gruppen: Schreiben Sie eine Funktion, die eine der obigen Abbildungsfunktionen auf alle Elemente der Teilnehmerliste anwendet und das Ergebnis jeweils in einer dafür vorgesehenen Komponente vermerkt. Die Abbildungsfunktion soll als Parameter an die Funktion übergeben werden (siehe Abschnitt ``Funktionsparameterübergabe in Turbo Pascal'').

Datenstruktur

Als Datenstruktur für die Teilnehmerliste verwenden Sie bitte eine einfach verkettete lineare Liste, deren Elemente mit den folgenden Komponenten ausgestattet sein sollen: Name, Matrikelnummer (LongInt) und Gruppennummer (Integer).

Funktionsparameterübergabe in Turbo Pascal Um eine Funktion als Parameter an eine Funktion oder Prozedur übergeben zu können, müssen Sie zunächst einen entsprechenden Funktionstyp deklarieren und die Funktionsvariable in der Parameterliste diesem Typ zuordnen. In unserem Fall könnte das dann beispielsweise so aussehen:

• Typdefinition mapfunc für Funktionen, die als Übergabeparameter einen Wert vom Typ longint akzeptieren und als Rückgabewert einen Integerwert liefern:

       type mapfunc = function (i:longint):integer;

• Beispiel für einen Funktionskopf, der es erlaubt Funktionen vom Typ mapfunc zu übergeben:

       function map (l:list; f: mapfunc): list;

• Funktionen, die man als Parameter an eine andere Funktion übergeben möchte, müssen mit dem Schlüsselwort far gekennzeichnet werden, z.B.:

       function f1 (i: longint):integer; far;

Ein Aufruf der Funktion map könnte jetzt z.B. folgende Form haben:

     gruppenliste := map(namensliste,f1);

A5 Hörsaalreservierung

Entwickeln Sie ein Programm zur Verwaltung von Hörsaalreservierungen. Dem Benutzer sollen folgende Möglichkeiten zur Verfügung stehen:

• Neuen Hörsaal mit eindeutigem Namen (max. 10 Zeichen) aufnehmen.
• Reservierung für bestehenden Hörsaal aufnehmen: Dazu ist vom Benutzer neben dem Hörsaal ein Name (max. 12 Zeichen), das Datum (Format TT.MM.JJJJ) sowie eine Beginn- und Endzeit (Format jeweils HH:MM) anzugeben.

  Eine neue Reservierung darf nur angenommen werden, wenn sie nicht mit bestehenden Reservierungen kollidiert! Außerdem ist eine Reservierung generell nur für Zeiten von 7:00 Uhr bis 22:00 Uhr möglich.

• Auflisten aller Hörsäle in alphabetischer Reihenfolge mit allen Reservierungen in zeitlicher Reihenfolge in übersichtlicher Form.
• Löschen einer Reservierung: Vom Benutzer muß Hörsaal, Datum und Beginnzeit angegeben werden.
• Löschen eines Hörsaals mit allen gespeicherten Reservierungen.
• Laden und Speichern der aktuellen Daten (beliebig wählbare Datei).

Beim Laden und Speichern soll folgendes Dateiformat verwendet werden: Für alle Hörsäle: Hörsaalname in einer eigener Zeile, dann Reservierungen für diesen Hörsaal jeweils in einer eigenen Zeile mit Name, Datum, Beginnzeit und Endzeit (durch Leerzeichen getrennt). Alle Reservierungszeilen beginnen dabei mit einem Tabulatorzeichen. Beispiel für das Dateiformat:

     HS1
             Kodydek 01.01.1999 07:00 10:30
             Buehler 24.12.1999 09:30 10:45
     FH7
             Huber 07.04.1999 14:30 16:30
     ...

Datenstrukturen

Zur Verwaltung aller Hörsäle ist eine alphabetisch sortierte lineare Liste zu verwenden. Zu jedem Hörsaal soll jeweils eine weitere, nach Beginnzeiten sortierte lineare Liste zur Verwaltung der Reservierungsdaten eingesetzt werden.

B1 Filmdatenbank

Schreiben Sie ein Programm, welches dazu dient, Filme und Schauspieler zu verwalten. Die nötigen Daten sind in einer Datei gespeichert. Dabei sind pro Zeile ein Filmtitel (max. 30 Zeichen) und der Name des mitspielenden Schauspielers (max. 30 Zeichen) durch ein Komma voneinander getrennt eingetragen. Jeder Schauspieler kann in verschiedenen Filmen mitspielen. Ebenso können jedem Filmtitel mehrere Schauspieler zugeordnet sein.

Beispiel für das Dateiformat:

     Snake Eyes,Nicolas Cage
     The Rock,Nicolas Cage
     The Rock,Sean Connery
     ...

Das Programm soll menügesteuert folgende Funktionen bieten:

• Einfügen einer neuen Zuordnung Film/Schauspieler.
• Löschen eines Schauspielers.
• Suchen nach einem Film und alphabetische Ausgabe aller zugeordneten Schauspieler.
• Suchen nach einem Schauspieler und alphabetische Ausgabe aller zugeordneten Filme.
• Ausgabe der Liste aller Filme mit allen zugeordneten Schauspielern: Die Filme können in der Reihenfolge, wie sie in der Hashtabelle stehen, ausgegeben werden. Unter jedem Film sollen eingerückt in alphabetischer Reihenfolge die jeweils zugeordneten Schauspieler stehen.
• Laden und Speichern der aktuellen Daten (beliebig wählbare Datei).

Datenstruktur

Zum Speichern der Filme bzw. Schauspieler verwenden Sie jeweils eine eigene Hashtabelle mit äußerer Verkettung. Zu jedem Film ist eine alphabetisch sortierte lineare Liste mit Verweisen auf die dazugehörigen Schauspieler zu speichern. Umgekehrt soll aber auch für jeden Schauspieler eine alphabetisch sortierte lineare Liste mit Verweisen auf die dazugehörigen Filme verwaltet werden.

Beim Löschen eines Schauspielers ist zu beachten, daß auch alle Referenzen auf ihn in Filmen gelöscht werden müssen. Falls ein Film dadurch ohne Schauspieler ist, muß auch der Film entfernt werden.

Alle Listen und Hashtabellen sollen auf den selben Daten operieren, es sollen keine Daten mehrfach abgespeichert werden!

B2 Interpreter

Entwickeln Sie einen Interpreter für eine einfache Programmiersprache, die Berechnungen mit globalen Integer-Variablen und globalen, parameterlosen Prozeduren erlaubt. Variablen- und Prozedurnamen bestehen nur aus Buchstaben. Alle Befehle und Variablennamen werden in Großbuchstaben konvertiert. Folgende syntaktische Konstrukte sind notwendig (Argumente in eckigen Klammern sind optional, eckige Klammern mit angehängtem Pluszeichen können beliebig oft (auch gar nicht) wiederholt werden, beim senkrechten Strich muß genau eine der durch den Strich getrennten Varianten gewählt werden):

Char: 'A'...'Z'
Digit: '0'...'9'
Int: Digit [ Digit ]+
Id: Char [ Char ]+
Expression: Id | Int |
    '(' Expression '+' Expression ')' | '(' Expression '-' Expression ')' |
    '(' Expression '*' Expression ')' | '(' Expression '/' Expression ')'

Der Interpreter soll eine Sequenz von Kommandos der folgenden Art von einer Datei lesen und abarbeiten können:

Command:
    'LET ' Id ':=' Expression |
    'WRITE ' Expression |
    'CALL ' Id |
    'PROCEDURE ' Id ':' |
    'END'

Jede Zeile enthält genau ein Command. Whitespaces (Leerzeichen, Tabulator) sind zu überlesen. Nachdem der Interpreter alle Zeilen eingelesen hat, soll das Programm interpretiert werden. Sie können davon ausgehen, daß sich das Hauptprogramm immer nach etwaigen Prozeduren befindet.

Bedeutung der Befehle:

LET:

Der Wert der Expression wird der Variablen zugewiesen. Die Verwendung von Prozedurnamen in LET ist nicht zulässig.

WRITE:

Der Wert der dem Befehl folgenden Expression wird ausgegeben.

PROCEDURE/END:

Mit PROCEDURE wird eine globale, parameterlose Prozedur definiert, die den nach PROCEDURE angegebenen Namen trägt. Geschachtelte Prozedurdefinitionen sind nicht zulässig (muß auch nicht behandelt werden). Alle Commands bis zu END gehören zur Definition der Prozedur.

CALL:

Mit CALL wird die angegebene Prozedur aufgerufen. Nach dem Ende der Abarbeitung der Prozedur wird die Abarbeitung in der Zeile nach dem CALL fortgesetzt. Prozeduraufrufe können auch innerhalb von Prozeduren erfolgen.

Eine mögliche Eingabedatei kann so aussehen:

	PROCEDURE ZWEIMAL :
	  LET RES:=(B*2)
	END

	PROCEDURE BERECHNE :
	  LET B:=WERT
	  CALL ZWEIMAL
	  LET SUM:=RES
	  LET B:=5
	  CALL ZWEIMAL
	  LET SUM:=(SUM+RES)
	END

	LET WERT=6
	CALL BERECHNE
	WRITE SUM

Die Ausgabe dieses Programms ist "22".

Datenstrukturen

Vor der eigentlichen Abarbeitung des Programms muß ein Verzeichnis aller Variablen- und Prozedurnamen aufgebaut werden. Verwenden Sie hierzu eine Hashtabelle, in der eine gegebene Variable oder Prozedur bei der eigentlichen Abarbeitung rasch gefunden werden kann. Bei Variablen kann der aktuelle Wert mitgespeichert werden. Im Fall von Prozeduren ist eine lineare Liste für alle ihre Anweisungen zu speichern. Jede Anweisung wird durch einen entsprechenden Parse-Tree repräsentiert.

Damit während der Interpretation eines Programms nach der Abarbeitung einer Prozedur der Programmablauf an der richtigen Stelle fortgesetzt werden kann, werden Rücksprungreferenzen (Verweise auf die einem Aufruf folgende Anweisung) in Form eines Stacks verwaltet.

B3 CD Verwaltung

Entwickeln Sie ein Programm zur Verwaltung von CDs. Die nötigen Daten sind in einer Datei gespeichert. Dabei sind pro Zeile der Name eines Interpreten (max. 30 Zeichen) und, durch ein Komma getrennt, der dazugehörige Titel der CD (max. 30 Zeichen) eingetragen. Zu einem Interpreten können mehrere CD-Titel existieren. Ein CD-Titel dagegen ist genau einem Interpreten zugeordnet.

Beispiel für das Dateiformat:

     U2,Joshua Tree
     U2,One
     REM,Out of Time
     ...

Das Programm soll menügesteuert folgende Funktionen bieten:

• Einfügen eines neuen CD-Titels und des zugehörigen Interpreten.
• Suche nach einem Interpreten und alphabetische Ausgabe aller zugeordneten CD-Titel.
• Suche nach einem CD-Titel und Ausgabe des Interpreten.
• Löschen eines CD-Titels (falls dadurch zu einem Interpreten kein CD-Titel mehr existiert, soll auch der Interpret gelöscht werden).
• Alphabetische Ausgabe aller Interpreten mit allen zugeordneten CDs.
• Laden und Speichern der Daten (beliebig wählbare Datei).

Datenstruktur

Verwenden Sie zur Speicherung der Interpreten einen binären Baum. Die CD-Titel sollen in einer Hashtabelle mit äußerer Verkettung verwaltet werden. Bei jedem CD-Titel speichern Sie auch einen Verweis auf den jeweiligen Interpreten.

Um auch effizient alle CD-Titel für einen bestimmten Interpreten zu finden, verwalten Sie noch zusätzlich bei jedem Interpreten eine alphabetisch sortierte Liste mit Verweisen auf alle seine CD-Titel.

Alle Listen und Hashtabellen sollen auf den selben Daten operieren, es sollen keine Daten mehrfach abgespeichert werden!

B4 Stücklistenverwaltung

Für einen Fertigungsbetrieb sollen alle Komponenten, aus denen ein zu fertigendes Produkt besteht, in Form einer hierarchischen Stückliste verwaltet werden.

Ein Produkt besteht dabei aus mehreren Komponenten, die selbst wiederum aus beliebig vielen anderen Komponenten zusammengesetzt werden können. Für jede Komponente wird zusätzlich vermerkt, wieviel Stück von ihr benötigt werden, um eine Einheit der übergeordneten Komponente zu fertigen. Der Einfachheit halber ist es nicht möglich, daß eine Komponente an verschiedenen Stellen in der Produkthierarchie vorkommt.

Das Programm soll menügesteuert folgende Funktionen bieten:

• Hinzufügen einer Unterkomponente (Name und Stückzahl) zu einer vom Benutzer angegebenen Komponente.
• Löschen einer Komponente und aller ihrer Unterkomponenten (auch den Verweis auf diese Komponente löschen).
• Ausgabe einer Liste aller nicht mehr weiter unterteilten Komponenten mit der jeweils benötigten Gesamtstückzahl.
• Ausgabe einer Liste aller Komponenten für das Produkt und ihrer bei der Eingabe bzw. beim Einlesen angegebenen Stückzahlen, wobei Unterkomponenten eingerückt unter den jeweiligen übergeordneten Komponenten stehen sollen.
• Berechnen der für die Fertigung des Produktes benötigten Gesamtstückzahl einer vom Benutzer angegebenen Komponente.
• Ausgabe einer alphabetischen Liste aller für das Produkt verwendeten Komponenten und der jeweiligen benötigten Gesamtstückzahlen.
• Laden und Speichern der aktuellen Produkthierarchie (beliebig wählbare Datei).

Die Gesamtstückzahl einer Komponente ist zu ermitteln, indem die Stückzahl der Komponente mit den Stückzahlen ihrer übergeordneten Komponenten multipliziert wird.

Beim Laden und Speichern sind die Daten hierarchisch (Preorder) aufgelistet. Jede Komponente steht in einer eigenen Zeile. Sie besteht aus der Hierarchieebene (Integer), die beim Produkt mit 0 beginnt, dem Namen (max. 30 Zeichen, nur Buchstaben) und der Stückzahl (Integer), die benötigt wird, um eine Einheit der übergeordneten Komponente zu fertigen. Die Informationen sind durch Leerzeichen voneinander getrennt.

Beispiel für das Dateiformat:

     0 Fahrzeug 1
     1 Rad 4
     2 Schraube 4
     2 Felge 1
     2 Reifen 1
     1 Motor 1
     ...

Datenstruktur

Um die Suche nach Komponenten effizient zu gestalten, sollen die Komponenten in Form eines binären Baumes gespeichert werden. Für jede Komponente ist dabei der Name, die Stückzahl, ein Verweis auf die übergeordnete Komponente (brauchbar beim Löschen einer Komponente) sowie eine lineare Liste mit Verweisen auf alle Unterkomponenten zu speichern.

B5 Dateisystem

Implementieren Sie eine Simulation für ein Dateisystem. Das Programm soll den Inhalt eines Verzeichnisses (in Listenform) alphabetisch sortiert anzeigen. Ein Verzeichniseintrag kann entweder eine Datei oder ein Verzeichnis sein.

Über die Eingabe von Kommandos sollen folgende Operationen ausgeführt werden können:

• Verzeichnis wechseln (wenn der ausgewählte Eintrag ein Verzeichnis ist). Vergessen Sie nicht, eine Funktion zum Wechseln in das übergeordnete Verzeichnis vorzusehen! cd Name
• Eintrag kopieren: cp Quelle Ziel
• Eintrag verschieben: mv Quelle Ziel
• Eintrag löschen: rm Name
• Eintrag umbenennen: rn alterName neuerName
• neues Verzeichnis anlegen: md Name
• neue Datei anlegen (diese Funktion ist nötig, weil hier die Dateien nicht von Applikationen erzeugt werden): mf Name
• Laden und Speichern des Dateisystems: load Dateiname bzw. save Dateiname

Ist der ausgewählte Eintrag beim Kopieren, Verschieben oder Löschen ein Verzeichnis, muß die Operation auf alle Dateien bzw. Unterverzeichnisse angewendet werden. Die Quelle bezieht sich jeweils auf einen Eintrag aus dem aktuellen Verzeichnis, daher reicht der Name des Eintrags aus. Beim Ziel dagegen muß der gesamte Pfad mitangegeben werden (z.B. beim Kopieren: cp Datei1 Wurzel/VerzeichnisB/Datei3). Die Operationen Löschen, Umbenennen, Verzeichnis-Anlegen und Datei-Anlegen beziehen sich immer nur auf Einträge des aktuellen Verzeichnisses und benötigen daher keine Pfadangabe. Nach jeder Operation muß die Anzeige am Bildschirm aktualisiert werden. Nach dem Laden eines Dateisystems soll das Hauptverzeichnis angezeigt werden.

Beim Laden und Speichern hat das Dateiformat wie folgt auszusehen: Das Dateisystem ist in Preorder in einer Textdatei gespeichert, d.h. übergeordnete Verzeichnisse kommen immer zuerst. Zu jedem Eintrag wird die Hierarchieebene (Integer, Wurzelebene = 0) und ein Name (max. 30 Zeichen, nur Buchstaben), mit Leerzeichen voneinander getrennt, gespeichert. Jeder Eintrag steht in einer eigenen Zeile.

Beispiel:

     Wurzel---VerzeichnisA---Datei1
       !        +------------Datei2
       +------VerzeichnisB---VerzeichnisC---Datei3
                +------------VerzeichnisD

Ergibt folgende Datei:

     0 Wurzel
     1 VerzeichnisA
     2 Datei1
     2 Datei2
     1 VerzeichnisB
     2 VerzeichnisC
     3 Datei3
     2 VerzeichnisD

Datenstruktur

Von der Struktur her ist ein Dateisystem (das keine symbolischen Verweise unterstützt) äquivalent einem allgemeinen Baum. Dateien sind immer Blätter, Unterverzeichnisse im allgemeinen Zwischenknoten (ausgenommen leere Verzeichnisse). Jeder Eintrag hat einen "Backpointer" auf den Vaterknoten (Wurzel: nil), damit man den Baum auch in umgekehrter Richtung (vom Blatt zur Wurzel) durchwandern kann.

Doppelte Einträge in einem Verzeichnis sind verboten (Achtung bei Kopierfunktion etc.). Der Inhalt von Dateien muß nicht repräsentiert werden.

Aktueller Hinweis zum Übungsbeispiel B5 "Dateisystem"

Die Spezifikation des Dateiformats dieses Beispiels hat sich leider als etwas unzureichend erwiesen: Beim Laden aus einer Datei kann unter Verwendung des gegebenen Dateiformats in der jeweils untersten Verzeichnisebene nicht unterschieden werden, ob es sich um ein leeres Verzeichnis oder einfach um eine Datei handelt.

Betrachten Sie daher beim Laden aus einer Datei alle Einträge aus der jeweils untersten Ebene als einfache Dateien. Im genannten Beispiel ist VerzeichnisD also als Datei einzulesen. Erst nachher kann man (interaktiv) auch leere Verzeichnisse hinzufügen. Beim Speichern in die Datei werden dann eventuelle leere Verzeichnisse wieder wie normale Dateien gespeichert - in der Datei ist dann der Unterschied also nicht mehr ersichtlich.

C1 Tabellenkalkulation

Entwickeln Sie eine primitive Tabellenkalkulation. Der Arbeitsbereich sei ein einfacher Textbildschirm, der in 8 Spalten A...H und 16 Zeilen aufgeteilt ist. Ein Feld wird durch den Spaltennamen und die Zeilennummer referenziert (z.B. C6).

Ein Feld kann leer sein oder eine Formel beinhalten, deren aktueller Wert immer am Bildschirm angezeigt werden soll. Formeln bestehen aus Integer-Konstanten, Referenzen auf andere Felder bzw. folgenden Funktionen, die auch beliebig geschachtelt verwendet werden können:

• Binäre Grundrechnungsarten '+', '-', '*', '/' (Punktrechnung vor Strichrechnung!)
• Klammerung mit '(' und ')'
• negatives Vorzeichen '-'
• SUM(Feld1..Feld2): Die Werte aller Formel-Felder im rechteckigen Bereich von Feld1 bis Feld2 werden addiert. Leere Felder werden hierbei ignoriert.

Über die Eingabe von Kommandos soll ein Benutzer die Tabelle manipulieren können:

• Zuweisung einer Formel an ein Feld mit ':=', z.B.: 'C6:=SUM(A3..C6)/(10+G4)'. Die rechte Seite ist dabei immer ein beliebiger Ausdruck in Infix-Notation mit den oben genannten Möglichkeiten.
• Ansicht der Formel eines vom Benutzer angegebenen Feldes in Infix-Notation.
• Löschen eines vom Benutzer angegebenen Feldes bzw. aller Felder.
• Laden und Speichern der gesamten Tabelle (beliebig wählbare Datei).

Beim Laden und Speichern hat das Dateiformat wie folgt auszusehen: Jedes nicht-leere Feld wird in Form einer eigenen Textzeile abgespeichert. Die Syntax dieser Zeile entspricht dabei genau der "händischen" Formelzuweisung, d.h. z.B. 'C6:=SUM(A3..C6)/(10+G4)'. Die Reihenfolge, in der die Felder in der Datei stehen, ist beliebig. Leere Felder werden in der Datei nicht speziell vermerkt.

Datenstruktur

Die Tabelle kann als zweidimensionales Array effizient realisiert werden. Formeln sollen unmittelbar nach der Eingabe bzw. dem Einlesen aus einer Datei geparst und in Form eines Parse-Trees abgespeichert werden. Grundsätzlich und insbesondere bei den Parse-Trees ist auf eine saubere, objekt-orientierte Implementation zu achten. Referenzen auf Felder werden besser nicht durch Zeiger, sondern durch entsprechende Zeilen- und Spaltenindizes gespeichert.

Propagieren von Änderungen

Wird der Inhalt eines Feldes geändert und sein Wert neu ermittelt, so sind die aktuellen Werte aller anderen davon betroffenen Felder ebenfalls neu zu berechnen. Um dies effizient realisieren zu können, ist eine zusätzliche Adjazenzliste zu verwalten, die diese Abhängigkeiten widerspiegelt. D.h., es wird zusätzlich zu einer eventuellen Formel für jedes Feld gespeichert, in welchen anderen Feldern es referenziert wird. Jedenfalls sind unnötige Mehrfachberechnungen bereits bekannter Werte zu vermeiden.

Der der Tabelle zu Grunde liegende Abhängigkeitsgraph muß zyklenfrei sein. Daher darf der Benutzer durch Eingabe neuer Formeln keine Zyklen erzeugen. Dies kann man erreichen, indem man nach Eingabe einer Formel zunächst den Graphen auf Zyklen überprüft. Bei Vorliegen eines Zyklus wird dann einfach die Annahme der Formel verweigert. Der Test auf Zyklenfreiheit erfolgt durch simples Abarbeiten und Markieren des Graphen. Trifft man bei der Suche auf einen bereits markierten Knoten, so liegt ein Zyklus vor.

C2 Flugplaner

Entwickeln Sie einen einfachen Flugplaner, der Ihnen dabei hilft, eine Reise nach bestimmten Kriterien (Preis, Entfernung, Zwischenstops) zusammenzustellen.

Die Flugverbindungen sind in einer Textdatei gespeichert und haben folgende Form: In jeder Zeile stehen jeweils getrennt durch ein Leerzeichen die Namen zweier Flughäfen (jeweils max. 15 Zeichen) für die eine Verbindung besteht, gefolgt vom Flugpreis in Euro (Integer) und der Meilenanzahl (Integer).

Beispiel für das Dateiformat:

     Hamburg Wien 350 608 
     Wien Frankfurt 220 390 
     Düsseldorf Paris 99 263
     ...

Dem Benutzer sollen menügesteuert folgende Funktionen zur Verfügung gestellt werden:

• Hinzufügen einer neuen Flugverbindung.
• Löschen einer bestehenden Flugverbindung.
• Erreichbarkeitstest: Test, ob man von jedem Flughafen zu jedem beliebigen anderen Flughafen (mit eventuellen Zwischenstops) fliegen kann.
• Ausgabe der kürzesten sowie billigsten Verbindung zwischen zwei vom Benutzer angegebenen Flughäfen. Optional soll der Benutzer auch einen fixen Zwischenstop angeben können.
• Ausgabe der billigsten Verbindung zwischen zwei vom Benutzer angegebenen Flughäfen, wobei ein zusätzlich vom Benutzer vorgegebenes Meilenkontingent nicht überschritten werden darf.
• "Nix wie weg": Ausgabe aller möglichen Zielflughäfen, die im Rahmen eines vom Benutzer angegebenen Reisebudgets von einem ebenfalls angegebenen Abflughafen aus erreicht werden können. Die Ausgabe soll nach fallenden Entfernungen sortiert sein.
• Laden und Speichern aller Daten (beliebig wählbare Datei).

Datenstrukturen und Algorithmen

Die dem Programm zugrundeliegende Datenstruktur ist ein gewichteter, ungerichteter Graph, der in Form einer Adjazenzliste verwaltet werden soll: Jedem Flughafen entspricht ein Knoten, jeder Flugverbindung eine Kante mit Preis und Entfernung als Gewichte.

Mittels Priority First Search kann man den optimalen (kürzesten bzw. billigsten) Weg zwischen zwei Flughäfen finden. Als Priority Queue soll ein Heap verwendet werden. Um den Weg am Ende der Berechnungen ausgeben zu können, ist eine Hilfsdatenstruktur notwendig: ein Feld, das für jeden Knoten den Vorgänger im optimalen Weg enthält. Die Werte in diesem Feld werden während der Suche berechnet: Beim Einordnen in den Heap wird für jeden Knoten der Vorgänger ebenfalls im Heap mitgespeichert, beim Entfernen aus dem Heap erhält man den Vorgänger und kann ihn ins Hilfsfeld eintragen. Wenn nun der kürzeste Weg gefunden wurde, können die einzelnen Knoten des schnellsten Weges in umgekehrter Reihenfolge aus dem Feld ausgelesen werden.

C3 Scheduling

In verschiedenen Bereichen wie z.B. dem Projektmanagement tritt oft das Problem auf, eine Menge von Arbeitsvorgängen, die teilweise von einander abhängen, zeitlich so einzuteilen, daß alle Abhängigkeiten erfüllt sind und ein Gesamtziel so rasch wie möglich erledigt werden kann. Entwickeln Sie ein Programm zur Unterstützung dieses Vorgangs.

Das Programm soll menügesteuert folgende Funktionen bieten:

• Verwaltung von Arbeitsvorgängen: Ein Arbeitsvorgang ist durch eine eindeutige Kurzbezeichnung (max. 4 Zeichen), einen ausführlicheren Namen (max. 20 Zeichen) und eine minimale sowie maximale Dauer (in Tagen) definiert. Arbeitsvorgänge sollen neu hinzugefügt, aufgelistet und gelöscht werden können.
• Verwaltung von Abhängigkeiten: Für jeden existierenden Arbeitsvorgang A soll vermerkt werden, von welchen Vorarbeiten dieser unmittelbar abhängt, d.h. welche anderen Arbeitsvorgänge vor Beginn von A bereits abgeschlossen sein müssen. Derartige Abhängigkeiten sollen neu hinzugefügt, für einen ausgewählten Arbeitsvorgang aufgelistet und gelöscht werden können.

  Beim Hinzufügen einer neuen Abhängigkeit ist zu überprüfen, ob diese einen Zyklus in den Abhängigkeitsgraphen bringen würde (ein Arbeitsvorgang ist direkt oder indirekt von sich selbst abhängig). Sollte dies der Fall sein, so darf die Abhängigkeit nicht aufgenommen werden.

  Werden Arbeitsvorgänge gelöscht, so sind auch die damit in Zusammenhang stehenden Abhängigkeiten zu löschen.

• Auflisten aller Arbeitsvorgänge, die unmittelbar, d.h. ohne Abschluß irgendwelcher Vorarbeiten, angefangen werden können (Startknoten).
• Auflisten aller Arbeitsvorgänge, die selbst keine Voraussetzung für weitere Arbeitsvorgänge darstellen (Zielknoten).
• Linearisierung: Zur Erledigung (a) eines vom Benutzer anzugebenden Arbeitsvorgangs oder (b) aller Arbeitsvorgänge soll eine mögliche Reihenfolge aller (notwendigen) Arbeitsvorgänge ausgegeben werden, die alle Abhängigkeiten erfüllt. Dazu ist auch die minimale sowie maximale Gesamtdauer auszugeben.
• Berechnung des kritischen Pfades und der maximalen Gesamtdauer bei bestmöglicher Parallelisierung: Es wird angenommen, daß Arbeitsvorgänge, deren Voraussetzungen erfüllt sind, immer sofort und gleichzeitig ausgeführt werden können. Wie hoch ist die maximale Gesamtdauer bis zur Erledigung eines vom Benutzer angegebenen Arbeitsvorgangs bzw. aller Arbeitsvorgänge? Geben Sie dazu auch die Arbeitsvorgänge am kritischen Pfad, d.h. die Vorgänge, die im Falle einer zeitlichen Verzögerung unmittelbar eine Erhöhung der Gesamtdauer bewirken würden, aus.
• Laden und Speichern sämtlicher Daten (beliebig wählbare Datei).

Beim Laden und Speichern besteht jede Zeile in der Datei aus: Kurzbezeichnung und ausführlicher Name eines Arbeitsvorgangs, minimale Dauer, maximale Dauer sowie Kurzbezeichnungen aller Arbeitsvorgänge, von denen der aktuelle Arbeitsvorgang abhängt (alle Daten sind durch jeweils ein Leerzeichen getrennt).

Alle Arbeitsvorgänge sollen beim Speichern in einer durch eine Linearisierung (siehe oben) ermittelten Reihenfolge ausgegeben werden. Dadurch sind die in einer Zeile als abhängig angeführten Arbeitsvorgänge vorher immer bereits definiert, was das Laden der Datei erheblich erleichtert.

Beispiel für das Dateiformat:

     DES Design 20 25
     IMP Implementierung 15 20 DES
     DOKU Dokumentation 60 70 DES
     TEST Test 20 30 IMP
     UEB Uebergabe 5 5 TEST DOKU

Für das oben angegebene Beispiel ist die maximale Gesamtdauer 100 Stunden und der kritische Pfad: DES, DOKU, UEB.

Datenstruktur und Algorithmen

Arbeitsvorgänge stellen die Knoten, Abhängigkeiten die Kanten eines Graphen dar. Dieser wird am besten in Form einer Adjazenzliste verwaltet.

Eine Reihenfolge aller Arbeitsvorgänge, in der alle Abhängigkeiten erfüllt sind (Linearisierung), kann mit Hilfe einer Tiefensuche im Graphen gefunden werden. Man beachte jedoch, daß dabei bei den Zielknoten begonnen werden muß.

Die maximale Gesamtdauer im Falle der bestmöglichen Parallelisierung sowie der kritische Pfad können ebenfalls über die Linearisierung ermittelt werden. Dazu wird für jeden Arbeitsvorgang in der Reihenfolge der Linearisierung die maximale Gesamtzeit aller davor notwendigen Arbeitsvorgänge bei bestmöglicher Parallelisierung berechnet. Gibt es für einen Arbeitsvorgang mehrere Abhängigkeiten, so muß das Maximum der Zeiten aller davor notwendigen Arbeitsvorgangssequenzen ermittelt werden.

Im Fall, daß mehrere parallel ausgeführte Arbeitsvorgänge (bzw. Sequenzen dieser) gleiche maximale Gesamtzeiten benötigen, ist der kritische Pfad mitunter nicht eindeutig. Dann sind alle kritischen Arbeitsvorgänge in beliebiger Reihenfolge auszugeben, was mit einer Tiefensuche nach der Berechnung der maximalen Gesamtzeiten für alle Arbeitsvorgänge möglich ist.