Jaka jest różnica między algorytmem, językiem i problemem?

Wygląda na to, że na tej stronie ludzie często korygują innych za mylące „algorytmy” i „problemy”. Jakie są między nimi różnice? Skąd mam wiedzieć, kiedy powinienem rozważać algorytmy i problemy? A jak odnoszą się one do pojęcia języka w formalnej teorii języka?

Dla uproszczenia zacznę od rozważenia tylko problemów związanych z „decyzją”, na które odpowiedź brzmi „tak / nie”. Problemy z funkcjami działają w przybliżeniu w ten sam sposób, z tym wyjątkiem, że zamiast tak / nie, z każdym słowem wejściowym jest powiązane słowo wyjściowe.

Język : język to po prostu zestaw ciągów znaków. Jeśli masz alfabet, taki jak , to jest zbiorem wszystkich słów zawierających tylko symbole w . Na przykład jest zbiorem wszystkich sekwencji binarnych o dowolnej długości. Alfabet nie musi być jednak binarny. Może być jednoargumentowy, trójskładnikowy itp.$\Sigma$$\Sigma^*$$\Sigma$$\{0,1 \}^*$

Język nad alfabetem jest dowolnym podzbiorem .$\Sigma$$\Sigma^*$

Problem : Problemem jest pytanie dotyczące odpowiedzi, na które chcielibyśmy uzyskać odpowiedź. W szczególności problemem decyzyjnym jest pytanie, które brzmi: „Czy dane dane wejściowe spełniają właściwość ?$X$

Język to formalna realizacja problemu. Gdy chcemy teoretycznie uzasadnić problem decyzyjny, często sprawdzamy odpowiedni język. W przypadku problemu odpowiednim językiem jest:$X$

$L = \{w \mid w$ jest kodowaniem wejścia dla problemu , a odpowiedzią na wejście dla problemu jest „Tak” $y$$X$$y$$X$$\}$

Ustalenie, czy odpowiedź na pytanie wejściowe do problemu decyzyjnego brzmi „tak”, jest równoważna z ustaleniem, czy kodowanie tego wejścia na alfabecie jest w odpowiednim języku.

Algorytm : Algorytm to krok po kroku sposób rozwiązania problemu. Zauważ, że algorytm można wyrazić na wiele sposobów i w wielu językach oraz że istnieje wiele różnych algorytmów rozwiązujących dany problem.

Maszyna Turinga : Maszyna Turinga jest formalnym analogiem algorytmu. Maszyna Turinga nad danym alfabetem, dla każdego słowa, zatrzyma się lub nie zatrzyma w stanie akceptacji. Zatem dla każdej maszyny Turinga istnieje odpowiedni język:$M$

$L(M) = \{w \mid M$ zatrzymuje się na wejściu .$w\}$

(Istnieje subtelna różnica między Maszynami Turinga, które zatrzymują się na wszystkich wejściach, a zatrzymują się na wejściach tak, co określa różnicę między klasami złożoności i .)$\mathsf{R}$$\mathsf{RE}$

Relacje między językami a maszynami Turinga są następujące

1. Każda maszyna Turinga akceptuje dokładnie jeden język

2. Może istnieć więcej niż jedna maszyna Turinga, która akceptuje dany język

3. Może nie istnieć Maszyna Turinga, która akceptuje dany język.

Możemy powiedzieć mniej więcej to samo o algorytmach i problemach: każdy algorytm rozwiązuje pojedynczy problem, ale może istnieć 0 lub wiele algorytmów rozwiązujących dany problem.

Złożoność czasowa : Jednym z najczęstszych źródeł nieporozumień między algorytmami i problemami są klasy złożoności. Prawidłowy przydział można podsumować następująco:

• Algorytm ma złożoność czasową
• Problem należy do klasy złożoności

Algorytm może mieć określoną złożoność czasową. Mówimy, że algorytm ma najgorszy przypadek z górną granicą złożoności jeśli algorytm zatrzymuje się co najwyżej kroków dla dowolnego wejścia o wielkości .$f(n)$$f(n)$$n$

Problemy nie mają czasu działania, ponieważ problem nie jest związany z konkretnym algorytmem, który faktycznie działa. Zamiast tego mówimy, że problem należy do klasy złożoności, jeśli istnieje jakiś algorytm rozwiązujący ten problem przy danej złożoności czasowej.

$\mathsf{P}, \mathsf{NP}, \mathsf{PSPACE}, \mathsf{EXPTIME}$ itd. są klasami złożoności. Oznacza to, że zawierają problemy, a nie algorytmy. Algorytm nigdy nie może znajdować się w , ale jeśli istnieje algorytm wielomianowy rozwiązujący dany problem , to jest w . Może być też kilka algorytmów czasu wykładniczego akceptujących , ale ponieważ istnieje jeden algorytm wielomianowy akceptujący , jest on w .$\mathsf{P}$$X$$X$$\mathsf{P}$$X$$X$$\mathsf{P}$