Złożoność obliczeniowa problemu szukania najprostszych poprawnych zespołów bireduktów decyzyjnych

Prelegent(ci)

Dr Sebastian Stawicki

Afiliacja

UW & QED Software

Język referatu

polski

Termin

29 listopada 2024 16:00

Pokój

p. 4060

Seminarium

Seminarium badawcze „Systemy Inteligentne”

---

Biredukty decyzyjne to rozszerzenie pojęcia reduktów decyzyjnych z teorii zbiorów przybliżonych, uwzględniające zarówno podzbiory atrybutów opisujących decyzję, jak i podzbiory obiektów, dla których te opisy są poprawne. Możemy powiedzieć bardziej formalnie, że biredukt decyzyjny jest reprezentowany jako para złożona z podzbioru obiektów oraz podzbioru atrybutów, dla których podzbiór atrybutów zapewnia poprawną klasyfikację dla wybranych obiektów.

W wystąpieniu zaprezentuję wyniki opracowane wspólnie z prof. dr. hab. Dominikiem Ślęzakiem, dotyczące złożoności obliczeniowej problemu znajdowania najprostszych poprawnych zespołów bireduktów decyzyjnych. Podczas prezentacji przypomnę podstawowe pojęcia z teorii złożoności obliczeniowej, a także pojęcie poprawnych zespołów bireduktów, które zilustruję przykładami. Następnie przedstawię dowód NP-zupełności (wersja decyzyjna) oraz NP-trudności (wersja optymalizacyjna) tego problemu.

 

---