392020 Algorithmische Problemlösetechniken (S) (WiSe 2010/2011)

In diesem Blockseminar soll eigenständiges Arbeiten an bisher ungelösten Problemen (z.B. Entscheidungs- oder Optimierungsprobleme) geübt werden. Zu Beginn werden verschiedene Probleme vorgestellt, für deren Lösung im Verlauf der Veranstaltung Algorithmen überlegt werden sollen.

Es kommt nicht darauf an, ein Problem vollständig oder effizient zu lösen; teilweise ist nicht einmal bekannt, ob effiziente Lösungen existieren. Vielmehr ist es wichtig das Problem vollständig zu verstehen, vorhandene Ansätze zu recherchieren, und schließlich verschiedene eigene Ansätze zu entwickeln, implementieren, evaluieren und dokumentieren.

Es soll in Kleingruppen an je einem Problem gearbeitet werden: theoretisch (Recherche, Verständnis, Analyse) als auch praktisch (Implementation, Dokumentation, Presentation).

Mögliche Themen:

• Varianten des TSP
• Färbbarkeit von Hypergraphen
• Varianten des Consecutive Ones Problems
• ...

Alle Problemstellungen sind kurz. Sie sind zwar formal und auf abstrakter Ebene definiert, haben aber einen bioinformatischen Hintergrund.

Konkretes Beispiel:

Consecutive-Ones-Problem allowing k blocks.
Given: Binary matrix M.
Question: Is there an ordering of the columns of M such that the
entries 1 in each row appear consecutively in at most k blocks?

Hintergrund: Rekunstruktion von Genclustern. Die zu sortierenden Spalten entsprechen Genen, Spalten die hintereinanderliegen sollen entsprechen Genen, die im Genom vermutlich hintereinanderliegen.

Teilnehmer können auch gerne eigene Themen vorschlagen.

Vielleicht ergibt sich hier auch ein Thema für eine Bachelorarbeit...!?

Requirements for participation, required level

• Grundlagen in Algorithmen und Datenstrukturen
• Beherrschen einer Programmiersprache

vor allem:

• Interesse
• Eigeninitiative

External comments page

http://wiki.techfak.uni-bielefeld.de/gi/Teaching/2010winter/AlgProb