Trzy przykłady problemów zapewne NP-trudnych z dziedzin przetwarzania i eksploracji danych

Speaker(s)

Dominik Ślęzak

Affiliation

Uniwersytet Warszawski

Date

March 21, 2014, 2:15 p.m.

Room

room 5820

Seminar

Seminarium badawcze Zakładu Logiki: Wnioskowania aproksymacyjne w eksploracji danych

---

Przedstawię przykłady trzech obszarów problemów optymalizacyjnych, które najprawdopodobniej są NP-trudne, lecz których NP-trudność nie jest jeszcze udowodniona.

 

Pierwszy przykład dotyczy wyznaczania z danych przybliżonych sieci Bayesowskich o minimalnej liczbie krawędzi, czyli minimalnych grafów acyklicznych, które kodują za pomocą d-separacji przybliżone niezależności warunkowe pomiędzy atrybutami, o zadanym stopniu przybliżenia wyznaczanym z danych.

 

Drugi przykład dotyczy ładowania danych do granularnej bazy danych typu Infobright, gdzie dane są przechowywane w paczkach powstałych w wyniku dekompozycji ze względu na atrybuty i podzbiory wierszy, a gdzie zależy nam na minimalizacji liczby paczek danych o zbyt heterogenicznej zawartości.

 

Trzeci przykład dotyczy wyznaczania z danych stabilnych podzbiorów atrybutów w formie przybliżonych reduktów decyzyjnych, które to podzbiory mają szansę pozostać reduktami na zadowalającym poziomie przybliżenia dla zmieniających się danych.

---