Algoritmics

วิชานี้เป็นการเรียนเกี่ยวกับ Algorithm (อัลกอริทึ่ม) ซึ่งเป็นกระบวนการคิดในการแก้ปัญหาที่สามารถใช้คอมพิวเตอร์ในการแก้ได้ หรือพูดง่ายๆว่าเขียนโปรแกรมเพื่อแก้ปัญหาได้ (อันนี้ไม่รวมปัญหาอกหัก และ ปัญหาเงินไม่พอใช้ นะครับ) วิชานี้ไม่ใช่วิชาการเขียนโปรแกรม (Progamming 1) (ซึ่งถ้าสนใจเรื่องนั้น ก็อ่านได้จากบทเรียนของ ดร.จันทร์จิรา ที่นี่ครับ การเขียนโปรแกรมภาษา C เบื้องต้น (Introduction to C Programming))

วิชานี้จะต่างจากวิชาการเขียนโปรแกรมนะครับ เพราะวิชาการเขียนโปรแกรม (Programming 1) คือวิชาที่ว่าด้วย grammar ของภาษาโปรแกรมนั้นๆ เช่น if ใช้งานอย่างไร for loop ใช้งานอย่างไร การอ่าน array ทำอย่างไร เป็นต้น แต่วิชานี้ไม่ได้เน้นที่ตัวโปรแกรม แต่ละเน้นที่ปัญหา และ การแก้ปัญหา ซึ่งแน่นอนว่าถ้าคุณมีพื้นฐานการเขียนโปรแกรมที่ดี การแก้ปัญหาด้วยคอมพิวเตอร์ก็ทำได้ดีขึ้นด้วย

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

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

ปัญหาและการแก้ปัญหา

การแก้ปัญหา ในที่นี่ ไม่ได้หมายถึงเพียงแค่การที่ให้เราใช้คอมพิวเตอร์แก้ปัญหา แล้วแก้ปัญหาได้ แต่เราหมายถึงการแก้ปัญหาอย่างเป็นระบบ (Systematically) และ และอย่างมีประสิทธิภาพด้วย (Efficiently)

คำว่ามี ประสิทธิภาพ ในที่นี้ก็หมายถึง การที่เราสามารถคิดวิธีแก้ปัญหา ที่รวดเร็ว ใช้ทรัพยากรของระบบน้อย เช่น ใช้ Memory เพียงนิดเดียว ใช้ Harddisk เพียงนิดเดียว หรือ CPU ที่มีความเร็วต่ำก็ยังใช้ในการประมวลผลเพื่อแก้ปัญหานี้ได้ (เอ๋ รู้สึกว่า Windows Vista จะตรงข้ามกับอันนี้ทุกอย่างเลยนะเนี่ย.. แหะๆ แซวเล่นครับ)

ปัญหา (Problem)

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



ที่เป็นแบบนั้น เพราะวิธีการคิดเพื่อการแก้ปัญหาข้างต้น ในแง่ของการทำงานของคอมพิวเตอร์แล้ว ถ้าคิดง่ายๆก็แทบจะไม่มีอะไรจะต้องคิด (แปลว่าถ้าคิดยากๆ โจทย์นี้ก็มีเรื่องให้คิดอยู่เหมือนกัน) แค่เอาค่า y ตั้งแต่ 1 ถึง 30 ไปแทนเรื่อยๆ แล้วเก็บค่า x ไว้ทีละตัวๆ แล้วมาหาค่าเฉลี่ยของ x เมื่อแทน y ในสมการครบทุกตัว (เรียกว่าเป็นวิธีที่ผมขอเรียกว่า "ตรงไปตรงมา" ที่สุดก็แล้วกัน) คราวนี้ลองดูปัญหาแบบนี้บ้างครับ



อ้าว....นี่มันเกี่ยวกับคอมพิวเตอร์ยังไงเหรอครับอาจารย์ ? ไม่เห็นจะเกี่ยวเลย ... หรือถ้ามันเีกี่ยวกัน แล้วอย่างนี้ผมจะเริ่มเขียนโปรแกรมยังไงดีเนี่ย โอย...งง ไม่รู้จะเริ่มตรงไหนดี... เอ้า..ผมใช้มือคิดบนกระดาษทดนี่เอาก็แล้วกัน!!

