Programmiertechnik I
Wintersemester 2017/18Prof. 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
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 10 ~ 11,00100100001111110110102 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
- ISO8859-1
- UTF-8
- UTF-16 LE
-
- 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
undc
, sowie die HilfssymboleX
,Y
undZ
. Welche Symbolfolgen können aus diesen Symbolen erzeugt werden, wenn man jeweilsX
,Y
oderZ
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]
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
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
undclean
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 Befehlmake 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 Programmcap_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 zeilenweiseYES
oderNO
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 Funktiongetchar()
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 Ihrwc.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 alsgdb_session.log
, sowie den korrigierten Programmquelltext ab.
Hinweis: Nutzen Sie die Poolrechner, sollten Sie auf Ihrem System Probleme mitscript
haben. - Reichen Sie Ihre Lösung als tar-Archiv ein, das neben Ihrem
Quelltext und
gdb_session.log
ein Makefile mit den Zielenall
undclean
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
undfputs
. Finden Sie Typ und Bedeutung der globalen C-Variablenstdin
,stdout
undstderr
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 Funktioncaesar_encrypt(char *, int)
undcaesar_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 Optionstrsort -num
die Zeichenketten als ganze Zahlen interpretiert und in numerisch aufsteigender Reihenfolge sortiert werden.
Schreiben Sie dazu eine Funktionint comp_num(char *, char *)
. Benutzen Sieatoi()
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 diestruct grading_entry_t
, sodass sie diese in einer einfach verketten Liste nutzen können.
Legen Sie eine Dateigrading_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 alsval
im nächsten Aufruf.reduce(l, f, s) = f(l[n], f(l[n-1], … f(l[0], s) … )))
- 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 (Kleinbuchstabena
bise
), 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 antraverse_list
oderreduce_list
übergeben:- Gibt zeilenweise alle Einträge im Format
"<Matrikelnummer> hat in <Serie> <Anzahl> Punkt(e) erreicht."
aus. - Gibt zeilenweise
"<Matrikelnummer> <Serie>"
für alle Serien aus, in denen weniger als 10 Punkte erreicht wurden. - Gibt aus wie viele Abgaben insgesamt existieren.
- Gibt die höchste erreichte Punktzahl aus.
- Gibt die Summe der Punkte aller Abgaben zur Serie 3 aus.
$ ./grading_tasks b grading_results.db 4211 3 2342 4 $ ./grading_tasks d < grading_results.db 23
- Gibt zeilenweise alle Einträge im Format
- 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 Funktionenpush()
,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
undclean
enthält. Binärdateien, das Datenbankbeispiel, sowie Backupdateien Ihres Editors sollen nicht enthalten sein.
Sie finden Aufzeichnungen der Lehrveranstaltung auf tele-TASK unter http://tele-task.de/archive/series/overview/1176/.
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
- Aussagenlogik
- Schaltnetze, Schaltwerke
- Register
- von Neumann Rechner
- CPU, ALU, CU
- Instruktionsverarbeitung
- OpCode Formate, RTL
- Instruktionsarten
- Ein- und Ausgabe
Unit 3: Informationsdarstellung
- Universalität binärer Daten
- Abtasttheorem
- ganze Zahlen
- 1er Komplement
- 2er Komplement
- Gleitkommaformate
- ASCII, EBCDIC
- Unicode
- 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
Unit 5: Werkzeuge und Technologien
- Compiler
- Technologieprogramme: make
- Quellcodeverwaltung: git
- Debugger: gdb
- Test: Check, CUnit
- Beispiel für eine .gitconfig
- Beispiele fü gdb (Quelltexte und Anleitungen)
Unit 6: Programmiersprache C - Integrale Datentypen
- Integrale Datentypen
- Operatoren
- Ausdrücke
- Typkonvertierungen
- Vorrangregeln
- Beispiele aus der Vorlesung (tar)
Unit 7: Programmiersprache C - Kontrollfluss
- Anweisungen und Blöcke
- if-else
- else-if
- switch
- Schleifen: while and for, do-while
- break and continue
- goto and labels
- Beispiele aus der Vorlesung (tar)
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
- Adressarithmetik
- 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