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
dowolnej, algorytmem Dijkstry
dowolnej, algorytmem poprawiania etykiet
najkrótszej, 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
l
d
m
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<10
nierealizowany, bo 6>=5
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 poprawiający wartość funkcji kosztu
różniący się jedną zmienną bazową i poprawiający wartość funkcji kosztu
zachowujący jedną zmienną bazową i najbardziej 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:
która zmienna powinna wejść do bazy
że problem jest sprzeczny
że problem jest nieograniczony
że zostało znalezione optimum
że zostało znalezione optimum
W algorytmie minimalizacji metodą sympleksu faza analizy kolumny tablicy sympleksowej może prowadzić do stwierdzenia:
że problem jest nieograniczony
że zostało znalezione optimum
która zmienna powinna wejść do bazy
że problem jest sprzeczny
ż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 k razy większy niż indeks rzadki
indeks gęsty jest n/k razy mniejszy 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:
tak samo szybkie
100 razy szybsze
10 razy wolniejsze
10 razy szybsze
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 lewej strony ze złożonością k
od lewej strony ze złożonością k log m
od prawej strony ze złożonością k log m
od prawej storny ze złożonością k
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 znaków i zaczynamy porównywanie od bieżącego znaku tekstu
przesuwamy wzorzec o i znakw i zaczynamy porównywanie od pierwszego znaku wzorca
przesuwamy wzorzec o 1 znak i zaczynamy porównywanie od bieżącego znaku tekstu
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
Kompresja tekstu xyuzyzy z użyciem algorytmu Huffmana zwróci:
111000101001
1110011011
11001110110
10110110001
111000101001
W modelu klucza publicznego strona B udowadnia niezaprzeczalność wiadomości otrzymanej od strony A korzystając z klucza:
prywatnego A
publicznego A
prywatnego B
publicznego B
publicznego A
W modelu klucza publicznego treść wiadomości wysyłanej przez stronę A jest szyfrowana przy użyciu klucza:
prywatnego A
publicznego B
tajengo wzgenerowanego przez B
tajnego wygenerowanego przez A
tajnego wygenerowanego przez A
Przy minimalizacji funkcji metodą największego spadku wykonujemy złoty podział aby:
ograniczyć obszar poszukiwań do otoczenia minimum globalnego
wyznaczyć minimum funkcji w kierunku największego spadku
ograniczyć przedział poszukiwań minimum funkcji w kierunku
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 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 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
W metodzie programowania liniowego całkowitoliczbowego dzielimy problem zrelaksowany dodając dodatkowe ograniczenia jeśli:
problem zrelaksowany jest sprzeczny
ż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 niesprzeczny i wszystkie zmienne przyjmują wartości całkowite
żadne z powyższych
W symulowanym wyżarzaniu zmniejszając temperaturę:
zwiększamy prawdopodobieństwo zaakceptowania gorszego rozwiązania
żadne z powyższych
zwiększamy prawdopodobieństwo wygenerowania lepszego rozwiązania
zwiększamy prawdopodobieństwo zaakceptowania lepszego rozwiązania
żadne z powyższych
Niedeterministyczna maszyna Turinga:
wypisuje losowy symbol na tasmie
w sposób losowy wybiera przejście
w sposób losowy zmienia stan głowicy
przesuwa głowicę w losowo wybranym kierunku
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ć go do znanego problemu NP. – zupełnego w czasie niewielomianowym
sprowadzić do niego znany problem NP. – zupełnego w czasie wielomianowym
sprowadzić go do znanego problemu NP. – zupełnego w czasie wielomianowym
sprowadzić do niego znany problem NP. – zupełnego w czasie niewielomianowym
sprowadzić do niego znany problem NP. – zupełnego w czasie wielomianowym