MATEMATYKA
Polub moją stronę:)
VIDEO

 

 

 

 

 

 
Tomasz Grebski
_________

 

 

 
     
Problem P czy NP
Problem P czy NP

 

Równo sto lat po słynnym programie Hilberta podczas majowej konferencji w Paryżu, Instytut Claya ogłosił listę siedmiu problemów milenijnych, aby uczcić nadchodzące nowe tysiąclecie.

Wyboru problemów dokonał Komitet Naukowy, zaś nagrody finansowe (w wysokości w sumie 7 milionów dolarów) ufundował i zapewnił Dyrektoriat Instytutu.

 

Na liście znalazł się

Problem „P czy NP.”

 

Niektóre problemy matematyczne i logiczne da się szybko rozwiązać przy użyciu komputerów – i stanowią one klasę problemów, z którą idealny komputer daje sobie radę w czasie będącym wielomianową funkcją zadanych mu parametrów (należą do tej klasy choćby układy równań liniowych czy problemy znajdowania najkrótszej drogi). Istnieją jednak zagadnienia, których rozwiązania znamy, ale nie są to rozwiązania równie „szybkie”, jak w wypadku poprzednim. Czy da się wszystkie podobne problemy (zgrupowane w pewnej klasie, oznaczonej jako NP) rozwiązać szybciej? Czy też istnieją takie, których analizy nie da się już przyspieszyć w żaden sposób? Pytanie ciekawe i szalenie istotne z praktycznego punktu widzenia, bowiem problemy te związane są z kryptografią (łamaniem kodów), kolorowaniem map czy układaniem harmonogramów.

Stephen Cook i Leonid Levin sformułowali problem P (tzn. łatwy do znalezienia) kontra NP (tzn. łatwy do sprawdzenia) niezależnie od siebie w 1971 roku.

Przykładem problemu NP jest tzw. problem komiwojażera. Jest to zagadnienie z teorii grafów, polegające na znalezieniu w nim minimalnego cyklu Hamiltona. Nazwa pochodzi od typowej ilustracji problemu, przedstawiającej go z punktu widzenia wędrownego sprzedawcy (komiwojażera): dane jest n miast, które komiwojażer ma odwiedzić, oraz odległość pomiędzy każdą parą miast. Należy znaleźć najkrótszą trasę wychodzącą z danego miasta, przechodzącą jednokrotnie przez wszystkie pozostałe miasta i wracającą do tego samego miasta.

Nie są znane algorytmy dające dokładne rozwiązanie tego problemu w czasie wielomianowym. W praktyce najefektywniejszymi sposobami jego rozwiązania są algorytmy genetyczne, często wykorzystywane w połączeniu z heurystycznymi (np. heurystyka najbliższego sąsiada). Są to jednak metody dające w większości jedynie rozwiązania bliskie optymalnemu. Niekiedy tylko zdarza się, że otrzymane rozwiązanie jest optymalne. Zależy to głównie od liczby punktów oraz czasem szczęścia (generacja populacji początkowej, krzyżowanie oraz mutacja w algorytmach genetycznych zawierają element losowy).

 
Logowanie
Nazwa użytkownika

Hasło



Nie masz jeszcze konta?
Zarejestruj się

Nie możesz się zalogować?
Poproś o nowe hasło
POLECAM
Mathteacher Matura Tomasz Grebski

 

 

 

 

 

 

 

 

MUZYKA

 

  O MNIE MUZYCZNIE

  MOJE INSTRUMENTY

  GALERIA FOTO

  TV & VIDEO

  TOTO SCO

  JOLLY BIRD

  MC KOWALSKY

  CANION

  REY CHRISTMAS

Tomasz Grebski

Losowa Fotka