Kategoria: Techniki projektowania algorytmów

Podkategorie:Artykuły w tej kategorii:
REKLAMA

Zobacz też

Dziel i zwyciężaj (ang. divide and conquer) – technika projektowania algorytmów polegająca na podejściu rekurencyjnym. W technice tej problem dzielony jest na mniejsze podproblemy, te podproblemy na jeszcze mniejsze podproblemy, aż dojdzie się do przypadków trywialnych (np. posortowanie jednoelementowej tablicy, obliczenie silni z 1).

Jeśli rozpatrywany problem wymaga podzielenia na podproblemy, jest on określany jako przypadek rekurencyjny. Jeśli mamy do czynienia z przypadkiem trywialnym, jest to przypadek bazowy. Tworząc algorytm wykorzystujący metodę dziel i zwyciężaj musimy ustalić:

  • Jak rozwiązać przypadek bazowy (trywialny).
  • Jak wyznaczyć rozwiązanie problemu, mając dostępne rozwiązania podproblemów.

Przykładem algorytmu opartego na tej metodzie jest sortowanie przez scalanie.

→ Czytaj całość

Quicksort, sortowanie szybkie – algorytm sortowania działający w średnim przypadku w czasie liniowo-logarytmicznym. Algorytm jest oparty na metodzie dziel i zwyciężaj. Nie jest to algorytm stabilny ani wykazujący zachowanie naturalne, jednak ze względu na efektywność jest algorytmem bardzo popularnym.

→ Czytaj całość

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.

→ Czytaj całość
Polityka prywatnościKontakt