1. Dla problemu Cyklicznego Rozmieszczenia Maszyn generujemy rozwiązanie na podstawie:

a) zamiany miejscami kolejnych par maszyn i generowaniu macierzy sąsiedztwa

b) wyszukujemy cykle Hamiltona w grafie

c) wykonujemy wszystkie te czynności po kolei

d) żadna z powyższych

2. Dla problemu Cyklicznego Rozmieszczenia Maszyn wygenerowana macierz B:

a) jest symetryczna

b) jest antysymetryczna

c) jest macierzą przepływu

d) żadna z powyższych

3. Dla problemu Cyklicznego Rozmieszczenia Maszyn wygenerowana macierz B:

a) jest antysymetryczna

b) jest macierzą sąsiedztwa

c) obie powyższe odpowiedzi są poprawne

d) żadna z powyższych

4. Dla problemu Cyklicznego Rozmieszczenia Maszyn koszt liczymy na podstawie:

a) przepływów części pomiędzy maszynami

b) czasów wykonywania zadań na maszynach

c) odległości pomiędzy maszynami

d) żadna z powyższych

5. W problemie szeregowania równoległego, z nierównoczesnym wykorzystaniem maszyn, graf z reprezentujący rozwiązanie niedopuszczalne zawiera:

a) cykle o ujemnej długości

b) cykle o dodatniej długości

c) nie zawiera cykli

d) żadna z powyższych

6. Dla problemu Cyklicznego Rozmieszczenia Maszyn:

a) minimalizujemy kryterium Lmax

b) zamieniamy łuki dysjunktywne na ścieżce krytycznej

c) znajdujemy cykl Eulera w grafie

d) żadna z powyższych

7. Jeśli G jest grafem o n wierzchołkach i m krawędziach, to G² ma wierzchołków i krawędzi odpowiednio:

a) n² i mn²

b) n² i m²

c) mn m²n

d) n² i mn

8. W terminach problemów algorytmicznych, pseudowielomianowym nazywamy algorytm, który jest:

a) wielomianowy jeśli liczby są zapisane przy podstawie 2, wykładniczy jeśli liczby są zapisane unarnie b) o złożoności na przykład n^{log n}

c) wykładniczy od rozmiaru danych i wielomianowy od wartości liczb w instancji

d) wielomianowy od rozmiaru danych i wykładniczy od wartości liczb w instancji Źle

9. Aby wykazać, że problem jest silnie NP-zupełny, wystarczy

a) wykazać, że posiada NP-zupełny podproblem o wielomianowo ograniczonej wartości największej liczby w instancji

b) skonstruować redukcję wielomianową z silnie NP-zupełnego problemu

c) wskazać algorytm pseudowielomianowy dla tego problemu

d) wykazać, że nie jest podproblemem silnie NP-zupełnego problemu