Vorlesung Computerorientierte Mathematik

Der Zyklus Computerorientierte Mathematik besteht aus zwei Vorlesungen, die in zwei aufeinanderfolgenden Semestern angeboten werden. Er entspricht einer Informatikgrundausbildung für Studenten der Studienrichtung Techno- und Wirtschaftsmathematik, sowie der Studienrichtung Informationstechnik im Maschinenwesen.

Die Veranstaltung gliedert sich in einen Vorlesungsteil (5 Semesterwochenstunden im ersten Semester und 3 Semesterwochenstunden im zweiten Semester) und einen Übungsteil (ebenfalls 5 Semesterwochenstunden im ersten Semester und 3 Semesterwochenstunden im zweiten Semester). Der Übungsteil beinhaltet eine umfangreiche praktische Programmierausbildung mit praktischen Übungen an UNIX-Rechnern, die zu Beginn individuell, später in Gruppen zu bearbeiten sind.

Neben dem Besuch von Vorlesung und Übung werden wöchentlich Aufgaben gestellt, die von Studierenden höheren Semesters korrigiert werden. Auf diese Weise erhalten die Studierenden einen Einblick, wieweit sie den Stoff der Vorlesung durchdrungen haben.

Eine Übersicht über den Stoff der Vorlesung und der Übung ist angefügt.

Inhalt der Vorlesung

Einleitung
Probleme, Algorithmen, Programme: Einige Beispiele
Ausdrücke, Anweisungen, Kontrollstrukturen
Darstellung von Syntaxregeln
Objekte, Typen, Datenstrukturen: Einführung und Beispiele

5.1
Einführung
5.2
Ein Überblick über Datenstrukturen
5.3
Arrays
5.4
Strings
5.5
Records
5.6
Listen
5.7
Stacks
5.8
Queues (Warteschlangen)
Algorithmen auf Arrays

6.1
Suchen einer Komponente vorgegebenen Wertes
6.2
Matrizenmultiplikation und Lösung von Linearen Gleichungssystemen
6.3
Kürzeste Wege in gerichteten Graphen
Abstraktion von Methoden und Daten

7.1
Funktionale (Prozedurale) Abstraktion

7.1.1
Funktionen und Prozeduren
7.1.2
Parameter und Datenfluß
7.1.3
Der Sonderfall der Arrays in C++
7.1.4
Gültigkeitsbereiche von Identifiern (Scope and Lifetime)
7.1.5
Funktionsprototypen und externe Deklarationen
7.1.6
Abarbeitung von Funktionsaufrufen
7.1.7
Der Run-Time Stack

7.2
Modulare Abstraktion

7.2.1
Module in C++
7.2.2
Ein Modul für einen Zufallszahlengenerator

7.3
Datenabstraktion durch Klassen

7.3.1
Structs in allgemeiner Form
7.3.2
Definition von Klassen
7.3.3
Die Klasse Istack
7.3.4
Die Klasse FracType
Rekursion

8.1
Beispiele für rekursive Algorithmen
8.2
Wo Rekursion zu vermeiden ist
Die Analyse von Algorithmen

9.1
Analysearten
9.2
Die asymptotische Notation
9.3
A posteriori Analyse: Laufzeitmessungen
Sortieren in Arrays

10.1
Direkte Methoden

10.1.1
Sortieren durch Austauschen (Bubblesort)
10.1.2
Sortieren durch direktes Auswählen
10.1.3
Sortieren durch direktes Einfügen (straight insertion)

10.2
Mergesort

10.3
Beschleunigung durch Aufteilung (Divide and Conquer)

10.4
Quicksort

10.4.1
Der Algorithmus
10.4.2
Der Rekursionsaufwand von Quicksort
10.4.3
Der Worst Case Aufwand von Quicksort
10.4.4
Der mittlere Aufwand von Quicksort

10.5
Heapsort

10.5.1
Die Grobstruktur von Heapsort
10.5.2
Die Implementation des Heaps
10.5.3
Die Implementation von Heapsort
10.5.4
Die Analyse von Heapsort
Untere Komplexitätsschranken für das Sortieren
Zahlendarstellungen und Rechnerarithmetik

12.1
Zahlensysteme
12.2
Darstellung ganzer Zahlen im Rechner

12.2.1
Die Vorzeichen/Betrags-Darstellung
12.2.2
Komplement-Darstellungen

12.3
Darstellung reeller Zahlen

12.3.1
Festkommazahlen
12.3.2
Gleitkommazahlen
12.3.3
Genauigkeit von Gleitkommadarstellungen
12.3.4
Der Einfluß von Algorithmen auf die numerische Genauigkeit
Pointer und dynamische Objekte

13.1
Das Speichermodell
13.2
Pointer und Adressen
13.3
Pointer und Arrays
13.4
Referenzen
13.5
Dynamische Objekte
13.6
Dynamische mehrdimensionale Arrays
Verkettete Listen

