Problem NP-zupełny: Różnice pomiędzy wersjami
M Znacznik: edytor źródłowy |
M (→Opis algorytmu) Znacznik: edytor źródłowy |
||
Linia 15: | Linia 15: | ||
# Wprowadź dane instancji problemu do niedeterministycznej maszyny Turinga. |
# Wprowadź dane instancji problemu do niedeterministycznej maszyny Turinga. |
||
# Nie zapomnij wybrać z opcji zaawansowanych tryb |
# Nie zapomnij wybrać z opcji zaawansowanych tryb „TURBO EXPERT”. |
||
# Poczekaj pińćdziesiąt jednostek czasu, wykorzystując je pożytecznie, na przykład zmywając naczynia lub grając w [[CS]]a |
# Poczekaj pińćdziesiąt jednostek czasu, wykorzystując je pożytecznie, na przykład zmywając naczynia lub grając w [[CS]]a. |
||
# Odczytaj wynik rozwiązanego problemu i odbierz milion dolarów za rozwiązanie milenijnego problemu. |
# Odczytaj wynik rozwiązanego problemu i odbierz milion dolarów za rozwiązanie milenijnego problemu. |
||
# Ciesz się i żyj w dobrobycie. |
# Ciesz się i żyj w dobrobycie. |
||
{{stub|sek}} |
|||
===Dowód poprawności=== |
===Dowód poprawności=== |
Wersja z 10:06, 19 lut 2015
Problem NP-zupełny (Problem niezwykle-pracogenno-zupełny) – rodzinka wyjątkowo złośliwych, męczących i upierdliwych w rozwiązaniu problemów. Aktor grający zbira w trzecim odcinku Kojaka udowodnił, że jeżeli uda się rozwiązać jeden problem NP-zupełny w ludzkim czasie, to można też rozwiązać w tym czasie inne problemy z tej rodzinki.
Przykłady
- Problem odkurzenia wszechświata – należy odkurzyć cały wszechświat, co z uwagi na zanieczyszczenia i oceany bywa kłopotliwe, a następnie zawartość worka wyrzucić na zewnątrz.
- Problem czasu reklamowego – należy obliczyć średni czas trwania bloku reklamowego na Polsacie w danym miesiącu.
- Problem sznurka do snopowiązałki w PRL-u – sznurek ten, pomimo dużej produkcji i braku eksportu, nie istniał w praktyce, a jego brak wymagał zastosowania domowych środków zaradczych.
Algorytm rozwiązujący problemy w czasie znośnym
Wynaleziony pod koniec 2007 roku algorytm rozwiązujący problemy NP-zupełne w czasie znośnym, tj. na przykład przed wybudowaniem planowanych w Polsce autostrad.
Opis algorytmu
Algorytm ten jest bardzo prosty, i opiera się na podstawowych własnościach matematycznych.
Aby wykonać algorytm rozwiązujący problemy NP należy działać według niżej wymienionych punktów a wynik będzie poprawny/optymalny.
- Wprowadź dane instancji problemu do niedeterministycznej maszyny Turinga.
- Nie zapomnij wybrać z opcji zaawansowanych tryb „TURBO EXPERT”.
- Poczekaj pińćdziesiąt jednostek czasu, wykorzystując je pożytecznie, na przykład zmywając naczynia lub grając w CSa.
- Odczytaj wynik rozwiązanego problemu i odbierz milion dolarów za rozwiązanie milenijnego problemu.
- Ciesz się i żyj w dobrobycie.
Dowód poprawności
- Dowód poprawności algorytmu jest banalny i jest modyfikacją dowodu na nieskończoność liczb pierwszych.
Autor tej sekcji wpisał tu raptem parę słów. Jeżeli denerwuje Cię takie postępowanie – rozwiń ją.