creatio ex nihilo

ศล
Location :
กรุงเทพ Thailand

[Profile ทั้งหมด]

ให้ทิปเจ้าของ Blog [?]
ฝากข้อความหลังไมค์
Rss Feed
Smember
ผู้ติดตามบล็อก : 85 คน [?]




Group Blog
 
All Blogs
 
Friends' blogs
[Add ศล's blog to your web]
Links
 

 

Sam Loyd's 15-Puzzle

หลายคนคงเคยเล่นเกมตัวเลื่อน 15 ตัว ในกรอบ 4 x 4 ช่องซึ่งมีช่องว่าง 1 ช่อง ที่สามารถเลื่อนตัวอื่นไปแทนที่ช่องว่างในแนว x-y ได้ จากรูปด้านล่างนี้เป็นเกมที่แซม ลอยด์ ท้าทายเอาไว้ว่าถ้าใครเลื่อนให้ตัวเลขเรียงกันได้ เอาไปเลย $1,000 (ว่ากันว่าเทียบกับเงินเดี๋ยวนี้คือ $100,000) ดูแล้วตัวเลขอยู่ตรงตำแหน่งหมดยกเว้น 14 กับ 15 ใครที่ไม่เคยลอง จะลองพยายามดูก่อนมั้ยครับ



เอาล่ะ หลังจากพยายามไปสักพักใหญ่ ๆ (หวังว่าคงไม่มีใครใช้เวลาทั้งชาติ) ก็คงจับไต๋ได้แล้วว่างานนี้แซม ลอยด์ ไม่ต้องเสียเงิน ไม่มีใครทำได้ครับ การสับเปลี่ยน (permutation) ระหว่าง 14 กับ 15 นั้นเป็นการสลับครั้งเดียว หมายความว่าถ้าคุณต้องการให้ 14 กับ 15 สลับกัน ไม่ว่าจะใช้วิธีเลื่อนซับซ้อนแค่ไหนก็ตาม คุณจะต้องใช้จำนวนคี่ครั้ง ไม่มีทางเป็นจำนวนคู่ครั้ง คุณอาจนึกภาพ 1 2 3 4 5 6 7 8 9 10 11 12 13 15 14 การสลับตำแหน่งแต่ละคู่คือการสลับ 1 ครั้ง หากผลลัพธ์ที่ต้องการคือ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 คุณอาจสลับได้หลายแบบ เช่น แบบแรกสลับ (14,15) แบบนี้ก็ทำแค่ครั้งเดียว หรือคุณอาจจะ สลับ (13,14) จากนั้น (13, 15) คุณหยุดแค่นี้ไม่ได้ ต้องสลับ (13,14) อีก รวมแล้วเป็น 3 ครั้ง ไม่ว่าคุณจะสลับแบบไหนท่าไหนก็ตาม มันจะยังคงเป็นจำนวนคี่ครั้ง (odd permutation) แต่เงื่อนไขสำคัญในการเล่นเกมนี้คือตัวเลื่อนต้องเลื่อนสลับกับช่องว่าง และไม่ว่าคุณจะเลื่อนพิสดารตระการตายังไงก็ตาม หากสุดท้ายแล้วช่องว่างกลับมาที่เดิม คุณต้องเลื่อนจำนวนคู่ครั้ง (even permutation) เท่ากับแซม ลอยด์บอกให้คุณเลื่อนตัวเลื่อนจำนวนคู่ครั้งที่เป็นจำนวนคี่ครั้ง ใครจะไปทำได้เล่าครับ นอกจากเราจะใช้อะไรแงะตัวเลื่อนให้หลุดออกมาจากกรอบแล้วสลับที่กันบนอากาศ




 

Create Date : 28 กรกฎาคม 2552    
Last Update : 28 กรกฎาคม 2552 13:44:16 น.
Counter : 1529 Pageviews.  

แฟนของคุณจับมือกับคนทั้งหมดกี่คน?

เรื่องมีอยู่ว่า คุณและแฟนของคุณเชิญคู่แต่งงานจำนวนหนึ่งมารับประทานอาหารค่ำ บรรดาแขกทั้งหมดจะจับมือทักทายเฉพาะกับคนที่เขาหรือเธอรู้จักเท่านั้น (คนที่ไม่รู้จักจะไม่จับมือกัน และคู่สามี-ภรรยากันก็จะไม่จับมือกันเอง และถ้าคุณรู้จักเฉพาะคนที่เป็นสามีของคู่หนึ่ง คุณก็จะจับมือกับคนที่เป็นสามีเท่านั้น) หลังจากแขกทุกคนของคุณทักทายกันเรียบร้อย นั่งลงรอบโต๊ะกินข้าว คุณใช้ช้อนเคาะแก้ว ลุกขึ้นประกาศ "เมื่อครู่ผมสังเกตพบว่า นอกจากตัวผมเองนะครับ ในพวกคุณทั้งหมดมีคนหนึ่งที่ไม่จับมือกับใครเลย, มีคนหนึ่งที่จับมือกับคนเพียงคนเดียว, มีคนหนึ่งที่จับมือกับคนสองคน, ..., และสุดท้ายมีคนหนึ่งที่จับมือกับทั้งแปดคน"

ถามว่าแฟนของคุณจับมือกับคนทั้งหมดกี่คนครับ?



โจทย์บอกเราว่าจำนวนการจับมือของคน 9 คนคือ 0, 1, 2, ..., 8 และสูงสุดที่เป็นไปได้คือ 8 เพราะจับมือกับตัวเองและแฟนของตัวเองไม่ได้ ดังนั้น 8 กับ 0 ต้องเป็นแฟนกัน (8,0) นอกจาก 0 กับ 8 แล้วทุกคนล้วนถูก 8 จับมือกันคนละครั้งทั้งนั้น นั่นทำให้ (7,1) เป็นแฟนกัน เนื่องจากหาก 1 ไปเป็นแฟนคนอื่นที่ไม่ใช่ 7 จะต้องถูก 7 จับมือทำให้มันไม่ใช่ 1 อีกต่อไป (มีเพียง 3 คนเท่านั้นที่ 7 ไม่จับมือด้วยคือ ตัวเอง, แฟนตัวเอง และ 0) กวาดสายตาสักหน่อย (คุณรู้ว่าแฟนของ 6 คือ 2 เพราะคนที่ 6 จะไม่จับมือด้วยมีเพียง 0, 1, 6 และแฟนของ 6 ถ้าหาก 2 เป็นแฟนของคนอื่น จะต้องถูกจับมือกับ 6 และทำให้ 2 ไม่ใช่ 2 เพราะมีคนจับมือด้วยแล้ว 3 คือ 8-7-6) สุดท้ายคุณก็จะพบว่าเหลือ 4 ตัวเดียว ทำให้ 4 เป็นแฟนของคุณและจะจับคู่ (4,4)




 

Create Date : 23 กรกฎาคม 2552    
Last Update : 23 กรกฎาคม 2552 17:37:28 น.
Counter : 2004 Pageviews.  

ประมาณความน่าจะเป็นที่มีการแจกแจงทวินามด้วยการแจกแจงปัวซอง


วันก่อนน้องเล่าให้ฟังว่ามีควิซเลข คุณครูเฉลยให้ดูพบว่านักเรียนทำผิดกันทั้งห้อง ผมถามโจทย์เขาก็บอกจำไม่ได้แล้ว (เอ๊ะ อะไรกัน - ทำไมจำไม่ได้) ถามต่อว่าทำไมผิดทั้งห้อง ได้คำตอบว่าคุณครูเฉลยโดยใช้ปัวซองแต่นักเรียนทั้งหมดคิดโดยการแจกแจงทวินาม ถามต่อว่า แล้วคำตอบไม่ตรงไม่ใกล้เคียงกันเหรอ เขาว่าไม่มีใครคิดคำตอบแต่ค้างไว้เพราะตัวเลขมันเยอะ อันที่จริงถ้าคอนเซ็ปถูก คุณครูก็ไม่น่าจะให้ผิดนะ ตรงนี้ทำให้ผมเดาต่อเอาเอง (เพราะมีข้อมูลอยู่แค่นั้น) ว่า คุณครูคงอยากให้ประมาณทวินามที่ n เยอะ ๆ ด้วยปัวซอง รายละเอียดสมบูรณ์ของหัวข้อนี้มีในหนังสือความน่าจะเป็นทั่วไป อันที่จริงมันก็ไม่ยากเย็นอะไร เริ่มต้นด้วย



การทดลองที่มีผลลัพธ์สองทาง (แบนูลลี) n ครั้งที่แต่ละครั้งมีความน่าจะเป็นที่จะเกิดเหตุการณ์ที่เราสนใจ p ความน่าจะเป็นที่ตัวแปรสุ่ม X ซึ่งก็คือจำนวนครั้งที่ได้ผลลัพธ์จากการทดลองที่สนใจเท่ากับ x หาได้จากความสัมพันธ์ข้างต้น และเรารู้ว่าค่าคาดหมายของจำนวนครั้งที่จะได้ผลลัพธ์ที่เราสนใจเท่ากับ np มันคือค่าเฉลี่ย E(X)



เมื่อแทน p = E(X)/n ได้



สังเกตว่าพจน์ nx คือ n คูณกัน x ตัว และ n(n-1)...(n-x+1) ก็มีทั้งหมด x พจน์ เราก็กระจาย n ที่เป็นตัวหารแต่ละตัวไปหารกับพจน์ n(n-1)...(n-x+1) ทั้ง x พจน์ ได้



เมื่อ n มีค่ามาก ๆ ทำให้ c/n เข้าสู่ศูนย์ และ (1-E/n)n เข้าสู่ e-E จากนิยามของ 1/e คือลิมิตของ (1-1/n)n เมื่อ n เข้าสู่อนันต์ ดังนั้นที่ n มาก ๆ เราได้



E(X) ก็คือค่าเฉลี่ย สุดท้ายมันก็ได้ความน่าจะเป็นที่ X=x การแจกแจงแบบปัวซอง






 

Create Date : 23 กรกฎาคม 2552    
Last Update : 23 กรกฎาคม 2552 2:12:55 น.
Counter : 2314 Pageviews.  

McNuggets

ชอบกินนักเก็ตมั้ยครับ? เวลาขายตามพวกแม็คฯหรือเคเอฟซีนี่เขาจะขายกันเป็นกล่อง ๆ มีให้เลือกหลายขนาด สมมติว่ามีกล่อง 6 ชิ้น, 9 ชิ้น กับ 20 ชิ้น (สมมติว่ามีแค่ 3 ขนาด) ปัญหาข้อนี้ให้หาจำนวนเต็ม M ที่น้อยที่สุด ที่ไม่ว่าเราจะสั่งนักเก็ต n ชิ้นใด ๆ ก็ตามที่ n ไม่น้อยกว่า M แล้วเราสามารถสั่งมันได้โดยเลือกจำนวนกล่องผสม ๆ กันจากกล่องสามขนาดที่มีอยู่นั้นเสมอ (ตัวอย่างของคำว่าสั่งได้ เช่น ถ้าคุณสั่ง 7 ชิ้น แบบนี้สั่งไม่ได้, หรือสั่ง 19 ชิ้นก็สั่งไม่ได้ แต่สั่ง 41 ชิ้นได้ เพราะ 41 = 20 + 9 + 6 + 6)

หรือคุณคิดว่าไม่มีค่า M ดังกล่าวอยู่ครับ?



โจทย์เรียบง่ายและสวยดีครับ เพราะถ้าไม่ถาม ก็คิดไม่ถึงว่าจะมีค่า M แบบนี้อยู่ เนื่องจาก 6 เป็นจำนวนน้อยสุดต่อชิ้น ดังนั้นถ้าเราสามารถจัด M, M+1, M+2, M+3, M+4, M+5 ได้ M ที่น้อยที่สุดก็จะเป็นคำตอบ สังเกตว่า (6 mod 3) = (9 mod 3) = 0 ส่วน (20 mod 3) = 2 เรายังขาดผลลัพธ์จากการ mod 3 แล้วเท่ากับ 1 ตัวต่ำสุดที่เป็นไปได้ก็คือ (40 mod 3) = 1 อันนี้มั่นใจได้เลยครับว่า M > 40 ชัวร์! ที่เหลือถ้าเราไม่อยากตั้งสมการหลายตัวแปร ก็ลองแทนค่าครับ 41 = 20 + 9 + 6 + 6, 42 = 9 + 9 + 9 + 9 + 6 แต่ 43 มีปัญหา จัดไม่ได้ 44 = 20 + 9 + 9 + 6, 45 = 9 x 5, 46 = 20 + 20 + 6, 47 = 20 + 9 + 9 + 9, 48 = 6 x 8 และ 49 = (2 x 20) + 9 ดังนั้น M = 44




 

Create Date : 22 กรกฎาคม 2552    
Last Update : 22 กรกฎาคม 2552 17:13:49 น.
Counter : 1164 Pageviews.  

State Machine

ผู้เล่นสองคน ฌาณกับโน้ต มีลูกเต๋าคนละลูก แต่ละคนทอยเต๋าของตัวเองและจดแต้มที่ออกแต่ละครั้งเป็นลำดับที่ต่อเนื่องกันไป ถ้าในลำดับของฌาณปรากฏเลข “12” เขาจะหยุดทันทีและนับจำนวนครั้งทั้งหมดที่ทอย ส่วนโน้ตจะหยุดทอยเมื่อมีเลข “11” เกิดขึ้นในลำดับ คุณผู้อ่านคิดว่าจำนวนครั้งที่ทอยระหว่างฌาณกับโน้ตใครจะมากน้อยกว่ากันครับ? หรือเท่ากัน?

ปัญหาข้อนี้เป็นปัญหาที่ผู้เขียนนำไปตั้งกระทู้เล่นกับเพื่อน ๆ ในเว็บบอร์ดของ pantip.com ห้องหว้ากอ เพราะคิดว่ามีแง่มุมที่น่าสนใจ และเมื่อผู้เขียนเฉลยปัญหาด้วยเทคนิคการนำ State Machine มาใช้คำนวณค่าคาดหมายของจำนวนครั้งที่แต่ละคนจะต้องทอย พบว่าเทคนิคนี้ช่วยลดทอนความซับซ้อนของการคำนวณและสร้างมุมมองอีกมุมหนึ่งได้อย่างสวยงาม จึงเป็นที่มาของบทความตอนนี้ ผู้เขียนจะนำเสนอ State Machine และการใช้ State Machine ช่วยแก้ปัญหาโจทย์

State Machine

ตัวอย่างยอดนิยมในการอธิบายเรื่องนี้คือตู้ขายสินค้าอัตโนมัติ สมมติว่าเรากำลังพูดถึงตู้ขายชา-กาแฟชนิดหยอดเหรียญ ผู้ซื้อสามารถเลือกได้ว่าต้องการเครื่องดื่มร้อนหรือเย็น เติมนมหรือไม่เติมนม หวานหรือไม่หวาน เมื่อผู้ซื้อหยอดเหรียญตามราคาสินค้าแล้วกดปุ่มเลือกสินค้า ซึ่งคุณอาจจะกดปุ่ม ชา/ร้อน/ไม่เติมนม/หวาน จากนั้นก็รอรับถ้วยกระดาษที่บรรจุชาร้อน เราสามารถวาดภาพกลไกอย่างง่ายภายในตู้ได้ว่าประกอบด้วย ท่อกาแฟ ท่อน้ำชา ท่อนม ท่อน้ำเชื่อม และท่อน้ำแข็ง โดยท่อเหล่านี้จะเปิดปิดตามคำสั่งที่ได้รับจากปุ่มกด เช่น ถ้าคุณกดปุ่มกาแฟ ท่อกาแฟก็จะเปิด, กดปุ่มหวาน ท่อน้ำเชื่อมเปิด หรือกดปุ่มเย็น ท่อน้ำแข็งเปิด กลไกดังกล่าวแสดงภาพอย่างง่ายของแบบจำลอง (model) ที่ประกอบด้วย ข้อมูลป้อนเข้า (input), ผลลัพธ์ (output) และกระบวนการ (process) ข้อมูลที่ป้อนเข้าได้แก่ปุ่มกด จากตัวอย่างเราอาจจะมีเพียง 5 ปุ่ม ชา (T), กาแฟ (C), เติมน้ำแข็ง (I), เติมนม (M), เติมน้ำเชื่อม (S) (ว่าโดยหลักการการออกแบบที่ดีแล้ว ชากับกาแฟควรใช้ปุ่มเดียวกัน โดยอาจจะกำหนด “กด” หมายถึงชา และ “ไม่กด” หมายถึงกาแฟ) ส่วนกระบวนการจะดูว่า input คืออะไร แล้วดำเนินการตาม input เช่น เปิดท่อนั้น ปิดท่อนี้ ผลที่ได้จากกระบวนการเราเรียกว่า output ซึ่งแบบจำลองดังกล่าวสามารถเขียนในรูปสมการอธิบายความสัมพันธ์อย่างง่ายได้ Z = f(T, C, I, M, S) เมื่อ Z คือ output และ Z ε {ชานมร้อนหวาน, ชานมร้อนจืด, ชานมเย็นหวาน, ชานมเย็นจืด, ชาร้อนหวาน, ชาร้อนจืด, ชาเย็นหวาน, ชาเย็นจืด, กาแฟนมร้อนหวาน, กาแฟนมร้อนจืด, กาแฟนมเย็นหวาน, กาแฟนมเย็นจืด, กาแฟดำร้อนหวาน, กาแฟดำร้อนจืด, กาแฟดำเย็นหวาน, กาแฟดำเย็นจืด} ถ้ากำหนดให้ “1” = กดปุ่ม และ “0” = ไม่กดปุ่ม จากโมเดล Z = f(T, C, I, M, S) จะพบว่า f(1, 0, 1, 1, 1) คือ ชานมเย็นหวาน เราเรียกวงจร (หรือกลไก) ที่สร้างจากโมเดลที่มีความสัมพันธ์ “output = f(input)” แบบนี้ว่าวงจร combination นอกจากวงจร combination ยังมีวงจรที่เป็นส่วนสำคัญอย่างยิ่งอีกส่วนหนึ่งในตู้ขายสินค้าอัตโนมัติ นั่นคือวงจร sequential ซึ่งวงจรนี้แหละครับ สร้างจากโมเดลที่เรียกว่า “State Machine”



สมมติว่าค่ากาแฟหรือชาร้อน 5 บาท ถ้าเติมนมต้องเพิ่มเงินอีก 5 บาท ใส่น้ำเชื่อมเพิ่มเงินอีก 5 บาท ใส่น้ำแข็งก็เพิ่มเงินอีก 5 บาท และตู้ขายเครื่องดื่มตู้นี้รับเฉพาะเหรียญ 5 บาทเท่านั้น ถ้าคุณต้องการกาแฟนมเย็นหวาน คุณจะต้องเตรียมเหรียญ 5 บาท 4 เหรียญให้พร้อมก่อนที่จะไปยืนหน้าตู้ กรอบความสนใจของเราอยู่ที่ระบบนับเงินนะครับ เหรียญที่หยอดลงตู้จะผ่านวงจรตรวจจับเหรียญห้าบาท ถ้ามีเหรียญห้าไหลผ่าน วงจรจะส่งข้อความบอกว่า “ใช่เหรียญห้า” (Got 5 Baht = 1) แต่ถ้าเหรียญที่ผ่านไม่ใช่เหรียญห้า วงจรก็จะส่งข้อความบอกว่า “ไม่ใช่เหรียญห้า” (Got 5 Baht = 0) ซึ่งข้อความสองข้อความนี้จะเป็น input ให้กับระบบนับเงิน ส่วน output ของระบบนับเงินก็คือการยินยอมให้กดปุ่ม สมมติว่าคุณหยอดเงินแค่ 10 บาท ตู้ขายเครื่องดื่มก็จะยินยอมให้คุณกดปุ่มเพียง 2 ปุ่ม คือ ปุ่ม T หรือ C (เพื่อเลือกชาหรือกาแฟ) และปุ่มใดอีกปุ่มหนึ่งในกลุ่ม I, M, S (ถ้าอยากกดมากกว่านี้ก็ต้องจ่ายมากกว่านี้) ถ้าเราจะเขียนสมการความสัมพันธ์ของระบบนับเงินโดยเลียนแบบโมเดลของวงจร combination เราจะได้ Z = f(Got 5 Baht) และ Z ε {กดได้ 0 ปุ่ม, กดได้ 1 ปุ่ม, กดได้ 2 ปุ่ม, กดได้ 3 ปุ่ม, กดได้ 4 ปุ่ม} คงเห็นได้ไม่ยากว่า input เพียงตัวเดียวและเป็น input ที่มีเพียงสองสถานะ (digital input) คือ 1 (ใช่เหรียญห้า) และ 0 (ไม่ใช่เหรียญห้า) เพียงแค่นี้ไม่สามารถใช้กำหนด output ที่มีถึง 5 สถานะได้ ในความเป็นจริง เมื่อเราหยอดเหรียญห้าบาทเหรียญแรกลงไปแล้ว ตู้จะยอมให้เรากดได้ 1 ปุ่ม และเมื่อเราหยอดเหรียญห้าบาทเหรียญที่สอง ตู้จะยอมให้เรากดอีก 1 ปุ่ม และเมื่อเราหยอดเหรียญห้าบาทอีกเป็นเหรียญที่สาม ตู้ก็จะยอมให้เรากดเพิ่มอีก 1 ปุ่ม สังเกตตรงนี้ให้ดีนะครับ input ของการหยอดเหรียญแต่ละเหรียญเหมือนเดิม คือ “1” แต่ output ของการหยอดเหรียญแต่ละครั้งไม่เหมือนกัน คือ “กดได้ 1 ปุ่ม”, “กดได้ 2 ปุ่ม” และ “กดได้ 3 ปุ่ม” ตามลำดับ นั่นหมายความว่า output ไม่ได้ขึ้นอยู่กับ input เพียงอย่างเดียว แต่มันขึ้นอยู่กับสถานะ (state) ของมันขณะนั้นด้วย อาจเขียนความสัมพันธ์รูปทั่วไปอย่างง่าย “output = f(input, state)” คำว่า “สถานะ” ในตัวอย่างนี้หมายถึงจำนวนเงินสะสมที่หยอดตู้ ดังนั้นสถานะทั้งหมดที่เป็นไปได้คือ {มีเงิน 0 บาท, มีเงิน 5 บาท, มีเงิน 10 บาท, มีเงิน 15 บาท, มีเงิน ≥ 20 บาท} โมเดลที่เขียนความสัมพันธ์ในรูป “output = f(input, state)” คือ State Machine และวงจร (หรือกลไก) ที่สร้างจากโมเดลนี้เรียกว่าวงจร sequential จากตัวอย่างระบบนับเงินเราสามารถเขียน Z = f(Got 5 Baht, state) เช่น f(1, มีเงิน 15 บาท) คุณก็สามารถกดปุ่มได้ 3 ปุ่ม (เลือกชาหรือกาแฟ 1 ปุ่ม และเลือกกด I, M, S ได้อีก 2 ปุ่ม)

เปรียบเทียบระหว่างวงจร combination หรือโมเดล output = f(input) กับวงจร sequential หรือโมเดล output = f(input, state) ได้ดังแผนภาพ



วิธีที่มีประสิทธิภาพวิธีหนึ่งในการบรรยาย State Machine1 คือการเขียนแผนภาพ State หรือ State Diagram2 ว่ากันตามตรง การแก้ปัญหาโจทย์ลำดับแต้มลูกเต๋าข้อนี้ ผู้อ่านไม่จำเป็นต้องรู้จัก State Machine ก็สามารถเรียนรู้ที่จะวาด State diagram ได้ แต่ผู้เขียนมีความเชื่อว่าถ้าเราเห็นภาพรวมของ State Machine ในมุมกว้าง ก็น่าจะมีประโยชน์และช่วยให้เกิดความกระจ่างในการกำหนด state มากยิ่งขึ้น การวาด state diagram สิ่งที่จำเป็นต้องรู้คือ state ทั้งหมด, input, output และปัจจัยที่ทำให้เกิดการเปลี่ยน state สัญลักษณ์ทั่วไปกำหนดให้วงกลมแทน state แต่ละ state และทิศทางของลูกศรแสดงการเปลี่ยน state จาก state ปลายลูกศรไปสู่ state หัวลูกศร บนเส้นลูกศรจะเขียน input/output กำกับ แผนภาพต่อไปนี้แสดง state diagram ของระบบนับเงินที่มี input คือ {ใช่เหรียญห้าบาท (1), ไม่ใช่เหรียญห้าบาท (0)}, output คือ {กดได้ 0 ปุ่ม, กดได้ 1 ปุ่ม, กดได้ 2 ปุ่ม, กดได้ 3 ปุ่ม, กดได้ 4 ปุ่ม} และ state ทั้งหมด ได้แก่ {มีเงิน 0 บาท, มีเงิน 5 บาท, มีเงิน 10 บาท, มีเงิน 15 บาท, มีเงิน ≥ 20 บาท}



ต่อไปผู้เขียนจะทำให้ State Machine ซับซ้อนขึ้นกว่าเดิมโดยการอัพเกรดตู้นี้ให้สามารถรับเหรียญ 10 บาทเพิ่มขึ้นอีกหนึ่งเหรียญ ฉะนั้น input จะเพิ่มขึ้นจากเดิม คือ 0 = ไม่ใช่เหรียญห้าบาท, 1 = ใช่เหรียญห้าบาท เป็น 0 = ไม่ใช่เหรียญห้าหรือไม่ใช่เหรียญสิบบาท, 1 = ใช่เหรียญห้าบาท, 2 = ใช่เหรียญสิบบาท



1State Machine ที่มีจำนวน state จำกัด มีชื่อเรียกว่า Finite State Machine (FSM) ถ้าหากคุณผู้อ่านมีโอกาสได้ค้นคว้าต่อในวิชา Digital Circuit คุณผู้อ่านจะพบว่า FSM มี 2 ชนิดได้แก่ Moore และ Mealy ซึ่งทั้งคู่แตกต่างกันที่การสร้าง output สำหรับ Moore ค่า output = f(state) ส่วน Mealy ค่า output = f(input, state) ถ้าคุณผู้อ่านเห็น output = f(state) ก็ไม่ต้องแปลกใจว่า input หายไปไหนนะครับ เพราะไม่ว่าอย่างไร state ก็ขึ้นอยู่กับ input นั่นแหละ สำหรับ diagram ที่ผู้เขียนวาดในบทความนี้ยึดตามแบบ Mealy

2State Diagram เมื่อพูดโดยรวม state diagram เป็น diagram ที่ใช้บรรยายพฤติกรรมของระบบ ซึ่งเจอบ่อยในวิชาสาขา Computer Science และ Digital Electronics บุคคลแรกที่บรรยาย FSM ด้วย state diagram คือ Taylor Booth (จากหนังสือ Sequential Machines and Automata Theory) นักคณิตศาสตร์ผู้มีผลงานโดดเด่นในทฤษฎี automata


ปัญหาลำดับแต้มจากการทอยเต๋า

กลับไปที่ผู้เล่นเกม ฌาณกับโน้ต ถ้าดูเพียงผิวเผินเหมือนกับโจทย์ถามเราว่าโอกาสเกิด “12” กับโอกาสเกิด “11” เท่ากันหรือไม่? อย่าหลงกลโจทย์แล้วรีบตอบว่าเท่ากันนะครับ แน่นอนว่าโอกาสเกิด “1” ตัวแรกของฌาณกับโน้ตเท่ากัน ระยะเวลาที่รอให้ออกแต้ม 1 (หรือจำนวนทีที่รอ) ก็ควรที่จะเท่ากัน สมมติว่าทั้งคู่ได้ 1 ตัวแรกมาครอบครองกันแล้ว ตอนนี้โน้ตกำลังรอ “1” ตัวที่สอง ซึ่งมีโอกาสเกิดขึ้นเท่ากับ 1/6 และฌาณก็รอ “2” มีโอกาสเกิดขึ้นเท่ากับ 1/6 เท่ากัน สำหรับทั้งคู่ โอกาสไม่ออก 1 ก็เท่ากับโอกาสที่ไม่ออก 2 คือ 5/6 ถ้าในการทอยครั้งนี้ โน้ตไม่ได้ “1” เขาจะต้องเริ่มต้นรอ “1” ตัวแรกใหม่ ในขณะที่ฌาน ถึงแม้ว่าในการทอยครั้งนี้จะไม่ได้ “2” แต่ถ้าฌาณได้ “1” เขาก็ยังสามารถคงสถานะรอ “2” เอาไว้เหมือนเดิมได้ จุดนี้เป็นข้อได้เปรียบของฌานที่ทำให้เราสามารถสรุปได้ว่า ฌาณจะใช้จำนวนครั้งที่ทอยน้อยกว่าโน้ต

ได้เวลาคำนวณตัวเลขออกมากันแล้วครับ ระหว่างจำนวนครั้งที่ทอยของฌาณกับโน้ต ใครจะได้เท่าไร? และมากน้อยกว่ากันเท่าไร? เริ่มจากเขียน state diagram สำหรับกลไกการรอ “11” ของโน้ต input คือแต้มที่ออกจากการทอยเต๋า {1, 2, 3, 4, 5, 6}, output มี 2 สถานะคือ {เล่นต่อ, จบเกม} และมี 3 states {รอ “1” ตัวที่ 1, รอ “1” ตัวที่ 2, หยุด}



ถ้ากำหนดให้ที่ state เริ่มต้น (S0) โน้ตจะต้องทอยเต๋า W ครั้งจึงจะได้ลำดับ “11” (S2) และโอกาสที่ทอยเต๋าได้ 1 เท่ากับ p = 1/6 เราสามารถเขียนความสัมพันธ์

W = (1-p)(W+1) + (p)[(1-p)(W+2) + 2p]

อธิบายสมการ: มีทางออกจาก S0 สองทาง ทางแรกคือกลับมายัง S0 ที่เดิม มีโอกาส 1-p และในเมื่อมันยังอยู่ที่ S0 ณ จุดนี้จึงใช้เวลารอเท่าเดิม (W) จนกว่าจะจบเกม (อย่าลืมว่าคุณต้องทอยเต๋าแล้ว 1 ครั้งจึงกลับมาที่จุดนี้ได้นะครับ) อีกทางคือไปต่อยัง S1 มีโอกาส p และที่ S1 มีโอกาส 1-p จะกลับไปที่ S0 (ถ้ากลับไปรอบนี้แปลว่าทอยเต๋ามาแล้ว 2 ครั้ง) และมีโอกาส p ที่จะถึง S2 (เราทอยเต๋า 2 ครั้ง)

เนื่องจากเป็นสมการตัวแปรเดียว สามารถแก้สมการได้ W = (1+p)/p2 = 42 ดังนั้นค่าคาดหมายจำนวนครั้งที่ทอยเต๋าของโน้ตเท่ากับ 42 ครั้ง ทำนองเดียวกัน วาด state diagram ของฌานได้ดังรูป



กำหนดให้ W0 แทนค่าคาดหมายของจำนวนครั้งที่ทอยเต๋าเมื่ออยู่ S0 กระทั่งได้ลำดับ “12” (หรือถึง S2), W1 แทนค่าคาดหมายจำนวนครั้งที่ทอยเต๋าเมื่ออยู่ S1 จนถึง S2 และ p แทนโอกาสทอยเต๋าได้แต้ม 1

W0 = (1-p)(W0+1) + (p)(W1+1)
W1 = (p)(W1+1) + (1-2p)(W0+1) + (p)(1)

แก้ระบบสมการหาค่า W0 = 36 ดังนั้นค่าคาดหมายจำนวนครั้งที่ทอยเต๋าของฌาณเท่ากับ 36 ครั้ง น้อยกว่าโน้ตถึง 6 ครั้ง เป็นไงบ้างครับ คุณผู้อ่านคิดว่าโจทย์ลักษณะนี้ ใช้ state diagram ช่วยให้เราเห็นภาพได้ชัดเจนยิ่งขึ้นและสามารถวิเคราะห์ความสัมพันธ์ได้ง่ายขึ้นบ้างมั้ยครับ?




 

Create Date : 12 กรกฎาคม 2552    
Last Update : 12 กรกฎาคม 2552 11:47:16 น.
Counter : 6225 Pageviews.  

1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  
 Pantip.com | PantipMarket.com | Pantown.com | © 2004 BlogGang.com allrights reserved.