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 eduction, tr ansfor m and
conquer )
Programowanie liniowe (linear
pr ogr amming)
Programowanie zachłanne (gr eedy method)
Programowanie dynamiczne (dynamic
pr ogr amming)
Algorytmy przeszukujące (tr ial and er r or )
Algorytmy probabilistyczne i heurystyki
(pr obabilistic, heur istic)
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