Matroid – struktura matematyczna składająca się z niepustego zbioru elementów E i takiej rodziny jego podzbiorów I, że spełnione są następujące warunki:
Drugi warunek, zwany własnością wymiany, formalnie może być zapisany jako:
$$⋀↙{A,B∊I}↙{ |A|>|B| }⋁↙{t∊(A-B)} B∪\{t\} ∈ I$$Co istotne, rodzina zbiorów I nie musi zawierać wszystkich możliwych podzbiorów zbioru E. Ważne tylko, aby była spełniona własność wymiany. Przykładowo, dla E={a,b,c,d} prawidłową rodziną I, może być zarówno { {a,b}, {b,c}, {a}, {b}, {c}, ∅}, jak i { {a}, {b}, {c}, {d}, ∅}. Trywialnym przypadkiem poprawnego matroidu jest taki, w którym rodzina I zawiera jedynie zbiór pusty.
Zbiory należące do I określane są jako zbiory niezależne. Zbiór niezależny o największej liczbie elementów to baza matroidu. Matroid może mieć wiele baz. W pierwszym wspomnianym wcześniej przykładzie bazami są zbiory {a,b} i {b,c}, w drugim zaś zbiory {a}, {b}, {c}, {d}.
Jeśli każdy element zbioru E ma przyporządkowaną dodatnią liczbę (wagę), to taki matroid jest określany jako matroid ważony. Każdemu zbiorowi niezależnemu również można wtedy przyporządkować wagę, będącą sumą wag wszystkich należących do niego elementów. Dla matroidów grafowych (tzn. takich, w których elementy zbioru E są krawędziami grafu), wagą może być długość krawędzi.
Więcej pojęć związanych z matroidami można znaleźć w książce [1].
Matroidy ważone mają duże zastosowanie przy ocenie skuteczności algorytmów zachłannych. Udowodniono, że jeśli problem obliczeniowy da się przedstawić za pomocą matroidu ważonego, to algorytm zachłanny zawsze zwróci rozwiązanie optymalne (dowód jest dostępny w książce [2]). W takim przypadku, jeśli do naszego rozwiązania będziemy zawsze dodawać ten spośród dostępnych elementów zbioru E, który ma największą wagę, to otrzymamy bazę matroidu o największej wadze spośród wszystkich baz. Przykładem takiego algorytmu jest algorytm Kruskala.
Dodano: 24 kwietnia 2020 13:50, ostatnia edycja: 24 kwietnia 2020 18:28.
Metoda przyrostowa – technika projektowania algorytmów polegająca na dodawaniu do rozwiązania kolejnych elementów z danych wejściowych. Przykładem algorytmu opartego na tej metodzie jest sortowanie przez wstawianie, gdzie kolejne elementy są wstawiane do posortowanej części tablicy.
Jest to metoda prosta, jednak sprawdza się tylko dla niektórych problemów obliczeniowych.
Sortowanie przez wstawianie (ang. insertion sort) – prosty algorytm sortowania polegający na wstawianiu kolejnych elementów ciągu we właściwe miejsca. Złożoności czasowa algorytmu wynosi O(n2). Jest to algorytm realizujący metodę przyrostową.
Metoda Otsu – algorytm służący do binaryzacji obrazu, czyli przekształcenia obrazu w odcieniach szarości do obrazu binarnego. Metoda ta realizuje progowanie globalne – dla całego obrazu wyznaczany jest jeden próg jasności, a następnie wszystkim pikselom jaśniejszym od tego progu przypisywana jest jedna wartość, a ciemniejszym druga.
Algorytm jest oparty na analizie histogramu. Przygotowanie histogramu polega na zliczeniu pikseli w każdym możliwym odcieniu (zazwyczaj liczba odcieni wynosi 256, gdyż tyle da się zakodować w jednym bajcie). Następnie należy sprawdzić każdy możliwy próg jasności i wybrać ten, dla którego wariancja międzyklasowa jest największa (lub suma ważona wariancji wewnątrzklasowych jest najmniejsza).
Jeśli obrazem wejściowym jest obraz kolorowy, można go łatwo sprowadzić do odcieni szarości. W przypadku kolorów zakodowanych w RGB najprostszym rozwiązaniem jest uśrednienie dla każdego piksela wartości wszystkich trzech kanałów.