อัลกอริทึมแอนิเมชั่น (Algorithm Animation)

KruskalAlgor….อัลกอริทึม(Algorithm) หรือ ขั้นตอนวิธี หมายความถึงลำดับของขั้นตอนเชิงคำนวณ ซึ่งแปลงตัวอย่างข้อมูลขาเข้าของปัญหา ไปเป็นผลลัพธ์ที่ต้องการ โดยขั้นตอนต่างๆ สามารถแปลงไปเป็นคำสั่งที่ทำงานด้วยคอมพิวเตอร์ได้
…..แอนิเมชั่น(Animation) คือขบวนการทำภาพให้เกิดการเคลื่อนไหว หรือการสร้างและเชื่อมโยงภาพที่มีท่าทางแตกต่างกันเล็กน้อยแต่ขยับอย่างต่อเนื่องมาเรียงต่อกันจนทำให้เกิดการเคลื่อไหว วิธีการที่จะทำให้ภาพเคลื่อนไหวได้นั้นขึ้นอยู่กับเทคนิคและความคิดสร้างสรรค์ส่วนบุคคลในการนำเสนอ Animation สร้างโดยการนำภาพต่อเนื่องของการเคลื่อนไหวซึ่งเรียกว่าเฟรม(Frame) มาแสดงต่อกันบนจอภาพไปทีละเฟรมด้วความเร็วหลายๆเฟรมต่อวินาที ทำให้มองเห็นว่ามีการเคลื่อนไหวของวัตถุบนจอภาพ แอนิเมชั่นมีทั้งแบบ 2 มิติและ 3 มิติ การสร้างการ์ตูน 2 มิติในยุคย้อนหลังไปกว่า 30 ปีจะต้องวาดภาพเป็นจำนวนมากกว่าจะได้การ์ตูนสักเรื่องหนึ่ง ลองจินตนาการดูว่าถ้าต้องการสร้างภาพยนต์การ์ตูนความยาว 30 นาทีด้วย Frame rate = 20 fps(แพร่ภาพจำนวน 20 ภาพใน 1 วินาที) จะต้องวาดภาพจำนวนกี่ภาพ

…..ในปัจจุบันการสร้างภาพแอนิเมชั่นด้วยคอมพิวเตอร์ ผู้สร้างเพียงแต่สร้างคีย์เฟรม(Key frame) และกำหนดตำแหน่งของคีย์เฟรมเหล่านั้นขึ้นมา คอมพิวเตอร์จะจำตำแหน่งของวัตถุต่างๆในแต่ละคีย์เฟรมไว้แล้วทำการสร้างเฟรม ที่อยู่ระหว่างคีย์เฟรมซึ่งเรียกว่า Inbetween ให้โดยอัตโนมัติทำให้ร่นระยะเวลาในการสร้างได้มาก
…..อัลกอริทึมแอนิเมชั่น(Algorithm Animation) คือภาพเคลื่อนไหวแสดงโครงสร้างข้อมูลและการทำงานของอัลกอริทึม
…..การเรียนโครงสร้างข้อมูลและอัลกอริทึมให้ได้ดี นักศึกษาต้องเรียนวิชาการโปรแกรมคอมพิวเตอร์ (Computer Programming) มาก่อน นอกจากนั้นยังต้องมีทักษะการนึกเป็นภาพ(visual thinking) หรือสร้างภาพในสมองได้

การสร้างอัลกอริทึมแอนิเมชั่น เรื่องการเรียงลำดับข้อมูลแบบเลือก(Selection Sort)
การเรียงลำดับข้อมูลแบบเลือกจากน้อยไปมาก(Ascending Order) มีขั้นตอนดังนี้
1. พิจารณาข้อมูล n ชุด Data[1], Data[2], Data[3], Data[4], . . . , Data[n]
2. หาข้อมูลที่มีค่าน้อยที่สุด
3. สลบค่ากับ Data[1]
4. พิจารณาข้อมูล n-1 ชุด เริ่มจาก Data[2], Data[3], Data[4], . . . , Data[n]
5. หาข้อมูลที่มีค่าน้อยที่สุด
6. สลับค่ากับ Data[2]
7. พิจารณาข้อมูล n-2 ชุด เริ่มจาก Data[3], Data[4], . . . , Data[n]
8. หาข้อมูลที่มีค่าน้อยที่สุด
9. สลับค่ากับ Data[3]
10. ดำเนินการจนกว่าข้อมูล n ชุดได้รับการจัดลำดับจากน้อยไปมาก

…..เริ่มต้นด้วยการออกแบบคีย์เฟรม(key frame) ซึ่งจะมีมากน้อยเพียงใด ขึ้นอยู่กับจำนวนขั้นตอนการทำงานของอัลกอริทึม คีย์เฟรมแรกกับคีย์เฟรมสุดท้าย จะมีหน้าตาดังนี้….กำหนดให้ n = 6

