Relative cost random access machines

• Autorzy: Penttonen, M.
• Języki publikacji: EN

Abstrakty

EN

The purpose of a model of computation is to provide the algorithm designer a device for run-ning algorithms. It should be conceptually clear to let him or her concentrate at the algo-rithmic ideas for solving the problem. At the same time it should be concrete enough to give a realistic estimate on the use resources, when the algorithm is executed on a real computer. In this paper we analyze some weaknesses of existing models of computation, namely sequential access machine and random access machine and propose a new cost model, called relative cost random access machine, which solves some contradictions between these models. The new model actually only generalizes the way of counting the complexity, and includes se-quential access machines and random access machines as special cases. At the same time, it is flexible enough to characterize the cost of memory access in current computers.

Słowa kluczowe

EN

Turing machine; random access machine; cost model

• Czasopismo: Fundamenta Informaticae
• Rocznik: 1999
• Tom: Vol. 38, Nr 1,2
• Strony: 17-23
• Opis fizyczny: bibliogr. 7 poz.

Twórcy

autor

Penttonen, M.

• Department of Computer Science and Applied Mathematics, University of Kuopio, Kuopio, Finland,