Test w formie fiszek Wrzucam pytania z odpowiedziami(tymi prawdopodobnie dobrymi).
1-25 pyt. z 1KolosaSem11Z
26-47 pyt. z EgzaminuSem10Z
48-55 pyt. z 1EgzaminuSem11Z(z pamięci)
56-79 pyt. z Kolos2_Szczatki
Fiszki
AISDE - bank pytań od Komandosa
Ilość pytań: 79
Rozwiązywany: 5710 razy
Wyznaczanie maksymalnego przepływu wymaga iteracyjnego znajdowania ścieżki wzbogacającej:
najkrótszej, algorytmem Dijkstry
najkrótszej, algorytmem poprawiania etykiet
dowolnej, algorytmem Dijkstry
dowolnej, algorytmem poprawiania etykiet
dowolnej, algorytmem poprawiania etykiet
W grafie o m wierzchołkach i n krawędziach stosunek liczby ograniczeń dotyczących przepustowości w
sformułowaniach problemu przepływu d towarów i l towaru wynosi:
sformułowaniach problemu przepływu d towarów i l towaru wynosi:
n
m
d
l
l
Dane są 4 krawędzie grafu i ich przepustowości: AB=1, BC=2, CD=1, DA=2 oraz zapotrzebowania
AC=3, BD=2. Przepływ wielotowarowy jest:
AC=3, BD=2. Przepływ wielotowarowy jest:
nierealizowany, bo 6>=5
nierealizowany, bo 6<10
realizowany, bo 6<=10
realizowany, bo 6>5
nierealizowany, bo 6<10
W algorytmie minimalizacji metodą sympleksu zawsze generowany jest kolejny wierzchołek zbioru
rozwiązań dopuszczalnych:
rozwiązań dopuszczalnych:
zachowujący jedną zmienną bazową i najbardziej poprawiający wartość funkcji kosztu
zachowujący jedną zmienną bazową i poprawiający wartość funkcji kosztu
różniący się jedną zmienną bazową i poprawiający wartość funkcji kosztu
różniący się jedną zmienną bazową i najbardziej poprawiający wartość funkcji kosztu
różniący się jedną zmienną bazową i najbardziej poprawiający wartość funkcji kosztu
W algorytmie minimalizacji metodą sympleksu faza analizy pierwszego wiersza tablicy sympleksowej może prowadzić do stwierdzenia:
że problem jest sprzeczny
która zmienna powinna wejść do bazy
że zostało znalezione optimum
że problem jest nieograniczony
że zostało znalezione optimum
W algorytmie minimalizacji metodą sympleksu faza analizy kolumny tablicy sympleksowej może prowadzić do stwierdzenia:
która zmienna powinna wejść do bazy
że problem jest nieograniczony
że problem jest sprzeczny
że zostało znalezione optimum
że problem jest nieograniczony
Jeżeli jeden sektor mieści k rekordów danych albo k' rekordów indeksu, to przy n rekordach danych:
indeks gęsty jest n/k razy mniejszy niż indeks rzadki
indeks gęsty jest k razy większy niż indeks rzadki
indeks gęsty jest k' razy mniejszy niż indeks rzadki
indeks gęsty jest n/k' razy większy niż indeks rzadki
indeks gęsty jest k razy większy niż indeks rzadki
Jeżeli wielkość rekordu danych to 100B wielkość rekordu indeksu 10B, wielkość sektora 1kB. to wyszukanie jednego spośród 100 000 rekordów przy zastosowaniu indeksu gęstego w porównaniu z zastosowaniem funkcji haszującej o 100 wartościach jest:
10 razy szybsze
100 razy szybsze
tak samo szybkie
10 razy wolniejsze
10 razy wolniejsze
W rekurencyjnym algorytmie sortowania pozycyjnego k ciągów binarnych o długości m znaków grupy bitów są sortowane:
od prawej storny ze złożonością k
od lewej strony ze złożonością k
od prawej strony ze złożonością k log m
od lewej strony ze złożonością k log m
od lewej strony ze złożonością k
W trakcie wyszukiwania wzorca w tekście gdy stwierdzamy niezgodność znaków wzorca i tekstu:
przesuwamy wzorzec o i znakw i zaczynamy porównywanie od pierwszego znaku wzorca
przesuwamy wzorzec o 1 znak i zaczynamy porównywanie od pierwszego znaku wzorca
przesuwamy wzorzec o i znaków i zaczynamy porównywanie od bieżącego znaku tekstu
przesuwamy wzorzec o 1 znak i zaczynamy porównywanie od bieżącego znaku tekstu
przesuwamy wzorzec o i znaków i zaczynamy porównywanie od bieżącego znaku tekstu
Kompresja tekstu xyuzyzy z użyciem algorytmu Huffmana zwróci:
111000101001
11001110110
1110011011
10110110001
111000101001
W modelu klucza publicznego strona B udowadnia niezaprzeczalność wiadomości otrzymanej od strony A korzystając z klucza:
prywatnego A
publicznego B
prywatnego B
publicznego A
publicznego A
W modelu klucza publicznego treść wiadomości wysyłanej przez stronę A jest szyfrowana przy użyciu klucza:
publicznego B
tajnego wygenerowanego przez A
tajengo wzgenerowanego przez B
prywatnego A
tajnego wygenerowanego przez A
Przy minimalizacji funkcji metodą największego spadku wykonujemy złoty podział aby:
wyznaczyć minimum funkcji w kierunku największego spadku
ograniczyć przedział poszukiwań minimum funkcji w kierunku
ograniczyć obszar poszukiwań do otoczenia minimum globalnego
wyznaczyć kierunek najwiekszego spadku wartości funkcji
ograniczyć przedział poszukiwań minimum funkcji w kierunku
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 dolne 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 górne funkcji kosztu jest nie wyższe od najlepszego znanego rozwiązania
oszacowanie górne funkcji kosztu jest nie wyższe od najlepszego znanego rozwiązania
W metodzie programowania liniowego całkowitoliczbowego dzielimy problem zrelaksowany dodając dodatkowe ograniczenia jeśli:
żadne z powyższych
problem zrelaksowany jest niesprzeczny i wartość funkcji kosztu jest nie lepsza od kosztu najlepszego rozwiązania całkowitoliczbowego
problem zrelaksowany jest sprzeczny
problem zrelaksowany jest niesprzeczny i wszystkie zmienne przyjmują wartości całkowite
żadne z powyższych
W symulowanym wyżarzaniu zmniejszając temperaturę:
żadne z powyższych
zwiększamy prawdopodobieństwo zaakceptowania lepszego rozwiązania
zwiększamy prawdopodobieństwo wygenerowania lepszego rozwiązania
zwiększamy prawdopodobieństwo zaakceptowania gorszego rozwiązania
żadne z powyższych
Niedeterministyczna maszyna Turinga:
w sposób losowy wybiera przejście
przesuwa głowicę w losowo wybranym kierunku
wypisuje losowy symbol na tasmie
w sposób losowy zmienia stan głowicy
w sposób losowy wybiera przejście
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
P <>NP. i PSPACE = NPSPCAE
Technika dowodzenia NP. – trudności polega na tym, by:
sprowadzić do niego znany problem NP. – zupełnego w czasie niewielomianowym
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łnego w czasie wielomianowym
sprowadzić do niego znany problem NP. – zupełnego w czasie wielomianowym