Ocena brak

Jakie problemy nazywamy nierozstrzygalnymi? Opisz przykładowy problem

Autor /Barnim7777 Dodano /29.12.2011

Problem, dla którego nie ma żadnego poprawnie działającego algorytmu nazywamy problemem nieobliczalnym. Jeśli problemem tym jest problem decyzyjny to nazywamy go problemem nierozstrzygalnym.

Przykładem problemu nierozstrzygalnego jest problem domina.

Problem domina polega na sprawdzeniu i udzieleniu odpowiedzi „tak” lub „nie”, na pytanie: czy danym zbiorem kart o wymiarach 1 na 1 da się poryć odpowiednio duży teren. Problem jest o tyle trudny, że każda krawędź karty ma inny kolor, a założenie jest takie, że kolory stykających się krawędzi muszą być identyczne.

Dla każdego algorytmu (zapisanego w dowolnym, dającym się efektywnie wykonać języku programowania), który przeznaczony jest do rozstrzygnięcia problemu domina, istnieje nieskończenie wiele zestawów danych wejściowych, dla których algorytm ten będzie działał w nieskończoność lub da błędną odpowiedź.

Do góry