Nach positiver Absolvierung der Lehrveranstaltung sind Studierende in der Lage...

Heuristiken und entsprechende Computerprogramme zu entwickeln, die bei der Suche in einem schlecht fassbaren Suchraum unterstützen.

Gegeben sind zwei endliche Mengen A und B mit |A| = |B|, oder zwei Listen von endlichen Mengen A= (A₁,A₂,…) und B = (B₁,B₂,…) mit |A_k| = |B_k| für alle k. Man sagt, dass die Objekte in A_k und B_k die Größe k haben.

Gesucht ist eine Bijektion S : A → B und/oder eine Funktion s : A→ ℕ, die verschiedene durch den Benutzer vorgegebene Einschränkungen erfüllen. In diesem Seminar soll ein Programm (aufbauend auf SageMath und vorhandene Routinen) entwickelt werden, das bei dieser Suche unterstützt. Ausgabe sind verschiedene Informationen über S und s, beispielsweise

• existiert nicht (idealerweise mit Begründung),
• existiert,
• folgende Werte sind erzwungen:…,
• das Bild von a ∈ A muss eines der folgenden Elemente aus B sein:…,
• …

Eine genaue Beschreibung der Ideen finden Sie in den Lehrunterlagen.

Gruppenarbeit und individuelle Betreuung

Das Seminar wird in mehreren Stufen ablaufen, Termine dienen nur der Orientierung:

• Ende Oktober: Einführung (einEr StudentIn): Bijektionen in der Kombinatorik
• bis Ende Dezember: Ausarbeiten von Modulen und experimentelle Implementierungen (in betreuten Projektgruppen von 2 bis 3 Personen)
• Anfang Jänner: Präsentation und Diskussion
• Ende Jänner: Zusammenführen der Module und endgültige Implementierung

Die Vorbesprechung sowie ein Einführungsvortrag finden am Donnerstag, 10.10 von 10-12 Uhr statt, und zwar im Zeichensaal 3 im Freihaus, 7. Stock, grüner Bereich.

Präsentation, Code oder Seminararbeit

• Grundkenntnisse Kombinatorik und Graphentheorie
• Kreativität
• rudimentäre Programmierkenntnisse in Python