Grundlagen der Informatik 1 (für Studiengang E-Technik),
WS 01/02
Auf dieser Seite werden während des Semesters weiterführende
Informationen sowie die jeweiligen Aufgabenzettel bereitgestellt.
Eine Übersicht über Inhalte, Termine,... der Veranstaltung
findet sich in unserer
Liste der Lehrveranstaltungen.
Inhalt dieser Seite:
Die kommentierten Lösungen der
Aufgaben werden von den Teilnehmern mit LaTeX formatiert. Hierzu gibt
es einfach zu handhabende Template-Dateien:
gdi1-muster.tex und das
Hilfsfile defs.tex.
Das im Praktikum verteilte
Einführungsblatt zu Emacs und LaTeX
ist auch online verfügbar.
(ps/gzip, 36 kB -
ps/gzip/2up, 37 kB -
pdf, 64 kB)
Für die eingehendere
Beschäftigung mit diesem System zum anspruchsvollen Setzen von
Dokumenten ist als Einstieg Leslie Lamport: Das LaTeX
Handbuch. Addison-Wesley 1995 ebenso wie Helmut Kopka: LaTeX
Einführung, Band 1. Addison-Wesley 2000 zu empfehlen. Alles, was in
bezug auf LaTeX für die Abgabe der Aufgabenblätter notwendig ist,
findet man ebenfalls in der online verfügbaren
Kurzanleitung zu LaTeX.
Eine Einführung in die Grundlagen der Benutzung des UNIX-
bzw. Linux-Betriebssystems findet man in dem
SuSE-Linux
Handbuch im Kapitel 19. Interessant sind dabei insbesondere die
Abschnitte 19.5 bis 19.9.
Fachbegriffe lassen sich häufig sehr gut in der im WWW
verfügbaren Encyclopaedia Britannica nachschlagen:
http://www.britannica.com
Falls Ihr zuhause Software installieren wollt, sind die folgenden
Links vielleicht nützlich:
- Linux-Betriebssystem:
Bei Linux sind üblicherweise bereits alle nötigen
Werkzeuge dabei, z.B. LaTeX, Emacs und der Gnu-C-Compiler.
Linux darf kostenlos kopiert werden.
Man kann auch CDs mit Handbuch und Support von einem Distributor
kaufen, z.B. von:
Solche Pakete sind z.B. im Fachbuchhandel erhältlich.
- Für Windows-Plattformen sind die Werkzeuge ebenfalls
kostenlos erhältlich:
- LaTeX:
Hier ist z.B.
MiKTeX
zu empfehlen (zum Herunterladen)
- Die Gnu-Werkzeuge einschließlich
C-Compiler und Editor Emacs gibt es z.B. im
Cygwin-Projekt
(zum Herunterladen).
- MacOS:
- Serie 1
(ps/gzip, 22 kB -
pdf, 36 kB):
ausgegeben am 19.10.2001.
Abgabe und Besprechung von Aufgabe 2
in der Übung am 25.10.2001.
Abgabe und Besprechung von Aufgabe 1
in der Übung am 8.11.2001.
- Serie 2
(ps/gzip, 25 kB -
pdf, 56 kB):
ausgegeben am 2.11.2001.
Abgabe und Besprechung in der Übung am 8.11.2001.
Musterlösung:
- Serie 3
(ps/gzip, 25 kB -
pdf, 69 kB):
ausgegeben am 23.11.2001.
Abgabe und Besprechung in der Übung am 29.11.2001.
Musterlösung:
- Serie 4
(ps/gzip, 28 kB -
pdf, 45 kB):
ausgegeben am 30.11.2001.
Abgabe und Besprechung in der Übung am 6.12.2001.
- Serie 5
(ps/gzip, 27 kB -
pdf, 48 kB):
ausgegeben am 11.1.2002.
Abgabe und Besprechung in der Übung am 17.1.2002.
- Serie 6
(ps/gzip, 27 kB -
pdf, 57 kB):
ausgegeben am 25.1.2002.
Abgabe und Besprechung in der Übung am 31.1.2002.
-
Zugang zu den Rechnern des Rechnerlabors
(ps/gzip, 25 kB -
pdf, 45 kB)
-
Einführungsblatt zu Emacs und LaTeX
(ps/gzip, 36 kB -
ps/gzip/2up, 37 kB -
pdf, 64 kB)
- Aufgaben zu: Erste Schritte in C / Grundlegende Unix-Kommandos / LaTeX
(ps/gzip, 27 kB -
pdf, 57 kB)
- Aufgaben zu: Primzahlen mit dem Sieb des Erathostenes / Der Goldene
Schnitt und die Fibonacci-Zahlen
(ps/gzip, 22 kB -
pdf, 55 kB)
- Aufgabe zu: Türme von Hanoi mit Rekursion
(ps/gzip, 25 kB -
pdf, 53 kB)
- Aufgabe zu: Kadonischer Leuchtturm mit Grammatik
(ps/gzip, 21 kB -
pdf, 45 kB)
- Aufgabe zu: Polymorphe Funktionen in C
(ps/gzip, 25 kB -
pdf, 51 kB)
- Aufgabe zu: Heapsort
(ps/gzip, 26 kB -
pdf, 67 kB)
Die folgende Liste von Lerninhalten wird im Laufe des Semesters
fortgeschrieben. Sie dient als Checkliste, mit welchen Themen und
Begriffen die Veranstaltungsteilnehmer vertraut werden sollten. Eine
"Session" entspricht einer zusammengehörigen
Lerneinheit, sie muß nicht notwendig in genau einer Vorlesung
abgehandelt werden.
- Die Hierarchie der Programmiersprachen (von "unten nach
oben", d.h. von hardwarenah bis anwendungsnah): (1) CPU
Mikrocode (2) Maschinencode (3) Assembler (4) Wide-spectrum
Languages, 3rd generation (C,C++,Java,Ada,...) (5) Domain-specific
Languages (anwendungsspezifische Sprachen)
- von-Neumann'sche Rechnerorganisation
(CPU, Datenbus und Adressbus, RAM und ROM, Ein-/Ausgabeeinheit)
- Rechnerarchitektur
- Bytes, Bits, Maschinenworte
- CPU und ihre Grundstruktur (MAR, PC, IR, Decodierer/Steuerwerk,
MBR, ALU, A, L, MR),
- SISD
- Speicheradresse versus Speicherinhalt
- Assembler und Maschinensprache
- Eine einfache "fiktive" Assemblersprache mit
Load/Store/Jump/Integer-Befehlen
- Realisierung der Assemblerbefehle im (fiktiven) Mikrocode einer CPU
- fetch-/execute-Phasen
Literatur zu Session 1
Oberschelp und G. Vossen: Rechneraufbau und Rechnerstrukturen, Kapitel 8
Hintergrundinformationen zu Session 1
- Liste von Mikroinstruktionen
(ps/gzip, 15 kB -
pdf, 41 kB)
- Das klassische Hello-World-Programm als einfachstes C-Programm
- Aufruf des C-Compilers
- Die Phasen des Übersetzens:
Präprozessor, Compiler, Assembler, Linker
- Die main()-Funktion
- Deklarationen und Anweisungen
(Eingabe-, Ausgabe-, leere, Kontrollfluß-, ...-Anweisungen)
- Ausgabe mit printf(), einige Formatparameter dazu
- Die Variablentypen int, float, char
- Zuweisungen
- Arrays und Strukturen (struct)
- Schleifen mit while, for
- Sprünge mit return, goto
- Bedingte Ausführung mit if
- Boolsche Vergleichsoperatoren ==, !=, <, >, <=, >=
- Aufzählungstyp enum
- benannte Typedefinition mit typedef
- Erweiterte Konstrukte für Schleifen: continue, break
- mehrfach-Zuweisung i=j=0;
- Post-Autoinkrement i++
- Schleifen mit do-while
- mehrfache Verzweigung mit switch
- Äquivalenz von switch und if-else
- boolsche Operatoren ||, &&, !, partielle Auswertung dabei
- Sprünge mit goto und Label
Literatur zu Session 2
Siehe das Online-Material zur Programmiersprache C
oben.
Hintergrundinformationen zu Session 2
- Einschub virtuelle Adreßverwaltung
- In Speicherworten: Operationen, Daten, Adressen
- Memory Management Unit (MMU)
- Address Map
- Speicherseiten, Page Frames
- Page Fault, Reaktion des Betriebssystems darauf
- Im virtuellen Adreßraum für Programmdaten: globale
Daten, Stack, Heap
- globale/lokale Datendefinition in C
- Scope von Variablen
- Stackpointer
- dynamisch verwalteter Speicher auf dem Heap
- Syntax von Pointern in C: Typdefinition und Verwendung
- Adreßarithmetik
- dynamischer Speicher mit malloc()/free()
- Systemaufrufe vs. Bibliothek LibC
- Cast zwischen Datentypen
- void-Zeiger
- Eingabe mit scanf()
- 0-terminierter (char-)String
- Array von Strings
- Grenzen eines Arrays, und das Unheil bei ihrer Überschreitung
- Länge eines Strings: strlen(s)
- Arithmetik mit Pointern und Arrays: &(a[3]), a+3
- Auswertung der Argumente der Programmaufrufzeile mit argc, argv
- rekursiver Funktionsaufruf
Literatur zu Session 3
Zur virtuellen Adreßverwaltung siehe:
Oberschelp und G. Vossen: Rechneraufbau und Rechnerstrukturen, Kapitel 11.3.1.
Zur Programmiersprache C siehe das Online-Material
oben.
Hintergrundinformationen zu Session 3
- Scanner
- Syntaxchecker
- Backus-Naur-Form (BNF)
- Zurücklegen eines Tokens, wenn es nicht paßt
- Syntax-Diagramme
Literatur zu Session 4
H. Balzert: Lehrbuch Grundlagen der Informatik, Kap. 2.4.2
Hintergrundinformationen zu Session 4
- Binäre Suche
- allgemeine Suchfunktion, die mit verschiedenen speziellen
Vergleichsfunktionen zusammengebunden werden kann, unter
Verwendung von void-Zeigern auf die Parameter
- Bubblesort
- Komplexitätsberechnung O(...)
- Quicksort
- Berechnung der Komplexität eines Algorithmus', am Beispiel
von Bubblesort
Literatur zu Session 5
- H. Balzert: Lehrbuch Grundlagen der Informatik, Kap 3.9, Kap.
3.10 und Kap 3.6.
- A. Aho, J. Hopcroft, J. Ullman: Data Structures and Algorithms,
Kap. 1.5 (über Komplexitätsberechnung)
Hintergrundinformationen zu Session 5
Der Schein für die Veranstaltung kann entweder durch Vorrechnen
in der Übung erlangt werden, oder durch Bestehen eines
Fachgesprächs.
Prüfungsstoff:
- alle Stichworte in der obigen Liste
- alle Beispiele aus der Vorlesung
- alle sechs Übungsaufgaben
Ein Teilnehmer muß ein paar Zeilen in C programmieren
können (aber kein größeres Programm).
Termin:
Montag, 11.2.2002, 16:00 Uhr bis ca. 17:30 Uhr
Orte:
MZH 8055 und MZH 8050 (8. Ebene im MZH)
Dauer: 20(-30) Minuten
Es werden 5 Gruppen zu je ca. 5 Teilnehmern geprüft, parallel
von Jan Peleska und Jan Bredereke. Falls sich die Studenten vorher
selbst in geeignete Gruppen organisieren, müssen sie nicht auf
den Beginn ihres Fachgespäches warten und können ggf.
später als 16:00 Uhr erscheinen.
Wer einen Schein haben möchte, besorgt sich diesen bitte bei
seiner Fachbereichsverwaltung, füllt ihn aus und bringt ihn am
besten gleich zum Fachgespräch mit.
Wer den Schein durch Vorrechnen bestanden hat, besorgt ihn sich
bitte ebenfalls selbst, füllt ihn aus und gibt ihn Jan Peleska
zum Unterschreiben.
agbs@informatik.uni-bremen.de,
letzte Änderung am 20. Juni 2002