Programmiertechnik I

Wintersemester 2005/2006

Dr. Martin v. Löwis

Die Anmeldung zur mündlichen Prüfung ist nun Online nicht mehr möglich. Die Prüfung findet in Raum A-2.1 statt.

Vorlesungen

Hinweise zu den Übungen

Subversion

Für das Praktikum wurde ein Subversion-Repository eingerichtet; für jeden Praktikumsteilnehmer eines. Auf das Repository haben nur der Praktikumsteilnehmer, sein im Abgabesystem eingetragener Partner und die Korrektoren Zugriff. Es ist ausschließlich für Zwecke des Praktikums bestimmt und mit Beginn des nächsten Semesters gelöscht.

Übungsaufgaben

1. Aufgabe

Abgabedatum: 7.11. 17:00 GMT

Punktzahl: 20P

Generieren Sie sich ein Zertifikat, indem Sie der Anleitung folgen. Sollten Sie in einer Gruppe arbeiten, muss jeder von Ihnen diesen Schritt bearbeiten.
Melden Sie sich am Aufgabenabgabesystem an. Tragen Sie Ihren Partner unter "Persönliche Daten" ein.
Geben Sie die im Dezimalsystem dargestellten Zahlen 42, 100, 256, 10000 und 1048576 in den folgenden Positionssystemen an:
- Binärsystem
- Oktalsystem
- Hexadezimalsystem
- Positionssystem zur Basis 13
Geben Sie die im Dezimalsystem dargestellten Zahlen -1, 1, 18, -25, -128, 129 im Zweierkomplement in Binärdarstellung und Hexadezimaldarstellung an. Verwenden Sie in der Darstellung jeweils 16 Bit.
Ermitteln Sie mit Hilfe der Unicode-Zeichendefinitionen oder Code-Charts die Unicode-Zeichenpositionen für
- A-Umlaut (Ä)
- den griechischen Großbuchstaben Delta (Δ)
- das Euro-Zeichen (€)
- den Existenz-Quantor (∃)
Schreiben Sie Ihre Lösungen in eine (reine) Textdatei, und geben Sie diese beim Abgabesystem ab.

2. Aufgabe

Abgabedatum: 21.11. 17:00 GMT

Punktzahl: 20P

Machen Sie sich mit /usr/bin/man vertraut. Rufen Sie dazu 'man man' auf.
Machen Sie sich mit /bin/tar vertraut. Lesen Sie dazu tar(1).
Entwickeln Sie ein Programm teiler.py, das für eine natürliche Zahl N alle Teiler ausgibt, die kleiner als N sind. N soll interaktiv durch den Nutzer eingegeben werden; das Programm soll sich nach Ausgabe aller Teiler beenden. Die Berechnungen dürfen alle vordefinierten Operatoren in Python verwenden, jedoch keine Funktionen (mit Ausnahme von input()). Die Teiler sollen auf die Standardausgabe ausgegeben werden, mit einer Zahl pro Zeile im Dezimalsystem.
Erweitern Sie teiler.py zu teilersumme.py. In diesem Programm sollen die Teiler von N nicht ausgegeben, sondern aufsummiert werden. Die Summe soll ausgegeben werden.
Erweitern Sie teilersumme.py zu perfekt.py. In diesem Programm wird vom Nutzer interaktiv eine Zahl N eingegeben. Das Programm soll alle die natürlichen Zahlen K zwischen 1 und N ausgeben, für die die Summe der Teiler gleich K ist.
Geben Sie eine Tar-Datei ab, die die drei Programme enthält.

3. Aufgabe

Abgabedatum: 5.12.. 17:00 GMT

Punktzahl: 20P

Alle Programme in dieser Aufgabe sollen in Python formuliert werden. Zur Umwandlung von Strings in Zahlen können die Funktion int und float verwendet werden.

Mit der Osterformel von Carl Friedrich Gauß (1777 - 1855) wird das Osterdatum für eine Jahreszahl zwischen 1582 und 8202 noch heute berechnet, ohne dass astronomische Beobachtungen nötig sind. Es bedeuten:
- j = 100p + n : Jahreszahl (0 ≤ n < 100)
- q: ganzzahliger Teil von p/3
- r: ganzzahliger Teil von p/4
- x: Dreißigerrest von 15+p-q-r
- y: Siebenerrest von p+4-r
- a: Neunzehnerrest von j
- b: Viererrest von j
- c: Siebenerrest von j
- d: Dreißigerrest von 19a + x
- e: Siebenerrest von 2b + 4c + 6d + y
Dann ist Ostern am (22+d+e)-ten März, wenn dieser Term kleiner 32 ist, oder am (d+e-9)-ten April, wenn der Term (22 + d + e) > 31 ist.
Ausnahmen: Ist d=29 und e=6, so ist Ostern am 19. April. Ist d=28 und e=6, so ist Ostern am 18. April.

