Nie jesteś zalogowany | zaloguj się

Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

  • Skala szarości
  • Wysoki kontrast
  • Negatyw
  • Podkreślenie linków
  • Reset

Aktualności — Wydarzenia

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

 

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


Seminarium Zakładu Logiki Matematycznej

Prelegent: Dominik Ślęzak

2014-03-21 14:15

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.