In graph theory,a Hamiltonian cycle is a path which covers all the vertexes exactly once and return to the same vertex.A graph is called a Hamiltonian graph if it contains at least one Hamiltonian cycle. An algorithm to check whether the graph is Hamiltonian or not is an np algorithm that is non deterministic polynomial algorithm . Hence there exists no general procedure too check whether a graph is Hamiltonian and involves a brute force method where we will be trying all possible combinations of paths that can occurs in the graph.such non deterministic algorithms are difficult to implement.For example breaching a 1024 bit encryption does not have any general algorithm and requires one to try out all possible combinations of numbers that can come.The first attempt of such kind was done by Alan Turing breaking German systems..which helped English win the war.
The simplest of the machine design is deterministic finite state automate or deterministic finite state machine.The machine involves a set of states through which the machine goes.When sequential inputs from a language set are givento the machine it state transitions occur and finally rests at the acceptor and not so the case in all other inputs.
The deterministic model involves simple cases and we are not much worried about the number of alphabets and only on the pattern in which they occur. This case is a more complex one and requires a different machine known as push down automate or push down machine.In tis machine a separate stack is used to determine whether the two alphabets are sane in number and is more complex compared to DFM.
The push down machine has a drawback that only two alphabets can be used.This is overcome using a Turing machine developed by Alan Turing.
It has read or write head which moves on top of a tape which contains the sequential data on it . The Turing machine can handle multiple symbols and works on a strike-replace procedure to ensure that the number of alphabets is taken into consideration.........
The simplest of the machine design is deterministic finite state automate or deterministic finite state machine.The machine involves a set of states through which the machine goes.When sequential inputs from a language set are givento the machine it state transitions occur and finally rests at the acceptor and not so the case in all other inputs.
The deterministic model involves simple cases and we are not much worried about the number of alphabets and only on the pattern in which they occur. This case is a more complex one and requires a different machine known as push down automate or push down machine.In tis machine a separate stack is used to determine whether the two alphabets are sane in number and is more complex compared to DFM.
The push down machine has a drawback that only two alphabets can be used.This is overcome using a Turing machine developed by Alan Turing.
It has read or write head which moves on top of a tape which contains the sequential data on it . The Turing machine can handle multiple symbols and works on a strike-replace procedure to ensure that the number of alphabets is taken into consideration.........
0 comments:
Post a Comment