(Donnerstags 14-16 Uhr, Raum
MI 01.11.018)
Noch Plätze frei!
Zusammenfassung
Es gibt viele interessante Themen in der Informatik, die im Studium gar
nicht, nur unzureichend, oder erst gegen Ende behandelt werden, die
aber sowohl wegen ihrer Relevanz als auch wegen der Schönheit der
Lösung zu den Perlen zählen. Dieses Proseminar möchte
Sie gerne mit einigen davon bekannt machen. Der Schwerpunkt liegt dabei
auf Problemen an der Schnittstelle von Informatik, Mathematik und
Logik.
Themenliste:
- Simplex: Hier
geht es darum, eine lineare Funktion unter linearen Nebenbedingungen zu
maximieren.
- Kildalls Algorithmus
wird in der Programmanalyse eingesetzt. Er führt das Herausfinden
bestimmter Programmeigenschaften auf die iterative Lösung eines
Ungleichungssystems zurück. Im Vordergrund steht die Arbeitsweise
und die Korrektheit dieses Algorithmus.
- FFT (Fast Fourier
Transform) ist ein bekannter Algorithmus, der mittlerweile in
fast jedem Chip zu finden ist. Neben der Darstellung der Funktionsweise
soll ein Anwendungsbeispiel (z.B. schnelle Multiplikation) vorgestellt
und implementiert werden.
- Coxeter-Todd:
Ein einfacher aber effektiver Algorithmus aus der Gruppentheorie, der
die Anzahl der Nebenklassen ein Gruppe bestimmt
- Graphenfärbung:
wird eingesetzt sobald eine Verteilung von mehrern Objekten auf eine
kleinere Menge stattfinden soll, wobei die Objekte von einander
abhängen können (z.B. in Compilern - Registervergabe).
- Lambda Kalkül
ist ein minimales Kalkül, das den Kern aller funktionalen
Programmiersprachen modelliert. Auf der Basis von nur 3 Konstrukten und
einer Rechenregel kann man Boolesche Werte, Zahlen, Listen und eine
ganze Programmiersprache schaffen.
- Typisiertes Lambda
Kalkül: Haben Sie sich schon mal gefragt, wie in
funktionalen Sprachen der Typ einer Funktion automatisch berechnet
werden kann? Die Antwort darauf kann man am besten am typisierten
Lambda Kalkül erklären.
- Unifikation:
Wer sich mal gefragt hat, wie Pattern Matching in funktionalen und
insbesondere in logischen Programmiersprachen (wie Prolog, Gofer, ML,
Haskell etc) funktioniert wird hier eine Anwort finden.
- Resolution :
ist ein mächtiges Verfahren um zu entscheiden ob eine (hier
aussagenlogische) Formel wahr oder falsch ist.
- Davis Putnam:
ist ein weit verbreitetes und schnelleres Verfahren, um das obige
Problem zu entscheiden.
- Pratts
Primalitätszertifikat: Wie kann ich jemanden davon
überzeugen, dass 20988936657440586486151264256610222593863921
eine Primzahl ist, ohne dass er lange rechnen muss? Hier wird ein
Verfahren vorgestellt, das ein kurzes
überprüfbares
Zertifikat liefert, dass die Primalität einer Zahl beweist.
- Rabin-Miller
Primatitätstest ist ein faszinierend einfacher und sehr
relevanter probabilistischer
Primalitätstest. Wird die Zahl nicht akzeptiert, so ist sie mit
Sicherheit keine Primzahl. Akzeptiert das Verfahren die Zahl, so
bedeutet das, dass sie mit sehr hoher Wahrscheinlichkeit eine Primzahl
ist.
- Symbolische
Berechnung mit Summen: Wie kann man geschachtelte
Summenausdrülcke vom Computer berechnen lassen? Sowohl
Computeralgebrasysteme als auch Theorembeweiser verfügen
ülber solche Möglichkeiten. Hier wird ein "einfacher" Fall
behandelt.
Lernziele
- Selbständige Einarbeitung in wissenschaftliche
Literatur.
- Präsentationstechniken.
- Umgang mit LaTeX, einem System zum Schreiben
technischer Texte.
- Programmierung kompakter mathematischer/logischer
Algorithmen.
Anmeldung
 |
Interessentinnen/en können sich bei der
Vorbesprechung oder vorab per Email bei ballarin@in.tum.de anmelden. In
der E-Mail sollen folgende Informationen enthalten sein:
- Name, Vorname
- Studiengang und Studienfach
- Semester
- E-Mail (nur Adressen @in.tum.de)
- bevorzugtes Thema
|
Vorbesprechung
| |
Die Vorbesprechung findet am 15.07.2004,
16.00 Uhr im Raum MI 01.09.014 statt. |
Termine und Betreuer
Das Proseminar findet donnerstags von 14
Uhr bis 16 Uhr im Raum 01.11.018 statt.
Hinweise
Ein Schein wird für folgende Leistungen vergeben : eine
Ausarbeitung, ein Vortrag, eine Implementierung (wenn verlangt) und die
regelmässige Anwesenheit.
Hinweise zur Anfertigung einer Seminararbeit
| |
Die Seminararbeiten sollten mit dem
Textsatzsystem LaTeX erstellt werden. |
| |
Bei Fragen zu LaTeX sei einerseits auf die
folgenden Links hingewiesen, ferner kann auch der Betreuer um
Hilfestellungen bzw. Literaturangaben gebeten werden: |
|
|
| |
Eine weitere Anleitung zur Erstellung von
Ausarbeitungen finden sie hier. |
| |
Informationen zur Installation von LaTeX
unter Windows finden Sie hier.
|
Hinweise zur Gestaltung der Vorträge
| |
Wer seine Folien mit LaTeX erstellen möchte
findet hier einige
Hinweise (einschließlich Rahmen-Datei als Vorlage) |
Interessante Links
|
