วันอาทิตย์ที่ 11 กันยายน พ.ศ. 2559

ผังงาน (Flowchart)

1. ผังงานระบบ(System Flowchat)

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

การใช้งานผังงานระบบ

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


ประโยชน์และข้อจำกัดของผังงานระบบ

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

ข้อจำกัดของผังงานระบบ

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

สัญลักษณ์ที่ใช้ในการเขียนผังงานระบบ

การเขียนผังงานระบบต้องใช้สัญลักษณ์ต่าง ๆ นำมาเรียงกัน เพื่อแสดงลำดับขั้นตอนการทำงาน โดยมีลูกศรเชื่อมระหว่างภาพต่าง ๆ สัญลักษณ์ที่ใช้ในการเขียนผังงานระบบที่นิยมใช้กันนั้นเป็นสัญลักษณ์ของหน่วยงานสถาบันมาตรฐานแห่งชาติสหรัฐอเมริกา (American National Standard Institute : ANSI) และองค์การมาตรฐานนานาชาติ
(International Standard Organization : ISO)หน่วยงานดังกล่าว ทำหน้าที่รวบรวมและกำหนดสัญลักษณ์มาตรฐานที่จะใช้เขียนผังงานระบบ ดังนี้


แบบทดสอบหลังเรียนเรื่องการเขียนผังงาน
1. ข้อใดอธิบายความหมายของผังงานได้ถูกต้อง
    1.แผนภูมิแสดงการเปรียบเทียบการทำงานโปรแกรม
    2.แผนภาพแสดงการทำงานของระบบหรือโปรแกรม
    3.แผนงานแสดงลำดับขั้นตอนของระบบงานคอมพิวเตอร์
    4.แผนผังแสดงการทำงานภายในระบบคอมพิวเตอร์
2. ลักษณะของโครงสร้างผังงานมีกี่โครงสร้าง อะไรบ้าง
    1.2 โครงสร้าง คือ การทำงานแบบลำดับ และแบบทางเลือก
    2.2 โครงสร้าง คือ การทำงานแบบลำดับ และแบบวนซ้ำ
    3.3 โครงสร้าง คือ การงานแบบลำดับ แบบทางเลือกและแบบวนซ้ำ
    4.3 โครงสร้าง คือ การทำงานแบบลำดับ แบบทางเลือก และแบบทำในขณะที่
3. ข้อใดไม่ใช่ประโยชน์ของผังงาน
   1.ช่วยลำดับขั้นตอนการทำงานได้ง่าย ไม่สับสน
   2.ไม่สามารถตรวจสอบได้ และแก้ไขงานได้ยาก
   3.ช่วยให้การดัดแปลง แก้ไข ทำได้อย่างสะดวกและรวดเร็ว
   4.สามารถเรียนรู้และเข้าใจผังงานได้ง่าย
4. ข้อใดเป็นวิธีการเขียนผังงานที่ดี
    1.คำอธิบายในภาพจะยาวหรือสั้นก็ได้
    2.ทุกแผนภาพไม่ต้องมีลูกศรแสดงทิศทางเข้า – ออก
    3.ไม่ควรโยงเส้นเชื่อมผังงานที่อยู่ไกลมาก ๆ ได้
    4.ใช้ลูกศรแสดงทิศทางการไหลของข้อมูลจากล่างไปบน หรือจากขวาไปซ้าย
5. การแสดงผลข้อมูลออกทางเครื่องพิมพ์คือสัญลักษณ์ในข้อใด
   1.Decision
   2. Manual Input
   3.Process
   4.Display
6. สัญลักษณ์ Connect คือสัญลักษณ์อะไร
   1.แสดงการประมวล
   2.แสดงจุดเชื่อมต่อในหน้าเดียวกัน
   3.แสดงจุดเริ่มต้นการทำงาน
   4.แสดงการรับข้อมูลเข้า
7. สัญลักษณ์ Process คือสัญลักษณ์อะไร
    1.แสดงจุดเริ่มต้นการทำงาน
    2.แสดงการรับข้อมูลเข้า
    3.แสดงการประมวล
    4.แสดงการตัดสินใจ
8. การเขียนผังงานโปรแกรมต้องเริ่มด้วยสัญลักษณ์ในข้อใด
    1.Manual Input
    2.Process
    3.Data
    4.Terminator
9. ถ้าต้องการกำหนดให้ตัวแปร A เป็นข้อมูลที่รับเข้าทางแป้นพิมพ์ ต้องใช้สัญลักษณ์ในข้อใด
    1.Data
    2.Display
    3.Process
    4.Manual Input
10. สัญลักษณ์ในข้อใด สามารถมีเพียงสัญลักษณ์เดียวเท่านั้นในผังงาน
     1.การตัดสินใจ
     2.การประมวลผล
     3.การรับค่าข้อมูล
     4.จุดสิ้นสุดของผังงาน
