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

Aus SDQ-Institutsseminar
Version vom 16. August 2022, 06:50 Uhr von Jakob Bach (Diskussion | Beiträge)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)
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.