jittat

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

(exteen หยุดให้บริการไปหลายวัน เขียนที่นี่ก่อนแล้วกัน---คงไม่มีใครมาอ่าน) ใหม่ ซีดีใหม่ที่เพิ่งซื้อมา มีศิลปินสองกลุ่ม (คน) ที่ชื่นชอบมากทั้งคู่ มาทำเพลงด้วยกัน ในอัลบั้ม Give#1 เพลงชื่อ " แสงและเงา " ร้องโดยญารินดา เนื้อร้องโดย วาสิต มุกดาวิจิตร (day tripper) ทำนอง/เรียบเรียงโดยทวนทอง นิยมชาติ (day tripper) เนื้อเพลงที่เขียนโดยอู วาสิต มุกดาวิจิตร นั้นล่องลอย แล้วก็กัดกร่อนความรู้สึกแบบแปร่งแปลก วลีต่อวลีที่เหมือนจะไม่เกี่ยวกัน แต่รวมกันได้ความหมายแบบเฉพาะตัว เป็นเอกลักษณ์ของเนื้อที่เขาแต่ง ตั้งแต่สมัยที่อยู่วงครับแล้ว ส่วนญารินดานี่ชอบมานานแล้ว ยิ่งมาทำเพลงเองก็ทำได้เก๋มาก อัลบั้มชุดนี้ก็ทำให้ได้ฟังเพลงของ อพาร์ตเมนต์คุณป้า ซึ่งเป็นเพลงประหลาดอีกเพลงหนึ่ง คนร้องจะไปฆ่ากามเทพ โยนคันศรทิ้ง ถ้าเธอต้องการ เก่า นั่งรถไปศรีราชา ฟังเพลงในรถตู้เป็นเพลงเก่ามาก ของนกแล "อย่าลืมน้องสาว" เพลงขึ้นว่า "ข้าวในนาแลเหลียว มือน้อยคอยเคียว มาเกี่ยวเก็บไป..." (ฟังได้ ที่นี่ ) " ไปเป็นด๊อกเตอร์ หรือเป็นนักศึกษาที่ไหน เป็นคุณนายบ้านใด บ้านใด ส่งเงินมามากพอแล้ว อ

