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

Programmiertechnik I

Prof. Dr. Andreas Polze

Tutoren: Sven Köhler, Robert Lehmann

Wintersemester 2012/13

Überblick

Die Lehrveranstaltung bietet eine Einführung in die Informatik und vermittelt Theorie und Praxis der Programmierung von Software am Beispiel der Sprachen C und Prolog. Die Vorlesung diskutiert Konzepte der strukturierten Programmierung auf Grundlage der Programmiersprache C sowie Konzepte der logischen Programmierung mit Prolog.

Objekte und Ansätze der objektorientierten Programmierung werden kurz gestreift, sollen aber erst in der nachfolgenden Veranstaltung "Programmiertechnik II" im Mittelpunkt stehen.

Termine:

Vorlesung:

  • Di 9:15-10:45, HS1
  • Do 11:00-12:30, HS1

Die erste Vorlesung findet am 16.10.2012 statt.

Übungen finden alle 2 Wochen zum Vorlesungstermin am Donnerstag statt. Zu den Übungen werden Übungsaufgaben ausgegeben (insgesamt 6 Serien). Diese sollen in Zweier-Gruppen bearbeitet und den Tutoren präsentiert werden. Für eine Zulassung zur Klausur ist der Erwerb von mindestens 50% aller Punkte der jeweiligen Übungsaufgaben erforderlich.

Lösungen zu den Übungsaufgaben müssen über das Abgabesystem unter http://www.dcl.hpi.uni-potsdam.de/pt1prak/ eingereicht werden. Sie können sich dort unter Auswahl der HPI-OpenID-Providers mit Ihrem HPI-Benutzerkonto anmelden. Anleitung OpenID

Literatur

  • Heinz Peter Gumm, Manfred Sommer; "Einführung in die Informatik"; 9. Auflage, Oldenburg Verlag, 2011
  • Brian W. Kernighan, Dennis M. Ritchie; "The C Programming Language"; Prentice Hall, 1988 (2000)
  • Axel T. Schreiner; "System Programmierung in UNIX"; B.G. Teubner, 1984
  • Helmut Balzert; "Lehrbuch Grundlagen der Informatik"; Elsevier 2005

Hausaufgaben

Serie 1: (Termin: 1.11.2012, 10 Punkte)

  1. Wir möchten Sie gerne kennenlernen. Was interessiert Sie an der Informatik? Schreiben Sie ein Essay zum Thema "Der wichtigste Computerpionier" (auf deutsch).
    Stellen Sie Ihre eigene, subjektive Meinung dar und erläutern Sie auf einer Seite Ihren Standpunkt. Geben Sie die von Ihnen verwendeten Quellen an.
  2. Machen Sie sich mit dem Aufgaben-Abgabesystem vertraut. Reichen Sie Ihr Essay im pdf-Format ein.

Serie 2: (Termin: 22.11.2012, 20 Punkte)

  1. Erzeugen Sie die disjunktive Normalform DNF(f) und die konjunktive Normalform KNF(f) aus den folgenden Ausdrücken:
    • f(x, y, z) = (x ∧ y ∨ z ) ⊕ ( ¬x ∧ y )
    • g(x, y, z) = x ∧ ( y ∨ z )
    • h(x, y, z) = (x ⊕ y) ∨ (x ∧ y) ∨ z
  2. Stellen Sie die folgenden Zahlen binär, oktal und hexadezimal dar:
    • 68 zur Basis 9
    • 118 zur Basis 11
    • 550 zur Basis 6
    • 1810 zur Basis 10
  3. Geben Sie die im Dezimalsystem dargestellten Zahlen -1, 1, 28, -35, -256, 257 im Zweierkomplement in Binärdarstellung und Hexadezimaldarstellung an.
    Verwenden Sie in der Darstellung jeweils 16 Bit.
  4. Gegeben seien die Terminalsymbole a, b und c, sowie die Hilfssymbole X, Y und Z. Welche Symbolfolgen können aus diesen Symbolen 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 a) *
    • Y ::= c | a Y b | b Y a
    • Z ::= [X] [Y]

    Reichen Sie Ihre Lösung in Form einer pdf-Datei beim Abgabesystem ein.

