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