Formulieren Sie ein Programm, das nach dieser Formel das Osterdatum für ein Jahr ausgibt, welches auf der Kommandozeile angegeben wird.
Formulieren Sie zwei Programme, die die Summe der ersten N natürlichen Zahlen ausgeben; N sei als Parameter auf der Kommandozeile gegeben. Entwickeln Sie zwei Varianten dieses Programms, nämlich
- eine Version, die die Zahlen iterativ addiert und
- eine Version, die die Zahlen rekursiv addiert.
Heron von Alexandria wird ein Verfahren zur Approximation von Quadratwurzeln positiver Zahlen zugeschrieben. Dabei wird die Wurzel der Zahl a durch die Folge
x_n+1 = (x_n + a/x_n)/2
angenähert.
- Formulieren Sie einen rekursiven Algorithmus, der x_k für auf der Kommandozeile gegebene Werte von a und k berechnet und ausgibt. Dabei sei a als positive reelle und k als natürliche Zahl im Dezimalsystem gegeben. x₁ sei 1.
- Testen Sie Ihren Algorithmus für verschiedene Werte von a und k
- Bestimmen Sie einen Wert N von Schritten, für den das Verfahren die Wurzel mit hinreichender Genauigkeit ermittelt; definieren Sie dazu eine geeignete Spezifikation für "hinreichende Genauigkeit". Hängt der Wert von N von der Zahl a ab?
Die Ackermann-Funktion A(m, n) (Wilhelm Ackermann, 1928) ist für natürliche Zahlen m und n wie folgt definiert:
- A(0, n) = n+1 für n ≥ 0
- A(m, 0) = A(m-1, 1) für m > 0
- A(m, n) = A(m-1, A(m, n-1)) für m, n >0
Lösen Sie die folgenden Teilaufgaben:
1. Entwickeln Sie ein Programm, das für zwei auf der Kommandozeile angegebene Zahlen den Wert der Ackermannfunktion ausgibt
2. Erweitern Sie das Programm, so dass es nicht nur den Wert der Funktion bestimmt, sondern auch die Zahl Z der Aufrufe der Funktion ermittelt und ausgibt.
3. Erweitern Sie das Programm, so dass es zusätzlich auch noch die maximale Rekursionstiefe R berechnet und ausgibt.
4. Bestimmen Sie für m=1,2,3,4 die maximalen Werte von n, für die auf Ihrer Maschine die Ackermann-Funktion noch fehlerlos berechenbar ist, und geben Sie die Werte von n, A(m,n), Z und R an.
Senden Sie Ihre Lösung als Tardatei ein, mit Verzeichnissen a,b,c,d für die Teilaufgaben.

4. Aufgabe

Abgabedatum: 19.12.. 17:00 GMT

Punktzahl: 20P

Alle Programme in dieser Aufgabe sollen in Python formuliert werden. Sie dürfen beliebige Funktionen der Standardbibliothek verwenden.

Gegeben sei die Fibonacci-Funktion:
```
                    def fib(n):
                        if n <= 1:
                            return 1
                        return fib(n-1)+fib(n-2)
                    
```
Definieren Sie eine Funktion calls(n), die die Zahl der Aufrufe von fib ermittelt, die zur Berechnung von fib(n) ausgeführt werden.
Berechnen Sie calls(n) für die natürlichen Zahlen von 1 bis 35.
Stellen Sie eine Formel auf, die die Berechnung von calls(n) erlaubt, wenn fib(n) gegeben ist. Begründen Sie Ihre Formel.
Gegeben sei eine Liste von Nutzernamen passwd (Password-Datei), die einen Nutzer pro Zeile enthält und die Nutzer in der Form
```
                    login_name:password:UID:GID:user_name:directory:shell
                    
```
enthält. Entwickeln Sie ein Modul account.py, das die folgenden Typen und Funktionen enthält:
- Account ist eine Datensatz-Klasse mit den Feldern login_name, password, UID, GID, user_name, directory und shell. Dabei sollen UID und GID ganze Zahlen sein, alle anderen Felder Byte-Strings.
- open(dateiname) liest eine Passwort-Datei, und gibt eine Liste von Account-Datensätzen zurück, in der Reihenfolge, wie sie auch in der Datei stehen. Hinweis: Um in der Implementierung von open Gebrauch von der eingebauten Funktion open zu machen, können Sie ausnutzen, dass diese Funktion auch unter dem Namen file bekannt ist.
- find_account(liste, login_name) durchmustert eine solche Liste und gibt den Datensatz mit dem angegebenen login_name zurück. Falls kein solcher Datensatz gefunden wurde, soll die Ausnahme KeyError ausgelöst werden.
Testen Sie Ihr Modul, indem Sie ein Programm schreiben, welches die Funktionen account.open und account.find_account aufruft, und mittels assert-Anweisungen überprüft, dass die Ergebnisse richtig sind. Setzen Sie dabei wenigstens die folgenden Testfälle um:
- Die UID des ersten Nutzers ist 5316.
- Der Name des letzten Nutzers ist Steffen Kensy.
- Es gibt genau einen Nutzer mit der UID 5131.
- find_account(liste,"fwesack") liefert einen Nutzer, dessen Verzeichnis /home/stud/2001/fwesack ist.
- find_account(liste,"billg") liefert eine Ausnahme.
Senden Sie Ihre Lösung als Tar-Datei ein, mit Unterverzeichnissen für die Teilaufgaben.