พิจารณาความสัมพันธ์เวียนบังเกิด (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 fun

ฝน ฟ้า อากาศ สุดแสนเงียบ ฉันนอนอยู่ในห้อง รอคอยเวลาที่จะตื่นขึ้น เพียงเพื่อพบกับวันใหม่ที่รออยู่อย่างไม่เปลี่ยนแปลง บทกวีรูปแบบใหม่ ที่ชื่อว่าฟิบ (เสนอโดย 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 สักหน่อยนะครับ... ไว้มาต่อพรุ่งนี้ครับ

กฎแห่งจำนวนมาก บอกกับเราว่า ถ้าข้อมูลตัวอย่างที่สุ่มมามีจำนวนมาก ค่าเฉลี่ยที่ได้ก็จะใกล้กับค่าเฉลี่ยจริง ๆ ทฤษฎีบทขีดจำกัดกลาง (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 ให้ใช้ได้กับการแจกแจงทวินามใด ๆ ถ้าเราทดลองแบบสุ่มไม่

เมื่อเรามีอสมการของเชบิเชฟแล้ว เราสามารถพิสูจน์ กฎแห่งจำนวนมาก ได้ไม่ยากนัก ก่อนอื่นเราต้องการหาค่าความแปรปรวนของผลรวมของตัวแปรสุ่มก่อน พิจารณาตัวแปรสุ่ม $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$ ที่ไม่ขึ้น

ปัญหานี้เป็นปัญหาเชิงทฤษฎีที่สำคัญที่สุดและโด่งดังที่สุดของวิทยาการคอมพิวเตอร์ หลายคนบอกว่าวิทยาการคอมพิวเตอร์เชิงทฤษฎีไม่สามารถจะพูดเกี่ยวกับผลงานของสาขาตนเองได้มากนัก เพราะแม้แต่ปัญหาที่เป็นพื้นฐานที่สุด เรายังไม่สามารถตอบได้เลย สำหรับคนที่เคยผ่านหูผ่านตาปัญหาชื่อประมาณนี้มาบ้าง ขอผมทบทวนสักหน่อยโดยใช้ภาษาที่ไม่เป็นทางการนัก เวลาผมกล่าวถึง "ปัญหา" ผมหมายถึงปัญหาที่ต้องการคำตอบว่า "ใช่" หรือ "ไม่ใช่" เช่น ปัญหาจำนวนเฉพาะ ที่ให้จำนวนเต็มบวกมาหนึ่งจำนวน แล้วถามว่าจำนวนหนึ่งเป็นจำนวนเฉพาะหรือไม่? ปัญหาที่ถูกจัดอยู่ในกลุ่มปัญหา P คือปัญหาที่เรามีวิธีที่หาคำตอบได้อย่างมีประสิทธิภาพ ปัญหาที่ถูกจัดอยู่ในกลุ่มปัญหา NP คือปัญหาที่ถ้าคำตอบของปัญหาหนึ่ง ๆ คือใช่ เรามีวิธีการที่จะยืนยันคำตอบนั้นอย่างมีประสิทธิภาพ (อ่านเพิ่มที่ วิกิพีเดียไทย ) ปัญหานี้เป็นเรื่องพื้นฐานมาก ๆ ของการหาคำตอบ กับการยืนยันคำตอบ ซึ่งหลาย ๆ คนเชื่อกันว่า อย่างหลังน่าจะ ง่าย กว่า ผมจำได้ว่าได้อ่านจาก โพล ที่ทำโดย William Gasarch เกี่ยวกับปัญหา P และ NP คำตอบหนึ่งของ Luca Trevisan ในโพลน

จากที่มีหลาย ๆ คนเข้ามาอ่าน แล้วมีปัญหาเกี่ยวกับการใช้ 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$ สะดวกมาก (สำหรับคนเขียน) ครับ

จะพิสูจน์กฎแห่งการมีจำนวนมาก เราจะใช้ต้อง อสมการของเชบิเชฟ (ดูรายละเอียดแบบเป็นทางการได้ที่ วิกิพีเดียไทย ) ซึ่งกล่าวว่าถ้าตัวแปรสุ่ม $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

(ในบล็อก wonam.exteen.com ผมมักจะเขียนเรื่องทั่ว ๆ ไป แต่สำหรับบล็อกนี้ ผมจะพยายามเีขียนเรื่องที่เกี่ยวข้องกับวิทยาการคอมพิวเตอร์เชิงทฤษฎี ซึ่งอาจเป็นเรื่องที่ผมศึกษาอยู่ หรือไปผ่าน ๆ ตามา) ให้เหรียญที่เที่ยงตรงมาหนึ่งอัน โยน 2 ครั้ง แล้วนับจำนวนหัวที่ออกมา ตามหลักความน่าจะเป็น ค่าคาดหวัง (expected value) ของจำนวนหัวก็คือ 1 แต่อย่างไรก็ตาม ไม่จำเป็นที่ผลที่ได้เป็นเช่นค่าคาดหวังเสมอไป ถ้าลองคำนวณดูจะพบว่า ความน่าจะเป็นที่จะได้หัว 1 ครั้งพอดี มีค่าเท่ากับ 0.5 เท่านั้น แล้วความน่าจะเป็นที่เราคำนวณมาเนี่ยะ มันจะมีประโยชน์อะไร? เช่นถ้าเราบอกว่าเหตุการณ์หนึ่งจะเกิดขึ้นด้วยความน่าจะเป็น 0.5 จริง ๆ แล้วมีความหมายอะไรหรือไม่? ถ้าถกกันเรื่องความหมายแล้ว จริง ๆ ก็ตอบได้ยาก แต่ถ้าเรายึดโมเดลมาตรฐานทั่วไปของความน่าจะเป็น เราสามารถแสดง "ความหมาย" ของตัวเลขความน่าจะเป็นพอได้บ้าง ความเข้าใจหนึ่งที่เรามีเกี่ยวกับความน่าจะเป็นก็คือจำนวนครั้ง โดยเฉลี่ย ที่เหตุการณ์หนึ่ง ๆ จะเกิดขึ้น แน่นอนคำว่าโดยเฉลี่ยนั้น มีนัยยะของจำนวนอยู่ด้วย นั่นคือ ยิ่งมีการทดลองมากครั้งเข้า จำนวนครั้งของการเกิดขึ้น

เพิ่งมาใช้ last.fm (สถิติของผม http://www.last.fm/user/wonam/ ) ซึ่งเป็น social network ของการฟังดนตรี หลาย ๆ คนสังเกตว่า มีวงดนตรีหลายวงที่ชื่อซ้ำกัน (อาจจะมาจากหลายประเทศ) วงดนตรีวงหนึ่ง เขียนได้หลายแบบ เช่น Modern dog กับ Moderndog หรือ P2 Warship กับ P 2 Warship กับ P II W P2 Warship ผมกำลังคิดว่าเป็นไปได้หรือไม่ที่จะพยายามแก้ปัญหาเหล่านี้โดยอัตโนมัติ