Fakultät für Informatik

TU München - Fakultät für Informatik
Software- and Systems Engineering Research Group

TUM

Proseminar | Wintersemester 2004/05
Mathematische und logische Perlen der Informatik
Tobias Nipkow, Clemens Ballarin, Amine Chaieb

 

(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:

  1. Simplex: Hier geht es darum, eine lineare Funktion unter linearen Nebenbedingungen zu maximieren.
  2. 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.
  3. 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.
  4. Coxeter-Todd: Ein einfacher aber effektiver Algorithmus aus der Gruppentheorie, der die Anzahl der Nebenklassen ein Gruppe bestimmt
  5. 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).
  6. 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.
  7. 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.
  8. 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.
  9. Resolution : ist ein mächtiges Verfahren um zu entscheiden ob eine (hier aussagenlogische) Formel wahr oder falsch ist.
  10. Davis Putnam: ist ein weit verbreitetes und schnelleres Verfahren, um das obige Problem zu entscheiden.
  11. 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.
  12. 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.
  13. 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



*  Simplex .
* Kildall's  paper .
*  FFT .

© Software & Systems Engineering Research Group
Sitemap |  Kontakt/Impressum
Letzte Änderung: 2004-07-15 16:53:18