If you're seeing this message, it means we're having trouble loading external resources on our website.

Jeżeli jesteś za filtrem sieci web, prosimy, upewnij się, że domeny *.kastatic.org i *.kasandbox.org są odblokowane.

Główna zawartość

Podstawy informatyki - program rozszerzony

Kurs: Podstawy informatyki - program rozszerzony > Rozdział 4

Lekcja 3: Rozwiązywanie trudnych problemów
Informatyka
Podstawy informatyki - program rozszerzony
Algorytmy
Rozwiązywanie trudnych problemów
© 2023 Khan AcademyWarunki użytkowaniapolitykę prywatnościInformacja o plikach cookie

Nierozstrzygalne problemy

Google Classroom
Rozwiązywanie niektórych problemów trwa bardzo długo, dlatego używamy algorytmów, które podają przybliżone rozwiązania. Istnieją problemy, których komputer nigdy nie rozwiąże, nawet najpotężniejszy komputer na świecie dysponujący nieskończonym czasem: są to problemy nierozstrzygalne.
Problem nierozstrzygalny to taki, który powinien dać odpowiedź "tak" lub "nie", ale nie istnieje żaden algorytm, który udzieliłby poprawnej odpowiedzi na wszystkie dane wejściowe.

Problem stopu

Alan Turing udowodnił istnienie problemów nierozstrzygalnych w 1936 roku, znajdując ich przykład — słynny dziś "problem stopu":
Czy na podstawie kodu i danych wejściowych dany program kiedykolwiek zakończy działanie?
Przykładem może być program, który odlicza:
num ← 10
REPEAT UNTIL (num = 0) {
  DISPLAY(num)
  num ← num - 1
}
Program ten zostanie zatrzymany, ponieważ num ostatecznie przyjmie wartość 0.
Porównaj to z tym programem, który zlicza:
num ← 1
REPEAT UNTIL (num = 0) {
  DISPLAY(num)
  num ← num + 1
}
Zlicza w nieskończoność, ponieważ num nigdy nie będzie równe 0.
Istnieją algorytmy, które potrafią poprawnie przewidzieć, że pierwszy program się zatrzyma, a drugi nigdy. Są to proste programy, które nie zmieniają się pod wpływem różnych danych wejściowych.
Nie istnieje jednak algorytm, który potrafiłby przeanalizować kod dowolnego programu i określić, czy się on zatrzyma, czy nie.
Aby udowodnić, że taki algorytm nie może istnieć, Turing zastosował "dowód nie wprost".
Zaczynamy od wyobrażenia sobie, że istnieje algorytm, który potrafi określić zatrzymywalność programu.
Następnie proponujemy program o nazwie HaltChecker, który pobiera dwa dane wejściowe: kod programu oraz dane wejściowe dla tego programu. Następnie używa on hipotetycznego algorytmu stopowalności do zwrócenia wyniku "halts" lub "never".
Ten schemat przedstawia wizualizację algorytmu HaltChecker:
Schemat programu sprawdzającego zatrzymanie. Wewnątrz bloku znajduje się schemat blokowy, który rozpoczyna się od rombowego warunku "Will program P halt with input Y?". Strzałka oznaczona jako prawda prowadzi do "RETURN "halts"", a strzałka oznaczona jako fałsz prowadzi do "RETURN "never"".
Gdybyśmy wprowadzili te wcześniejsze programy do HaltChecker, zobaczylibyśmy, że program odliczający daje wynik "halts", a program zliczający - "never". Zauważ, że program nie uruchamia tych programów, tylko patrzy na ich kod i podejmuje decyzje na podstawie struktury kodu.
Teraz jednak zaproponujemy program o nazwie Reverser. Przyjmuje on jedną daną wejściową, kod programu. Wysyła on HaltCheckerowi ten program zarówno jako program do przeanalizowania, jak i jako dane wejściowe dla programu. Następnie HaltChecker określa, czy program wejściowy zatrzymuje się, gdy jest podany jako wejście. Jeśli HaltChecker zwraca "halts", Reverser wykonuje nieskończoną pętlę. Jeśli HaltChecker zwróci "never", Reverser natychmiast kończy pracę.
Ten schemat blokowy przedstawia wizualizację Reverser:
Schemat programu reverser. Zewnętrzny blok zawiera jedno wejście, program P. Wewnątrz zewnętrznego bloku dane wejściowe przepływają do dwóch wejść programu sprawdzającego, programu P i wejścia I. Przepływają one do wewnętrznego bloku ze schematem blokowym. Zaczyna się on od bloku warunkowego "Czy program P zatrzyma się przy danych wejściowych Y?". Strzałka oznaczona jako prawda prowadzi do "RETURN "halts"", a strzałka oznaczona jako fałsz prowadzi do "RETURN "never"". Strzałka oznaczona jako "halts" wypływa z bloku z węzła "RETURN "halts"" i przechodzi do węzła "LOOP" ze strzałką skierowaną z powrotem do niego samego. Kolejna strzałka oznaczona jako "never" wychodzi z bloku z węzła "RETURN "never"" i wchodzi do węzła "END".
Jeśli wprowadzimy program odliczający do Reverser, zobaczy on, że HaltChecker zwraca "halts" i wybierze pętlę nieskończoną.
Schemat programu reverser. Przedstawiono zewnętrzny blok z jednym wejściem, CountDown. Wewnątrz zewnętrznego bloku dane wejściowe są przekazywane do dwóch wejść programu sprawdzającego stan zatrzymania. Wejścia te przepływają do wewnętrznego bloku z diagramem blokowym. Zaczyna się on od bloku warunkowego "Czy CountDown zatrzyma się po wprowadzeniu CountDown?". Podkreślona strzałka oznaczona jako prawda prowadzi do "RETURN "halts"", a wyblakła strzałka oznaczona jako fałsz prowadzi do "RETURN "never"". Zaznaczona strzałka z napisem "halts" wypływa z bloku z napisem "RETURN "halts"" i przechodzi do węzła "LOOP" ze strzałką skierowaną z powrotem do niego samego. Wyblakła strzałka z napisem "never" wychodzi z bloku z węzła "RETURN "never"" i przechodzi do węzła "END".
Jeśli wprowadzimy program liczący do Reverser, to zobaczy on, że HaltChecker zwraca "never", a więc zadecyduje o natychmiastowym zakończeniu programu.
Schemat programu reverser. Na rysunku pokazano zewnętrzny blok z jednym wejściem, CountUp. Wewnątrz zewnętrznego bloku dane wejściowe są przekazywane do dwóch wejść programu sprawdzającego poprawność działania. Wejścia te przepływają do wewnętrznego bloku ze schematem blokowym. Zaczyna się on od bloku decyzyjnego "Czy CountUp zatrzyma się przy wejściu CountUp?". Wyblakła strzałka oznaczona jako prawda prowadzi do "RETURN "halts"", a wyróżniona strzałka oznaczona jako false prowadzi do "RETURN "never"". Wyblakła strzałka oznaczona jako "halts" wypływa z bloku od węzła "RETURN "halts"" i przechodzi do węzła "LOOP" ze strzałką skierowaną z powrotem do siebie. Wyróżniona strzałka z napisem "never" wychodzi z bloku z węzła "RETURN "never"" i przechodzi do węzła "END".
Reverser jest rzeczywiście dziwnym programem. Zatrzymuje się, gdy dowiaduje się, że inny program się nie zatrzymuje, i lubi trwać bez końca, gdy zauważy, że inny program się zatrzymał. Jest to dziwne, ale to nic nie szkodzi, dziwne programy mają prawo istnieć na świecie.
Ale tu wszystko się rozlatuje: co się stanie, jeśli do Reverser wprowadzimy sam Reverser?
HaltChecker analizuje kod Reverser, aby określić, czy się zatrzymuje. Jeśli zdecyduje, że nie zatrzymuje się, to zwróci "never". Reverser widzi ten wynik i natychmiast kończy pracę.
Schemat programu reverser. Przedstawiono zewnętrzny blok z jednym wejściem, Reverser. Wewnątrz zewnętrznego bloku dane wejściowe są przekazywane do dwóch wejść programu sprawdzającego poprawność działania. Wejścia te przepływają do wewnętrznego bloku ze schematem blokowym. Zaczyna się on od blokowego warunku "Czy program Reverser zatrzyma się przy wejściu Reverser?". Wyblakła strzałka oznaczona jako prawda prowadzi do "RETURN "halts"", a podkreślona strzałka oznaczona jako fałsz prowadzi do "RETURN "never"". Wyblakła strzałka oznaczona jako "halts" wypływa z bloku z węzła "RETURN "halts"" i przechodzi do węzła "LOOP" ze strzałką skierowaną z powrotem do siebie. Podkreślona strzałka z napisem "never" wychodzi z bloku z węzła "RETURN "never"" i przechodzi do węzła "END".
Ale, chwileczkę! HaltChecker właśnie stwierdził, że Reverser nigdy się nie zatrzymuje, a potem poszedł dalej i zatrzymał się. HaltChecker nie dał nam poprawnej odpowiedzi.
Co jeśli HaltChecker zamiast tego zwróci "halts"? Gdy Reverser widzi ten wynik, zapętla się w nieskończoność.
Schemat programu reverser. Przedstawiono zewnętrzny blok z jednym wejściem, Reverser. Wewnątrz zewnętrznego bloku dane wejściowe są przekazywane do dwóch wejść programu sprawdzającego poprawność działania. Wejścia te przepływają do wewnętrznego bloku ze schematem blokowym. Rozpoczyna się on od bloku decyzyjnego "Czy program Reverser zatrzyma się przy wejściu Reverser?". Podkreślona strzałka oznaczona jako prawda prowadzi do "RETURN "halts"", a wyblakła strzałka oznaczona jako fałsz prowadzi do "RETURN "never"". Podkreślona strzałka oznaczona jako "halts" wypływa z bloku z węzła "RETURN "halts"" i przechodzi do węzła "LOOP" ze strzałką skierowaną z powrotem do siebie. Wyblakła strzałka z napisem "never" wychodzi z bloku z węzła "RETURN "never"" i przechodzi do węzła "END".
HaltChecker tylko stwierdził, że Reverser się zatrzymuje, a jednak trwało to bez końca. Po raz kolejny, HaltChecker nie dał nam poprawnej odpowiedzi. W rzeczywistości, nie ma sposobu, aby HaltChecker dał nam poprawną odpowiedź w tej sytuacji.
W ten sposób udowodniliśmy, że doskonale poprawny algorytm przewidywania zatrzymania nigdy nie może istnieć oraz że problem zatrzymania jest nierozstrzygalny.
Zajęło mi trochę czasu, zanim naprawdę zrozumiałem, na czym polega problem zatrzymania. Jeśli też masz z tym problemy, ten film animowany może być pomocny.

