Zasady projektowania algorytmów

Adam Morawiec
163125
ARK, W-4
PWR

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 (r educt ion, t r ansf or m and

conquer )

●

Programowanie liniowe (linear

pr ogr am m ing)

●

Programowanie zachłanne (gr eedy m et hod)

●

Programowanie dynamiczne (dynam ic

pr ogr am m ing)

●

Algorytmy przeszukuj

ą

ce (t r ial and er r or )

●

Algorytmy probabilistyczne i heurystyki

(pr obabilist ic, heur ist ic)

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