Sprawdź się

1
Pokaż ćwiczenia:
1
Ćwiczenie 1
RfGnYDdVJJIlQ
Na czym polega stosowanie metody siłowej do rozwiązywania zadań? Możliwe odpowiedzi: 1. Na sprawdzeniu wszystkich możliwych odpowiedzi, 2. Na optymalnym rozwiązaniu zadania, 3. Na rozbiciu głównego problemu na podproblemy

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.
1
Ćwiczenie 2
Ri7v7WFvqQbRY
Wskaż, jaką złożoność obliczeniową ma algorytm generujący wszystkie podzbiory zbioru. Możliwe odpowiedzi: 1. Złożoność wykładniczą., 2. Złożoność kwadratową., 3. Złożoność liniowo-logarytmiczną., 4. Złożoność liniową.

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ą
2
Ćwiczenie 3
R16bG70bHNi2M
Oblicz, ile czasu będzie wykonywał się ten algorytm w sytuacji, gdy n=35 oraz funkcja f opisująca liczbę operacji wykonywanych przez algorytm w zależności od liczby danych wejściowych, będzie w następującej postaci: fn=3n. Przyjmij, że komputer wykonuje 109 operacji w ciągu 1 sekundy. Możliwe odpowiedzi: 1. Około 580 dni., 2. Około 580 lat., 3. Około 580 godzin., 4. Około 580 minut.

Oblicz, ile czasu będzie wykonywał się ten algorytm w sytuacji, gdy n = 35 oraz funkcja f opisująca liczbę operacji wykonywanych przez algorytm w zależności od liczby danych wejściowych, będzie w następującej postaci: f(n) = 3n. 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
2
Ćwiczenie 4
R1VSycBK1c6KV
Jeżeli problem jest klasy NP-zupełnej, to oznacza, że: Możliwe odpowiedzi: 1. nie znamy do niego rozwiązania o złożoności wielomianowej, 2. nie znamy do niego rozwiązania o złożoności wykładniczej, 3. nie znamy do niego żadnego rozwiązania

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.
2
Ćwiczenie 5
RWBzT1OSP2jcW
Czy problem komiwojażera jest problemem NP-zupełnym? Możliwe odpowiedzi: 1. Tak, jest on problemem NP-zupełnym, 2. Nie, nie jest on problemem NP-zupełnym

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.
3
Ćwiczenie 6
R1StHoDQsk6mb
Zaznacz wszystkie podstawowe elementy z których składa się graf. Możliwe odpowiedzi: 1. Wierzchołki, 2. Krawędzie, 3. Etykiety, 4. Strzałki, 5. Kropki

Wskaż wszystkie podstawowe elementy, z których składa się graf:

  • wierzchołki
  • krawędzie
  • etykiety
  • strzałki
  • kropki
3
Ćwiczenie 7
R1AxsxzLj78Uk
Wstaw brakujące wyrażenia tak, aby treść poniższego tekstu była prawdziwa. Rozwiązywanie problemów 1. wadą, 2. metod silnych, 3. dużych, 4. małych, 5. wykładnicza, 6. NP-zupełnych, 7. P-zupełnych, 8. metod siłowych, 9. zaletą, 10. wielomianowa jest bardzo trudnym i pracochłonnym zadaniem. Optymalizacja czasowa i pamięciowa 1. wadą, 2. metod silnych, 3. dużych, 4. małych, 5. wykładnicza, 6. NP-zupełnych, 7. P-zupełnych, 8. metod siłowych, 9. zaletą, 10. wielomianowa jest zadaniem wymagającym od programisty sporych umiejętności algorytmicznych. Największą 1. wadą, 2. metod silnych, 3. dużych, 4. małych, 5. wykładnicza, 6. NP-zupełnych, 7. P-zupełnych, 8. metod siłowych, 9. zaletą, 10. wielomianowa rozwiązań do problemów NP-zupełnych jest ich 1. wadą, 2. metod silnych, 3. dużych, 4. małych, 5. wykładnicza, 6. NP-zupełnych, 7. P-zupełnych, 8. metod siłowych, 9. zaletą, 10. wielomianowa złożoność. To właśnie przez nią możemy stosować je jedynie dla bardzo 1. wadą, 2. metod silnych, 3. dużych, 4. małych, 5. wykładnicza, 6. NP-zupełnych, 7. P-zupełnych, 8. metod siłowych, 9. zaletą, 10. wielomianowa liczby danych wejściowych.

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.

3
Ćwiczenie 8
Rn2Gm4RuKANOt
Dopasuj elementy do grup. problemy NP Możliwe odpowiedzi: 1. sortowanie przez scalanie, 2. złożoność wielomianowa, 3. złożoność wykładnicza, 4. wyszukiwanie binarne, 5. problem komiwojażera, 6. znajdowanie najmniejszej wartości w zbiorze, 7. problem najdłuższej ścieżki P Możliwe odpowiedzi: 1. sortowanie przez scalanie, 2. złożoność wielomianowa, 3. złożoność wykładnicza, 4. wyszukiwanie binarne, 5. problem komiwojażera, 6. znajdowanie najmniejszej wartości w zbiorze, 7. problem najdłuższej ścieżki

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  
Aplet
Dla nauczyciela