Niedeterministyczn maszyna Turinga

Hej.

Mam pytanie odnośnie pomocy w zadaniu. Mam: Skonstruować (nie)deterministyczną maszynę Turinga
rozwiązującą w czasie wielomianowym jeden z wybranych problemów
z klasy (NP) P:
PATH, UHAMPATH, SPATH, LPATH, PRIMES.

Umielibyście mi pomóc??

Dzięki.

Musisz jakoś rozwinąć temat, bo na razie wygląda jakby ktoś chciał Cię wsadzić na minę.

Chodzi o Programowanie Genetyczne?

Witaj.
Dziękuje za odpowiedź. Chodzi o zwykły projekt bez kodu. Zadanie polega głownie na zaprojektowaniu takowej maszyny(może być w formie ręką na kartce), która rozwiąże dany warunek.

Podaj jakieś linki do materiałów, bo nazwy które podałeś są mało unikalne.

http://pl.wikipedia.org/wiki/Maszyna_Turinga

http://www.cs.put.poznan.pl/akobusinska/downloads/wprowadzenie/w6-maszyna_Turinga.pdf

http://www.wfis.uni.lodz.pl/kft2/algcomp/NTuring.pdf

Coś na takowej zasadzie ale jak to rozwiązać nie wiem:(

W tym temacie (dość wąskim) może być przydatny język angielski.
W teorii jest to dość proste - Non-deterministic Turing Machine (NTM/NDTM) to połączenie wersji podstawowej z IFS (Iterated Function System).

Opisy zasady działania:
http://www.asiplease.net/computing/alevel/turing_machines.htm
http://www.cs.rpi.edu/~goldberg/14-CC/02-ndt.pdf

Przykładowe implementacje:
http://swizec.com/blog/nondeterministic-turing-machine-simulator-in-23-lines-of-javascript/swizec/3047
http://web.archive.org/web/20080515023814/http://semillon.wpi.edu/~aofa/AofA/msg00020.html
http://sourceforge.net/projects/turing-machine/

Jak to zastosować do podanych problemów?
Myślę, że to temat na magisterkę.
W każdym razie podaj opis jeśli już coś zrobisz i zostanie zaakceptowane.

@vpiotr co ty gadasz? Jaka magisterka? To są przecież zadania na 15 minut. Widzę że ktoś znów przespał Teorię Złożoności Obliczeniowej :D
@kamis159 a ty łaskawie mógłbyś podać sensowne nazwy dla tych problemów. Zgaduje że twoje UHAMPATH to nieskierowana ścieżka hamiltona (http://en.wikipedia.org/wiki/Hamiltonian_path_problem) a LPATH to najdłuższa ścieżka (http://en.wikipedia.org/wiki/Longest_path_problem)?

Deterministycznej wielomianowej maszyny to nie zrobisz, chyba że udowodnisz że P=NP i zgadniesz milion dolarów :D

Dla maszyny niedeterministycznej to nie ma specjanie wiekiego problemu. Na przykład dla longest-path robisz pętlę po każdym wierzchołku szukając "początkowego" a następnie podejmujesz decyzję którą krawędzią iśc. Maszyna niedeterministyczna pozwala "zgadywać", więc po prostu na każdym rozgałęzieniu bierzesz "dobrą" ścieżkę. W efekcie masz złożoność O(V*E).
Analogicznie na to "zgadywanie" można patrzeć tak, że maszyna potrafi rozgałęziać obliczenia i prowadzić je równolegle. Więc w każdym wierzchołku możemy rozgałęzić obliczenia dla każdej krawędzi i prowadzić je równolegle a na koniec wybrać tą opcje która dała najlepszy wynik.

Shalom napisał(a):

@vpiotr co ty gadasz? Jaka magisterka? To są przecież zadania na 15 minut. Widzę że ktoś znów przespał Teorię Złożoności Obliczeniowej :D

Świat się dzieli na tych co piszą że coś jest złożone i na tych co piszą że zadanie jest na 15 minut.
Ale efekt jest ten sam - obaj nie podają rozwiązań...

Dziękuje za odpowiedź.

Shalom sprawa wygląda tak jak mówisz. Ale ja za chiny nie mogę tego ugryść:(. Myślałem nad którymś z tym ale poza Wiki nic nie mogę znaleźć. Kwestia rozpisania tego i działania poprawnego to ponad moje siły:(

możesz mi to rozpisać tzn. rozwiązać całe zadanie?

Ale tam nie ma nic więcej do rozpisywania. Podałem ci algorytm i jego złożoność. Czego jeszcze chcesz?

1. dla każdego wierzchołka
2. rozchodzimy się po wszystkich przyległych krawędziach tworząc osobne ścieżki obliczeń
3. jeśli wierzchołek do którego trafiliśmy nie był jeszcze odwiedzony na tej ścieżce obliczeń to oznaczamy go jako odwiedzony i następnie wracamy do 2.
4. jeśli wierzchołek był odwiedzony to kończymy tą ścieżkę obliczeń i zwracamy liczbę odwiedzonych krawędzi
5. Po zakończeniu wszystkich ścieżek obliczeń wybieramy tą która miała najwięcej odwiedzonych krawędzi.
   Jak widać jedna ścieżka obliczeń może przejść maksymalnie przez wszystkie krawędzie czyli ma O(E) a wyliczaliśmy taką ścieżkę dla każdego wierzchołka więc w sumie mamy O(V*E) co jest niewątpliwie wielomianowe.

Analogicznie możesz przyjąć model ze "zgadywaniem" tzn:

1. dla każdego wierzchołka
2. zgadujemy którą krawędź należy w tej chwili wybrać aby uzyskać najdłuższą drogę
3. wybieramy tą krawędź i idziemy do kolejnego wierzchołka
4. wracamy do 2.
5. na koniec wypisujemy uzyskaną trasę

Jakieś rysunki jeszcze mógłbym prosić?. Schemat krok po kroku na podstawie rysunków?

Ps. Dziekuje raz jeszcze za poświęcony czas i opis zasady działania.

I prosiłbym o informacje? Jaki problem z podanych przeze mnie został rozwiazany??

Nie no do prowadzacego nie. Ale za zasadę działania będę wdzięczny :)

Słabo mi jak czytam takie posty. Żałuje że w ogóle coś tu napisałem, bo możliwe że przyczyniłem sie do tego że nie wywalą cię ze studiów. A powinni...

Tak zle nie będzie. Ale nie każdy musi wszystko wiedzieć:)

kamis159 napisał(a):

Tak zle nie będzie. Ale nie każdy musi wszystko wiedzieć:)

Myślę, że przede wszystkim powinieneś oczekiwać pomocy od prowadzących zajęcia.

Ale tak przy okazji - to informacja o tym co "rozwiązuje" podana wyżej odpowiedź @Shaloma byłaby pomocna...

@vpiotr @kamis159 napisałem wyraźnie który problem rozzwiązuje podany algorytm. Nic nie poradzę że nie umiecie czytać ze zrozumieniem. Co więcej, dla kolegi @kamis159 mam złą wiadomość: jeśli nie potrafisz stwierdzić który z podanych problemów rozwiązuje ten algorytm to nie wyobrażam sobie jak miałbyś umieć go samodzielnie wymyślić. No ale wykształcenie nie piwo, nie musi być pełne...

@kamis159:

Shalom napisał(a):

Na przykład dla longest-path robisz pętlę po każdym wierzchołku szukając "początkowego" a następnie podejmujesz decyzję którą krawędzią iśc.

Czyli prawdopodobnie chodzi o LPATH.
Skąd wziąłeś takie nieludzkie nazwy? Autor zadania musiał Ci wskazać jakiś opis gdzie one są zawarte.