เฉลย
1. แผนภาพแสดงการทำงานของระบบหรือโปรแกรม
2. 3 โครงสร้าง คือ การงานแบบลำดับ แบบทางเลือกและแบบวนซ้ำ
3. ไม่สามารถตรวจสอบได้ และแก้ไขงานได้ยาก
4.  ไม่ควรโยงเส้นเชื่อมผังงานที่อยู่ไกลมาก ๆ ได้
5. Display
6.  แสดงจุดเชื่อมต่อในหน้าเดียวกัน
7. แสดงการประมวล
8. Terminator
9. Manual Input
10. จุดสิ้นสุดของผังงาน

วันจันทร์ที่ 5 กันยายน พ.ศ. 2559

โครงสร้างข้อมูลแบบกราฟ

จุดประสงค์การเรียนรู้
1. เพื่อให้นักศึกษาทราบโครงสร้างข้อมูลแบบกราฟ และการทำงาน
2. เพื่อให้นักศึกษาทราบนิยามของกราฟ
3. เพื่อให้นักศึกษาทราบกระบวนวิธีการแทนที่กราฟในหน่วยความจำ
4. เพื่อให้นักศึกษาทราบวิธีการท่องไปในกราฟในแบบข้อมูลชนิดต่าง ๆ
กราฟ (Graph) เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้น อีกชนิดหนึ่ง กราฟเป็นโครงสร้างข้อมูลที่มีการนำไปใช้ในงานที่เกี่ยวข้องกับการแก้ปัญหาที่ค่อนข้างซับซ้อนเช่น การวางข่าย งานคอมพิวเตอร์ การวิเคราะห์เส้นทางวิกฤติ และปัญหาเส้นทาง ที่สั้นที่สุด เป็นต้น

นิยามของกราฟกราฟ
เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้นที่ประกอบ ด้วยกลุ่มของสิ่งสองสิ่งคือ
(1) โหนด (Nodes) หรือ เวอร์เทกซ์ (Vertexes)
(2) เส้นเชื่อมระหว่างโหนด เรียก เอ็จ (Edges)กราฟที่มีเอ็จเชื่อมระหว่างโหนดสองโหนดถ้าเอ็จไม่มีลำดับ ความสัมพันธ์จะเรียกกราฟนั้นว่ากราฟแบบไม่มีทิศทาง (Undirected Graphs) และถ้ากราฟนั้นมีเอ็จที่มีลำดับความสัมพันธ์หรือมีทิศทางกำกับด้วยเรียกกราฟนั้นว่า กราฟแบบมีทิศทาง(Directed Graphs)บางครั้งเรียกว่า ไดกราฟ (Digraph)ถ้าต้องการอ้างถึงเอ็จแต่ละเส้นสามารถเขียนชื่อเอ็จกำกับไว้ก็ได้




การเขียนกราฟแสดงโหนดและเส้นเชื่อมความสัมพันธ์ ระหว่างโหนดไม่มีรูปแบบที่ตายตัวการลากเส้นความสัมพันธ์เป็นเส้นลักษณะไหนก็ได้ที่สามารถแสดงความสัมพันธ์ระหว่างโหนดได้ถูกต้อง นอกจากนี้เอ็จจากโหนดใด ๆ สามารถวนเข้าหาตัวมันเองได้โดยทั่ว ๆ ไปการเขียนกราฟเพื่อแสดงให้เห็นความสัมพันธ์ ของสิ่งที่เราสนใจแทนโหนดด้วย จุด (pointes)หรือวงกลม (circles)ที่มีชื่อหรือข้อมูลกำกับ เพื่อบอกความแตกต่างของแต่ละโหนดและเอ็จแทนด้วยเส้นหรือเส้นโค้งเชื่อมต่อระหว่างโหนดสองโหนดถ้าเป็นกราฟแบบมีทิศทางเส้นหรือเส้นโค้งต้องมีหัวลูกศรกำกับทิศทางของความสัมพันธ์ด้วย
กราฟแบบไม่มีทิศทางเป็นเซตแบบจำกัดของโหนดและเอ็จ โดยเซตอาจจะว่างไม่มีโหนดหรือเอ็จเลยเป็นกราฟว่าง (Empty Graph)แต่ละเอ็จจะเชื่อมระหว่างโหนดสองโหนด หรือเชื่อมตัวเอง เอ็จไม่มีทิศทางกำกับ ลำดับของการเชื่อมต่อกันไม่สำคัญ นั่นคือไม่มีโหนดใดเป็นโหนดแรก (First Node) หรือไม่มีโหนดเริ่มต้น และไม่มีโหนดใดเป็นโหนดสิ้นสุด
โหนดสองโหนดในกราฟแบบไม่มีทิศทางถือว่าเป็นโหนดที่ใกล้กัน (Adjacent) ถ้ามีเอ็จเชื่อมจากโหนดที่หนึ่งไปโหนดที่สอง
กราฟ (ก) แสดงกราฟที่มีลักษณะ ต่อเนื่อง(Connected) เป็นกราฟที่มีเส้นทางเชื่อมจากโหนดใด ๆ ไปยังโหนดอื่นเสมอ
กราฟ (ข) แสดงกราฟที่มีลักษณะเป็น วีถี(Path) มีเส้นทางเชื่อมไปยังโหนดต่าง ๆ อย่างเป็นลำดับ โดยแต่ละโหนดจะเป็นโหนดที่ใกล้กันกับโหนดที่อยู่ถัดไปกราฟ (ค) แสดงกราฟที่เป็นวัฎจักร (Cycle)ซึ่งต้องมีอย่างน้อย 3 โหนด ที่โหนดสุดท้ายต้องเชื่อมกับโหนดแรก
กราฟ (ง) แสดงกราฟที่มีลักษณะ ไม่ต่อเนื่อง(Disconnected) เนื่องจากไม่มีเส้นทางเชื่อมจากโหนด 3 ไปยังโหนดอื่นเลย
กราฟ (จ) แสดงกราฟที่เป็นทรี โดยทรีเป็นกราฟที่ต่อเนื่อง ไม่มีทิศทาง และไม่เป็นวัฏจักร
กราฟแบบมีทิศทาง เป็นเซตแบบจำกัดของโหนดและเอ็จ โดยเซตอาจจะว่างไม่มีโหนดหรือเอ็จเลยเป็นกราฟว่าง (Empty Graph) แต่ละเอ็จจะเชื่อมระหว่างโหนดสองโหนด เอ็จมีทิศทางกำกับแสดงลำดับของการเชื่อมต่อกัน โดยมีโหนดเริ่มต้น(Source Node) และ โหนดสิ้นสุด (Target Node)รูปแบบต่าง ๆ ของกราฟแบบมีทิศทางเหมือนกับรูปแบบ ของกราฟไม่มีทิศทาง ต่างกันตรงที่กราฟ แบบนี้จะมีทิศทางกำกับด้วยเท่านั้น


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




