Reading...
Play button
Play button
Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
15 Cards in this Set
- Front
- Back
|
Def. Złożoność czasowa algorytmów |
Złożoność czasowa algorytmu P to liczba kroków po jakich P zatrzymuje się dla danych wejściowych n |
|
|
* Def. Złożoność czasowa algorytmu
|
złożoność czasowa algorytmu P to liczba kroków po jakich P zatrzymuje się dla danych wejściowych n
|
|
|
Def. Złożoność pamięciowa algorytmu
|
złożonością pamięciową algorytmu P nazywamy ilość pamięci jaką algorytm P potrzebuje dla danych wejściowych n
|
|
|
Def. Notacja O
|
g: w -> w jest O(f(x)) jeżeli istnieją a i b takie, że dla dowolnego x zachodzi g(x) <= a * f(x) + b; czyli g(x) jest co najwyżej rzędu f(x)
|
|
|
Def. Notacja Omega
|
g: w -> w jest Omega(f(x)) wtedy i tylko wtedy, gdy f(x) jest O(g(x)); czyli g(x) jest conajmniej rzędu f(x)
|
|
|
Wymień rodzaje złożoności
|
pesymistyczna, średnia, amortyzowana
|
|
|
Def. Złożoność pesymistyczna
|
maksymalna ilość zasobów potrzebna dla danych wejściowych o rozmiarze n
|
|
|
Def. Złożoność średnia
|
oczekiwana ilość zasobów dla danych wejściowych o rozmiarze n
|
|
|
W jaki sposób ustala się złożoność średnią?
|
należy założyć prawdopodobieństwo z jakim występują poszczególne instancje problemu - przy różnych rozkładach uzyskamy różne rzędy złożoności
|
|
|
Def. Złożoność amortyzowana
|
pesymistyczna złożoność wielokrotnego wykonania algorytmu dzielona przez liczbę wykonań
|
|
|
Def. Przeszukiwanie wyczerpujące
|
(brute-force) poszukiwanie rozwiązania przez metodyczne generowanie i sprawdzanie potencjalnych rozwiązań; generowanie odbywa się w opraciu o strukturę problemu
|
|
|
Wymień sposoby implementacji przeszukiwania wyczerpującego
|
generowanie potencjalnych rozwiązań w określonej kolejności; budowanie ciągu częściowych (coraz pełniejszych) rozwiązań i sprawdzanie przy każdym rozszerzeniu czy otrzymaliśmy poprawne potencjalne rozwiązanie
|
|
|
Def. Przeszukiwanie z nawrotami (back-tracking)
|
budujemy ciąg częściowych rozwiązań i sprawdzamy przy rozszerzeniu czy jest to potencjalne rozwiązanie - jeśli nie, to cofamy się i próbujemy innego rozszerzenia
|
|
|
Opisz problem n hetmanów
|
problem, w którym rozstawiamy n hetmanów na planszy wielkości n x n; w każdym wierszu i w każdej kolumnie ma stać dokładnie jeden hetman; ustawiamy hetmanów w kolejnych wierszach tak, aby nie szachowali się wzajemnie; jeżeli aktualne rozwiązanie zawodzi, cofamy się i próbujemy innego miejsca
|
|
|
Opisz problem SAT (problem spełnialności formuł logicznych koniunkcja w postaci normalnej UFF!)
|
szukamy wartości dla zmiennych takich, aby sprawdzana formuła była spełniona; w każdym kroku nadajemy wartość jednej zmiennej; jeśli dojedziemy do sprzeczności, cofamy się i próbujemy innej wartości |
