วงแหวนเว็บ

neizod's speculation

insufficient data for meaningful answer

แบบฝึกหัดสุดคลาสสิกในวิยุตคณิต สนใจปริภูมิ $\mathbb{R}^2$ ถามว่าเส้นตรง $n$ เส้นสามารถตัดแบ่งปริภูมินี้ออกเป็นชิ้นส่วนได้เป็นจำนวนมากที่สุดกี่ชิ้น?

Read More
February 29, 2024

คอมพิวเตอร์นั้นแท้จริงแล้วก็คือระบบตรรกะที่ซับซ้อนมากๆ ระบบหนึ่ง นั่นก็คือเราสามารถคำนวณสิ่งต่างๆ ได้ผ่านการนำตัวดำเนินการ $\wedge,\vee,\neg$ (AND/OR/NOT — เพื่อความสะดวก ในที่นี้จะเขียนนิเสธด้วยเส้นขีดยาวข้างบนแทน) มาทำงานร่วมกัน เช่น ถ้าเรามีจำนวนนับสองตัว $n,m$ ที่เขียนผ่านเลขฐานสองขนาด 4 บิต เราสามารถคำนวณ $n+m$ ได้จาก

Read More

เพื่อนในแลปเล่าให้ฟังว่า เจอโจทย์ฝึกสัมภาษณ์งานที่ให้เขียนโปรแกรมเพื่อบวกจำนวนเต็มสองตัวโดยห้ามใช้เครื่องหมายบวก(และลบ) … คือแว๊บแรกก็เข้าใจแหล่ะว่า โจทย์นี้ต้องการทดสอบพื้นฐานการจัดการข้อมูลในระดับบิต ซึ่งก็โอเค คำตอบก็แค่จับ nand gate มาประกอบเป็น halfadder, fulladder เพื่อทำงานบน 2’s compliment ก็เสร็จแล้ว (ถ้ายังจำเทคนิคเหล่านั้นได้จากสถาปัตยกรรมคอมพิวเตอร์อะนะ)

Read More

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

Read More

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

Read More

หนึ่งในคำถามสุดคลาสสิกในเรขาคณิตเชิงคำนวณ เริ่มจากให้ข้อมูลตั้งต้นที่ประกอบด้วยจุด $n$ จุดบนระนาบ เราจะถามว่า ภายในพิสัย (range) ที่เราสนใจนั้นมีจุดใดปรากฏตัวขึ้นมาบ้าง?

Read More
November 30, 2023

ความน่าตื่นตาตื่นใจของเรขาคณิตวิเคราะห์ที่ชาวกรีกโบราณน่าจะไม่มีวันคาดคิดถึง (เพราะสมัยนั้นยังไม่ได้ประดิษฐ์ระบบพิกัดคาร์ทีเซียนมาใช้งาน) คงหนีไม่พ้นแนวคิดทวิภาวะ (duality)1 ระหว่างจุดกับเส้นตรง ซึ่งก็คือ เริ่มจากเรามีจุด $p$ และเส้นตรง $\ell$ ที่นิยามผ่านสมการพิกัดว่า

  1. ตัวอย่างอื่นๆ ของแนวคิดทวิภาวะทางคณิตศาสตร์ที่แพร่หลาย เช่น ลูกบากศ์-ทรงแปดหน้า, เส้นเชื่อม-หน้าติดกันในกราฟเชิงระนาบ, ทฤษฎีบทการไหลสูงสุด-การตัดต่ำสุด ฯลฯ 

Read More
November 26, 2023

จบไปแล้วอีกปีกับงานบาร์แคมป์บางเขน ซึ่งเอาจริงก็นับว่าเป็นบาร์แคมป์ที่สนุกมากทีเดียว แม้ว่างานช่วงเช้าจะดูอ๊องๆ เงียบเหงาคนน้อยไปหน่อยก็ตาม

Read More
November 22, 2023

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

Read More