Pytania z wykładu z 12 X 2011, 1 ROK (mgr), 2gi SEMESTR, ARS, Elastyczne Systemy Montażowe


Pytania z wykładu z 12 X 2011

  1. Na czym polega rozwiązanie problemu decyzyjnego?

    1. wybór jednego z przynajmniej dwóch dostępnych rozwiązań

    2. wyznaczenie listy możliwych rozwiązań

    3. wyznaczenie rozwiązania optymalnego

    4. udowodnienie braku możliwego rozwiązania

  1. Problem decyzyjny jest bezpośrednio związany z pytaniem:

    1. jakie jest optymalne rozwiązanie?

    2. czy istnieje optymalne rozwiązanie?

    3. co należy dalej zrobić w danej sytuacji?

    4. jakie są zalety danego rozwiązania?

  1. Problem optymalizacyjny jest problemem:

    1. obliczeniowym

    2. decyzyjnym

    3. społecznym

    4. kulturowym

  1. Dla problemu klasy NP:

    1. nie można zweryfikować rozwiązania w czasie wielomianowym

    2. można zweryfikować rozwiązanie w czasie wielomianowym

    3. nie należy szukać rozwiązania gdyż nie istnieje

    4. można znaleźć poprawne rozwiązanie w czasie wielomianowym

  1. Dla problemu klasy P:

    1. nie można zweryfikować rozwiązania w czasie wielomianowym

    2. można zweryfikować rozwiązanie w czasie wielomianowym

    3. nie należy szukać rozwiązania gdyż nie istnieje

    4. można znaleźć poprawne rozwiązanie w czasie wielomianowym

  1. Rozwiązując problem silnie NP-trudny po odpowiedniej transformacji:

    1. można rozwiązać inne problemy z P oraz NP

    2. można rozwiązać inne problemy tylko i wyłącznie z klasy P

    3. można rozwiązać inne problemy tylko i wyłącznie z klasy NP

    4. nie gwarantuje to możliwości rozwiązania żadnego innego problemu

  1. Algorytm X-aproksymacyjny:

    1. w najlepszym przypadku daje rozwiązanie x razy rozwiązanie optymalne

    2. w najgorszym przypadku daje rozwiązanie x razy rozwiązanie optymalne

    3. w najlepszym przypadku daje rozwiązanie o x gorsze od rozwiązania optymalnego

    4. w najgorszym przypadku daje rozwiązanie o x lepsze od rozwiązania optymalnego

  1. Algorytmem nieaproksymacyjnym jest:

    1. algorytm symulowanego wyżarzania

    2. algorytm mrówkowy

    3. algorytm podziału i ograniczeń

    4. algorytm rozwiązujący problem cyklu Hamiltona

  1. Dla problemu komiwojażera, gdy spełnione są wszystkie warunki trójkąta jest:

    1. 2/3 aproksymacyjnym

    2. 3/2 aproksymacyjnym

    3. 3/4 aproksymacyjnym

    4. 3/5 aproksymacyjnym


Wyszukiwarka