SelectSort1
คีย์เฟรมแรก ข้อมูล 6 ชุด(n=6) ซึ่งยังไม่ได้จัดเรียงลำดับกัน

SelectSort11
คีย์เฟรมสุดท้าย จบการทำงาน ข้อมูล 6 ชุด ถูกจัดเรียงลำดับกันจากน้อยไปมาก ขั้นตอนทั้งหมดจะมีการเปรียบเทียบข้อมูลกัน(เพื่อหาข้อมูลที่มีค่าน้อยที่สุด) 15 ครั้ง และมีการสลับข้อมูลเพื่อให้เรียงกันจากน้อยไปมาก 5 ครั้ง

….ดูภาพแอนิเมชั่น… Selection Sort>>
…..หมายเหตุ คอมพิวเตอร์ที่ใช้ดูภาพแอนิเมชั่นต้องติดตั้ง JRE(Java Runtime Environment) โดยสามารถ Download ได้ที่….Download JRE>>

อัลกอริทึมการเรียงลำดับแบบเลือก(Selection Sort) ในรูปแบบรหัสลำลองหรือรหัสเทียม(pseudo code)
Procedure SelectionSort(Data,n) จัดเรียงลำดับข้อมูลจากน้อยไปมาก(Ascending Order) กำหนดให้ Data เป็นอาร์เรย์ 1 มิติ มีข้อมูล n ชุด ตัวแปร MinDex เป็นดัชนีของข้อมูลที่มีค่าน้อยที่สุดในอาร์เรย์ Data ตัวแปร i และ j เป็นตัวแปรเสริม

1. [วนซ้ำจนกระทั่ง i มีค่าเท่ากับ n-1]
…..Repeat thru step 3 for i = 1, 2, 3, …. , n-2, n-1
……….MinDex ← i
2. [วนซ้ำจนกระทั่ง j มีค่าเท่ากับ n] (หาดัชนีของข้อมูลที่มีค่าน้อยที่สุด)
……….repeat for j = i+1, i+2, …. , n
……………if Data[j] < Data[MinDex]
………………..then MinDex ← j
3. [สลับค่า]
……………swap(Data[i], Data[MinDex])
4. [เสร็จเรียบร้อย]
…..Return

อัลกอริทึมในรูปแบบรหัสเทียมอีกแบบหนึ่ง
For i = 1 to n-1
begin
……..MinDex ← i
……..for j = i+1 to n
……..begin
………….if Data[j] < Data[MinDex]
……………..then MinDex ← j
……..end  // of for
……..swap(Data[i], Data[MinDex])
end  // of For

…..เริ่มต้นด้วยการออกแบบคีย์เฟรม(key frame) ซึ่งจะมีมากน้อยเพียงใด ขึ้นอยู่กับจำนวนขั้นตอนการทำงานของอัลกอริทึม คีย์เฟรมแรกกับคีย์เฟรมสุดท้าย จะมีหน้าตาดังนี้….กำหนดให้ n = 6

algor1
คีย์เฟรมแรก ข้อมูล 6 ชุดในอาร์เรย์ Data ซึ่งยังไม่ได้มีการจัดเรียงลำดับกัน

algor27
คีย์เฟรมสุดท้าย จบการทำงาน ข้อมูล 6 ชุดในอาร์เรย์ Data ถูกจัดเรียงลำดับกันจากน้อยไปมาก ขั้นตอนทั้งหมดจะมีการเปรียบเทียบข้อมูลกัน(เพื่อหาข้อมูลที่มีค่าน้อยที่สุด) 15 ครั้ง และมีการสลับข้อมูลเพื่อให้เรียงกันจากน้อยไปมาก 5 ครั้ง

   ผลตอบรับในชั้นเรียน
♦ ผู้สอนสามารถสอนทบทวนได้หลายๆเที่ยว โดยใช้เวลาไม่มาก
♦ ผู้สอนสามารถสอนให้ครอบคลุมเนื้อหาทั้งหมดได้ในเวลาที่กำหนด
♦ นักศึกษาสามารถทบทวนบทเรียนได้ด้วยตนเอง เพราะสามารถนำขึ้นไปไว้บนเว็บไซต์ได้
ถ้า Algorithm Animations นี้ครอบคลุมบทเรียน Array, Stack, Queue, Linked List, Tree, Graph, Sorting, Heap, Searching คงทำให้วิชาโครงสร้างข้อมูลและอัลกอริทึม เป็นวิชาที่น่าเรียนมากขึ้น..

Advertisements

ใส่ความเห็น

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / เปลี่ยนแปลง )

Twitter picture

You are commenting using your Twitter account. Log Out / เปลี่ยนแปลง )

Facebook photo

You are commenting using your Facebook account. Log Out / เปลี่ยนแปลง )

Google+ photo

You are commenting using your Google+ account. Log Out / เปลี่ยนแปลง )

Connecting to %s