jittat

Merb blog tutorial

2008-12-27T18:45:00.001-08:00

I started using merb a few days ago. After searching through the net, I couldn't find any working blog example for merb 1.0.6.1 (that also uses datamapper) that I'm using. Yes, I know that the new documentation is underway, but I'd rather get this out quickly. (And, yes, I know that merb 2 = rails 3.)

This tutorial just tries to be an shorter updated version of this great tutorial "merb + datamapper + noob: quick start" (from a slightly different viewpoint). It also assumes that you have some knowledge of rails.

First you have to install merb. The easiest way is to just

$ sudo gem install merb

Because we'll use datamapper and sqlite3:

$ sudo gem install datamapper merb_datamapper do_sqlite3

Start by generating merb application:

$ merb-gen app blog

Using this merb-gen app command generates an empty merb application that uses datamapper.

In blog/, you'll find a familiar directory structure. As in rails, configuration files are in config/. The ones that you want to look at are dependencies.rb (that basically lists all the components you're using), init.rb (that specifies your choice of ORM, test framework, and template framework), and database.yml (that, as in rails, provides database config).

Right now, everything merb generates for us looks fine, so we'll stick with it.

Creating the model

It's time to create a model. Issue the command (inside blog/),

$ merb-gen model post

to create model Post. It'll be in app/models/post.rb.

In rails, you'll only have to write migration and model specification (e.g., all the columns) will be automatically read from the database. With DataMapper, we have to specify the model's properties inside its class definition. Out Post model looks like this:


class Post
  include DataMapper::Resource
  
  property :id, Serial
  property :title, String
  property :body, String
end

After that, we have to work with the database to create the table for it. For simple property changes (e.g., adding a new model or adding properties), you don't have to write any migration as merb is clever enough to do that for you: just call

$ rake db:autoupgrade

There's another option for migrating table structures, rake db:automigrate, but this rake task also deletes all your old data (it is destructive), so I prefer db:autoupgrade.

Merb has an interactive console that we can play will models, so let's try to add some post to our blog before moving on.

$ merb -i
irb(main):001:0> p = Post.new :title => 'Hello!', :body => 'This is my first post'
=> #<Post id=nil title="Hello!" body="This is my first post">
irb(main):002:0> p.save
 ~ INSERT INTO "posts" ("title", "body") VALUES ('Hello!', 'This is my first post')
=> true
irb(main):003:0> p2 = Post.create :title => 'Second post', :body => 'what??'
 ~ INSERT INTO "posts" ("title", "body") VALUES ('Second post', 'what??')
=> #<Post id=2 title="Second post" body="what??">

Creating the controller

Okay, we have something to display now. Let's create a controller. Call

$ merb-gen controller posts

This command generates app/controllers/posts.rb. Note that there's no Controller suffix to the name. Let's add something to method index.


class Posts < Application
  def index
    @posts = Post.all
    render
  end  
end

In merb, you have to call render explicitly. This would render a default view for this action. Another point to note is that instead of using Post.find(:all) with Active Record, in Datamapper you only have to call Post.all.

Let's create a view for this action. We can edit views/posts/index.html.erb like this:

<h1>My posts</h1>
<% for post in @posts %>
  <h2><%= post.title %></h2>
  <p><%= post.body %></p>
<% end %>

It's time to see the posts! Run

$ merb

then point your browser to http://localhost:4000/posts or http://127.0.0.1:4000/posts.

New posts

Let's create a new post! We'll add a link "add new post" at the bottom of the index page.

<%= link_to 'add new post', url(:controller => :posts, :action => :new) %>

Method url, that returns a url for an action, can be really fancy, but for now we go with a simple rails-like version.

Then create methods new in Posts controller that render the view.


class Posts < Application
  # ...
  def new
    @post = Post.new
    render
  end
end

Also, the view new.html.erb in app/views/posts:

<h1>Creating new post</h1>
<%= form_for @post, :action => 'create' do %>
  <%= text_field :title, :label => 'Title' %><br/>
  <%= text_area :body, :label => 'Body' %><br/>
  <%= submit 'New post' %>
<% end =%>

