Sprawdź się
Wskaż, na czym polega stosowanie metody siłowej do rozwiązywania zadań.
- Na sprawdzeniu wszystkich możliwych odpowiedzi.
- Na optymalnym rozwiązaniu zadania.
- Na rozbiciu głównego problemu na podproblemy.
Wskaż, jaką złożoność obliczeniową ma algorytm generujący wszystkie podzbiory zbioru.
- złożoność wykładniczą
- złożoność kwadratową
- złożoność liniowo-logarytmiczną
- złożoność liniową
Oblicz, ile czasu będzie wykonywał się ten algorytm w sytuacji, gdy oraz funkcja opisująca liczbę operacji wykonywanych przez algorytm w zależności od liczby danych wejściowych, będzie w następującej postaci: . Przyjmij, że komputer wykonuje 109 operacji w ciągu 1 sekundy.
- około 580 dni
- około 580 lat
- około 580 godzin
- około 580 minut
Dokończ zdanie.
Jeżeli problem jest klasy NP-zupełnej, to oznacza, że…
- nie znamy do niego rozwiązania o złożoności wielomianowej.
- nie znamy do niego rozwiązania o złożoności wykładniczej.
- nie znamy do niego żadnego rozwiązania.
Wskaż, czy problem komiwojażera jest problemem NP-zupełnym.
- Tak, jest on problemem NP-zupełnym.
- Nie, nie jest on problemem NP-zupełnym.
Wskaż wszystkie podstawowe elementy, z których składa się graf:
- wierzchołki
- krawędzie
- etykiety
- strzałki
- kropki
Wstaw brakujące wyrażenia tak, aby treść poniższego tekstu była prawdziwa.
dużych, P-zupełnych, metod silnych, metod siłowych, wielomianowa, wadą, małych, NP-zupełnych, zaletą, wykładnicza
Rozwiązywanie problemów .............................. jest bardzo trudnym i pracochłonnym zadaniem. Optymalizacja czasowa i pamięciowa .............................. jest zadaniem wymagającym od programisty sporych umiejętności algorytmicznych. Największą .............................. znanych rozwiązań do problemów NP-zupełnych jest ich .............................. złożoność. To właśnie przez nią możemy stosować je jedynie dla bardzo .............................. liczby danych wejściowych.
Dopasuj elementy do grup.
problem najdłuższej ścieżki, złożoność wielomianowa, wyszukiwanie binarne, problem komiwojażera, złożoność wykładnicza, znajdowanie najmniejszej wartości w zbiorze, sortowanie przez scalanie
problemy NP | |
---|---|
problemy P |