การวิเคราะห์โครงสร้างข้อมูลและอัลกอริธึมด้วย Python (ฉบับที่ 2)
หนังสือเล่มนี้เป็นหนังสือเรียนคลาสสิกที่ใช้ภาษา Python ในการอธิบายโครงสร้างข้อมูลและอัลกอริธึม โดยครอบคลุมหัวข้อต่างๆ เช่น การทบทวนพื้นฐานของ Python, การวิเคราะห์อัลกอริธึม (การเขียนแบบโอใหญ่), โครงสร้างข้อมูลพื้นฐาน (สแตก, คิว, ลิสต์), การเรียกซ้ำ, การค้นหาและการจัดเรียงข้อมูล, อัลกอริธึมของต้นไม้และกราฟ พร้อมด้วยรายการโค้ดจริงเพื่อช่วยให้ผู้อ่านเข้าใจวิธีการนำเอาชนิดข้อมูลเชิงนามธรรมต่างๆ มาใช้งานอย่างมีประสิทธิภาพผ่านภาษา Python
ภาพรวมคอร์สเรียน
📚 สรุปเนื้อหา
หนังสือเล่มนี้เป็นตำราคลาสสิกที่ใช้ภาษา Python ในการอธิบายโครงสร้างข้อมูลและอัลกอริธึม โดยครอบคลุมหัวข้อต่าง ๆ เช่น การทบทวนพื้นฐานของ Python, การวิเคราะห์อัลกอริธึม (การเขียนเชิงคำนวณแบบโอใหญ่), โครงสร้างข้อมูลพื้นฐาน (สแตก, คิว, ลิสต์), การเรียกซ้ำ, การค้นหาและการจัดเรียง, อัลกอริธึมของต้นไม้และกราฟ ผ่านรายการโค้ดที่ใช้งานจริง เพื่อช่วยให้ผู้อ่านเข้าใจวิธีการนำเอาประเภทข้อมูลที่ถูกนามธรรมมาใช้ในภาษา Python ได้อย่างมีประสิทธิภาพ
เพียงแค่เข้าใจโครงสร้างข้อมูลและอัลกอริธึมอย่างลึกซึ้ง จึงจะสามารถเชี่ยวชาญภาษา Python ได้จริง
ผู้แต่ง: แบรดลีย์ มิลเลอร์ (ศาสตราจารย์เกียรติคุณด้านวิทยาการคอมพิวเตอร์ มหาวิทยาลัยลูเธอรัน สหรัฐอเมริกา) และ เดวิด ราแนม (วิศวกรซอฟต์แวร์ด้านความฉลาดทางปัญญาจาก IBM Watson)
ขอบคุณ: ขอขอบคุณเพื่อนร่วมงานสตีฟ ฮับบาร์ด สำหรับข้อเสนอแนะจำนวนมากในฉบับที่ 1 และข้อมูลใหม่สำหรับฉบับที่ 2 รวมถึงผู้อ่านทุกท่านที่ส่งอีเมลแจ้งข้อผิดพลาดและข้อเสนอแนะ ขอบคุณพนักงานที่ร้านกาแฟ "จาเว่ จอห์น" ในเมืองดิโกล่า อย่างเมรี่ บ๊อบ เป็นต้น ที่ยอมให้เราเป็น “นักเขียนประจำ” ระหว่างหยุดพัก ขอขอบคุณทีมงานบริษัทสำนักพิมพ์แฟรงคลิน บีเดิล & แอสโซซิเอทส์ (โดยเฉพาะเจมส์ ไลซี่ และทอม ซัมเนอร์) ที่ทำงานร่วมกันอย่างสนุก ท้ายที่สุด ขอขอบคุณภรรยาของเราทั้งสองคน แจน มิลเลอร์ และเบรนดา ราแนม ที่มอบความรักและความสนับสนุน ทำให้หนังสือเล่มนี้กลายเป็นจริงได้
🎯 วัตถุประสงค์การเรียนรู้
- เข้าใจความสัมพันธ์ระหว่างวิทยาการคอมพิวเตอร์ อัลกอริธึม และการเขียนโปรแกรม พร้อมทั้งเข้าใจแนวคิดเรื่องประเภทข้อมูลที่ถูกนามธรรม (ADT) และการซ่อนข้อมูล (Information Hiding)
- ใช้ประเภทข้อมูลรวมภายในภาษา Python (ลิสต์ ทูเปิล เซต ไดก์ชันนารี) และโครงสร้างควบคุม (การวนซ้ำ การแยกเงื่อนไข การจัดการข้อผิดพลาด) ได้อย่างคล่องแคล่ว
- เข้าใจหลักการสำคัญของการเขียนโปรแกรมแบบวัตถุ (OOP) ของภาษา Python ได้แก่ การกำหนดคลาส การตั้งค่าคอนสตรัคเตอร์ การใช้โอเวอร์โหลดตัวดำเนินการ (เช่น การบวกเศษส่วน) การประยุกต์ใช้อัลกอริธึมยูคลิด และความแตกต่างระหว่างการเทียบเท่าแบบลึกกับแบบตื้น
- วิเคราะห์หลายแนวทางของอัลกอริธึม: สามารถอธิบายแนวทางสี่แบบในการตรวจจับคำที่มีตัวอักษรสลับกัน (การนับจำนวน, การเรียงลำดับ, การลองทุกกรณี, การนับจำนวน) พร้อมทั้งระบุความซับซ้อนตามเวลา (Time Complexity) ที่สัมพันธ์กัน
- วัดประสิทธิภาพของตัวเก็บข้อมูลในภาษา Python: เข้าใจประสิทธิภาพระดับโอใหญ่ (Big O) ของฟังก์ชันหลักในลิสต์ (List) และไดก์ชันนารี (Dict) และสามารถแยกความแตกต่างด้านประสิทธิภาพระหว่าง
pop()กับpop(i)ได้ - ความสามารถในการตรวจสอบประสิทธิภาพ: สามารถออกแบบการทดลองโดยใช้โมดูล
timeitเพื่อยืนยันความสอดคล้องระหว่างความซับซ้อนทางทฤษฎีกับเวลาทำงานจริง - เข้าใจและแยกแยะลักษณะเชิงตรรกะของโครงสร้างข้อมูลแบบเส้นตรง (สแตก คิว ควีว ลิสต์)
- สามารถใช้ประเภทข้อมูลพื้นฐานของภาษา Python (เช่น ลิสต์) สร้างสแตก คิว และควีวที่กำหนดเองได้
- เข้าใจการประยุกต์ใช้สแตกในการจัดการนิพจน์ (แปลงจากแบบปรกติเป็นแบบโพสต์ฟิกซ์ คำนวณผลลัพธ์จากแบบโพสต์ฟิกซ์) และการประยุกต์ใช้คิวในการจำลองระบบ (เช่น การจำลองเครื่องพิมพ์)
- เข้าใจหลักการสามข้อพื้นฐานของอัลกอริธึมแบบเรียกซ้ำ: สามารถระบุและเขียนฟังก์ชันแบบเรียกซ้ำที่มีเงื่อนไขพื้นฐาน สถานะที่เปลี่ยนแปลง และการเรียกตนเองได้อย่างแม่นยำ
บทเรียน 共 8 课时 · 预计 24.0h
บทเรียน
Lesson
This lesson introduces the core principles of computer science, focusing on problem-solving through algorithms, procedural abstraction, and Python’s object-oriented nature. Students will learn to manage complexity by leveraging Python’s dynamic variable references, efficient built-in data structures, and robust error-handling techniques to build reliable, scalable software.
本课程深入探讨了算法分析的核心工具——大O记法，通过异序词检测案例展示了从暴力法到计数法的性能优化过程。学习重点在于理解不同操作（如列表索引与pop操作）的复杂度差异，并掌握如何通过空间换时间及选择合适的数据结构来提升程序效率。
This lesson introduces linear data structures and the concept of Abstract Data Types (ADTs), focusing on the stack as a fundamental LIFO (Last-In, First-Out) structure. Students will learn to implement stacks in Python and apply them to complex tasks, including converting infix expressions to postfix notation and evaluating those expressions efficiently.
本课程深入探讨了递归算法的核心原理，重点讲解了递归三原则（基准情况、状态改变、自我调用）以及递归与系统调用栈之间的内在联系。通过进制转换、汉诺塔及动态规划等案例，学生将学习如何将复杂问题拆解为自相似的子问题，并掌握从递归思维向高效动态规划算法的进阶转换。
This lesson explores fundamental search and retrieval algorithms, progressing from $O(n)$ sequential search to the $O(\log n)$ efficiency of binary search and the $O(1)$ potential of hash tables. Students learn to optimize data access through divide-and-conquer strategies, sophisticated hash function design, and collision-handling techniques to build efficient, dictionary-like data structures.
This lesson explores the hierarchical and recursive nature of tree data structures, covering fundamental terminology, implementation methods like nested lists and object-oriented references, and the construction of expression trees. It also introduces essential tree traversal algorithms—preorder, inorder, and postorder—and explains how these recursive patterns are applied to tasks like file system analysis and AVL tree balancing.
This lesson introduces graph theory as a powerful tool for modeling real-world problems by abstracting entities as vertices and relationships as edges. Students will learn to implement graphs using adjacency lists, compare storage efficiency, and master the Breadth-First Search (BFS) algorithm to solve pathfinding and state-space challenges.
This lesson explores the memory efficiency of Python's ArrayList, explaining how amortized analysis ensures $O(1)$ performance for append operations through strategic over-allocation. It also covers the mathematical foundations of RSA encryption, demonstrating how modular exponentiation and divide-and-conquer algorithms optimize complex calculations for secure data processing.