concrete mathematics
jonsul
already I've learned a lot, thanks to Joe I've got the book Concrete
Mathematics, I'm going to be working through that as much as I can. I
will post in this thread everything I've learned or am working through
here. As I find the time of course.
Honestly I think this course was a success, but not really as a
course. This thread should stay open and be a long running thing.
jonsul
I mentioned above. To show what I've already learned, is the symbols
used in mathematics. Before when I saw symbols I was overwhelmed and
looked to something more pleasant after. But now I realize they're
almost like shortcuts, I guess not really functions in programming but
macros like in Lisp. If you've learned lisp macros you know what I
mean. Now I think I should learn why these symbols are important.
I'm getting the logarithms somewhat, it's the exponent to reach a
number given according to a certain base. And there are three main
bases, 2 or binary, 10 or common, and e which is a long ass number
that starts with 2.7...... I think.
I want to ask, how are these are useful? What is the logarithms used t
do?
jonsul
I'm working on the hanoi tower. In the passage:
This gives us a clue for transferring n disks
in general: We first transfer the n - 1 smallest to a different peg
(requiring
T(n-1) moves), then move the largest (requiring one move), and finally
transfer
the n- 1 smallest back onto the largest (requiring another Tn..1
moves). Thus
we can transfer n disks (for n > 0) in at most 2T(n-1) + 1 moves:
Tn 6 2T(n-1) + 1 for n > 0.
I somewhat get this. But not a lot, I don't really know what it is I
don't understand. It feels like some of it makes sense, yet a lot of
it is just beyond my grasp. This is the point most teachers would tell
me to don't worry about it and just write it down for later. So what
is it saying here.
Alan Cooper
As you have noticed, in general logarithms are defined as the
solutions of "exponential equations" (which just means finding the
exponents which make powers have specified values)
Here are a couple of situations where you might want to do that:
1. Investing money (say a "principal" of $P) at a rate of 4% compounded
annually yields an amount $A which is given after t years by
A=P(1.04)^t. So if you want to find how long it will take to double your
money you need to find t satisfying A=2P ie P(1.04)^t=2P. Cancelling the
Ps gives (1.04)^t=2 so t is the logarithm base 1.04 of 2.
2. For a radioactive sample of half life 6 years which is now emitting
10 times the "safe" level of radiation it may be fairly clear that
after 6 years the amount of radiation is 5 times the safe level, after
12 years it is down to 2.5 times, and so on. So we can see that the time
when the safe level is reached is somewhere between 18 and 24 years, but
by using logarithms we can get a more exact answer. In fact we need to
wait exactly t years where (1/2)^(t/6)=(1/10) so t/6= log(base0.5)of(0.1).
Using properties of logarithms (which are just the exponent laws
"translated" into log language) it is possible to express these answers
in terms of the "common"(base 10) or "natural"(base e) logarithms that
are provided on a typical calculator.
The "naturalness" of that weird number e arises from a couple of neat
properties. One has to do with what happens in the case of compound
interest when we go from annual comounding to semi-annual to monthly to
daily and so on to the limiting case of "continuous compounding". And
the other has to do with properties of the graph of the function f(x)=e^x
You might be able to find more applications and illustrations of the e
business by checking out what is available at the College Math Resources
website (http://qpr.ca/math/resources)
I hope some of this helps a bit.
cheers,
Alan
Joe Corneli
I feel the same way about busy with work and the thread staying open
and long running. :0
I'll reply with more about the math stuff tomorrow, gotta sleep now!
Joe
Alan Cooper
them (onto the "spare" peg) then the big one to the "target" peg and
then the rest on top of it. This gives a strategy for moving n disks
which takes one more than twice the moves required to move just n-1 of
them (twice because they have to be moved twice - once onto the "spare"
peg and once onto the "target", and one more because of the move of the
big disk). We don't know that it is the *best* strategy for n disks, but
the best strategy certainly can't take more moves than this. So the
least number of moves required for n disks (called T(n)) is less than or
equal to one more than twice the least number of moves required for
(n-1) disks (which is denoted by T(n-1)).
In algebraic form this is T(n) ≤ 2T(n-1)+1
(if you are reading this as html ≤ will be the "less than or equal"
sign, which in comp sci is often writen as <=, and I don't know if the
numeral 6 which you had is a misprint or a misreading from unclear print)
cheers,
Alan
jonsul
understand why T was there at all, but I think I understand. Is this
using recursion? Where it's calling itself until n equals 0, because n
> 0. I would normally see this because I'm using lisp a lot, but
recursion in lisp traditionally uses tail-call recursion where T would
be at the end of the equation. Not used to seeing it in the middle of
an equation.
Sometimes it helps me to understand math when I put it as a
programming function. This is how I would write it.
(defun hanoi (num)
(if (zerop num)
0
(1+ (* 2 (hanoi (1- num))))))
Am I right about it being recursive?
Alan Cooper
are calling "hanoi".
And, although I don't speak Lisp, your definition looks as if it's
probably right except for possibly wanting (num-1) in place of (1- num).
That may just be something idiosyncratic about the way Lisp works, but
according to what I just looked up perhaps it should be (- 1 num).
cheers,
Alan
>> In algebraic form this is T(n)≤ 2T(n-1)+1
>> (if you are reading this as html≤ will be the "less than or equal"
Joe Corneli
those who want to follow along but haven't bought the book, I happen
to have noticed that it's currently available online as a PDF, just google
for "concrete mathematics". I assume you'll try before you buy, because
the book is one we will all want to own eventually :)
BTW, 1- is a lisp function for "subtract one". (- 1 num) would be "subtract
num from 1", typically different.
(1- NUMBER)
Return NUMBER minus one.
Alan Cooper
the first all the others" as "successively subtracts the first from all
the othes" (and failed to check the example which would have shown me I
had it wrong)
Alan Cooper
option? (or perhaps defaulting to replyPrivate with replyAll being
necessary to go to the list) Or are people ok with getting extra
messages so long as they can tell from the subject that it can safely be
ignored and deleted? (In this instance it was useful to get joe's input,
and jonsul may be interested in the fact that I was corrected, so there
may have been some value in spamming everyone after all)
-Alan
On 2010.10.09 10:07 AM, Alan Cooper wrote:
> You're right I misread the description "successively subtracts from
> the first all the others" as "successively subtracts the first from
> all the othes" (and failed to check the example which would have shown
> me I had it wrong)
>
> On 2010.10.09 3:49 AM, Joe Corneli wrote:
>> Hi all, I guess I'll leave the discussion to you for the moment, but
>> btw for
>> those who want to follow along but haven't bought the book, I happen
>> to have noticed that it's currently available online as a PDF, just
>> google
>> for "concrete mathematics". I assume you'll try before you buy, because
>> the book is one we will all want to own eventually :)
>>
>> BTW, 1- is a lisp function for "subtract one". (- 1 num) would be
>> "subtract
>> num from 1", typically different.
>>
>> (1- NUMBER)
>>
>> Return NUMBER minus one.
>>
>> On Sat, Oct 9, 2010 at 6:56 AM, Alan Cooper<al...@qpr.ca> wrote:
>>> etc etc etc
>
Alison Jean Cole
Thanks!
ALISON COLE
Joe Corneli
turn on Emacs and run M-x hanoi or M-x hanoi-unix. The code
is so complex that any intuition would likely be lost in the details,
don't you think?