Reduktionen

Informatikern wird häufig nachgesagt, faul zu sein. „Sie haben einen Hammer und sehen in jedem Problem einen Nagel!“ Dabei sind sie eigentlich nur effizient: Haben sie einen Algorithmus geschrieben, so wollen sie mit seiner Hilfe viele Probleme lösen, anstatt für jedes einzelne Problem einen neuen Algorithmus zu finden.

In diesem Workshop werden wir das Konzept der Reduktionen kennen lernen, mit deren Hilfe algorithmische Probleme ineinander überführt werden können und wir so Algorithmen für verschiedene Probleme wiederverwenden können. Wir werden diese Erkenntnisse anwenden und sehen, wie wir so genannte SAT-Solver einsetzen können, um schwierige Berechnungsprobleme zu lösen.