Wichtigkeit von Merkmalen für die Klassifikation von SAT-Instanzen (Abschlusspräsentation)

Aus IPD-Institutsseminar
Zur Navigation springen Zur Suche springen
Vortragende(r) Elizaveta Danilova
Vortragstyp Bachelorarbeit
Betreuer(in) Jakob Bach
Termin Fr 19. August 2022
Vortragsmodus in Präsenz
Kurzfassung Das SAT-Problem ist ein zentrales Problem der theoretischen Informatik. Wegen seiner NP-Schwere sind Forscher insbesondere an effizienten Lösungsverfahren dafür interessiert. Die Kenntnis der Familie einer Instanz kann zur Problemlösung beitragen. In unserer Arbeit haben wir untersucht, wie SAT-Instanzen durch maschinelles Lernen effizient klassifiziert werden können und welche Verfahren sich am besten dazu eignen. Außerdem betrachteten wir, welche Merkmale die Instanzen am eindeutigsten charakterisieren und wie sich die Anzahl der verwendeten Merkmale auf das Klassifikationsergebnis auswirkt. Letztlich untersuchten wir, welche Familien vermehrt fehlklassifiziert werden und was die Gründe dafür sind.