Hasso-Plattner-Institut Potsdam Operating Systems and Middleware Group at HPI University of Potsdam, Germany
Operating Systems and Middleware Group at HPI

Programmiertechnik I

Dr. Martin v. Löwis

Wintersemester 08/09

Der Termin der nächsten Übung ist der 19./20.1.

Die mündlichen Prüfungen finden am 24.2.,25.2.,27.2.,2.3.,3.3.,4.3. und vom 6.4.-9.4. sowie 14.4.,15.4. im Raum A-1.1 statt. Die Online-Prüfungsanmeldung ist nicht mehr möglich; wenden Sie sich ab 9.2. bei Terminänderungen an Frau Wagner in Büro C-1.8.

Literatur

  • Gumm, Sommer. Einführung in die Informatik. Oldenburg Verlag, 2004
  • v. Löwis, Fischbeck. Python 2. Addison-Wesley, 2000
  • Barnes, Michael Kölling. Objects First with Java - A Practical Introduction using BlueJ. Prentice Hall, 2004
  • Broy. Informatik . Eine grundlegende Einführung. Band 1, Springer 1998
  • Balzert. Lehrbuch Grundlagen der Informatik. Elsevier 2005
  • Futschek. Programmentwicklung und Verifikation. Springer, 1998

Vorlesungen

  1. Einführung (19.10.2008 12:39:24)
  2. Darstellung von Informationen (19.10.2008 13:25:02)
  3. Darstellung von Zahlen (30.10.2008 10:27:06)
  4. Darstellung von Text (21.10.2008 18:10:14)
  5. Darstellung von anderen Daten (21.10.2008 18:11:39)
  6. Programmiersprachen (30.10.2008 10:26:22)
  7. Spezifikationen, Algorithmen, Programme (06.11.2008 16:52:53)
  8. Formale Beschreibung von Programmiersprachen (06.11.2008 16:58:43)
  9. Erweiterte Kontrollflusskonzepte (06.11.2008 16:50:16)
  10. Unterprogramme (01.12.2008 09:48:20)
  11. Ausnahmebehandlung (01.12.2008 09:48:49)
  12. Konstruktion neuer Datentypen (12.01.2009 14:50:07) (Terminal Log)
  13. Verifikation (12.12.2008 19:38:46) (assert demo)
  14. Versionsverwaltung (12.01.2009 14:49:27) (Terminal Log)
  15. Objekt-orientierte Programmierung (23.01.2009 12:44:30)
  16. Klassen und abstrakte Datentypen (23.01.2009 12:45:14)
  17. Java (05.02.2009 18:30:25)
  18. Scheme (10.02.2009 17:52:01) (user.ss)

Hinweise zu den Übungen

Übungsaufgaben

Abgabedatum: 6.11. 17:00 UTC

Punktzahl: 20P

  1. Generieren Sie sich ein Zertifikat. Sollten Sie in einer Gruppe arbeiten, muss jeder von Ihnen diesen Schritt durchführen.
  2. Melden Sie sich am Aufgabenabgabesystem an. Für die Arbeit in einer Gruppe muss ein Mitglied eine Gruppe anlegen und das andere Mitglied in die Gruppe aufnehmen.
  3. Geben Sie die im Dezimalsystem dargestellten Zahlen 93, 10000, 32768, 314171 und 1048576 in den folgenden Positionssystemen an:
    • Binärsystem
    • Oktalsystem
    • Hexadezimalsystem
    • Positionssystem zur Basis 13
  4. Geben Sie die im Dezimalsystem dargestellten Zahlen -1, 1, 57, -84, -256, 257 im Zweierkomplement in Binärdarstellung und Hexadezimaldarstellung an. Verwenden Sie in der Darstellung jeweils 16 Bit.
  5. Ermitteln Sie mit Hilfe der Unicode-Zeichendefinitionen oder Code-Charts die Unicode-Zeichenpositionen für
    • der Buchstabe æ
    • das Drei-Viertel-Zeichen (¾)
    • der griechische Buchstabe Xi (Ξ)
    • das Symbol für die leere Menge (∅)
  6. Schreiben Sie Ihre Lösungen in eine (reine) Textdatei, und geben Sie diese beim Abgabesystem ab.

