Strona główna

Algorytm Dijkstry jest zachłanny, bo rozpatruje wierzchołki pośrednie


Pobieranie 20.81 Kb.
Data18.06.2016
Rozmiar20.81 Kb.
Zdania prawdziwe:
Algorytm Dijkstry jest zachłanny, bo rozpatruje wierzchołki pośrednie

w relaksacji od najbliższych źródła do najdalszych.


Algorytm szeregowania zadań zgodnie z malejącą drogą krytyczną

nie zawsze jest optymalny.


Zachłanny algorytm triangulacji wielokąta polegający na wybieraniu

kolejno najkrótszych nie przecinających się przekątnych nie jest optymalny.


Algorytm zachłanny tworzący najliczniejszy zbiór zajęć bezkolizyjnych

daje optymalne rozwiązanie gdy zajęcia są uszeregowane według

wzrastającego czasu ich zakończenia.
Zachłanny algorytm Kruskala tworzący minimalne drzewo rozpinające polega

na dobieraniu drzewowych krawędzi uporządkowanych rosnąca względem swoich wag.


Jeżeli w algorytmie szeregowania dana liczba wykonawców m=4 oraz

graf poprzedzania jest pusty, to 4*fdk ≤ 5*fopt

(fdk –czas drogi krytycznej, fopt –czas optymalny)
Algorytm poszukiwania obwiedni wypukłej (n-punktów) mimo

‘pozornego backtreckingu’ jest złożoności O(n*log2n).


Algorytm zachłanny pakowania kontenerów przy malejącym

ich uporządkowaniu nie zawsze daje rozwiązanie optymalne.


Złożoność algorytmu Knutha-Morrisa-Prata poszukiwania

wzorca P w tekście T jest liniowa względem |T|+|P|.


Algorytm mnożenia liczb naturalnych w:=x*y jest następujący:

{czytaj(x,y); w=0; for(i=0;i

Rozmiarem danych jest n = liczba cyfr (dziesiętnych) liczby y.

Złożoność tego algorytmu jest wykładnicza.


Operacją dominującą (o czasie stałym) jest W(Z) = zbadanie

własności W dla zbioru Z. Jeśli rozmiar danych jest n=3*k,

a algorytm A bada własność W(Z) każdego k-elementowego

podzbioru zbioru danych, to złożoność A jest wykładnicza.


Operacją dominującą (o czasie stałym) jest W(Z) = zbadanie

własności W dla zbioru Z. Jeśli rozmiar danych jest n=3*k,

a algorytm A bada własność W(Z) każdego 3-elementowego

podzbioru zbioru danych, to złożoność A jest wielomianowa.


Jeżeli problem jest NP-zupełny, to jest NP-trudny.
Jeżeli f(n)=O(2n) to f(n)=O(4n).
Zdania fałszywe:
Algorytm Dijkstry nie jest zachłanny, bo nie rozpatruje w relaksacji

krawędzi od najkrótszych do najdłuższych.


Algorytm szeregowania zadań zgodnie z malejącą drogą krytyczną daje

zawsze rozwiązanie optymalne.


Zachłanny algorytm triangulacji wielokąta polegający na wybieraniu

kolejno najkrótszych nie przecinających się przekątnych jest optymalny.


Algorytm zachłanny tworzący najliczniejszy zbiór zajęć bezkolizyjnych

daje optymalne rozwiązanie gdy zajęcia są uszeregowane według

wzrastającj długości czasu ich trwania.
Zachłanny algorytm Prima tworzący minimalne drzewo rozpinające polega

na dobieraniu drzewowych krawędzi uporządkowanych rosnąca względem swoich wag.


Jeżeli w algorytmie szeregowania dana liczba wykonawców m=4 oraz

graf poprzedzania jest spójny, to 7*fdk ≤ 8*fopt

(fdk –czas drogi krytycznej, fopt –czas optymalny)
Algorytm poszukiwania obwiedni wypukłej (n-punktów) mimo

‘pozornego backtreckingu’ jest złożoności O(n).


Algorytm zachłanny pakowania kontenerów przy malejącym

ich uporządkowaniu daje rozwiązanie optymalne.


Złożoność algorytmu Knutha-Morrisa-Prata poszukiwania

wzorca P w tekście T jest liniowa względem |T|+|P|.


Algorytm mnożenia liczb naturalnych w:=x*y jest następujący:

{czytaj(x,y); w=0; for(i=0;i

Rozmiarem danych jest n = liczba cyfr (dziesiętnych) liczby y.

Złożoność tego algorytmu jest liniowa.


Operacją dominującą (o czasie stałym) jest W(Z) = zbadanie

własności W dla zbioru Z. Jeśli rozmiar danych jest n=3*k,

a algorytm A bada własność W(Z) każdego 3-elementowego

podzbioru zbioru danych, to złożoność A jest wykładnicza.


Operacją dominującą (o czasie stałym) jest W(Z) = zbadanie

własności W dla zbioru Z. Jeśli rozmiar danych jest n=3*k,

a algorytm A bada własność W(Z) każdego k-elementowego

podzbioru zbioru danych, to złożoność A jest wielomianowa.


Jeżeli problem jest NP-trudny, to jest NP-zupełny.
Jeżeli f(n)=O(4n) to f(n)=O(2n).

+ - Wykładniczy => .NP-zupełny


+ - Poprawna i niepoprawna definicja O, omega, theta
+ - inne twierdzenie o NPC i/lub NPH
- zachłanne => wielomianowe
- dynamiczne => wielomianowe


©snauka.pl 2016
wyślij wiadomość