Nauka
AiSDE Egzamin
Wyświetlane są wszystkie pytania.
Pytanie 33
Przy minimalizacji funkcji metodą największego spadku wykonujemy złoty podział aby:
ograniczyć przedział poszukiwań minimum funkcji w kierunku
wyznaczyć minimum funkcji w kierunku największego spadku
ograniczyć obszar poszukiwań do otoczenia minimum globalnego
wyznaczyć kierunek najwiekszego spadku wartości funkcji
Pytanie 34
Przy maksymalizacji metodą podziałów i ograniczeń podzbioru rozwiązań można nie przeglądać jeśli:
oszacowanie dolne funkcji kosztu jest nie niższe od najlepszego znanego rozwiązania
oszacowanie górne funkcji kosztu jest nie wyższe od najlepszego znanego rozwiązania
oszacowanie dolne funkcji kosztu jest nie niższe od najlepszego znanego rozwiązania
oszacowanie dolne funkcji kosztu jest nie wyższe od najlepszego znanego rozwiązania
Pytanie 35
W metodzie programowania liniowego całkowitoliczbowego dzielimy problem zrelaksowany dodając dodatkowe ograniczenia jeśli:
problem zrelaksowany jest niesprzeczny i wartość funkcji kosztu jest nie lepsza od kosztu najlepszego rozwiązania całkowitoliczbowego
problem zrelaksowany jest sprzeczny
żadne z powyższych
problem zrelaksowany jest niesprzeczny i wszystkie zmienne przyjmują wartości całkowite
Pytanie 36
Niedeterministyczna maszyna Turinga:
w sposób losowy zmienia stan głowicy
przesuwa głowicę w losowo wybranym kierunku
w sposób losowy wybiera przejście
wypisuje losowy symbol na tasmie
Pytanie 37
Prawdopodobnie obowiązują następujące relacje między klasami problemów:
P =NP. i PSPACE = NPSPCAE
P <>NP. i PSPACE <> NPSPCAE
P <>NP. i PSPACE = NPSPCAE
P =NP. i PSPACE = NPSPCAE
Pytanie 38
Technika dowodzenia NP. – trudności polega na tym, by:
sprowadzić go do znanego problemu NP.- zupełnego w czasie wielomianowym
sprowadzić go do znanego problemu NP.- zupełnego w czasie niewielomianowym
sprowadzić do niego znany problem NP.- zupełny w czasie niewielomianowym
sprowadzic do niego znany problem NP.- zupełny w czasie wielomianowym
Pytanie 39
W przypadku kompresji tekstu metoda kodowania powtórzeń kodowanie licznika powtórzeń zależy od:
minimalnej długości ciągu jednakowych znaków
żadne z powyższych
maksymalnej długości ciągu jednakowych znaków
średniej długości ciągu jednakowych znaków
Pytanie 40
Algorytm sortowania przez zliczanie ma złożoność:
większą niż sortowanie przez wstawianie i mniejszą niż sortowanie przez wybieranie
mniejszą niż quicksort
większa niż szybkie sortowanie i mniejsza niż sortowanie przez wstawianie
wiekszą niż sortowanie przez wybieranie