2. Aufgabe

Abgabedatum: 20.11. 17:00 UTC

Punktzahl: 20P

  1. Machen Sie sich mit /usr/bin/man vertraut. Rufen Sie dazu 'man man' auf.
  2. Machen Sie sich mit /bin/tar vertraut. Lesen Sie dazu tar(1).
  3. 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 vordefinierten Funktionen (mit Ausnahme von input()). Die Teiler sollen auf die Standardausgabe ausgegeben werden, mit einer Zahl pro Zeile im Dezimalsystem.
  4. 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.
  5. Eweitern Sie teilersumme.py zu befreundet.py. In diesem Programm soll von zwei Zahlen bestimmt werden, ob sie befreundet sind. Zwei Zahlen a und b heißen befreundet, wenn sie verschieden sind und die Teilersumme von a gleich b ist und die Teilersumme von b gleich a. Falls die Zahlen befreundet sind, soll der Text JA ausgegeben werden, ansonsten NEIN.
  6. Erweitern Sie befreundet.py zu findefreunde.py. Dieses Programm soll für ein durch die Obergrenze N gegebenen Intervall [1,N] alle Paare (a,b) befreundeter Zahlen ausgeben, für die a und b im Intervall liegen.
  7. Geben Sie eine Tar-Datei ab, die die vier Programme enthält.

3. Aufgabe

Abgabedatum: 4.12., 17:00 UTC

Punktzahl: 20P

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

  1. Gegeben seien die Terminalsymbole a, b und c, sowie die Hilfssymbole X, Y und Z. Welche Symbolfolgen können aus diesen Symbolfolgen erzeugt werden, wenn man jeweils X, Y oder Z als Startsymbol wählt? Geben Sie für jedes Hilfssymbol 5 Beispiele an.
    • X ::= (a b) *
    • Y ::= c | a Y b
    • Z ::= [X] [Y]
  2. Formulieren Sie ein Programm round.py, welches eine auf der Kommandozeile gegebene ganze Zahl auf das nächste Vielfache von 100 rundet. Dabei soll "unverzerrt" gerundet werden, sind die letzten zwei Stellen also 50, soll auf das nächste gerade Vielfache von 100 gerundet werden. Beispiele: 613 wird auf 600 gerundet, 1072 auf 1100, 1150 und 1250 beide auf 1200. Formulieren Sie dazu eine geeignete Funktion runde.
  3. Heron von Alexandria wird ein Verfahren zur Approximation von Quadratwurzeln positiver Zahlen zugeschrieben. Dabei wird die Wurzel der Zahl a durch die Folge
    xn+1 = (xn + a/xn)/2
    angenähert.
    • Formulieren Sie einen rekursiven Algorithmus in sqrt.py, der xk 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. x1 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?

  4. Formulieren Sie ein (möglichst rekursives) Programm combine.py, welches Kombinationen von Primfaktoren zu ganzen Zahlen zählt. Das Programm erhält als erstes Kommandozeilenargument eine Obergrenze N (etwa: 50), gefolgt von beliebig vielen paarweise verschiedenen Primzahlen pi (etwa: 3 7 13). Das Programm soll ausgeben, wie viele verschiedene k (1 ≤ k ≤ N) nur aus Primfaktoren pi zusammengesetzt sind (im Beispiel: 9 Zahlen, nämlich 1 3 7 9 13 21 27 39 49). Die Lösung soll konstruktiv sein; es sollen also nicht alle Zahlen bis N auf diese Eigenschaft getestet werden. Versuchen Sie, in der rekursiven Funktion auf globale Variablen zu verzichten.
  5. 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 a1.py, das für zwei auf der Kommandozeile angegebene Zahlen den Wert der Ackermannfunktion ausgibt
    2. Erweitern Sie das Programm zu a2.py, 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 zu a3.py, 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.

  6. Senden Sie Ihre Lösung als Tardatei ein, mit Verzeichnissen a,b,c,d,e für die Teilaufgaben.

