Wichtigkeit von Merkmalen für die Klassifikation von SAT-Instanzen (Proposal)

Aus IPD-Institutsseminar
Zur Navigation springen Zur Suche springen
Vortragende(r) Elizaveta Danilova
Vortragstyp Proposal
Betreuer(in) Jakob Bach
Termin Fr 29. April 2022
Vortragsmodus in Präsenz
Kurzfassung SAT gehört zu den wichtigsten NP-schweren Problemen der theoretischen Informatik, weshalb die Forschung vor allem daran interessiert ist, besonders effiziente Lösungsverfahren dafür zu finden. Deswegen wird eine Klassifizierung vorgenommen, indem ähnliche Probleminstanzen zu Instanzfamilien gruppiert werden, die man mithilfe von Verfahren des maschinellen Lernens automatisieren will. Die Bachelorarbeit beschäftigt sich unter anderem mit folgenden Themen: Mit welchen (wichtigsten) Eigenschaften kann eine Instanz einer bestimmten Familie zugeordnet werden? Wie erstellt man einen guten Klassifikator für dieses Problem? Welche Gemeinsamkeiten haben Instanzen, die oft fehlklassifiziert werden? Wie sieht eine sinnvolle Familieneinteilung aus?