Vorlesung im Wintersemester 2013/2014:

Algorithmische Mathematik I

Prof. Dr. Marc Alexander Schweitzer und Dr. Einar Smith

Assistenten: Patrick Diehl und Daniel Wissel

Die Mathematik stellt eine wichtige Grundlage für viele Bereiche des alltäglichen Lebens dar. Ingenieurswesen, Transport, und selbst Finanzmärkte profitieren von mathematischen Methoden und Modellen. Während viele Probleme direkt gelöst werden können, ist der Großteil von Hand nicht mehr zu bewältigen. Aus diesem Grund bedient man sich des Computers als Hilfsmittel zur Umsetzung mathematischer Verfahren.

Ziel und Inhalt der Vorlesung Algorithmischen Mathematik ist die Vermittlung von Fähigkeiten, die Schritte von der mathematischen Formulierung eines Problems bis hin zur Schritt-für-Schritt-Umsetzung in einem Algorithmus durchzuführen. Der Entwurf geeigneter Verfahren ist dabei ebenso Bestandteil des Lehrmaterials wie die Verifikation und Analyse von benötigter Laufzeit und erreichter Qualität (bei approximativen Verfahren).

Vorlesung

Vorkenntnisse

Die Algorithmische Mathematik I benötigt als Erstsemestervorlesung keine Vorkenntnisse.

Im Rahmen der Vorlesung wird jedoch auch die Fähigkeit zur konkreten Implementierung von Verfahren in C/C++ gelehrt. Eine Vertiefung der zugehörigen Grundlagen in Eigenarbeit wird empfohlen. Zu diesem Zweck können die unter Literatur angegeben Materialien dienlich sein (s.u.).

Vorlesungszeiten

Termine:
Gruppe A:	Mo	10-12 Uhr
	Mi	10-12 Uhr
Gruppe B:	Mo	12-14 Uhr
	Mi	08-10 Uhr
Beginn:	Mo	14.10.2013
Ort:	Großer Hörsaal Mathematik, We 10

Hinweis: Die Zuordnung der Gruppe A oder Gruppe B erfolgt durch die Wahl der Übungsgruppe. Dadurch entsteht ein überschneidungsfreier Stundenplan im ersten Semester. Vorlesung A und Vorlesung B sind inhaltlich identisch!

Sprechstunden

Die Sprechstunde von Herr Dr. Smith findet Montags (14:00 Uhr bis 16:00 Uhr) und Mittwochs (10:00 Uhr bis 12:00 Uhr) in der Wegelerstr. 4 in Zimmer 0.030 statt.

Die Sprechstunde von Herr Prof. Dr. Schweitzer findet Montags (14:00 Uhr bis 16:00 Uhr) in der Wegelerstr. 6 in Zimmer 6.005 statt

Ergänzungen

Die Folien zur Organisation der Vorlesung finden Sie hier (aktualisierte Fassung, 15.10.).

Die Folien zur Einführung in C finden Sie hier.

Die Folien zu Advanced C finden Sie hier und hier die Beispiele.

C-Programmcode aus der Vorlesung

Beispiele aus der Vorlesung vom 16.10.13 Bubblesort-Algorithmus Mergesort-Algorithmus Quicksort-Algorithmus Blatt04 (Programmieraufgabe 1) Blatt06 (Programmieraufgabe 1)

Übung

Übungsgruppen

Termine und Adressen:	Termine
Beginn:	Die erste Übung findet in der Woche ab dem 28.10.2013 statt
Ansprechpartner:	Patrick Diehl

Hinweis Die Anmeldungen zu den Übungsgruppen erfolgt vom 10.10.13 bis 16.10.13 im BASIS . Bei Fragen wenden Sie sich bitte an das Bachelor-Master-Büro.

Hinweis:
Am 14.10.13 und 15.10.13 wird in der Vorlesung Analysis I die Anmeldung zu den Übungsgruppen detailiert erklärt.

Übungsblätter

blatt01.pdf (Update 1) blatt02.pdf Material: util.h blatt03.pdf Material: graphen.zip blatt04.pdf Material: Programmieraufgabe 01 blatt05.pdf (Update 1: Graph in Aufgabe 2) blatt06.pdf (Update 1: Dreiecksgraph in Aufgabe 6) Material: Programmieraufgabe 01 blatt07.pdf (Update 1: Hinweise zu Aufgabe 1 und 2) blatt08.pdf (Abgabe Programmieraufgaben 16.12. (sic!)) blatt09.pdf Weihnachtsblatt Material: input1.dat blatt11.pdf blatt12.pdf blatt13.pdf (letztes Blatt)

