Fiszki
AiSDE Egzamin
Test w formie fiszek Odpowiedzi na podstawie "biblii algorytmów"
Ilość pytań: 73
Rozwiązywany: 3900 razy
Wyznaczanie maksymalnego przepływu wymaga iteracyjnego znajdowania ścieżki wzbogacającej:
dowolnej, algorytmem Dijkstry
najkrótszej, algorytmem poprawiania etykiet
najkrótszej, 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 1 towaru wynosi:
1
m
d
n
1
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:
nierealizowany, bo 6<10
realizowany, bo 6<=10
realizowany, bo 6>5
nierealizowany, bo 6>=5
nierealizowany, bo 6<10
W algorytmie minimalizacji metodą sympleksu zawsze generowany jest kolejny wierzchołek zbioru rozwiązań dopuszczalnych:
óżniący się jedną zmienną bazową i najbardziej 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 poprawiający wartość funkcji kosztu
zachowujący jedną zmienną bazową i poprawiający wartość funkcji kosztu
óżniący się jedną zmienną bazową i najbardziej poprawiający wartość funkcji kosztu
W algorytmie minimalizacji metodą sympleksu faza analizy kolumny tablicy sympleksowej może prowadzić do stwierdzenia:
że problem jest nieograniczony
że zostało znalezione optimum
że problem jest sprzeczny
która zmienna powinna wejść do bazy
ż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 mniejszy niż indeks rzadki
indeks gęsty jest k razy większy 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
tak samo szybkie
10 razy wolniejsze
100 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
od prawej 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 znaków i zaczynamy porównywanie od pierwszego znaku wzorca
przesuwamy wzorzec o 1 znaków 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:
011001110110
010110110001
01110011011
0111000101001
0111000101001
W modelu klucza publicznego strona B udowadnia niezaprzeczalność wiadomości otrzymanej od strony A korzystając z klucza:
publicznego A
prywatnego A
publicznego B
prywatnego B
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
prywatnego A
tajnego wygenerowanego przez B
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ć obszar poszukiwań do otoczenia minimum globalnego
wyznaczyć kierunek najwiekszego spadku wartości funkcji
ograniczyć przedział poszukiwań minimum funkcji w kierunku
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 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:
problem zrelaksowany jest sprzeczny
problem zrelaksowany jest niesprzeczny i wszystkie zmienne przyjmują wartości całkowite
żadne z powyższych
problem zrelaksowany jest niesprzeczny i wartość funkcji kosztu jest nie lepsza od kosztu najlepszego rozwiązania całkowitoliczbowego
żadne z powyższych
Niedeterministyczna maszyna Turinga:
wypisuje losowy symbol na tasmie
w sposób losowy wybiera przejście
przesuwa głowicę w losowo wybranym kierunku
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ć go do znanego problemu NP.- zupełnego w czasie niewielomianowym
sprowadzić go do znanego problemu NP.- zupełnego w czasie wielomianowym
sprowadzić do niego znany problem NP.- zupełny w czasie niewielomianowym
sprowadzic do niego znany problem NP.- zupełny w czasie wielomianowym
sprowadzic do niego znany problem NP.- zupełny w czasie wielomianowym
W przypadku kompresji tekstu metoda kodowania powtórzeń kodowanie licznika powtórzeń zależy od:
średniej długości ciągu jednakowych znaków
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
Algorytm sortowania przez zliczanie ma złożoność:
wiekszą niż sortowanie przez wybieranie
większą niż sortowanie przez wstawianie i mniejszą niż sortowanie przez wybieranie
większa niż szybkie sortowanie i mniejsza niż sortowanie przez wstawianie
mniejszą niż quicksort
mniejszą niż quicksort