Więcej nierozstrzygalnych problemów

Informatycy i matematycy odkryli wiele innych problemów niedających się rozstrzygnąć. Sporo z nich, po uproszczeniu, wygląda jak kolejny przypadek problemu stopu. Ogólnie rzecz biorąc, wszystkie problemy nierozstrzygalne dotyczą trudności w określeniu własności wejścia i wyjścia programów.
Pomocne jest uświadomienie sobie, kiedy mamy do czynienia z problemem niedeterministycznym. Możemy wtedy zaakceptować fakt, że nasz program nie może poprawnie udzielić odpowiedzi "tak" lub "nie" na wszystkie dane wejściowe, i wymyślić inne podejście.
Na przykład nasze środowisko programistyczne Khan Academy stara się unikać uruchamiania programów z nieskończonymi pętlami, aby zapobiec zawieszaniu się przeglądarki. Ale skąd możemy wiedzieć, że program ma nieskończoną pętlę? Nie możemy, to jest niedeterministyczne! Zamiast tego monitorujemy, jak długo trwają pętle, a gdy pętla trwa zbyt długo, odmawiamy wykonania kodu. Nie mamy pewności, czy pętla będzie się ciągnęła w nieskończoność, ale dla naszych celów lepiej dmuchać na zimne.
🙋🏽🙋🏻‍♀️🙋🏿‍♂️Czy masz jakieś pytania na ten temat? Chętnie na nie odpowiemy — wystarczy, że zadasz pytanie w poniższym obszarze pytań!

Chcesz dołączyć do dyskusji?

Zaloguj się
Na razie brak głosów w dyskusji
Rozumiesz angielski? Kliknij tutaj, aby zobaczyć więcej dyskusji na angielskiej wersji strony Khan Academy.