Model computer - Revision history

JanR at 14:28, 13 January 2015

2015-01-13T14:28:58Z

← Older revision		Revision as of 14:28, 13 January 2015
Line 1:		Line 1:
	[[Category:Other]]		[[Category:Other]]
			[[Category:Checkup]]

JanR at 14:27, 13 January 2015

2015-01-13T14:27:35Z

← Older revision		Revision as of 14:27, 13 January 2015
Line 16:		Line 16:
	For simplicity, interfaces to background devices, terminals, networks, etc., are ignored here. These details are not necessary for the analysis of algorithms and data structures.		For simplicity, interfaces to background devices, terminals, networks, etc., are ignored here. These details are not necessary for the analysis of algorithms and data structures.

	It may be useful to regard the storage units as being organized in larger units (machine words) of fixed size like in a real-world computer. But this is not necessary for most considerations. In fact, an elementary instruction on fixed-size machine words (like on [//~~http:~~en.wikipedia.org/wiki/Reduced_instruction_set_computing RISC]) machines amounts to a constant number of elementary operations on bits. A constant factor on the number of execution steps makes no difference with respect to asymptotic complexity. In other words, a machine model with elementary instructions on bits and an analogously organized machine model elementary instructions on machines words are equivalent and undistinguishable with respect to asymptotic complexity.		It may be useful to regard the storage units as being organized in larger units (machine words) of fixed size like in a real-world computer. But this is not necessary for most considerations. In fact, an elementary instruction on fixed-size machine words (like on [//en.wikipedia.org/wiki/Reduced_instruction_set_computing RISC]) machines amounts to a constant number of elementary operations on bits. A constant factor on the number of execution steps makes no difference with respect to asymptotic complexity. In other words, a machine model with elementary instructions on bits and an analogously organized machine model elementary instructions on machines words are equivalent and undistinguishable with respect to asymptotic complexity.


Line 25:		Line 25:

	=== Remark ===		=== Remark ===
	This model computer is equivalent to the [~~//http:~~//en.wikipedia.org/wiki/Turing_machine Turing machine] model with respect to computability and asymptotic complexity of algorithmic problems. Therefore, all computability and complexity results in this wiki are identical to those in Theoretical Computer Science (but derived differently).		This model computer is equivalent to the [//en.wikipedia.org/wiki/Turing_machine Turing machine] model with respect to computability and asymptotic complexity of algorithmic problems. Therefore, all computability and complexity results in this wiki are identical to those in Theoretical Computer Science (but derived differently).

	=== Reference ===		=== Reference ===
	General introduction to [~~//http:~~//en.wikipedia.org/wiki/Abstract_machine abstract machines].		General introduction to [//en.wikipedia.org/wiki/Abstract_machine abstract machines].

JanR at 14:26, 13 January 2015

2015-01-13T14:26:51Z

← Older revision		Revision as of 14:26, 13 January 2015
Line 8:		Line 8:
	The storage is a large array of elementary storage units, each of which stores one bit of information.		The storage is a large array of elementary storage units, each of which stores one bit of information.

	The processing unit is a [~~//http:~~//en.wikipedia.org/wiki/Boolean_circuit Boolean circuit], that is, a number of logical gates connected by wires. Both the input and the output pins are attached to the bits in the storage, in both cases in a one-to-one correspondence.		The processing unit is a [//en.wikipedia.org/wiki/Boolean_circuit Boolean circuit], that is, a number of logical gates connected by wires. Both the input and the output pins are attached to the bits in the storage, in both cases in a one-to-one correspondence.

	In each clock cycle of the computer, the current values of the storage bits are imported into the combinatorial circuit via the input bins, and the values exported at the output bins are the new values of the storage bins.		In each clock cycle of the computer, the current values of the storage bits are imported into the combinatorial circuit via the input bins, and the values exported at the output bins are the new values of the storage bins.
Line 16:		Line 16:
	For simplicity, interfaces to background devices, terminals, networks, etc., are ignored here. These details are not necessary for the analysis of algorithms and data structures.		For simplicity, interfaces to background devices, terminals, networks, etc., are ignored here. These details are not necessary for the analysis of algorithms and data structures.

	It may be useful to regard the storage units as being organized in larger units (machine words) of fixed size like in a real-world computer. But this is not necessary for most considerations. In fact, an elementary instruction on fixed-size machine words (like on [//http://en.wikipedia.org/wiki/Reduced_instruction_set_computing RISC]) machines amounts to a constant number of elementary operations on bits. A constant factor on the number of execution steps makes no difference with respect to asymptotic complexity. In other words, a machine model with elementary instructions on bits and an analogously organized machine model elementary instructions on machines words are equivalent and undistinguishable with respect to asymptotic complexity.		It may be useful to regard the storage units as being organized in larger units (machine words) of fixed size like in a real-world computer. But this is not necessary for most considerations. In fact, an elementary instruction on fixed-size machine words (like on [//http:en.wikipedia.org/wiki/Reduced_instruction_set_computing RISC]) machines amounts to a constant number of elementary operations on bits. A constant factor on the number of execution steps makes no difference with respect to asymptotic complexity. In other words, a machine model with elementary instructions on bits and an analogously organized machine model elementary instructions on machines words are equivalent and undistinguishable with respect to asymptotic complexity.

JanR at 14:25, 13 January 2015

2015-01-13T14:25:58Z

← Older revision		Revision as of 14:25, 13 January 2015
Line 18:		Line 18:
	It may be useful to regard the storage units as being organized in larger units (machine words) of fixed size like in a real-world computer. But this is not necessary for most considerations. In fact, an elementary instruction on fixed-size machine words (like on [//http://en.wikipedia.org/wiki/Reduced_instruction_set_computing RISC]) machines amounts to a constant number of elementary operations on bits. A constant factor on the number of execution steps makes no difference with respect to asymptotic complexity. In other words, a machine model with elementary instructions on bits and an analogously organized machine model elementary instructions on machines words are equivalent and undistinguishable with respect to asymptotic complexity.		It may be useful to regard the storage units as being organized in larger units (machine words) of fixed size like in a real-world computer. But this is not necessary for most considerations. In fact, an elementary instruction on fixed-size machine words (like on [//http://en.wikipedia.org/wiki/Reduced_instruction_set_computing RISC]) machines amounts to a constant number of elementary operations on bits. A constant factor on the number of execution steps makes no difference with respect to asymptotic complexity. In other words, a machine model with elementary instructions on bits and an analogously organized machine model elementary instructions on machines words are equivalent and undistinguishable with respect to asymptotic complexity.

	~~'''Algorithmic problem:''' [[Graph traversal]]~~

	~~'''Type of algorithm:''' loop~~

	~~== Definitions ==~~
	# For each node, an arbitrary but fixed ordering of the outgoing arcs is assumed. An arc <math>(v,w)</math> preceding an arc <math>(v,w')</math> in this ordering is called '''lexicographically smaller''' than <math>(v,w)</math>.
	# Let <math>p</math> and <math>p'</math> be two paths that start from the same node <math>v\in V</math>, but may or may not have the same end node. Let <math>w</math> be the last common node such that the subpaths of <math>p</math> and <math>p'</math> from <math>v</math> up to <math>w</math> are identical (possibly <math>v=w</math>). If the next arc of <math>p</math> from <math>w</math> onwards is lexicographically smaller than the next arc of <math>p'</math> from <math>w</math> onwards, <math>p</math> is said to be '''lexicograpically smaller''' than <math>p'</math>. Note that the lexicographically ''smallest'' path from <math>v\in V</math> to <math>w\in V</math> is well defined and unique.
	# With respect to a starting node <math>s\in V</math>, a node <math>v\in V</math> is '''lexicographically smaller''' than <math>w\in V</math> if the lexicographically smallest path from <math>s</math> to <math>v</math> is lexicographically smaller than the lexicographically smallest path from <math>s</math> to <math>w</math>.
	~~# In all of the above cases, the reverse relation is called '''lexicographically larger'''.~~
	# A node <math>v\in V</math> is '''lexicographically smaller''' (resp., '''lexicograpically larger''') than a path <math>p</math> if <math>v</math> does not belong to <math>p</math> and the lexicographically smallest path from the start node of <math>p</math> to <math>v</math> is lexicographically smaller (resp., larger) than <math>p</math>. (Note the asymmetry: In both cases, the lexicographically ''smallest'' path to <math>v</math> is used.)
	~~# In all cases, we also say '''precedes''' and '''succeeds''', respectively, instead of "is lexicograpically smaller/larger".~~

	=== Known Related Topics ===		=== Known Related Topics ===

JanR at 14:25, 13 January 2015

2015-01-13T14:25:26Z

Show changes

JanR at 14:12, 13 January 2015

2015-01-13T14:12:21Z

Show changes

Luedecke: Created page with "http://huffmann.algo.informatik.tu-darmstadt.de/wiki/wiki.algo.informatik.tu-darmstadt.de/index.php/Model_computer.html"

2014-10-06T21:56:22Z

Created page with "http://huffmann.algo.informatik.tu-darmstadt.de/wiki/wiki.algo.informatik.tu-darmstadt.de/index.php/Model_computer.html"

New page

http://huffmann.algo.informatik.tu-darmstadt.de/wiki/wiki.algo.informatik.tu-darmstadt.de/index.php/Model_computer.html