Archiwum Seminarium Ogólnoinstytutowego 2018-2019:


Seminaria ogólnoinstytutowe:

Informacje:

Poniedziałki, o godz. 12:00
Miejsce seminarium: sala seminaryjna IPI PAN
ul. Jana Kazimierza 5
e-mail: seminarium@ipipan.waw.pl

Prowadzący seminarium:

08.10.2018 - Seminarium Instytutowe - godz. 13:00,

Teofil Sidoruk (Instytut Podstaw Informatyki PAN) 

20181008 Sidoruk

W seminarium przedstawię dziewięć SAT-solverów, w tym nowoczesne narzędzia takie jak Lingeling, Glucose i Clasp, których efektywność zostanie porównana dla problemów obliczeniowych o różnej złożoności: od P (dwie popularne zagadki szachowe) do EXPTIME (wieże Hanoi), ale głównie będą to problemy NP-zupełne. Należą do nich problem odpowiedniości Posta (BPCP), extended string-to-string correction (ESCP) a także trzy klasyczne zagadnienia z teorii grafów. Ponadto dla niektórych problemów (m.in. BPCP i ESCP) definiujemy własne, oryginalne kodowania do SAT. Przedstawione wyniki eksperymentalne pozwalają na wyciągnięcie ciekawych wniosków odnośnie efektywności i przydatności SAT-solverów do rozwiązywania problemów o różnej złożoności. Ponadto, po przeprowadzonych testach analizuję formuły w postaci CNF zawarte w wygenerowanych benchmarkach w poszukiwaniu charakterystycznych wspólnych cech dla relatywnie najłatwiejszych i najtrudniejszych instancji.


© 2021 INSTYTUT PODSTAW INFORMATYKI PAN | Polityka prywatności | Deklaracja dostępności