Hinweise zur Abgabe

Auf jedem Übungblatt gibt es immer zwei Abgabetermine für die Theorieaufgaben und Praxisaufgaben:

1. Oben neben dem Text Übungsblatt finden Sie den Agbagetermin für alle Theorieaufgaben.
2. Unter dem Text Programmieraufgabe finden Sie in einem grauen Kasten den Abgabetermin zur Programmieraufgabe.

Die Theorieaufgaben werden wöchentlich in der Pause zwischen der Vorlesung A und der Vorlesung B abgegeben.
Die Praxisaufgaben (Programmieraufgaben) werden ab dem zweiten Übungblatt alle zwei Wochen in der Pause zwischen der Vorlesung A und der Vorlesung B abgegeben.

Klausur

Prüfungszulassung

1. Theorieaufgaben:

   Die Aufgabenblätter werden von zwei Studenten gemeinsam bearbeitet und schriftlich in der darauf folgenden Übung (Termin auf dem Übungsblatt) abgegeben. Auf jedem der Übungsblätter müssen 50% der Punkte erreicht werden. Ein beliebiges Übungsblatt darf gestrichen werden.

2. Praxisaufgaben:

   Die Programmieraufgaben werden einzeln bearbeitet. Es dürfen nur Programme in der Programmiersprache C nach Standard C99 (ISO-Standard ISO/IEC 9899:1999) abgeben werden. Auf jedem der Übungsblätter müssen 50% der Punkte erreicht werden.

3. Votierpunkte:

   Jeder Student muss im Laufe der Übungen jeweils eine Praxisaufgabe und jeweils eine Theorieaufgabe im Tutorium präsentieren. Wir erwarten, dass abgebene Aufgaben von jedem aus der Gruppe präsentiert werden können.

Klausurtermin

Die Klausur findet am 13.02.2014 statt. Weitere Informationen (Ort und Uhrzeit) werden im Laufe des Semesters hier veröffentlicht. Die Nachklausur findet am 28.03.2014 statt.

Fragestunde

Am 10.02.2014 findet zwischen 12:00 Uhr und 13:00 Uhr eine Fragestunde im großen Hörsaal Mathematik, We 10 statt. Bitte senden Sie uns Ihre Fragen bis zum 07.02.2014 per Mail zu.

Am Montag, den 10.02.2014, von 12:00-16:00 Uhr und am Dienstag, den 11.02.2014, von 10:00-13:00 Uhr findet eine zusätzliche Sprechzeit am HelpDesk statt.

Folgende Termine werden vom HelpDesk angeboten:

• Freitag, 21. März 2014, 15-17 Uhr
• Dienstag, 25. März 2014, 14-17 Uhr
• Mittwoch, 26. März 2014, 14-17 Uhr

Klausureinsicht

Klausureinsicht Nachtermin:	Mi.	26.02.2014, 16-17 Uhr
	Ort:	Wegelerstr 6 in Raum 5.002
	Hinweis:	letzte Möglichkeit zur Klausureinsicht
	Hinweis:	Lichtbildausweis und Studentenausweis sind mitzubringen
Klausureinsicht:	Do.	20.02.2014
	Ort:	Wegelerstr 6 in Raum 5.002
		Teilnehmer mit Nachname von A-F: 12:00 Uhr bis 13:00 Uhr Teilnehmer mit Nachname von G-M: 13:00 Uhr bis 14:30 Uhr Teilnehmer mit Nachname von N-S: 14:45 Uhr bis 15:45 Uhr Teilnehmer mit Nachname von T-Z: 15:45 Uhr bis 16:15 Uhr
	Hinweis:	Lichtbildausweis und Studentenausweis sind mitzubringen

Klausur

Klausurtermin:	Do.	13.02.2014
	Beginn:	09:00 Uhr
	Ort:	Wegelerstr 10 (Großer Hörsaal + Kleiner Hörsaal) und Nußallee 10 (Hörsaal A + B)
		Teilnehmer mit Nachname von A-F: Nußallee 10, Hörsaal B Teilnehmer mit Nachname von G-M: Nußallee 10, Hörsaal A Teilnehmer mit Nachname von N-S: Wegelerstr. 10, Großer Hörsaal Teilnehmer mit Nachname von T-Z: Wegelerstr. 10, Kleiner Hörsaal