Serie 3: (Termin: 18.12.2012, 20 Punkte)

Hinweis: Der zugehörige Übungstermin am 13.12. findet in den Poolräumen im ABC-Gebäude statt.

  1. Schreiben Sie zwei Shellskripte, die verschiedene Aufgaben erfüllen:
    1. 10 Dateien mit eindeutigem Namen erzeugen.
    2. Im einem Verzeichnis rekursiv nach der Textdatei mit den meisten Wörtern suchen.
      Der Verzeichnisname soll als Kommandozeilenparameter übergeben werden.
      Wird kein Parameter übergeben, so soll die Suche im Heimatverzeichnis beginnen.
  2. Erweitern Sie das Programm numbers.c aus der Vorlesung um die Fähigkeit, das Quadrat einer Zahl zu errechnen.
    Implementieren Sie dazu eine Funktion int sqr( int ) in zwei neuen Dateien sqr.c und sqr.h.
  3. Passen Sie das Makefile für die neue Funktionalität an.
    Außerdem soll das ausführbare Programm auch als Datei "sqr" (ein hard link auf numbers) zur Verfügung stehen.
  4. Erzeugen Sie ein neues Git-Repository und fügen Sie Ihre Lösung hinzu.
    Achten Sie darauf in Ihrer Git-Konfiguration Ihren richtigen Namen und ihre E-Mailadresse anzugeben.
  5. Reichen Sie Ihre Lösung als tar-Archiv ein, das neben Ihrem Quelltext auch das Git-Repository (.git) enthält.
    Hinweis: Sie können dazu folgenden Befehl nutzen: "make clean; tar cf abgabe.tar ."

Serie 3*: (Termin: 08.01.2013, 20 Punkte)

  • Erstellen Sie eine interaktive (Mehr-Benutzer) Fassung des NIM-Spiels aus Vorlesung 8 (Folie 9 ff.). Entwickeln Sie eine Kommandozeilen-basierte Benutzungsschnittstelle, bei der mehrere Benutzer abwechselnd Eingaben am Terminal vornehmen können.
  • Ihr Programm soll es erlauben, dass 1..n Benutzer gegeneinander oder gegen den Computer als Gegner spielen. Die Zahl der Spieler soll beim Start des Programms auf der Kommandozeile angegeben werden. (Sie dürfen für n eine feste Obergrenze, bspw. 5, annehmen).
  • Die Aufgabe ist ein "Joker". Haben Sie sie erfolgreich gelöst, so dürfen Sie eine nachfolgende Aufgabe auslassen. Wenn Sie die Aufgabe nicht lösen wollen, so ist das kein Problem...

Serie 5: (Termin: 17.01.2013, 20 Punkte)

