Złożoność obliczeniowa: Różnice pomiędzy wersjami
| [wersja nieprzejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
Nie podano opisu zmian Znaczniki: Wycofane Z urządzenia mobilnego Z wersji mobilnej (przeglądarkowej) |
m Wycofano edycje użytkownika 187.38.62.90 (dyskusja). Autor przywróconej wersji to Ts123321. Znacznik: Wycofanie zmian |
||
Linia 5:
Za twórców tej teorii uważani są [[Juris Hartmanis]] i [[Richard Stearns]]. Jako przykłady problemów t.z.o. można podać [[problem spełnialności]], [[problem najkrótszej ścieżki]], problem [[Rozkład na czynniki|faktoryzacji]] oraz wiele innych, o których wiadomo, że są obliczalne. Kwestią obliczalności zajmuje się [[teoria obliczalności]], będąca drugą ważną gałęzią teorii obliczeń.
Wyniki, jakie podaje t.z.o., można podzielić na dwie kategorie: pozytywne i negatywne, czyli na takie, które podają, co i jak można obliczyć, oraz takie, w których dowodzi się, czego nie da się obliczyć, wykorzystując określoną ilość zasobów. Wyniki pozytywne są łatwiejsze do uzyskania i zwykle mają postać [[algorytm]]u rozwiązującego dany problem wraz z dowodem poprawności oraz opisem potrzebnych
== Złożoność algorytmów ==
| |||