4. Aufgabe

Abgabedatum: 18.12. 17:00 UTC

Punktzahl: 20P

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

  1. 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.
  2. 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/2005/fwesack ist.
    • find_account(liste,"billg") liefert eine Ausnahme.
  3. Gegeben sei das Programm expr.py, mit welchem sich Ausdrücke bestehend aus Zahlen und den Grundrechenarten darstellen lassen (im Beispiel 3*(4+5)). Erweitern Sie es um zwei Funktionen calc und infix:
    • calc erwartet einen Ausdruck, und liefert den berechneten Wert zurück (im Beispiel 27).
    • infix erwartet einen Ausdruck, und liefert einen String zurück, der eine Infix-Darstellung des Ausdrucks enthält (im Beispiel "3*(4+5)"); es ist Ihnen freigestellt, "überflüssige" Klammern wegzulassen (3+4*5 kann also auch als "3+(4*5)" dargestellt werden).
    Hinweis: Zur Erkennung, ob ein Term einen binären Ausdruck oder eine Zahl darstellt, können Sie die Länge des Tupels überprüfen (die also 1 oder 3 sein muss).
  4. Senden Sie Ihre Lösung als Tar-Datei ein, mit Unterverzeichnissen für die Teilaufgaben.

5. Aufgabe

Abgabedatum: 22.1. 17:00 UTC

Punktzahl: 20P

  1. 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.
  2. 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.
  3. Eine Vorrangwarteschlange (priority queue) ist ein abstrakter Datentyp, dessen Inhalt aus Paaren (Priorität, Wert) besteht. Beim Einfügen muss man beide Parameter angeben; beim Entfernen erhält man den Wert mit der höchsten Prioritält.
    Diese Datenstruktur lässt sich mithilfe zweier Klassen realisieren: eine Klasse, die die Warteschlange selbst realisiert, und eine Klasse, die Elemente einer einfach verketteten Liste realisiert, absteigend nach Priorität sortiert. Beim Einfügen muss darauf geachtet werden, dass die Sortierung erhalten bleibt; beim Entfernen reicht es, das vorderste Element aus der Liste zu entnehmen.
    Implementieren Sie ein Modul pqueue, in dem eine Klasse PQueue definiert wird, mit folgenden Eigenschaften:
    • Der Konstruktor PQueue() erzeugt eine Vorrangwarteschlange ohne Elemente.
    • Die Methode enqueue(priority, item) erzeugt ein neues Listenelement, dessen Datum item ist, und sortiert diesen Wert an die entsprechende Stelle der Liste. Bei mehrfacher Verwendung der gleichen Priorität werden die neuen Elemente hinter die bestehenden eingefügt.
    • Die Methode dequeue() löscht ein Element aus der Liste und gibt den enthaltenen Wert zurück. Falls die Liste leer ist, wird die Ausnahme pqeue.EmptyQueue ausgelöst.
    • Die Methode empty() liefert True, falls die Warteschlange leer ist, sonst False.
  4. Testen Sie Ihre Implementierung anhand des TestProgramms.
  5. Ü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.
  6. 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 Aufgabe b)

6. Aufgabe

Abgabedatum: 5.2. 17:00 UTC

Punktzahl: 20P

  1. 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. Reichen Sie diesen Teil Ihrer Lösung als Text- oder PDF-Datei ein.
  2. Lösen Sie die Teilaufgaben 4a 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. Bei Scheitern des Einlesens soll diese Funktion null zurückgeben.
      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.
  3. Lösen Sie die Teilaufgabe 4b in Java. Definieren Sie dazu eine Klasse AccountTest, deren Methode main() alle Testfälle ausführt.
  4. 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.