Hinweis: Der zugehörige Übungstermin am 10.01. findet in den Poolräumen im ABC-Gebäude statt.

  1. Schreiben Sie in Anlehnung an das Programm "reverse.c" aus Unit 7 ein Programm "cap_rev.c", das jedes seiner Kommandozeilenargumente in umgekehrter Reihenfolge ausgibt.
    Zusätzlich sollen in jedem Argument alle Kleinbuchstaben durch Großbuchstaben ersetzt werden.
    • Beispiel: $ cap_rev Guten Tag
    • Ausgabe: GAT NETUG
  2. Erweitern Sie die Funktion "atoi()" aus Unit 6 / Folie 16 derart, dass Zahlen in Hexadezimalformat und mit Vorzeichen eingelesen werden können.
    Geben Sie eine Formatdefinition für Hexadezimalzahlen vor. Zahlen entsprechend dieser Definition sollen zur Basis 16 interpretiert werden, alle anderen Zahlen sollen zur Basis 10 interpretiert werden.
  3. Schreiben Sie ein Testprogramm "test_atoi.c", das Ihre Version von atoi() benutzt. Verwenden Sie den Präprozessor (bedingte Übersetzung) um in Ihrem Testprogramm wahlweise "atoi()" aus der Standardbibliothek oder aber Ihre Fassung aus 5.2 zu verwenden.
    Das Testprogramm soll seine Argumente als Zahlen zur Basis 16 oder 10 (mit atoi() aus 5.2) oder nur zur Basis 10 (mit atoi() aus <stdlib.h>) interpretieren und als Zahlen zur Basis 10 ausgeben (mit printf()).
    • Beispiel: $ test_atoi 0x6F 23 (Ihre Fassung)
    • Ausgabe: 111 23
  4. Schreiben Sie ein Programm "wc.c", das Zeilen, Worte und Zeichen der Standardeingabe erfasst. Verwenden Sie die Funktion "getchar()" zum zeichenweisen Einlesen der Standardeingabe.
  5. Analysieren Sie Ihr Programm mit Hilfe von lint (splint). Entwickeln Sie Ihr Programm solange weiter, bis lint keine Warnungen mehr ausstösst.
    (Natürlich sollen Sie lint immer verwenden, im Rahmen dieser Aufgabe werden wir aber nur überprüfen, ob Ihr wc.c-Programm keine Warnungen produziert.)
  6. Erstellen Sie ein Makefile für Ihre Lösung. Reichen Sie Ihre Lösung als tar-Archiv ein, das neben Ihrem Quelltext auch das Makefile enthält.
    Hinweis: Sie können dazu folgenden Befehl nutzen: "make clean; tar cf abgabe.tar ."

Serie 6: (Termin: 31.01.2013, 20 Punkte)

Hinweis: Der zugehörige Übungstermin am 24.01.2013 findet in den Poolräumen im ABC-Gebäude statt.

  1. Erweitern Sie strsort.c aus der Vorlesung so, dass bei Aufruf mit der Option

    strsort -num

    die Zeichenketten als ganze Zahlen interpretiert werden und in numerisch aufsteigender Reihenfolge sortiert werden.
    Schreiben Sie dazu eine Funktion int comp_num( char *, char *)!
    Benutzen Sie atoi() um eine Zeichenkette in eine ganze Zahl zu überführen.
  2. Schreiben Sie ein Programm, das ein Array mit den Zahlen 1..100 initialisiert, in einer Schleife die Quadratzahlen von 1*1 bis 100*100 errechnet und in einem zweiten Array speichert. Resultate sollen zudem auf der Standardausgabe angezeigt werden. Benutzen Sie dafür die Funktion

    printf("%d", val );

    Diskutieren Sie den für die Berechnung der Quadratzahlen benötigten Wertebereich. Legen Sie die Datentypen für Ihre Feldelemente passend (mit minimalem Speicherbedarf) fest.
  3. Erweitern Sie Ihr Programm aus 6.2 derart, dass Argumente von der Kommandozeile eingelesen werden. Ermitteln Sie dazu die Zahl der Kommandozeilenargumente und legen Sie Quell- und Ziel-Feld dynamisch an. Benutzen Sie dazu die Funktion

    void * malloc( size_t size );

    Der Zugriff auf Feldelemente soll über zwei Zeigervariablen erfolgen.
  4. Erweitern Sie die Implementierung von i2stack aus der Vorlesung derart, dass der Stack neben Integer-Zahlen auch Gleitkommazahlen enthalten kann.
    Verwenden Sie einen Struktur aus union-Typ und Diskriminante als Element innerhalb struct stackElem. Anhand der Diskriminanten soll eine Unterscheidung des Typs des gespeicherten Wertes möglich sein.
    Die Funktionen push(), pop(), top() sollen Parameter Ihres Struktur-Typs als Argumente bzw. Rückgabewerte benutzen.
  5. Erstellen Sie ein Makefile für Ihre Lösung. Reichen Sie Ihre Lösung als tar-Archiv ein, das neben Ihrem Quelltext auch das Makefile enthält.
    Hinweis: Sie können dazu folgenden Befehl nutzen: "make clean; tar cf abgabe.tar ."

