Model computer: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
No edit summary
 
(3 intermediate revisions by the same user not shown)
Line 1: Line 1:
[[Category:Other]]
[[Category:Other]]
[[Category:Checkup]]




Line 8: Line 9:
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 17:
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.


'''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 ===
Line 35: Line 26:


=== 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].

Latest revision as of 14:28, 13 January 2015


Defintion

The model computer consists of a storage and a processing unit.

The storage is a large array of elementary storage units, each of which stores one bit of information.

The processing unit is a 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, only a single machine instruction is executed, that is, a single bit is copied or two bits are processed logically/arithmetically (giving the values of one or two other bits). In particular, in each clock cycle, a constant, instruction-specific number of gates is involved in the update of the bit values in the storage.

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 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.


Known Related Topics

All descriptions of algorithms and data structures and algorithmic problems in this wiki shall be based on this model of computation (unless clearly stated otherwise).

Remark

This model computer is equivalent to the 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

General introduction to abstract machines.

Retrieved from "https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Model_computer&oldid=2733"