Zasady projektowania

algorytmów

Algorytm - pojęcie

Algorytm

–

w

matematyce

oraz

informatyce skończony, uporządkowany

ciąg jasno zdefiniowanych czynności,

koniecznych do wykonania pewnego

rodzaju

zadań.

Algorytm

ma

przeprowadzić system z pewnego stanu

początkowego do pożądanego stanu

końcowego.

Techniki projektowania

algorytmów

●

Dziel i zwyciężaj (divide and conquer) –

rekursja

●

Redukcja (reduction, transform and

conquer)

●

Programowanie liniowe (linear

programming)

●

Programowanie zachłanne (greedy

method)

●

Programowanie dynamiczne (dynamic

programming)

●

Algorytmy przeszukujące (trial and error)

●

Algorytmy probabilistyczne i heurystyki

(probabilistic, heuristic)

Rekursja

Rekursja albo rekurencja (ang. recursion,

z łac. recurrere, przybiec z powrotem) to

w programowaniu i w matematyce

odwoływanie się(np. funkcji lub definicji)

do

samej

siebie.

Każda

definicja

rekurencyjna potrzebuje przynajmniej

jednego

przypadku

bazowego

(nie

rekurencyjnego).

- Wieże Hanoi,

- algorytm Euklidesa znajdowania NWD,

Przykładowy algorytm - QuickSort

Programowanie liniowe

Programowanie

liniowe

to

klasa

problemów

programowania

matematycznego, w której wszystkie

warunki ograniczające oraz funkcja celu

mają postać liniową. Rozwiązania tego

problemu

nazywamy

rozwiązaniami

optymalnymi.

Metody rozwiązywania:

- graficznie,

- algorytm Simplex,

- metoda elipsoid,

- algorytm Karmarkera,

Programowanie zachłanne

Algorytm zachłanny – algorytm, który w celu

wyznaczenia rozwiązania w każdym kroku

dokonuje zachłannego, tj. najlepiej rokującego

w danym momencie wyboru rozwiązania

częściowego. Innymi słowy algorytm zachłanny

nie patrzy czy w kolejnych krokach jest sens

wykonywać dane działanie, dokonuje decyzji

lokalnie optymalnej, dokonuje on wyboru

wydającego się w danej chwili najlepszym,

kontynuując

rozwiązanie

podproblemu

wynikającego z podjętej decyzji. Typowe

zadanie rozwiązywane metodą zachłanną ma

charakter optymalizacyjny.

Programowanie dynamiczne

Programowanie dynamiczne opiera się na podziale

rozwiązywanego

problemu

na

podproblemy

względem kilku parametrów. W odróżnieniu od

techniki dziel i zwyciężaj podproblemy w

programowaniu dynamicznym nie są na ogół

rozłączne, ale musi je cechować własność

optymalnej podstruktury. Zazwyczaj jednym z

parametrów definiujących podproblemy jest liczba

elementów znajdujących się w rozpatrywanym

problemie, drugim jest pewna wartość liczbowa,

zmieniająca się w zakresie od 0 do największej

stałej występującej w problemie. Możliwe są

jednak

bardziej

skomplikowane

dobory

parametrów, a także większa ich liczba. Ponieważ

jednak uzyskiwany algorytm zazwyczaj wymaga

pamięci (i czasu) proporcjonalnego do iloczynu

maksymalnych wartości wszystkich parametrów,

stosowanie większej ilości parametrów niż 3-4

rzadko bywa praktyczne.

Algorytmy przeszukujące

Algorytm przeszukujący - redukujący liczbę

węzłów, które muszą być rozwiązywane w

drzewach przeszukujących przez algorytm

min-max.

Jest

to

przeszukiwanie

wykorzystywane w grach dwuosobowych,

takich jak kółko i krzyżyk, szachy, go.

Warunkiem stopu jest znalezienie przynajmniej

jednego

rozwiązania

czyniącego

obecnie

badaną opcję ruchu gorszą od poprzednio

zbadanych opcji. Wybranie takiej opcji ruchu

nie

przyniosłoby

korzyści

graczowi

ruszającemu się, dlatego też nie ma potrzeby

przeszukiwać dalej gałęzi drzewa tej opcji. Ta

technika

pozwala

zaoszczędzić

czas

poszukiwania bez zmiany wyniku działania

algorytmu.

Algorytmy probabilistyczne i

heurystyczne

Algorytm probabilistyczny albo randomizowany to

algorytm który do swojego działania używa losowości.

W praktyce oznacza to że implementacja takiego

algorytmu korzysta przy obliczeniach z generatora

liczb

losowych.

Główną

zaletą

algorytmów

probabilistycznych

w

porównaniu

z

deterministycznymi jest działanie zawsze w "średnim

przypadku", dzięki czemu złośliwe dane wejściowe nie

wydłużają jego działania. Formalnie efektywność

takiego algorytmu jest zmienną losową określoną na

przestrzeni możliwych losowych ciągów. Wartość

oczekiwana

takiej

zmiennej

nazywana

jest

oczekiwanym

czasem

działania.

Przypadek

pesymistyczny

jest

zwykle

na

tyle

mało

prawdopodobny, że można go pominąć w analizie.

Heurystyka - metoda znajdowania rozwiązań, dla której

nie

ma

gwarancji

znalezienia

rozwiązania

optymalnego, a często nawet prawidłowego.

KONIEC