P(łatwe) wielomianowe deterministyczne

Sortowanie, najkrótsza droga, najkrótsze drzewo, cykl Eulera,

NP(trudne) wielomianowe niedeterministyczne

cykl Hamiltona, kolorowanie grafów, problem plecakowy

deterministyczna symulacja takiego algorytmu daje algorytm wielomianowy

Dobra złożoność algorytmu

Wielomianowa n , n²

Ograniczona przez wielomian

log n , bo log n <=n

n log n, bo n log n <=n²

Zła złożoność algorytmu

nie jest ograniczona przez wielomian

n elementów 2ⁿ operacji

n elementów n! permutacji

2ⁿ nie jest ograniczony przez żaden wielomian

Plecak

Wersja binarna/ogólna

xi - liczba szt. i-tego towaru

xi €No

∑pi xi -> max

(n,i=1)∑xiwi≤W

R Bellmana zasada optymalnośći jak mamy jakiś proces etapowy (złożoność O(n*W){W=log₂w}

Przeszukiwanie z nawrotami

For n€V do |

F(V) random(1,k); | O(n)

for e= {n,V}€E do |

if f(V)=f(n) then zle HALT | O(n)

SUKCES!

Algorytm skończony ciąg poleceń do wykonania

Uniwersalność - wykonywalność dla wszystkich danych spełniających specyfikację

Algorytm zachłany wykonuje zawsze działanie które wydaje się w danej chwili najkorzystniejsze przykładem jest problem kasjara

Przeszukanie z nawrotami O(n)

Programowanie dynamiczne O(nw) nie jest wielomianowa względem długości danych czyli względem nlog2W

Znajdowanie najkrótszej drogi Algorytm Dijkstry O(n²)

Najkrótsze drzewo spinające Prim i Kruskal

Kolorowania grafu algorytm sekwencyjny i sekwencyjny LF

Liczba pierwsza n^½

for i:=2,3,4,5…, to √n do

if n dzieli się przez i then stop

liczbę n możemy zapisać na logn bitach

Cykl Eulera, to taki cykl w grafie, który zawiera każdą krawędź grafu dokładnie raz.

spójność grafu,

dla grafu skierowanego należy sprawdzić czy do każdego wierzchołka wchodzi tyle samo krawędzi co wychodzi

dla grafu nieskierowanego z każdego wierzchołka musi wychodzić parzysta liczba krawędzi.

Cykl Eulera, cykl w grafie spójnym, który przechodzi przez każdą krawędź grafu dokładnie jeden raz, przy czym dopuszcza się, aby ten sam wierzchołek był odwiedzany więcej niż jeden raz.

Cykl Hamiltona, wirzchilek cykl w grafie G = (V, E) zawierający wszystkie wierzchołki zbioru V, każdy dokładnie jeden raz. Graf, który ma cykl Hamiltona, nazywa się grafem hamiltonowskim, w przeciwnym razie mówi się o grafie niehamiltonowskim. Przykładem grafu hamiltonowskiego są krawędzie dwunastościanu. Problem cyklu Hamiltona w grafach badano od przeszło stu lat, pozostaje on w związku z problemami NP-zupełnymi.

---