Pojęcia
Teoria złożoności obliczeniowej
[kategoria] Zagadnienia związane z teorią złożoności obliczeniowej.
Wykaz elementów dowiązanych
| DTIME |
Złożoność czasowa algorytmu, rozpatrywana na deterministycznej maszynie Turinga. (pojęcie) |
| klasy złożoności |
Zbiory problemów obliczeniowych o podobnych złożonościach obliczeniowych. (pojęcie) |
| NTIME |
Złożoność czasowa algorytmu, rozpatrywana na niedeterministycznej maszynie Turinga. (pojęcie) |
| problem decyzyjny |
Opisanie problemu w taki sposób, że jego rozwiązaniem jest zawsze prawda lub fałsz. (pojęcie) |
| problem NP |
Sprawdzenie poprawności danego rozwiązania wymaga złożoności obliczeniowej wielomianowej. (pojęcie) |
| problem NP-Trudny |
Znalezienie rozwiązania problemu nie jest możliwe ze złożonością obliczeniową wielomianową. (pojęcie) |
| problem NP-Zupełny |
Sprawdzenie poprawności danego rozwiązania wymaga złożoności obliczeniowej wielomianowej oraz nie jest możliwe rozwiązanie problemu ze złożonością obliczeniową wielomianową. (pojęcie) |
| problem optymalizacyjny |
Opisanie problemu w taki sposób, że jego rozwiązaniem jest najlepszy możliwy do uzyskania wynik. (pojęcie) |
| problem P |
Znalezienie rozwiązania wymaga złożoności obliczeniowej wielomianowej. (pojęcie) |
| problem przeszukiwania |
Opisanie problemu w taki sposób, że jego rozwiązaniem jest zbiór wyników spełniających warunki wynikające z opisu problemu. (pojęcie) |
| złożoność obliczeniowa |
Ilość operacji jakie trzeba wykonać aby został zrealizowany dany algorytm, posiadając określoną ilość danych wejściowych. (pojęcie) |
Wszystkie teksty są chronione prawami autorskimi. Kopiowanie lub rozpowszechnianie treści poza niniejszym serwisem
jest zabronione.
Powyższe ograniczenie nie dotyczy autora opracowania, któremu przysługuje prawo do rozpowszechniania własnego tekstu wedle własnego uznania.