Note that we use form_for and methods text_field and text_area know that it is inside this form automatically. (In rails you'd need the block parameter.)

Finally, we add method create to Posts controller:


class Posts < Application
  # ...
  def create
    @post = Post.new params[:post]
    @post.save
    redirect url(:action => 'index')
  end
end

Try it to see if you can create new posts.

Comments

What kind of blogs without comments?

So we'll create the comment model. Call

$ merb-gen model comment

and edit app/models/comment.rb:


class Comment
  include DataMapper::Resource
  
  property :id, Serial
  property :body, String
end

We have to tell a Post that it has many comments. We'll do this by adding something like has_many in Active Record to the model:


class Post
  # ...
  has n, :comments
end

This is how you specify one-to-many association in Datamapper. If you want one, just use has 1, :comment.

Now let's turn to view and controller. Edit app/views/posts/index.html.erb by adding comment listing and new comment form.

<h1>My posts</h1>
<% for post in @posts %>
  <h2><%= post.title %></h2>
  <p><%= post.body %></p>
  <ul>
    <% post.comments.each do |comment| %>
      <li><%= comment.body %></li>
    <% end %>
    <li>
      <%= form_for Comment.new, :action => url(:controller => 'posts', 
                                               :action => 'create_comment', 
                                               :id => post.id) do %>
        <%= text_field :body %>
        <%= submit 'New comment' %>
      <% end =%>
    </li>
  </ul>
<% end %>

<%= link_to 'add new post', url(:controller => :posts, :action => :new) %>

I believe that with merb router, we can write a better the action url. I'll update this entry after I find out how. Also, note that to get the list display correctly, I have to delete the merb stylesheet link line in app/views/layout/application.html.erb because it hides my list items.

To handle this action, we create method create_comment in Posts controller.


class Posts < Application
  # ...
  def create_comment
    post = Post[params[:id]]
    comment = Comment.new params[:comment]
    post.comments << comment
    post.save
    redirect url(:action => 'index')
  end
end

Note the way we find a post by id (Post[params[:id]]).

Hope this blog post help getting you started with merb and Datamapper. Any comments are welcome!

ฉบับภาษาไทย

การสร้างรากฐานรัฐด้วยการศึกษา

2006-08-12T01:49:00.000-07:00

ที่แอลเอ หน้าประตูเข้าสวนกุหลาบ หน้าบริเวณจัดแสดงใหญ่ ที่เป็นที่ตั้งของพิพิธภัณฑ์ประวัิติศาสตร์ธรรมชาติ (Natural History Museum) และศูนย์วิทยาศาสตร์ (Science Center) มีเสาประตูสองอันสลักเป็นประโยคว่า

เสาประตูซ้าย: "THE END OF ALL GOOD GOVERNMENT IS THE HAPPINESS OF THE PEOPLE"

เสาประตูขวา: "THE FOUNDATION OF EVERY STATE IS ITS EDUCATION OF ITS YOUTH"

บังเอิญเหลือเกินที่พกหนังสือ "หลังโครงสร้างนิยม: ฉบับย่อ" เขียนโดยแคทเธอรีน เบลซีย์ แปลโดยอภิญญา เฟื่องฟูสกุล ติดมือไปด้วย แล้วก็บังเอิญเช่นกันที่อ่านเจอข้อความนี้:

"[...] ประเด็นหลักของอัลตูแซร์ก็คือโรงเรียนและมหาวิทยาลัยไม่เพียงผลิตคนหนุ่มสาวป้อนตลาดแรงงานทุกระดับของโครงสร้างเศรษฐกิจเท่านั้น ทว่าในกระบวนการสอนอ่านเขียนและคิดเลข ก็ผลิตคำสอนเรื่องความเชื่อฟัง ความสุภาพอ่อนน้อม จิตวิทยาเบื้องต้น [...] คุณค่าของประชาธิปไตยเสรีนิยม วิธีออกคำสั่ง และวิธีทำงานรับใช้ชุมชน กล่าวสั้น ๆ ก็คือ สถาบันการศึกษาทำให้วินัย โดยเฉพาะวินัยในตัวเองหยั่งรากฝังลึกในความคิดและสนับสนุนให้นักเรียนออกไปสู่สังคมและผดุงรักษาสภาพต่าง ๆ ที่เป็นอยู่ 'ด้วยตัวของพวกเขาเอง"

อืม พอได้อ่านข้อความข้างล่างแล้ว การตีความและการทำความเข้าใจประโยคที่สองข้างต้นก็คงจะเหมือนเดิมไม่ได้แล้ว

เพลงเก่า-เพลงใหม่

2006-06-18T03:56:00.000-07:00

(exteen หยุดให้บริการไปหลายวัน เขียนที่นี่ก่อนแล้วกัน---คงไม่มีใครมาอ่าน)

ใหม่

ซีดีใหม่ที่เพิ่งซื้อมา มีศิลปินสองกลุ่ม (คน) ที่ชื่นชอบมากทั้งคู่ มาทำเพลงด้วยกัน ในอัลบั้ม Give#1

เพลงชื่อ "แสงและเงา" ร้องโดยญารินดา เนื้อร้องโดย วาสิต มุกดาวิจิตร (day tripper) ทำนอง/เรียบเรียงโดยทวนทอง นิยมชาติ (day tripper) เนื้อเพลงที่เขียนโดยอู วาสิต มุกดาวิจิตร นั้นล่องลอย แล้วก็กัดกร่อนความรู้สึกแบบแปร่งแปลก วลีต่อวลีที่เหมือนจะไม่เกี่ยวกัน แต่รวมกันได้ความหมายแบบเฉพาะตัว เป็นเอกลักษณ์ของเนื้อที่เขาแต่ง ตั้งแต่สมัยที่อยู่วงครับแล้ว ส่วนญารินดานี่ชอบมานานแล้ว ยิ่งมาทำเพลงเองก็ทำได้เก๋มาก

อัลบั้มชุดนี้ก็ทำให้ได้ฟังเพลงของอพาร์ตเมนต์คุณป้า ซึ่งเป็นเพลงประหลาดอีกเพลงหนึ่ง คนร้องจะไปฆ่ากามเทพ โยนคันศรทิ้ง ถ้าเธอต้องการ

เก่า

นั่งรถไปศรีราชา ฟังเพลงในรถตู้เป็นเพลงเก่ามาก ของนกแล "อย่าลืมน้องสาว" เพลงขึ้นว่า "ข้าวในนาแลเหลียว มือน้อยคอยเคียว มาเกี่ยวเก็บไป..." (ฟังได้ที่นี่)

"ไปเป็นด๊อกเตอร์ หรือเป็นนักศึกษาที่ไหน เป็นคุณนายบ้านใด บ้านใด ส่งเงินมามากพอแล้ว อย่าให้ส่งตัวพี่ไป หรือรวยแล้วมีน้องใหม่ลงลืมน้องสาว"

ตอนเด็ก ๆ ฟังก็ไม่ได้คิดอะไร แต่ฟังอีกที เพลงนี่จะมีความหมายอื่น ๆ หรือเปล่า? พี่สาวที่กล่าวถึง (เธอเป็นชาวเขา) ไปในเมืองไปทำอะไร? เธอจะไปเป็นด๊อกเตอร์ได้หรือเปล่า? แล้วตอนนี้ล่ะ

คงเป็นเพลงคลาสสิกเพลงหนึ่งเลยทีเดียว

หมายเหตุ: อ้อ.. ระหว่างหา ค้น ๆ เจอว่า นกแล กลับมาอีกครั้ง ชื่อ ดอยเต่าดอตคอม

การแก้สมการเวียนบังเกิดเชิงเส้น

2006-04-14T20:38:00.000-07:00

พิจารณาความสัมพันธ์เวียนบังเกิด (recurrence relations): $F(n) = A\cdot F(n-1) + B\cdot F(n-2)$ และมีค่าเริ่มต้น $F(0)$ และ $F(1)$

ข้อสังเกต 1: ถ้าฟังก์ชัน $f$ และ $g$ สอดคล้องกับความสัมพันธ์เวียนบังเกิดข้างต้น $f+g$ ก็จะสอดคล้องด้วย
บทพิสูจน์: พิสูจน์โดยการแทนค่า

[X]

ข้อสังเกต 2: ฟังก์ชันดังกล่าวเป็นฟังก์ชัน exponential ถ้า $A> 0$ และ $B\geq 0$
บทพิสูจน์:
(lowerbound): เราจะแสดงว่า $F$ มีค่ามากกว่า exponential function บางอัน

สามารถตรวจสอบได้ว่า $F$ เป็นฟังก์ชันไม่ลดลง นั่นคือ $F(n')\geq F(n)$ เมื่อ $n'\geq n$

ให้ $k$ เป็นจำนวนเต็มที่มากกว่า $2\cdot(2/A)$ (จริง ๆ ควรใช้สัญลักษณ์ ceiling แต่ยังหาไม่เจอว่าทำใน ASCIIMathMLได้อย่างไร) พิจารณา
$F(n+k)=AF(n+k-1) + BF(n+k-2) $
$= AF(n+k-1) + AF(n+k-3) + BF(n+k-4)$
$= AF(n+k-1) + AF(n+k-3) + AF(n+k-5) + BF(n+k-6)$
$=\sum_{i=1}^{k//2} AF(n+k+1-2i) + BF(n) \geq (k/2)\cdot AF(n+1) \geq 2F(n)$
นั่นคือ $F(n+k)\geq 2F(n)$ หรือ $F(n)\geq C\cdot 2^(n//k)$ สำหรับค่า $C$ บางค่า

(upperbound): เราจะแสดงว่า $F$ มีค่าไม่เกิน exponential function บางอันเช่นกัน
$F(n)=AF(n-1)+BF(n-2)\leq AF(n-1)+BF(n-1)=(A+B)F(n-1)$ หรือ
$F(n)\leq C'\cdot (A+B)^n$ สำหรับค่าคงที่ $C'$ บางค่า

[X]

ดังนั้นวิธีการที่เราจะพิจารณาต่อไปก็คือการพยายามหา exponential function ที่สอดคล้องกับเงื่อนไขดังกล่าว

คราวหน้ามาต่อครับ...

บทกวีแบบฟิบ

2006-04-10T09:11:00.000-07:00

ฝน
ฟ้า
อากาศ
สุดแสนเงียบ
ฉันนอนอยู่ในห้อง
รอคอยเวลาที่จะตื่นขึ้น
เพียงเพื่อพบกับวันใหม่ที่รออยู่อย่างไม่เปลี่ยนแปลง

บทกวีรูปแบบใหม่ ที่ชื่อว่าฟิบ (เสนอโดย Gregory K. ผมอ่านเจอจาก Geomblog) แต่ละบรรทัดจะประกอบด้วยจำนวนพยางค์เป็นไปตามเลขฟิโบนัชชี คือ 1, 1, 2, 3, 5, 8, 13, 21, ... ที่มีลักษณะคือตัวเลขตัวใด ๆ มีค่าเท่ากับตัวก่อนหน้าสองตัวบวกกัน หรือ ถ้าเขียนเป็นสูตรคณิตศาสตร์ก็คือ $F(1) = 1$, $F(2) = 1$, $F(n) = F(n-1) + F(n-2) $ กว่าจะเขียนได้ห้าบรรทัดก็แทบแย่แล้ว

ลองอีกอัน...

อิ่ม
ง่วง
อยากนอน
ท้องที่อิ่ม
มันทำให้สมอง
หยุดและไม่อยากคิดอะไรอีก

แล้ว closed form ของ $F(i)$ เป็นเช่นใด?

ลำดับฟิโบนัชชีนี้ เป็นรูปหนึ่งของ linear recurrence ซึ่งมีรูปทั่วไปเป็น $x_n = Ax_(n-1)+Bx_(n-2)$ เมื่อ $n\geq 3$ และในกรณีนี้เรามี $x_1=x_2=1$

ขอเอาเรื่องนี้แทรก Central limit theorem สักหน่อยนะครับ... ไว้มาต่อพรุ่งนี้ครับ

ทฤษฎีบทขีดจำกัดกลาง (1)

2006-04-08T04:32:00.000-07:00

กฎแห่งจำนวนมาก บอกกับเราว่า ถ้าข้อมูลตัวอย่างที่สุ่มมามีจำนวนมาก ค่าเฉลี่ยที่ได้ก็จะใกล้กับค่าเฉลี่ยจริง ๆ ทฤษฎีบทขีดจำกัดกลาง (Central Limit Theorem) ให้ข้อมูลที่มากขึ้นกับเรา นั่นคือ ลักษณะของการแจกแจงของค่าเฉลี่ยที่ได้เป็นอย่างไร

Central Limit Theorem กล่าวว่าการแจกแจง (distribution) ของค่าเฉลี่ยเมื่อจำนวนข้อมูลที่สุ่มมามีจำนวนมากจะเข้าใกล้การแจกแจงปกติ (Normal distribution) ซึ่งจะมีรูปโค้งเป็นแบบระฆังคว่ำ (สุดฮิต) ดังรูปด้านล่าง

(รูปจากวิกิพีเดีย)

ในรูปแสดงกราฟการแจกแจงปกติที่ค่าเฉลี่ยและความแปรปรวนต่าง ๆ กัน

ค่าความหนาแน่นน่าจะเป็นของตัวแปรสุ่มที่มีการแจกแจงปกติซึ่งมีค่าเฉลี่ย $\mu$ และความแปรปรวน $\sigma^2$ คือ $f(x) = 1/(\sigma\sqrt((2\pi)))\exp(-\frac{(x-\mu)^2}{2\sigma^2})$

การแจกแจงปกตินี้ถูกนิยามขึ้นโดย Abraham de Moivre (ราชบัณฑิตเรียกเขาว่า เดอมัวฟวร์) ซึ่งใช้การแจกแจงนี้ในการประมาณค่าของการแจกแจงทวินามของจำนวนครั้งที่โยนเหรียญได้หัวจากการโยนเหรียญที่เป็นกลาง 1800 ครั้ง จากนั้น Laplace ได้ขยายทฤษฎีของ de Moivre ให้ใช้ได้กับการแจกแจงทวินามใด ๆ

ถ้าเราทดลองแบบสุ่มไม่ขึ้นต่อกัน $n$ ครั้ง แต่ละครั้งจะทดลองสำเร็จด้วยความน่าจะเป็น $p$ ตัวแปรสุ่มที่นับจำนวนครั้งของการทดลองสำเร็จจะมี การแจกแจงทวินาม ยกตัวอย่างเช่นจำนวนที่ได้หัวจากการโยนเหรียญที่เป็นกลาง 1800 ครั้ง มีการแจกแจงแบบทวินาม ที่มีค่า $n=1800$ และ $p=0.5$ เป็นต้น

ครั้งต่อไปเราจะพิสูจน์ทฤษฎีบทท้องถิ่นเดอมัวฟวร์-ลาปลาส (local theorem of DeMoivre-Laplace)

กฎแห่งจำนวนมาก (2)

2006-04-07T22:17:00.000-07:00

เมื่อเรามีอสมการของเชบิเชฟแล้ว เราสามารถพิสูจน์ กฎแห่งจำนวนมาก ได้ไม่ยากนัก

ก่อนอื่นเราต้องการหาค่าความแปรปรวนของผลรวมของตัวแปรสุ่มก่อน พิจารณาตัวแปรสุ่ม $X$ และ $Y$ เราจะใช้ความจริง (ที่อาจจะไปพิสูจน์กันในวันหลัง)

ความจริง 1 (Linearity of Expectation): $E[X+Y] = E[X] + E[Y]$

ความจริง 2 (ผลคูณของตัวแปรสุ่มที่ไม่ขึ้นต่อกัน): ถ้า $X$ และ $Y$ ไม่ขึ้นต่อกัน เราจะได้ว่า $E[X\cdot Y] = E[X]\cdot E[Y]$

สำหรับตัวแปรสุ่ม $X$ ใด ๆ ค่าความแปรปรวนมีนิยามเป็น $Var[X]=E[X^2]-E[X]^2$ ดังนั้น

$Var[X+Y]=E[(X+Y)^2] - E[X+Y]^2 $
$= E[X^2 + 2X\cdot Y+Y^2]-(E[X]+E[Y])^2$
$= E[X^2] + E[2X\cdot Y]+ E[Y^2]-E[X]^2-2E[X]E[Y] - E[Y]^2$ (ใช้ความจริง 1 ในการกระจาย)

จากความจริง 2: เราจะได้ว่า E[2X\cdot Y] = 2E[X\cdot Y] = 2E[X]E[Y] นั่นคือ

$Var[X+Y]=E[X^2] + E[Y^2] - E[X]^2 - E[Y]^2$
$= (E[X^2] - E[X]^2) + (E[Y^2] - E[Y]^2)$
$= Var[X] + Var[Y]$

นั่นคือ:

ความจริง 3: ถ้าตัวแปรสุ่ม $X$ และ $Y$ ไม่ขึ้่นต่อกัน $Var[X+Y] = Var[X] + Var[Y]$

ดังนั้น, ถ้า $X$ เป็นผลรวมของตัวแปรสุ่ม $X_1,X_2,\ldots,X_n$ ที่ไม่ขึ้นต่อกัน แต่ละตัวมีค่าคาดหวัง $\mu$ และมีความแปรปรวน $\sigma^2$ เราจะได้ว่า

$Var[X]=Var[\sum_{i=1}^n X_i] = n\sigma^2$

เรายังต้องการความจริงอีกข้อหนึ่ง

ความจริง 4: สำหรับค่าคงที่ $c$ ใดๆ $Var[cX] = c^2 Var[X]$

หมายเหตุ: อาจจะสงสัยว่า $Var[2X] = Var[X+X]$ น่าจะเท่ากับ $2Var[X]$ ตามความจริง 3 แต่จากข้างบนเราจะได้ว่า $Var[X+X] = Var[2X] = 4Var[X]$ นั่นเป็นเพราะ $X$ กับ $X$ นั้นไม่ใช่ตัวแปรสุ่มที่ไม่ขึ้นต่อกัน

บทพิสูจน์ (กฎแห่งจำนวนมากแบบอ่อน):
พิจารณา $X_n=(X_1+X_2+\cdots+X_n)//n$ จากความจริงข้างต้น เราทราบว่า $E[X_n] = (E[X_1]+E[X_2]+\cdots+E[X_n])//n = \mu$ และ $Var[X_n] = \frac{1}{n^2}Var[X_1+X_2+\cdots+X_n] = \frac{n}{n^2}\sigma^2 = \sigma^2/n$

เราต้องการหา
$Pr[|X_n-\mu|<\epsilon] =1-Pr[|X_n-\mu|\geq\epsilon]$ พิจารณา $Pr[|X_n-\mu|\geq\epsilon]$ ตามอสมการเชบิเชพ เราจะได้ว่า $Pr[|X_n-\mu|\geq\epsilon]\leq (\sigma^2//n)/epsilon^2 = \sigma^2/(n\cdot\epsilon^2)$ นั่นคือ $\lim_{n\rightarrow\infty}\Pr[|\bar{X}_n-\mu|<\epsilon] \geq 1-\sigma^2/(n\cdot\epsilon^2)=1$ ตามต้องการ

[X]

เกี่ยวกับปัญหา P กับ NP

2006-04-04T19:18:00.000-07:00

ปัญหานี้เป็นปัญหาเชิงทฤษฎีที่สำคัญที่สุดและโด่งดังที่สุดของวิทยาการคอมพิวเตอร์ หลายคนบอกว่าวิทยาการคอมพิวเตอร์เชิงทฤษฎีไม่สามารถจะพูดเกี่ยวกับผลงานของสาขาตนเองได้มากนัก เพราะแม้แต่ปัญหาที่เป็นพื้นฐานที่สุด เรายังไม่สามารถตอบได้เลย

สำหรับคนที่เคยผ่านหูผ่านตาปัญหาชื่อประมาณนี้มาบ้าง ขอผมทบทวนสักหน่อยโดยใช้ภาษาที่ไม่เป็นทางการนัก

เวลาผมกล่าวถึง "ปัญหา" ผมหมายถึงปัญหาที่ต้องการคำตอบว่า "ใช่" หรือ "ไม่ใช่" เช่น ปัญหาจำนวนเฉพาะ ที่ให้จำนวนเต็มบวกมาหนึ่งจำนวน แล้วถามว่าจำนวนหนึ่งเป็นจำนวนเฉพาะหรือไม่?

ปัญหาที่ถูกจัดอยู่ในกลุ่มปัญหา P คือปัญหาที่เรามีวิธีที่หาคำตอบได้อย่างมีประสิทธิภาพ
ปัญหาที่ถูกจัดอยู่ในกลุ่มปัญหา NP คือปัญหาที่ถ้าคำตอบของปัญหาหนึ่ง ๆ คือใช่ เรามีวิธีการที่จะยืนยันคำตอบนั้นอย่างมีประสิทธิภาพ

(อ่านเพิ่มที่วิกิพีเดียไทย)

ปัญหานี้เป็นเรื่องพื้นฐานมาก ๆ ของการหาคำตอบ กับการยืนยันคำตอบ ซึ่งหลาย ๆ คนเชื่อกันว่า อย่างหลังน่าจะง่ายกว่า

ผมจำได้ว่าได้อ่านจาก โพล ที่ทำโดย William Gasarch เกี่ยวกับปัญหา P และ NP คำตอบหนึ่งของ Luca Trevisan ในโพลนั้น (ที่หลาย ๆ คนคงคิดคล้าย ๆ กับเขา) ก็คือ เขากลัวว่าการพิสูจน์ปัญหาดังกล่าวจะเกิดจากการที่บางคนสังเกตเห็นความเกี่ยวข้องบางอย่างระหว่างปัญหานี้กับคณิตศาสตร์แปลก ๆ แล้วก็พิสูจน์ปัญหานี้ออกมาโดยการทำงานในคณิตศาสตร์แปลก ๆ นั้น แล้วเราซึ่งเป็นนักวิทยาการคอมพิวเตอร์ซึ่งรู้เรื่องแค่คอมบินาทอริคส์ จะไม่มีทางเข้าใจบทพิสูจน์นั้นเลย

(ผมได้ข่าวจากบล็อกของ Luca) ในงานการประชุมนักคณิตศาสตร์นานาชาติที่กรุงมาดริก (ICM'06) ที่จะถึงนี้ Avi Wigderson จะนำเสนอบทความ ที่สรุปความคืบหน้าของการพิสูจน์ปัญหา P กับ NP ตอนต้นบทความเขาอ้างถึงคำพูดของ Steve Smale ว่า "ปัญหา P กับ NP --- ของขวัญสำหรับคณิตศาสตร์จากวิทยาการคอมพิวเตอร์"

เราอาจได้เห็นความคืบหน้าบางอย่าง และสิ่งที่ Luca กลัวที่สุดอาจเป็นจริงก็ได้

เกี่ยวกับ MathML และ ASCIIMathML

2006-04-02T20:16:00.000-07:00

จากที่มีหลาย ๆ คนเข้ามาอ่าน แล้วมีปัญหาเกี่ยวกับการใช้ MathML หรือได้ให้ความเห็นเกี่ยวกับการใช้ MathML เอาไว้ (ดู mk หรือ comment ของ bact')

จริง ๆ ผมก็ไม่ค่อยทราบเท่าไหร่นักเกี่ยวกับตัว MathML นี่ พอดีคุยกับ Kanat (ชื่อไทยเขียนไงนะ) ก็แนะนำวิธีที่ได้จาก นุ มา คือให้เอาบรรทัดนี้

<script src="http://www1.chapman.edu/~jipsen/mathml/ASCIIMathML.js" type="text/javascript"></script>

ใส่ลงไปที่หัวบล็อก script นี้เป็นของคุณ Peter Jipsen ชื่อว่า ASCIIMathML

เวลาใช้ก็เขียนแบบที่เขียนใน LaTex คือ ใส่นิพจน์ทางคณิตศาสตร์ในเครื่องหมายดอลลาร์ เช่น

$n^2+b^2/c$

จะได้เป็น $n^2+b^2/c$

สะดวกมาก (สำหรับคนเขียน) ครับ

อสมการของเชบิเชฟ

2006-04-02T08:14:00.000-07:00

จะพิสูจน์กฎแห่งการมีจำนวนมาก เราจะใช้ต้อง อสมการของเชบิเชฟ (ดูรายละเอียดแบบเป็นทางการได้ที่ วิกิพีเดียไทย) ซึ่งกล่าวว่าถ้าตัวแปรสุ่ม $X$ มีค่าคาดหวัง $\mu$ และความแปรปรวน $\sigma^2$ เราจะได้ว่า
$\Pr[|X-\mu|\geq t]\leq (\sigma^2)/(t^2)$

ก่อนอื่นต้องระบุก่อนว่าผมไม่ค่อยแน่ใจว่าบล็อกนี้จะเขียนให้ใครอ่าน คือ.. ไม่ค่อยแน่ใจว่าต้องเขียนถึงเรื่องพื้นฐานแค่ไหน เป้าหมายจริง ๆ ผมพยายามจะเขียนเกี่ยวกับ central limit theorem และการพิสูจน์ (เพราะว่าตอนนี้กำลังอ่านเรื่องที่เกี่ยวข้องกับเรื่องนี้อยู่) ผมก็จะเขียนลึกบ้างตื้นบ้างตามสะดวกแล้วกันนะครับ

คิดว่าหลาย ๆ คนคงเคยเห็นการพิสูจน์อสมการของเชบิเชฟที่ใช้อสมการของมาร์คอฟแล้ว ผมเลยจะเขียนการพิสูจน์โดยตรงแทน (ซึ่งมีแนวคิดเหมือนกัน) ผมตามหนังสือของ Gnedenko ครับ

เอากรณีที่เป็นดิสครีตแล้วกันนะครับ เราทราบว่า
$\Pr[|X-\mu|\geq t] = \sum_{x:|x-\mu|\geq t}\Pr[X=x]$
สังเกตว่าในส่วนที่เราหาผลรวมนั้น $(|x-\mu|)/t\geq 1$ เราจะได้
$\sum_{x:|x-\mu|\geq t}\Pr[X=x]\leq \sum_{x:|x-\mu|\geq t}((|x-\mu|)/t)^2\Pr[X=x] $
$= 1/(t^2) \sum_{x:|x-\mu|\geq t}(x-\mu)^2\Pr[X=x]$
เนื่องจาก $(x-\mu)^2$ นั้นไม่น้อยกว่าศูนย์ ดังนั้นเราสามารถขยายขอบเขตของการหาผลรวมได้ โดยไม่ทำให้ผลที่ได้ลดลง นั่นคือ
$\sum_{x:|x-\mu|\geq t}\Pr[X=x]\leq 1/(t^2) \sum_{x=-\infty}^{\infty}(x-\mu)^2\Pr[X=x]=(\sigma^2)/(t^2)$
เพราะว่า $\sum_{x=-\infty}^{\infty}(x-\mu)^2\Pr[X=x]=\sigma^2$ ตามนิยามของความแปรปรวน

กฎแห่งการมีจำนวนมาก (1)

2006-04-01T06:58:00.000-08:00

(ในบล็อก wonam.exteen.com ผมมักจะเขียนเรื่องทั่ว ๆ ไป แต่สำหรับบล็อกนี้ ผมจะพยายามเีขียนเรื่องที่เกี่ยวข้องกับวิทยาการคอมพิวเตอร์เชิงทฤษฎี ซึ่งอาจเป็นเรื่องที่ผมศึกษาอยู่ หรือไปผ่าน ๆ ตามา)

ให้เหรียญที่เที่ยงตรงมาหนึ่งอัน โยน 2 ครั้ง แล้วนับจำนวนหัวที่ออกมา ตามหลักความน่าจะเป็น ค่าคาดหวัง (expected value) ของจำนวนหัวก็คือ 1 แต่อย่างไรก็ตาม ไม่จำเป็นที่ผลที่ได้เป็นเช่นค่าคาดหวังเสมอไป ถ้าลองคำนวณดูจะพบว่า ความน่าจะเป็นที่จะได้หัว 1 ครั้งพอดี มีค่าเท่ากับ 0.5 เท่านั้น

แล้วความน่าจะเป็นที่เราคำนวณมาเนี่ยะ มันจะมีประโยชน์อะไร? เช่นถ้าเราบอกว่าเหตุการณ์หนึ่งจะเกิดขึ้นด้วยความน่าจะเป็น 0.5 จริง ๆ แล้วมีความหมายอะไรหรือไม่?

ถ้าถกกันเรื่องความหมายแล้ว จริง ๆ ก็ตอบได้ยาก แต่ถ้าเรายึดโมเดลมาตรฐานทั่วไปของความน่าจะเป็น เราสามารถแสดง "ความหมาย" ของตัวเลขความน่าจะเป็นพอได้บ้าง

ความเข้าใจหนึ่งที่เรามีเกี่ยวกับความน่าจะเป็นก็คือจำนวนครั้ง โดยเฉลี่ย ที่เหตุการณ์หนึ่ง ๆ จะเกิดขึ้น แน่นอนคำว่าโดยเฉลี่ยนั้น มีนัยยะของจำนวนอยู่ด้วย นั่นคือ ยิ่งมีการทดลองมากครั้งเข้า จำนวนครั้งของการเกิดขึ้นของเหตุการณ์ที่เรานับได้ ก็ควรจะมีสัดส่วนเข้าใกล้กับความน่าจะเป็น นี่คือ "กฎแห่งการมีจำนวนมาก" หรือ Law of large number (ดูเพิ่มที่ en.wikipedia.org)

ถ้าเราจะอธิบายในเชิงคณิตศาสตร์ เราก็อาจเขียนได้ดังนี้ (นี่คือรูปของ weak law of large numbers): ให้ $X_1,X_2,\ldots$ เป็นลำดับของตัวแปรสุ่ม ที่ไม่ขึ้นต่อกัน มีค่าคาดหวัง $\mu$ และค่าความแปรปรวน $\sigma^2$ ให้ค่าเฉลี่ยของตัวแปรสุ่ม $n$ ตัวแรก $\bar{X}_n = (X_1 + X_2 +\cdots + X_n)/n$ สำหรับ $\epsilon$ ใด ๆ ที่มากกว่าศูนย์

$\lim_{n\rightarrow\infty}\Pr[|\bar{X}_n-\mu|<\epsilon] = 1$
สำหรับการพิสูจน์จะมาเขียนต่ออีกครั้ง

ชื่อซ้ำ ชื่อต่าง

2006-03-23T22:29:00.000-08:00

เพิ่งมาใช้ last.fm (สถิติของผม http://www.last.fm/user/wonam/) ซึ่งเป็น social network ของการฟังดนตรี หลาย ๆ คนสังเกตว่า

มีวงดนตรีหลายวงที่ชื่อซ้ำกัน (อาจจะมาจากหลายประเทศ)
วงดนตรีวงหนึ่ง เขียนได้หลายแบบ เช่น Modern dog กับ Moderndog หรือ P2 Warship กับ P 2 Warship กับ P II W P2 Warship

ผมกำลังคิดว่าเป็นไปได้หรือไม่ที่จะพยายามแก้ปัญหาเหล่านี้โดยอัตโนมัติ