From e0f54b7d452eac13c388f7d1657e2506a1bd16c1 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 13 Sep 2008 20:30:38 +0200 Subject: [PATCH] Simplified the introduction to models. --- TODO | 4 ---- ram.tex | 37 ++++++------------------------------- 2 files changed, 6 insertions(+), 35 deletions(-) diff --git a/TODO b/TODO index 8f8561e..24a6438 100644 --- a/TODO +++ b/TODO @@ -14,7 +14,3 @@ Ranking: Typography: - formatting of multi-line \algin, \algout - -Diaz: - -> 2: simplify, remove proof sketches diff --git a/ram.tex b/ram.tex index 87bed0c..74a651c 100644 --- a/ram.tex +++ b/ram.tex @@ -196,37 +196,12 @@ course trivial as the adjacency matrix has only~$\Theta(n^2)$ bits.} \para Compared to the RAM, the PM lacks two important capabilities: indexing of arrays -and arithmetic instructions. We can emulate both with poly-logarithmic slowdown, -but it will turn out that they are rarely needed in graph algorithms. We are -also going to prove that the RAM is strictly stronger, so we will prefer to -formulate our algorithms for the PM and use the RAM only when necessary. - -\thm -Every program for the Word-RAM with word size~$W$ can be translated to a~PM program -computing the same with $\O(W^2)$ slowdown (given a~suitable encoding of inputs and -outputs, of course). If the RAM program does not use multiplication, division -and remainder operations, $\O(W)$~slowdown is sufficient. - -\proofsketch -Represent the memory of the RAM by a~balanced binary search tree or by a~radix -trie of depth~$\O(W)$. Values are encoded as~linked lists of symbols pointed -to by the nodes of the tree. Both direct and indirect accesses to the memory -can therefore be done in~$\O(W)$ time. Use standard algorithms for arithmetic -on big numbers: $\O(W)$ per operation except for multiplication, division and -remainders which take $\O(W^2)$.\foot{We could use more efficient arithmetic -algorithms, but the quadratic bound is good enough for our purposes.} -\qed - -\thm -Every program for the PM running in polynomial time can be translated to a~program -computing the same on the Word-RAM with only $\O(1)$ slowdown. - -\proofsketch -Encode each cell of the PM's memory to $\O(1)$ integers. Store the encoded cells to -the memory of the RAM sequentially and use memory addresses as pointers. As the symbols -are finite and there is only a~polynomial number of cells allocated during execution -of the program, $\O(\log N)$-bit integers suffice ($N$~is the size of the program's input). -\qed +and arithmetic instructions. We can emulate both with slowdown $\O(W^2)$, where +$W$~is the word size, but it will turn out that they are rarely needed in graph +algorithms. On the other hand, a~PM program can be translated to a~RAM program +with only constant slowdown, so the RAM is strictly stronger. We will therefore +prefer to formulate our algorithms for the PM and use the RAM only when +necessary. \para There are also \df{randomized} versions of both machines. These are equipped -- 2.39.2