14.1
Grundoperationen in einfach verketteten Listen
14.2
Eine Implementation der Klasse ilist mit verketteten Listen
14.3
Andere Listenstrukturen
Eine Anwendung verketteter Listen: Bucketsort

15.1
Einfaches Bucketsort
15.2
Einige Anwendungen auf Sortierverfahren
Baumstrukturen

16.1
Grundlegende Konzepte und Definitionen
16.2
Durchlaufstrategien
Suchbäume

17.1
Definition
17.2
Operationen auf Suchbäumen
17.3
Balancierte Bäume
AVL-Bäume
B-Bäume

19.1
Definition von B-Bäumen
19.2
Basis-Operationen auf B-Bäumen
19.3
Einfügen eines Schlüssels
19.4
Löschen eines Schlüssels
Optimale Statische Suchbäume
Huffman Codes und Datenkompression
Hash Tabellen, Gestreute Speicherung

22.1
Direkte Adressierung
22.2
Hash-Tabellen
22.3
Hash-Funktionen
22.3.1
Die Divisions Methode
22.3.2
Die Multiplikations Methode
22.3.2
Universelles Hashen

22.4
Offene Adressierung
Rechnerarchitektur: Schaltfunktionen und Schaltnetze
Vereinfachung von Schaltnetzen

24.1
Das Verfahren von Karnaugh
24.2
Das Verfahren von Quine und McCluskey
Schaltungen mit Delays (Schaltwerke)

25.1
Einführung
25.2
Addierwerke
Programmierbare Logische Arrays (PLAs) - Das Prinzip der Mikroprogrammierung

26.1
Aufbau eines PLAs
26.2
Zur Programmierung von PLAs

26.3
Anwendungen von PLAs: ROMs und Mikroprogrammierung

Inhalt der Übungen

Ziel der Übungen ist es, die in der Vorlesung vermittelten Kenntnisse anzuwenden und zu vertiefen. Dazu werden Aufgaben gestellt, welche von den Studierenden zu bearbeiten sind. Neben Aufgaben zu den in der Vorlesung behandelten Stoff werden auch Implementationsaufgaben gestellt. Im Zusammenspiel zwischen Vorlesung und Übung werden die Studierenden so mit der Programmiersprache C++ vetraut gemacht. Der Arbeitsaufwand für die Bearbeitung der Aufgaben liegt bei etwa 4-6 Stunden für die schriftlich zu bearbeitenden Aufgaben und bei 12-14 Stunden für die Programmieraufgaben. Die Anzahl der gestellten Aufgaben ist im zweiten Teils des Zyklus geringer als im ersten Teil.

Die Programmieraufgaben umfassen folgende Themenkomplexe:

Erlernen der Handhabung einer UNIX-Workstation. Einrichten von Subdirectories, Umgang mit Editoren und Compilern.
Implementation einfacher Programme wie Berechnung von Devisenkursen und Zinseszins. Erstellen von Nassi-Schneidermann Diagrammen vorab.
Implemetation einfacher Simulationen wie Kartenspielen und der Ausbreitung eines Waldbrandes.
Einlesen einer Entfernungsmatrix und Berechnung der kürzesten Wege zwischen vorgegebenen Punkten, welche der Benutzer dann mittels eines Menüs vom Computer erfragen kann (Reiseplanung).
Sortieren ganzzahliger Werte.
Implementation einfach verketter, dynamisch abgespeicherter Listen. Erstellen einer C++-Klasse für einfach verkettete Listen.
Implementation von dynamisch abgespeicherten Suchbäumen. Erstellen einer C++-Klasse für höhenbalancierte Suchbäume (AVL-Bäume).
Erstellen einer C++-Klasse zur Implementation der Datenstruktur Hashtable.

Besonderes Augenmerk wird auf sorgfältiges Programmieren und auf eine gute Vorabplanung gelegt, da der Rechnersaal nur von 9 bis 18 Uhr geöffnet ist. Bei der Abnahme der Programme wird auf folgende Punkte besonderen Wert gelegt. Eine Forderung nach Nachbearbeitung der Programme ist gerade bei den ersten Programmen der Normalfall.

Aufteilen komplexer Programme in Header- und Implementationsdateien. Erstellen von Readme-Dateien neben der Kommentierung innerhalb des Source-Textes.
Gute Kommentierung der einzelnen Programmfragmente und ihrer Schnittstellen.
Stabilität der Programme bezüglich Fehleingaben. Prüfen der Parameter einer Funktion auf Zulässigkeit, Ausgabe von verständlichen Fehlermeldungen bei Problemen.
Einfache Form der Benutzerführung über Menüs.
Integration von Datenstruktur und Zugriffsmethoden in C++-Klassen.

About this document ...

Vorlesung Computerorientierte Mathematik

The command line arguments were:
latex2html -split 0 coma_uebersicht.tex.

The translation was initiated by Markus Schaeffter on Wed Jul 19 16:28:47 MET DST 1995

Markus Schaeffter
Wed Jul 19 16:28:47 MET DST 1995