Sie finden Aufzeichnungen der Lehrveranstaltung im tele-task System unter http://tele-task.de/archive/series/overview/918/.

Ablauf

Unit 1: Informatik als Fachgebiet

  • Was ist Informatik?
  • Algorithmenbegriff
  • Technische Informatik
  • Theoretische Informatik
  • Praktische Informatik
  • Angewandte Informatik
  • Geschichte - 100 Jahre IBM
  • Studium am HPI - Einordnung der LV
  • Bits, Bytes, Worte, Dateien – Information vs. Daten
  • top down vs. bottom up

Unit 2: Rechnerarchitektur

  • Aussagenlogik
  • Schaltnetze, Schaltwerke
  • Register
  • von Neumann Rechner
  • CPU, ALU, CU
  • Instruktionsverarbeitung
  • OpCode Formate, RTL
  • Instruktionsarten
  • Ein- und Ausgabe

Unterlagen zur 1. Übung

Unit 3: Informationsdarstellung

  • Universalität binärer Daten
  • Abtasttheorem
  • ganze Zahlen
  • 1er Komplement
  • 2er Komplement
  • Gleitkommaformate
  • ASCII, EBCDIC
  • Unicode

Unit 4: Programmiersprachen

  • Spezifikation, Algorithmen, Programme
  • Imperative Programmierung: Modula, C
  • Objektorientierte Programmierung: Smalltalk, C++, Objective-C, Java
  • Logische Programmierung: Prolog
  • Funktionale Programmierung: Lisp
  • Formale Beschreibung von Programmiersprachen: EBNF
  • Ein erstes Beispiel in C

Unterlagen zur 2. Übung

Unit 5: Werkzeuge und Technologien

  • Interpreter
  • Compiler
  • Technologieprogramme: make
  • Quellcodeverwaltung: sccs, cvs, subversion, git
  • Debugger: gdb
  • Test: Check, CUnit
  • Betriebssysteme
  • Beispiele aus der Vorlesung (tar)

Unit 6: Programmiersprache C - Integrale Datentypen

Unit 7: Programmiersprache C - Kontrollfluss

Unit 8: Programmiersprache C - Funktionen und Programmstruktur

  • Grundlagen, Prinzip Funktionsaufruf, Stack
  • call-by-value, call-by-ref, call-by-copy
  • Rückgabewerte
  • externe Variablen, Scope
  • header files und Übersetzungseinheiten
  • Initialisierung
  • Rekursion
  • C Präprozessor
  • Beispiele aus der Vorlesung (tar)

Unit 9: Programmiersprache C - Zeiger und Felder

  • Heap und Stack
  • Zeiger und Adressen
  • Zeiger und Funktionen (-argumente)
  • Zeiger und Arrays
  • Adreßarithmetik
  • Beispiel: malloc und Algorithmen zur Speicherallokation
  • Mehrdimensionale Felder
  • Initialisierung von Feldern
  • Kommandzeilenbearbeitung
  • Funktionszeiger
  • Komplizierte Deklarationen
  • Beispiele aus der Vorlesung (tar)

Unit 10: Programmiersprache C - Strukturen

  • Grundlagen
  • Strukturen und Funktionen
  • Felder von Strukturen
  • Zeiger auf Strukturen
  • Selbstreferentielle Strukturen
  • Unions, typedefs, bit-fields
  • Objekte in C
  • Beispiele aus der Vorlesung (tar)

Unit 11: Programmiersprache C - Ein- und Ausgabe (libc)

  • Standard Ein- und Ausgabe – stdio
  • Formatierte Ausgabe – printf
  • Argumentlisten variabler Länge – varargs
  • Formatierte Eingabe – scanf
  • Dateizugriff
  • Fehlerbehandlung – stderr und exit
  • Zeilenweise Ein- und Ausgabe
  • Weitere Funktionen
  • Beispiele aus der Vorlesung (tar)

Unit 12: Programmiersprache C - Betriebssystemschnittstellen

  • file descriptors
  • low-level i/O - read and write
  • open, creat, close, unlink
  • lseek
  • Standard library