แหะๆๆ ถ้าคิดแบบนี้ก็จบแน่ครับ 11-7 ทั้ง 500 สาขา ของคุณเจ๊งหมด เพราะหนทางความเป็นไปได้ทั้งหมดของปัญหานี้ (possible path) มีมากมายถึง 499! (สี่ร้อยเก้าสิบเก้าแฟค โอ! พระเจ้าจอร์จ กล้วยทอด มันยอดมาก 499 แฟคทอเรียล นี่มัน กี่พัน กี่ล้าน หนทางกันละเนี่ย) - (ลองคิดดูเล่นๆนะครับว่าทำไมถึง 499! ถ้าคิดไม่ออกก็อดใจรอ บทถัดไปมีคำตอบเรื่องนี้) งั้นถ้าคุณคิดโดยใช้มือในกระดาษว่าหนทางไหนจาก 499! หนทาง เป็นทางที่ดีที่สุด มีหวังว่าน้ำแข็งขั้วโลกละลาย น้ำท่วมโลกแตกไปแล้วหลายรอบ คุณก็ยังคิดไม่ออก

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

โอว มันยอดมากเลยจอร์จ... ใช่เลย ซาร่า... แต่ช้าก่อน เราลองมาดูอีกซัก 2 ตัวอย่าง ที่ classic ระดับอมตะนิรันดร์กาล เหมือนกันครับ

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

ปัญหา 8Queen (Facility Allocation Problem)

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

      

โจทย์นี้ดูเหมือนจะไร้สาระ แต่จริงๆก็เป็นเวอร์ชั่นง่ายๆของปัญหาประเภทที่เรียกว่า Facility Allocation Problem คือว่าเรามีของหลายอย่าง หรือ โรงงานหลายอันที่ต้องการวางในพื้นที่ โดยการจะวางก็มีเงื่อนไขหรือกฏเกณฑ์ต่างๆมากกำหนดไว้ ยกตัวอย่างเช่น เราเป็น 11-7 (อีกแล้ว) ถ้าหากว่าเราต้องการเปิด 11-7 อีก 8 สาขาโดยมีเงื่อนไขว่า ห้ามอยู่บนถนนเดียวกัน ห้ามอยู่ซอยเดียวกัน ห้ามอยู่ในรหัสไปรษณีย์เดียวกัน เป็นต้น หรือแม้แต่ ห้ามอยู่ใกล้ BigC ห้ามอยู่ติดกับ Tesco หรือเงื่อนไขอะไรอื่นๆอีกสารพัด ปัญหา 8-Queen ของเราก็เป็นแค่เวอร์ชั่นตัวแทนของปัญหาในชีวิตจริงพวกนั้นนั่นเอง


มีอีกปัญหานะครับเดี๋ยวมาเติมให้
ปัญหาการจัดตัวผู้เล่น (Optimization Problem)

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

ผมขอนอกเรื่องตรงนี้นิดนึงครับ แน่นอนในบางปัญหาถ้าเรามี โครงสร้างข้อมูล (Data Structure) ที่ดี มันจะทำให้แก้ปัญหาได้มีประสิทธิภาพขึ้น แต่เอาเป็นว่าในวิชานี้ เราแยกเรื่องของ Data Structure ออกไปก่อน เราจะสมมติว่าโครงสร้างข้อมูลที่เราใช้เป็นแบบพื้นฐาน เช่น array แต่ในวิชาถัดไป เราจะว่าด้วยเรื่องของ Data Structure อย่างเดียว แล้วตอนนั้นคุณจะเห็นว่า Data structure มาเสริมกับ Algorithm ได้เป็นอย่างดี ทำให้ Algorithm ของคุณเร็วและฉลาดยิ่งขึ้นไปอีก

ในหลายมหาวิทยาลัยที่หลักสูตรไม่ได้เน้นเรื่องของ Algorithm และ Data Structure มากนัก ก็เลยรวบเอาสองวิชานี้ (Algorithm Design และ Data Structure) มาเป็นวิชาเดียวกันซะเลย ก็ไม่ผิดตรงไหนและไม่แปลกอะไรเพราะทั้งคู่มันต้องไปด้วยกันอยู่แล้ว หรือ บางแห่งก็รวบสาม คือ ควบวิชา Programming เข้ามาด้วย เพื่อให้นักศึกษาได้เห็นภาพรวมก่อน แต่จะได้ส่วนละนิดละหน่อย ซึ่งก็ไม่ว่ากัน แต่ของเราจะแยกทั้ง 3 วิชาออกจากกัน เพราะเราจะได้เจาะละเอียดขึ้นทั้งในส่วนของ Algorithm และ Data structure นั่นเอง (พวก CS และ IT เจอ Data structure ตอนปี 2 เทอม 1 นะครับ)

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