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