แบบฝึกหัดข้อมูลแบบกราฟ

แบบฝึกหัด 
1.โครงสร้างข้อมูลแบบกราฟเปรียบได้กับอะไร
   . เซ็ตของจุด
  . เซ็ตของเส้น
  เส้นการเชื่อมต่อ
  ถูกทุกข้อ
2. กราฟรูปนี้เป็นกราฟชนิดใด
  . กราฟระบุทิศทาง
  . กราฟไม่ระบุทิศทาง
  . กราฟระบุน้ำหนัก
  . ผิดทุกข้อ
3. รูปแบบโครงสร้างที่กำหนดเชื่อมต่อแบบเส้นมีความสัมพันธ์แบบใด
  . One to One
  . One to many
  . Many to One
  . Many to Many
4. การท่องเข้าไปในกราฟแบบ Breadth First Traversal ท่องอย่างไร
  . เข้าจากโหนดล่างสุดจากซ้ายไปขวา
  . เข้าจากโหนดล่างสุดจากขวาไปซ้าย
  . เข้าจากตัวโหนดแรกแล้วลงซ้ายไปขวา
  . เข้าจากตัวโหนดแรกแล้วลงขวาไปซ้าย
5. การท่องเข้าไปในกราฟแบบ Depth First Search (BFS) ท่องอย่างไร
  . เข้าจากโหนดล่างสุดจากซ้ายไปขวา
  . เข้าจากโหนดล่างสุดจากขวาไปซ้าย
  ท่องเข้ายังโครงสร้างทรีแบบอินออเดอร์
  .ท่องเข้ายังโครงสร้างทรีแบบพรีออเดอร์
6. Node  of  Graph  มีความหมายตรงกับข้อใด
  . การเชื่อม
  . เซ็ตของจุดบนกราฟ
  . เซ็ตของเส้นบนกราฟ
  . โหนดของกราฟหรือโหนด
7. Critical path method  มีความหมายตรงกับข้อใด
  เส้นทางการเชื่อมต่อ
  . เซ็ตของจุดบนกราฟ
  . เส้นทางเดินบนกราฟ
  . การวิเคราะห์เส้นทางวิกฤต
8. Shortest path analysis มีความหมายตรงกับข้อใด
  . เส้นทางสั้นๆ
  . เส้นทางเดินบนกราฟ
  การวิเคราะห์เส้นทางที่สั้นที่สุด
  . การออกแบบเส้นทางเดินที่สั้นที่สุด
9. รูปแบบข้อมูลของกราฟเป็นอย่างไร
  . เป็นข้อมูลเชิงเส้น
  . มีเส้นทางเดินบนกราฟทางเดียวกัน
  . ข้อมูลที่จัดเก็บต้องกำหนดเป็นชนิดเดียวกัน
  . มีความสัมพันธ์ระหว่างโหนดในลักษณะ many to many
10. กราฟระบุน้ำหนักเป็นอย่างไร
  . เป็นกราฟที่ไม่ระบุทิศทาง
  . เป็นกราฟที่ระบุทิศทางและบอกน้ำหนักได้
  . เป็นกราฟที่ใช้ชั่งน้ำหนักของสินค้าที่ใช้ในการซื้อขาย

  ง. ไม่มีข้อใดถูก