Błyskawica (Lightning)
Pliki dołączone do zasobu:
Opis zasobu:
Redukcja argumentów jest procesem polegającym na znajdowaniu najmniejszych zbiorów argumentów funkcji boolowskich, dla których dane pozostają spójne. W przypadku, gdy dane te reprezentują tablice prawdy funkcji boolowskich, redukcja argumentów zmniejsza liczbę zmiennych wejściowych układu realizującego te funkcje, co zawsze upraszcza ich implementacje. W przypadku tablic danych redukcja argumentów (nazywana redukcją atrybutów lub ekstrakcją cech) znajduje duże zastosowanie w eksploracji danych. Niejednokrotnie gromadzone dane są nadmiarowe, a do podjęcia jednoznacznej decyzji wystarczy podzbiór parametrów, co w konsekwencji przyczynia się do zmniejszenia złożoności obliczeniowej dalszych zabiegów w analizie danych.
Z obliczeniowego punktu widzenia są to identyczne procesy, zatem algorytmy i narzędzia redukcji atrybutów z powodzeniem mogą być stosowane w redukcji argumentów. Jest to istotne o tyle, że procesom redukcji atrybutów poświęcono ogromną liczbę prac naukowych i wypracowano bardzo skuteczne (z punktu widzenia szybkości obliczeń) algorytmy. Wyjątkowo skuteczny w tym zakresie okazał się algorytm, w którym klasyczne rozwiązanie problemu, polegające na przekształceniu koniunkcyjnej postaci normalnej funkcji rozróżnialności, do dysjunkcyjnej postaci normalnej zostało zredukowane do obliczenia uzupełnienia tej funkcji.
Metoda uzupełniania bardzo przyspiesza obliczenia, a wydajna reprezentacja algorytmu w pamięci operacyjnej maszyny obliczeniowej umożliwia osiągnięcie wyników, które nie mogą być osiągnięte przy użyciu innych publikowanych metod i systemów. Z tych powodów program do redukcji argumentów i atrybutów nazwano Błyskawicą (Lightning).
W celu zwiększenia uniwersalności metody program Błyskawica został wyposażony w algorytm dekompozycji liniowej. Dekompozycja liniowa polega na łączeniu zmiennych w pary i wprowadzanie ich do wejść pamięci ROM za pośrednictwem bramek EXOR. Jest to istotne o tyle, że prowadzi do dalszego redukowania wejść w realizacjach na pamięciach ROM.
Literatura
- Białas M., Implementacja oprogramowania wspomagającego redukcję i klasyfikację danych. Praca inżynierska, Wydział EiTI Politechniki Warszawskiej, OKNO, Warszawa 2018.
- Kowalski K., Synteza funkcji generowania indeksów metodą redukcji i kompresji argumentów Praca magisterska, Wydział EiTI Politechniki Warszawskiej, Warszawa 2017.