Programmiertechnik I

Wintersemester 2017/18

Prof. Dr. Andreas Polze

Tutoren: Sven Köhler

Ü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 13:30-15:00, HS1
Do 09:15-10:45, HS1

Übungen finden alle 2 Wochen zum Vorlesungstermin am Donnerstag statt. Zu den Übungen werden Übungsaufgaben ausgegeben (insgesamt 5 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 /submit/ 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: (Abgabe: 09.11.2017, 21:00 Uhr, 20 Punkte)

Wir möchten Sie gerne kennenlernen. Was interessiert Sie an der Informatik? Schreiben Sie ein Essay zum Thema "Der/die wichtigste Computerpionier(in)" (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.
Machen Sie sich mit dem Aufgaben-Abgabesystem vertraut. Reichen Sie Ihr Essay im pdf-Format ein.

Serie 2: In den Poolräumen am 16.11.2017 (Abgabe: 23.11.2017, 21:00 Uhr, 20 Punkte)

Stellen Sie die folgenden Zahlen binär, oktal, dezimal und hexadezimal dar:
- 68 zur Basis 9
- 118 zur Basis 11
- 550 zur Basis 6
Geben Sie die im Dezimalsystem dargestellten Zahlen -1, 1, 28, -35, -256, 257 im Zweierkomplement in Binär- und Hexadezimaldarstellung an.
Verwenden Sie in der Darstellung jeweils 16 Bit.
Interpretieren Sie die folgenden beiden Ziffernvokabeln als Gleitkommazahlen im IEEE-754-Single-Format (d.h. geben Sie den Wert jeweils als Dezimalzahl an).
- 0|10000000|00000000000000000000000
- 1|01111110|10000000000000000000000
Stellen Sie die Zahl π ~ 3,14159265 ₁₀ ~ 11,0010010000111111011010₂ als IEEE-754 Single Precision dar.
Ermitteln Sie mit Hilfe der Unicode-Zeichendefinitionen oder Code-Charts die Unicode-Zeichenpositionen für
- den Buchstaben Æ
- das Pfund-Zeichen (£)
- den griechischen Buchstaben rho (ρ)
- das Kleiner-oder-gleich-Zeichen (≤)
Welche Codepoints und welche Zeichen werden von den Bytesequenzen
- 0x64 0x75 0x63 0x6B
- 0xF0 0x9D 0x95 0xBD
repräsentiert, wenn sie als
- ISO8859-1
- UTF-8
- UTF-16 LE
interpretiert werden?
Laden Sie Ihre Lösungen als PDF-Datei ins Abgabesystem hoch. Machen Sie Lösungswege erkenntlich.
Wenn Sie als Gruppe einreichen wollen, genügt eine Abgabe. Suchen und markieren Sie die zweite Person im dafür vorgesehen Feld (Screenshot).

Serie 3: In den Poolräumen am 14.12.2017 (Abgabe: 21.12.2017, 21:00 Uhr, 20 Punkte)

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]
Speichern Sie Ihre Lösung als xyz.txt.
Zeigen Sie mithilfe der C-Sprachdefinition (S. 409ff) dass die gegeben Beispiele gültige expression sind. Geben Sie dafür die Ableitung an. Welche Werte ergeben diese Ausdrücke?
- (int) 3.141
- e = 2.0 + .718
- a = 0, a += e
Speichern Sie Ihre Lösung als expression.txt.
Hinweis zum Umfang: Geben Sie mindestens eine Ableitung vollständig an. Für die Übrigen reicht es die Lösung nachvollziehbar zu skizzieren. Symbole, die außerhalb von A.2.1 definiert sind, müssen nicht weiter aufgelöst werden.
Entwickeln Sie ein Programm factors.c, das für eine natürliche Zahl N alle Teiler ausgibt, die kleiner als N sind. N soll als Kommandozeilenparameter übergeben werden. Die Teiler sollen auf der Standardausgabe ausgegeben werden, mit einer Zahl pro Zeile im Dezimalsystem. (z.B. f(12) = 1, 2, 3, 4, 6)
Entwickeln Sie basierend auf der letzen Aufgabe primefactors.c, das nur die Primteiler der übergebenen Zahl ausgibt (z.B. pf(12) = 2, 3).
Entwickeln Sie factorial_factors.c, das für eine übergebene Zahl zuerst die Fakultät berechnet und anschließend eine Primzahlzerlegung durchführt. Beachten Sie, dass in der Primzahlzerlegung ein Primfaktor u.U. mehrfach enthalten ist (z.B. 5! = 2 * 2 * 2 * 3 * 5). Die Fakultät muss nicht ausgegeben werden.
Schreiben Sie ein Makefile, dass die einzelnen Programme erstellt. Es soll außerdem die Targets all und clean anbieten zum bauen, bzw. löschen aller Programme.
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.
Reichen Sie Ihre Lösung als tar-Archiv ein, das neben Ihrem Quelltext auch das Git-Repository (.git) enthält. Binärdateien und Backupdateien Ihres Editors sollen nicht enthalten sein.
Hinweis: Sie können dazu dem Befehl make clean; tar cf abgabe.tar . nutzen.

Serie 4: In den Poolräumen am 11.01.2018 (Abgabe: 18.01.2018, 21:00 Uhr, 20 Punkte)
Musterlösung (ohne GDB-Log)

Schreiben Sie in Anlehnung an das Programm reverse.c aus Unit 7 ein Programm cap_rev.c, das jedes seiner Kommandozeilenargumente in umgekehrter Reihenfolge, pro Zeile, ausgibt. Zusätzlich sollen in jedem Argument alle Kleinbuchstaben durch Großbuchstaben ersetzt werden (andere Zeichen bleiben unverändert). Zum Beispiel:
```
$ ./cap_rev Guten Tag
GAT
NETUG
```
Schreiben Sie ein Programm is_palindrome.c, dass für jedes seiner Kommandozeilenargumente prüft, ob es sich um ein Palindrom handelt. Es soll zeilenweise YES oder NO ausgegeben werden.
Schreiben Sie ein Programm sundarams_sieve.c, das mithilfe des Siebs von Sundaram zeilenweise alle Primzahlen kleiner als eine per Kommandozeilenargument übergebene Obergrenze G ausgibt. Sie können annehmen, dass ihr Programm nicht mit G größer als 1000 gerufen wird.
Hinweis: Berechnen Sie zuerst für welche Maximalwerte der Zählvariablen ihre Zugriffe noch in den Grenzen des Feldes liegen, um daraus die Abbruchbedingunngen der Schleifen zu schließen.
Schreiben Sie ein Programm wc.c, das Zeilen, Worte und Zeichen der Standardeingabe zählt und mit Leerzeichen getrennnt ausgibt. Verwenden Sie die Funktion getchar() zum zeichenweisen Einlesen der Standardeingabe. Beachten Sie, dass zwei Wörter durch mehrere Whitespaces getrennnt sein können.
Analysieren Sie Ihr wc.c Programm mit Hilfe von lint (splint). Entwickeln Sie Ihr Programm solange weiter, bis lint keine Warnungen mehr ausgibt. (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.)
Das Programm strlen_utf8.c soll die UTF-8 Symbole in einem übergeben String zählen. Leider arbeitet es fehlerhaft. Nutzen Sie /usr/bin/script um aufzeichnen, wie Sie in GDB nach der Fehlerstelle suchen. Geben Sie die Aufzeichnung als gdb_session.log, sowie den korrigierten Programmquelltext ab.
Hinweis: Nutzen Sie die Poolrechner, sollten Sie auf Ihrem System Probleme mit script haben.
Reichen Sie Ihre Lösung als tar-Archiv ein, das neben Ihrem Quelltext und gdb_session.log ein Makefile mit den Zielen all und clean enthält. Binärdateien und Backupdateien Ihres Editors sollen nicht enthalten sein.

Serie 5: Klausurvorbereitung (unbewertet).
Musterlösung

Lesen Sie die Manual-Pages zu fopen, fclose, fread, fwrite, fgets und fputs. Finden Sie Typ und Bedeutung der globalen C-Variablen stdin, stdout und stderr heraus.
Schreiben Sie ein Programm dec2rom.c, das alle auf der Kommandozeile übergebenen Dezimalzahlen in römische Zahlen (max. 3999) umwandelt und zeilenweise ausgibt.
```
$ ./dec2rom 2018 1 29
MMXVIII
I
XXIX
```
In caesar.c implementieren Sie die zwei Funktion caesar_encrypt(char *, int) und caesar_decrypt(char *, int), die alle Buchstaben in einem übergebenen String mithilfe der Caesar-Chiffre ver-, bzw. entschlüsseln.
```
$ echo "Hallo Welt." | ./caesar encrypt 13
Unyyb Jryg.
$ echo "Hallo Welt." | ./caesar encrypt 13 | ./caesar decrypt 13
Hallo Welt.
```
Erstellen Sie basierend auf der letzten Aufgabe caesar_file.c, das zeilweise Dateien ver-, bzw. entschlüsselt. Die Namen der Ein- und Ausgabedatei sollen hierbei als Kommandozeileargumente übergeben werden.
```
$ echo "Hallo Welt" > klartext.txt
$ ./caesar_file encrypt 13 klartext.txt verschluesselt.txt
$ cat verschluesselt.txt
Unyyb Jryg.
```
Erweitern Sie strsort.c aus der Vorlesung so, dass bei Aufruf mit der Option strsort -num die Zeichenketten als ganze Zahlen interpretiert 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.
Implementieren Sie eine einfache Bibliothek zur Punkteverwaltung eines Übungsbetriebs. Gegeben sei Ihnen die Header-Datei grading_table.h. Definieren Sie darin die struct grading_entry_t, sodass sie diese in einer einfach verketten Liste nutzen können.
Legen Sie eine Datei grading_table.c an, in der Sie folgende Funktionen definieren:
- read_list Liest den übergebenen Dateistream ein und speichert die Elemente in einer verkettenten Liste.
- delete_list Gibt den Speicher aller Elemente in der übergebenen Liste frei.
- traverse_list Ruft die übergebene Funktion für jedes Element der Liste auf.
- reduce_list Ruft die übergebene Funktion für jedes Element der Liste auf und nutzt deren Rückgabe als val im nächsten Aufruf. reduce(l, f, s) = f(l[n], f(l[n-1], … f(l[0], s) … )))
Hinweise:
- Dies ist eine Bibliothek. Implementieren Sie keine main-Methode!
- Die read_list übergebenen Dateien enthalten Binärdaten (litte-endian order) und repräsentieren eine Folge von Datenbankeinträgen.
- Jeder Eintrag besteht aus 3 vorzeichenlosen Ganzzahlen: 4 Byte Matrikelnummer, sowie 2 Byte Aufgabennummer und 2 Byte erreichte Punktzahl. Nutzen Sie stdint.h um geeignete Datentypen zu finden.
Schreiben Sie ein Programm grading_tasks.c, das Ihre Bibliothek aus letzter Aufgabe nutzt (binden Sie diese im Makefile ein). Ihr Programm soll einen Task (Kleinbuchstaben a bis e), sowie den Namen einer Datenbankdatei übergeben bekommen. Wird kein Dateiname gegeben, soll von der Standardeingabe gelesen werden.
Implementieren Sie folgende Tasks, indem Sie einen passenden Funktionspointer an traverse_list oder reduce_list übergeben:
1. Gibt zeilenweise alle Einträge im Format "<Matrikelnummer> hat in <Serie> <Anzahl> Punkt(e) erreicht." aus.
2. Gibt zeilenweise "<Matrikelnummer> <Serie>" für alle Serien aus, in denen weniger als 10 Punkte erreicht wurden.
3. Gibt aus wie viele Abgaben insgesamt existieren.
4. Gibt die höchste erreichte Punktzahl aus.
5. Gibt die Summe der Punkte aller Abgaben zur Serie 3 aus.
Beispiele (Eingabedatei):
```
$ ./grading_tasks b grading_results.db
4211 3
2342 4
$ ./grading_tasks d < grading_results.db
23
```
Erweitern Sie die Implementierung von i2stack.c aus der Vorlesung derart, dass der Stack neben Integer-Zahlen auch Gleitkommazahlen enthalten kann.
Verwenden Sie eine 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.
Reichen Sie Ihre Lösung als tar-Archiv ein, das neben Ihrem Quelltext ein Makefile mit den Zielen all und clean enthält. Binärdateien, das Datenbankbeispiel, sowie Backupdateien Ihres Editors sollen nicht enthalten sein.