• erlaubte Hilfsmittel: KEINE (bitte insbesondere Handys ausschalten)
• Papier (auch Schmierpapier) wird von uns zur Verfügung gestellt!
• Bitte PÜNKTLICH erscheinen!

Nachklausur

Ergebnisse

Die Ergebnisse der Nachklausur werden ab heute Nachmittag (02.04.2014) im BASIS-System einsehbar sein.

Klausureinsicht

Termin:	Do.	03.04.2014
	Ort:	Wegelerstr 6 in Raum 5.002
		Teilnehmer mit Nachname von A-M: 10:00 Uhr bis 12:00 Uhr Teilnehmer mit Nachname von N-Z: 14:00 Uhr bis 16:00 Uhr
	Hinweis:	Lichtbildausweis und Studentenausweis sind mitzubringen

Fragestunde

Am Freitag, den 21.03.2014 findet zwischen 13:30 Uhr und 14:30 Uhr eine Fragestunde im großen Hörsaal Mathematik (We 10) zur Nachklausur statt.

Nachklausur

Termin:	Fr.	28.03.2014
	Beginn:	13:00 Uhr
	Ort:	Wegelerstr 10 (Großer Hörsaal + Kleiner Hörsaal), Wolfgang-Paul-Hörsaal, Geographie-Hörsaal
		Teilnehmer Nachname von A-F: Wegelerstr. 10, Großer Hörsaal Teilnehmer Nachname von G-P: Kreuzbergweg 28, Wolfgang-Paul-Hörsaal Teilnehmer Nachname von Q-S: Meckenheimer Allee 166, Hörsaal der Geographie Teilnehmer Nachname von T-Z: Wegelerstr. 10, Kleiner Hörsaal

• erlaubte Hilfsmittel: KEINE (bitte insbesondere Handys ausschalten)
• Papier (auch Schmierpapier) wird von uns zur Verfügung gestellt!
• Bitte PÜNKTLICH erscheinen!

Literatur

Theorie

• Alternatives Skript zur Algorithmischen Mathematik
• Martin Hanke-Bourgois: Grundlagen der Numerischen Mathematik. Teubner
• Josef Stoer: Numerische Mathematik I. Springer
• B. Korte, J. Vygen: Combinatorial Optimization: Theory and Algorithms. Springer, 2006
• P. Deuflhard, A. Hohmann: Numerische Mathematik, de Gruyter
• T.H. Cormen, C.E. Leiserson, R.L. Rivest: Introduction to Algorithms. MIT Press 1990
• J. Kleinberg, E. Tardos: Algorithm Design. Pearson 2006

Ergänzungen zur Vorlesung

• Ergänzungen (Stand: 19.12.) zur Vorlesung
• Folien "Direkte Löser"
• Folien "Kondition, Stabilität, Rundung"

Programmieren

• Brian W. Kernighan, Dennis M. Ritchie: Programmieren in C
• Bjarne Stroustrup: Die C++-Programmiersprache
• Bruce Eckel: Thinking in C++ [frei erhältlich zum Download]
• Stanley B. Lippman, Josée Lajoie, Barbara E. Moo: C++ Primer

Literatur kann beispielsweise in der Institutsbibliothek oder der Universitäts- und Landesbibliothek Bonn entliehen werden.

Die Beispiele in der Vorlesungen werden in C vorgestellt werden. Dennoch ist oben genannte Literatur zu C++ uneingeschränkt zu empfehlen, da C++ Compiler auch C verstehen. C++ ist die modernere Sprache, deren Kenntnis insbesondere auch nach abgeschlossenem Studium hohen Wert hat. Programmieraufgaben dürfen nur in C abgegeben werden.

Onlinematerialien zum Lernen von C/C++

Zur Bedienung und Installation von Compilern

Gleitkommazahlen

• IEEE 754-Standard für Gleitkommazahlen
Wikipedia-Artikel zu IEEE 754
• Lecture Notes by William Kahan: IEEE Standard 754 for Binary Floating-Point-Arithmetic

Plotten von Daten

• Gnuplot
• Beispiele zu Gnuplot