« Teoria złożoności obliczeniowej, C++ »
Teoria złożoności obliczeniowej - Zagadnienia związane z teorią złożoności obliczeniowej. (kategoria)
Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Zarejestruj się!
Opracował: Piotr DejaVu Szawdyński

Teoria złożoności obliczeniowej

[kategoria] Zagadnienia związane z teorią złożoności obliczeniowej.

Wykaz elementów dowiązanych

DTIMEZłożoność czasowa algorytmu, rozpatrywana na deterministycznej maszynie Turinga. (pojęcie)
klasy złożonościZbiory problemów obliczeniowych o podobnych złożonościach obliczeniowych. (pojęcie)
NTIMEZłożoność czasowa algorytmu, rozpatrywana na niedeterministycznej maszynie Turinga. (pojęcie)
problem decyzyjnyOpisanie problemu w taki sposób, że jego rozwiązaniem jest zawsze prawda lub fałsz. (pojęcie)
problem NPSprawdzenie poprawności danego rozwiązania wymaga złożoności obliczeniowej wielomianowej. (pojęcie)
problem NP-TrudnyZnalezienie rozwiązania problemu nie jest możliwe ze złożonością obliczeniową wielomianową. (pojęcie)
problem NP-ZupełnySprawdzenie 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 optymalizacyjnyOpisanie problemu w taki sposób, że jego rozwiązaniem jest najlepszy możliwy do uzyskania wynik. (pojęcie)
problem PZnalezienie rozwiązania wymaga złożoności obliczeniowej wielomianowej. (pojęcie)
problem przeszukiwaniaOpisanie 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ść obliczeniowaIlość operacji jakie trzeba wykonać aby został zrealizowany dany algorytm, posiadając określoną ilość danych wejściowych. (pojęcie)