5. Aufgabe

Abgabedatum: 16.1. 17:00 GMT

Punktzahl: 20P

Richten Sie in Ihrem Subversion-Repository die Verzeichnisse aufgabe5, aufgabe5/trunk, aufgabe5/tags, aufgabe5/branches ein. Fügen Sie Ihre Lösungen der anderen Teilaufgaben in aufgabe5/trunk ein.

Gegeben sei der folgende Algorithmus zur Berechnung des Durchschnitts zweier Listen:

                    def intersection(list1, list2):
                      result = []
                      for e1 in list1:
                        for e2 in list2:
                           if e1 == e2:
                             # Element ist in beiden Listen enthalten;
                             result.append(e1)
                      return result

Beweisen Sie, dass die Ergebnisliste result nur Elemente enthält, die sowohl in list1 als auch in list2 vorkommen. Hinweis: Formulieren Sie den Algorithmus zunächst so um, dass anstelle der for-Schleifen while-Schleifen verwendet werden.
Als Abgabeformat für diese Teilaufgabe wird reiner Text oder PDF akzeptiert.

Eine doppelt-verkettete Liste ist eine Datenstruktur, in der jedes Element einen Verweis auf das Vorgänger-Element und einen Verweis auf das Nachfolger-Element enthält; zusätzlich enthält jedes Element ein (frei wählbares) Datum.
Diese Datenstruktur lässt sich mithilfe zweier Klassen realisieren: eine Klasse, die die Liste selbst realisiert, und eine Klasse, die Elemente der Liste realisiert.
Der Vorteil doppelter Verkettung (gegenüber der einfachen Verkettung) besteht darin, dass zum Löschen eines Elements nur das Element bekannt sein muss.
Implementieren Sie ein Modul dlist, in dem eine Klasse DList definiert wird, mit folgenden Eigenschaften:
- Der Konstruktor DList() erzeugt eine Liste ohne Elemente.
- Die Methode append(item) erzeugt ein neues Listenelement, dessen Datum item ist, und hängt diesen Wert an das Ende der Liste.
- Die Methode remove(item) löscht ein Element aus der Liste. Sie löst ValueError aus, falls das Element nicht in der Liste enthalten ist.
- Die Methode first() liefert das erste Listenelement (oder None, falls die Liste leer ist). Listenelemente unterstützen die Methoden
  - next(): liefert das nächste Listenelement (oder None, wenn das Ende der Liste erreicht wurde).
  - data(): liefert den Inhalt des Elements
Testen Sie Ihre Implementierung anhand des TestProgramms.
Überprüfen Sie, dass Ihre Implementierung folgende Eigenschaften besitzt:
- Das Modul, alle Klassen und alle Methoden besitzen doc strings, die die Verwendung dieser Konstrukte erläutern
- Die Algorithmen in Ihrem Code enthalten Kommentare, die die Implementierungsstrategie erläutern.
- Ihr Code enthält keine überflüssigen Tests, Anweisungen, oder Algorithmen.
Richten Sie für die Lösung ein Subversion-Tag "abgabe" ein, und geben Sie im Abgabesystem den vollständigen URL dieses Tags an.

Musterlösung für Teil b)

6. Aufgabe

Abgabedatum: 2.2. 17:00 GMT

Punktzahl: 20P

Studieren Sie die Java-Sprachbeschreibung und geben Sie Java-Fragmente an, die den Produktionsregeln für
- CatchClause
- NormalInterfaceDeclaration und
- die zweite Alternative von Expression3
entsprechen. Erklären Sie jeweils die Bedeutung (Semantik) dieses Konstrukts in der Sprache Java.
Lösen Sie die Teilaufgaben 4b in Java. Verwenden Sie dabei die folgende Schnittstelle:
- Account soll durch eine Java-Klasse repräsentiert werden, für die alle Felder public sind und geeignete Datentypen haben.
- Account soll eine Methode public static Account[] open(String filename); besitzen.
  Hinweise: Zum zeilenweisen Einlesen können Sie die Klasse BufferedReader verwenden. Fügen Sie die Strings/Account-Objekte zunächst in einen Container, etwa Vector ein, um dann ein Ergebnis-Array der passenden Größe zu produzieren.
- Außerdem soll Account eine Methode public static Account find_account(Account[] liste, String login_name); besitzen, die das zu login_name passende Account-Exemplar liefert, oder null, falls es kein passendes gibt.
Lösen Sie die Teilaufgabe 4c in Java. Definieren Sie dazu eine Klasse AccountTest, deren Methode main() alle Testfälle ausführt.
Richten Sie im Subversion-Repository die Struktur aufgabe6/(trunk,tags,branches) ein, legen Sie ein Subversion-Tag abgabe an, und senden Sie den Repository-URL dieses Tags ein.

Musterlösung für Teil b) und c): Account.java, AccountTest.java