ศิลปะแห่งการเขียนโปรแกรม “ศิลปะแห่งการเขียนโปรแกรม” - บทวิจารณ์หนังสือชุดในตำนาน
ศิลปะแห่งการเขียนโปรแกรม?
- การเขียนโปรแกรม
ฉันชอบอ่านบทความเกี่ยวกับการเขียนโปรแกรมที่ไม่มีโค้ดแม้แต่บรรทัดเดียว บทความดังกล่าวเหมาะสำหรับการพัฒนา "เชิงลึก" และมักจะให้เหตุผลในการมองสิ่งที่มีมายาวนานจากมุมที่ต่างออกไป ดังนั้น ด้วยความเสี่ยงที่ประชาชนบางส่วนจะโกรธเคืองต่อกรรมที่แคระแกรนอยู่แล้วของฉัน ฉันจึงตัดสินใจตีพิมพ์บทความนี้ ด้วยความหวังว่าบทความนี้จะไม่เพียงให้ความรู้แก่ใครบางคนเท่านั้น แต่ยังช่วยให้มีสติอีกด้วย ดูกิจกรรมของพวกเขาสดๆ
เริ่ม
มันเกิดขึ้นที่สถานที่ทำงานปัจจุบัน โปรแกรมเมอร์ถูกทิ้งให้อยู่กับอุปกรณ์ของตัวเอง แน่นอนว่าพวกเขาเขียนโค้ดเพื่อประโยชน์ขององค์กร แต่ไม่สามารถควบคุมได้อย่างสมบูรณ์จนถึงขั้นไม่มีผู้ทดสอบซ้ำซาก เงื่อนไขการอ้างอิง แม้สำหรับโปรแกรม "หนัก" ก็แทบจะไม่เกินแผ่น A4 สามแผ่น (หนึ่งในนั้นคือลายเซ็นของผู้ที่เกี่ยวข้องทั้งหมด)การโทรเกี่ยวกับปัญหาซอฟต์แวร์จะถูกส่งไปยังโปรแกรมเมอร์โดยตรง นี่คือจุดเริ่มต้นทั้งหมด
ฉันสังเกตเห็นว่าจำนวนการโทรถึงเพื่อนร่วมงานของฉัน (บุคคลที่ทำงานในสาขาพิเศษของเขาและในตำแหน่งนี้นานกว่าฉันหลายปี) นั้นมีลำดับความสำคัญ (โดยไม่มีการพูดเกินจริง) สูงกว่าจำนวนการโทรเกี่ยวกับซอฟต์แวร์ของฉัน . ในขณะเดียวกัน การโทรมักจะ "หนัก" มากกว่า ความชุกและความเข้มของแรงงานของผลิตภัณฑ์ของเราใกล้เคียงกัน
ในกระบวนการสื่อสาร ฉันเริ่มสนใจมุมมองของเพื่อนร่วมงานเกี่ยวกับการเขียนโปรแกรม หลังจากนั้นฉันก็ดูซอร์สโค้ดของบางโปรแกรม และทุกอย่างก็เข้าที่
บทประพันธ์เกี่ยวกับบุคลิกภาพที่สร้างสรรค์
ด้วยเหตุผลส่วนตัวและทางธุรกิจ ฉันสื่อสารกับคนที่สร้างสรรค์ เหล่านี้ส่วนใหญ่เป็นนักดนตรีและศิลปินประเภทต่างๆ ฉันมักจะไปเยี่ยมพวกเขาในสภาพแวดล้อมต่างๆ ตั้งแต่ถิ่นที่อยู่ไปจนถึงร้านค้าและร้านกาแฟที่บ้าน คนประเภทนี้มักจะมีความวุ่นวายและความคิดสร้างสรรค์ ตั้งแต่โซฟาเปื้อนสี ผนังโทรม ไปจนถึงเครื่องใช้ในครัวเรือนและจานชามที่ดูแย่
การกระทำของคนเหล่านี้มีเวกเตอร์ที่แน่นอน แต่พารามิเตอร์ไม่ได้ระบุด้วยตัวเลขทศนิยม แต่ตามทิศทาง "ตะวันตกเฉียงใต้" สิ่งนี้ไม่เพียงแต่ใช้กับการไปที่ร้านเท่านั้น (การซื้อของจากรายการกับคนดังกล่าวนั้นไม่สมจริง) แต่ยังใช้กับทุกสิ่งโดยทั่วไป รวมถึงความคิดสร้างสรรค์ด้วย
เมื่อทำงาน ศิลปิน/นักดนตรีมักจะเริ่มต้นจาก "เวกเตอร์ตะวันตกเฉียงใต้" - จากอารมณ์ แนวคิดบางอย่าง (เกิดภายในหรือออกโดยลูกค้า สิ่งนี้ไม่สำคัญในกรณีนี้) ผลลัพธ์สุดท้าย ในกรณีส่วนใหญ่ ดูเหมือนคลุมเครือมาก ด้วยความเป็นธรรม เราสังเกตว่านี่คือส่วนแบ่งความสุขในการสร้างสรรค์อย่างมหาศาล โดยการทำในสิ่งที่ทำเสร็จแล้ว โดยพื้นฐานแล้ว นี่คือความพยายามที่จะ "แสดงออก"
โปรแกรมเมอร์เชิงสร้างสรรค์
กลับไปที่การสนทนาเกี่ยวกับโปรแกรมเมอร์ ในระหว่างการสนทนา เห็นได้ชัดว่าเพื่อนร่วมงานบางคนพูดตัวเองว่าเป็นตัวแทนของ "อาชีพเชิงสร้างสรรค์" ซึ่งไม่รู้สึกภาคภูมิใจเลย ในเวลาเดียวกัน พวกเขาใช้วิธีการสร้างสรรค์ (“เวกเตอร์ตะวันตกเฉียงใต้”) โดยมีชุดคุณลักษณะที่เกือบจะสมบูรณ์ เป็นผลให้โมดูลของการเชื่อมต่อแปลก ๆ ปรากฏขึ้นคลาสที่มีลำดับชั้น "ที่นี่ฉันจะสร้างตัวเลขเช่นนี้" วิธีการแบ่งออกเป็น "น่าสนใจ" อย่างน่าอัศจรรย์ (ออกแบบมาอย่างดีพร้อมการจัดการข้อผิดพลาดที่ชัดเจน - เช่นการใช้งาน การเข้ารหัสและโปรโตคอลเครือข่าย) และ "ไม่น่าสนใจ" (รายการส่งออกข้อมูลยาวเป็นกิโลเมตร โดยมีการคัดลอกและวางจำนวนมาก)
การจัดการข้อผิดพลาดเสร็จสิ้นตามที่ปรากฏ - ที่นี่เราจะตรวจสอบค่าที่ส่งคืนและในไฟล์ถัดไปเรามีกลไกการจัดการข้อยกเว้น ที่นี่เราใช้พอยน์เตอร์อัจฉริยะ ที่นั่นเราทำงานโดยตรง และอีกหลายอย่างเช่นนั้น
ผลลัพธ์ของงานดังกล่าวคือผลิตภัณฑ์ที่ไม่สามารถคาดเดาพฤติกรรมได้อย่างสมบูรณ์ ปัญหาหลักของนักพัฒนาคนหนึ่งของเราคือการแก้ไขข้อผิดพลาดในเวอร์ชันใหม่ทำให้เกิดข้อผิดพลาดใหม่ในโมดูลที่ดูเหมือนจะดีบั๊กอยู่แล้วและการป้องกันสิ่งนี้โดยไม่ต้องเขียนใหม่ทั้งหมดนั้นไม่สมจริง เป็นเรื่องยากมากที่จะรักษาผลิตภัณฑ์ดังกล่าว - การปรับแต่งประเด็นพื้นฐานที่สุดต้องใช้สมาธิในระยะยาวกับโค้ดเพื่อพยายามทำความเข้าใจวิธีการทำเพื่อให้ทุกอย่างไม่ล่มสลายและโดยเฉพาะอย่างยิ่งโดยไม่ต้องคัดลอกวาง "ความคิดสร้างสรรค์ที่มีอยู่" ".
คุณธรรมของเรื่องนี้
การเขียนโปรแกรมไม่ใช่การแสดงออกถึงตัวตน ไม่ว่ารุ่นน้องที่มีความคิดโรแมนติกจะอ้างอะไรก็ตาม รหัสที่ดีคือเอกสารที่ได้รับการออกแบบอย่างชัดเจนและเป็นไปตามกฎเกณฑ์บางประการ ถึงแม้จะเป็นเรื่องน่าเศร้าสำหรับบางคน โปรแกรมเมอร์ก็คือหุ่นยนต์ซึ่งขึ้นอยู่กับคุณภาพของคำสั่งที่ใส่เข้าไป ด้วยประสิทธิภาพที่แตกต่างกัน จะอธิบายให้หุ่นยนต์อีกตัวหนึ่งทราบว่ามวลโปรตีนเหล่านี้ต้องการจากเขาอย่างไร ไม่มีที่สำหรับความคิดสร้างสรรค์ในการเขียนโปรแกรม - ตั้งแต่การตั้งชื่อไฟล์และตัวแปรไปจนถึงรูปแบบ ทุกอย่างอยู่ภายใต้ตรรกะที่ชัดเจนและมีประสิทธิภาพสูงสุด ด้วยเหตุนี้โปรแกรมเมอร์จึงไม่เพียงได้รับเงินจากนายจ้างเท่านั้น แต่ยังได้รับความอุ่นใจเมื่อดูแลรักษาผลิตภัณฑ์และความรู้สึกควบคุมสถานการณ์ในกรณีที่เกิดปัญหากับโปรแกรมด้วยแม้ว่าโปรแกรมเมอร์จะไม่ได้รับข้อกำหนดทางเทคนิคที่เขียนไว้อย่างดี แต่เขาก็ต้องทำความเข้าใจให้ชัดเจนถึงสิ่งที่จะเกิดขึ้นในที่สุด หากมีความเป็นไปได้ที่สิ่งที่เขียนจะต้องได้รับการแก้ไขอย่างลึกซึ้งยิ่งดียิ่งขึ้น - งานเขียนซอฟต์แวร์ที่มีความเป็นไปได้ที่จะมีการปรับเปลี่ยนอย่างมากนั้นน่าตื่นเต้นมากและไม่ง่ายเลย
โดยสรุปแล้ว วลีของ Steve McConnell - “เขียนโค้ดราวกับว่ามันจะมาพร้อมกับคนโรคจิตหัวรุนแรงที่รู้ว่าคุณอาศัยอยู่ที่ไหน” และคนโรคจิตอาจจะโกรธมากถ้าเขาหัวแตกเพราะขาดตรรกะและความเป็นระเบียบ
มีหนังสือหลายเล่มเกี่ยวกับตลาดวรรณกรรมคอมพิวเตอร์ทั่วโลกที่ออกแบบมาเพื่อสอนอัลกอริธึมพื้นฐานและใช้ในการเขียนโปรแกรม มีค่อนข้างเยอะและส่วนใหญ่ก็แข่งขันกันเอง อย่างไรก็ตามในหมู่พวกเขามีหนังสือพิเศษเล่มหนึ่ง นี่คือ "ศิลปะแห่งการเขียนโปรแกรม" สามเล่มโดย D. E. Knuth ซึ่งโดดเด่นเหนือคู่แข่งใดๆ รวมอยู่ในกองทุนทองคำของวรรณกรรมโลกเกี่ยวกับวิทยาการคอมพิวเตอร์และเป็นหนังสืออ้างอิงสำหรับเกือบทุกคนที่เกี่ยวข้องกับการเขียนโปรแกรม
ในฐานะผู้จัดพิมพ์ เรามองเห็นคุณค่าของหนังสือเล่มนี้ตรงที่หนังสือเล่มนี้ไม่ได้มีจุดประสงค์เพื่อสอนเทคนิคการเขียนโปรแกรมมากนัก แต่หากเป็นไปได้ แทนที่จะสอน "ศิลปะ" ของการเขียนโปรแกรม จึงมีสูตรมากมายสำหรับการปรับปรุงโปรแกรมและ ที่สำคัญที่สุดคือสอนวิธีค้นหาสูตรอาหารเหล่านี้ด้วยตัวเอง
ไม่เป็นความลับเลยที่โปรแกรมเมอร์ของเราเป็นหนึ่งในผู้เชี่ยวชาญที่มีคุณสมบัติสูงที่สุดในโลก พวกเขาเป็นตัวแทนของโรงเรียนการเขียนโปรแกรมและวิทยาการคอมพิวเตอร์ในประเทศอย่างมีค่าควรซึ่งมีส่วนสำคัญในการสร้างรากฐานพื้นฐานของวิทยาการคอมพิวเตอร์ เพื่อรักษาระดับนี้และก้าวไปข้างหน้าจำเป็นต้องจัดพิมพ์หนังสือเป็นภาษารัสเซียให้ทันเวลาซึ่งสะท้อนถึงความสำเร็จระดับโลกในสาขานี้ หนังสือสามเล่มเรื่อง “The Art of Programming” โดย D. E. Knuth เป็นหนังสือเล่มหนึ่ง
เราภูมิใจที่หนังสือคลาสสิกเล่มนี้จะถูกเพิ่มเข้าไปในห้องสมุดของโปรแกรมเมอร์ ครู นักเรียน นักเรียนมัธยมปลาย และอื่นๆ อีกมากมาย และการทำเช่นนี้เราจะมีส่วนช่วยให้มีความเข้าใจที่ลึกซึ้งยิ่งขึ้นเกี่ยวกับพื้นฐานของวิทยาการคอมพิวเตอร์ เราเชื่อมั่นอย่างลึกซึ้งว่าหนังสือ “The Art of Programming” ของ D. E. Knuth สามารถพาบุคคลเข้าใกล้ความสมบูรณ์แบบได้ เราหวังว่าการตีพิมพ์หนังสือที่ยอดเยี่ยมนี้เป็นภาษารัสเซียจะยืนยันอีกครั้งว่าคุณค่าที่แท้จริงไม่ล้าสมัยในช่วงหลายปีที่ผ่านมา
- Victor Shtonda, Gennady Petrikovets, Alexey Orlovich ผู้จัดพิมพ์
เกี่ยวกับหนังสือ "ศิลปะแห่งการเขียนโปรแกรม"
หนังสือแต่ละเล่มมีชะตากรรมของตัวเอง บางส่วนดูเหมือนไม่มีใครสังเกตเห็นและหายไปตามกระแสเวลาจนแทบมองไม่เห็น และถูกปกคลุมไปด้วยฝุ่นบนชั้นวางของห้องสมุด คนอื่น ๆ เป็นที่ต้องการในช่วงระยะเวลาหนึ่งในหมู่ผู้เชี่ยวชาญในวงแคบ ๆ จนกว่าพวกเขาจะถูกแทนที่ด้วยหนังสืออ้างอิงใหม่ ส่วนคนอื่นๆ ที่อยู่เหนือกาลเวลา มีอิทธิพลอย่างมากต่อการพัฒนาทางเทคโนโลยีของสังคม มีหนังสือไม่มากนักที่อยู่ในประเภทหลัง การปรากฏตัวของพวกเขาในโลกนี้ถือเป็นวันหยุดเสมอ หลายปีผ่านไป เทคโนโลยีเปลี่ยนไป แต่คนรุ่นใหม่อ่านซ้ำหน้าต่างๆ ด้วยความสนใจอย่างต่อเนื่อง หนังสือเหล่านี้รวมเอางานหลายเล่มที่เสนอให้กับผู้อ่านโดยนักวิทยาศาสตร์ชาวอเมริกันชื่อดังอย่าง Donald Erwin Knuth เรื่อง “The Art of Programming”
เกือบ 30 ปีผ่านไปนับตั้งแต่หนังสือเล่มนี้ตีพิมพ์ครั้งแรกในปี 1972 ในสหรัฐอเมริกา ได้รับการแปลเป็นภาษาส่วนใหญ่ของโลก รวมถึงภาษารัสเซียด้วย จนถึงปัจจุบัน ในประเทศ CIS งานสามเล่มของ D. E. Knuth ได้กลายเป็นสิ่งที่หายากในบรรณานุกรม ในปี 1998 “The Art of Programming” ฉบับที่สามได้รับการตีพิมพ์ในสหรัฐอเมริกา โดยยังคงรักษาลำดับการนำเสนอเนื้อหาในเวอร์ชันก่อนหน้า แต่รายการข้อมูลอ้างอิงได้รับการขยายอย่างมีนัยสำคัญ ซึ่งรวมถึงผลลัพธ์ล่าสุดและสำคัญที่สุด มีการเพิ่มแบบฝึกหัดและความคิดเห็นใหม่ และกำจัดความไม่ถูกต้องออกไป เมื่อพิจารณาถึงความนิยมของ "ศิลปะแห่งการเขียนโปรแกรม" ทั่วโลก เราควรคาดหวังมานานแล้วว่าจะมีฉบับแปลใหม่ในภาษารัสเซียซึ่งคุณกำลังถืออยู่ในมือ
ความสำเร็จของ "The Art of Programming" ของ D.E. Knuth คืออะไร?
ประการแรก หนังสือเล่มนี้เป็นตำราเรียนที่ยอดเยี่ยมเกี่ยวกับการออกแบบและการวิเคราะห์อัลกอริธึมคอมพิวเตอร์ หัวข้อต่างๆ สามารถรวมอยู่ในหลักสูตรของมหาวิทยาลัยหลายหลักสูตรเกี่ยวกับเทคโนโลยีการเขียนโปรแกรม ทฤษฎีอัลกอริทึม และคณิตศาสตร์แยกส่วน นักเรียนมัธยมปลายที่คุ้นเคยกับพื้นฐานของการเขียนโปรแกรมสามารถอ่านหนังสือนี้ได้ ผู้เขียนเลือกภาษาคำสั่งเครื่องของคอมพิวเตอร์สากล MIX สมมุติเป็นภาษาหลักสำหรับอัลกอริธึมการบันทึก สิ่งนี้ช่วยให้คุณสร้างโปรแกรมที่เหมาะสมที่สุดโดยคำนึงถึงลักษณะของคอมพิวเตอร์ การถ่ายโอนโปรแกรม MIX ไปยังคอมพิวเตอร์จริงหรือเขียนใหม่เป็นภาษาระดับสูงนั้นไม่ใช่เรื่องยากโดยเฉพาะ ตรรกะของโปรแกรมมักอธิบายโดยใช้บล็อกไดอะแกรมอย่างง่ายเกือบทุกครั้ง
ประการที่สอง เนื้อหาที่คัดสรรมาอย่างดีซึ่งรวมอยู่ในหนังสือเล่มนี้ประกอบด้วยคลาสพื้นฐานหลักของอัลกอริธึม ซึ่งมักพบในรูปแบบใดรูปแบบหนึ่งในการฝึกฝนการเขียนโปรแกรม
ประการที่สาม ปัจจัยสำคัญในความสำเร็จของหนังสือของ D.E. Knuth คือลักษณะของการนำเสนอที่เป็นสารานุกรม ศาสตราจารย์คนุธมีความสามารถพิเศษในการติดตามปัญหาตั้งแต่ภูมิหลังทางประวัติศาสตร์ไปจนถึงสถานะปัจจุบัน การอ้างอิงถึงผลงานของปรมาจารย์ผู้เฒ่าจำนวนมาก (จนถึงสมัยโบราณ) ซึ่งวางไว้ในบริบทสมัยใหม่ทำให้ผู้อ่านรู้สึกถึงการมีส่วนร่วมเป็นพิเศษในการพัฒนาทางประวัติศาสตร์ของแนวคิดและวิธีการทางวิทยาศาสตร์
ประการที่สี่ ควรสังเกตทักษะการนำเสนอ หนังสือเล่มนี้มีไว้สำหรับผู้อ่านที่หลากหลาย ตั้งแต่นักเรียนระดับเริ่มต้นไปจนถึงโปรแกรมเมอร์มืออาชีพ ทุกคนจะสนใจเรียนรู้อัลกอริธึมคอมพิวเตอร์ในระดับของตนเอง วัสดุเป็นแบบพอเพียง การทำความเข้าใจสาระสำคัญของวิธีการไม่จำเป็นต้องมีความรู้ในสาขาพิเศษของคณิตศาสตร์หรือเทคโนโลยีการเขียนโปรแกรมพิเศษ สามารถตรวจสอบองค์ประกอบ "ดนตรี" บางอย่างของโครงสร้างพล็อตได้ (D. E. Knuth มีอวัยวะเล็ก ๆ ที่บ้านที่เขาเล่น)
รายการองค์ประกอบแห่งความสำเร็จใน The Art of Programming สามารถดำเนินต่อไปได้อย่างง่ายดาย
ผู้เขียนหัวข้อเหล่านี้เข้าเรียนหลักสูตร "ศิลปะแห่งการเขียนโปรแกรม" ซึ่งนำเสนอโดยศาสตราจารย์ Knuth ในปี 1976-1977 ระหว่างฝึกงานที่มหาวิทยาลัยสแตนฟอร์ด จากนั้นจึงสร้างพื้นฐานอัลกอริธึมของเทคโนโลยีการเขียนโปรแกรมโดยมีต้นกำเนิดคือ D. E. Knuth มีเสวนา สัมมนา และไอเดียสร้างสรรค์มากมาย
หนังสือสำคัญมักเชื่อมโยงกับชะตากรรมของผู้แต่งเสมอ Donald Erwin Knuth เริ่มทำงานเกี่ยวกับ The Art of Programming ในปี 1962 มันยังคงดำเนินต่อไปจนถึงทุกวันนี้ เขามีแผนมากมาย “The Art of Programming” เล่มใหม่รออยู่ข้างหน้า ซึ่งผู้อ่านต่างรอคอยอย่างใจจดใจจ่อ
- ศาสตราจารย์อนาโตลี อานิซิมอฟ
จากบรรณาธิการแปล
เวลาผ่านไปประมาณ 25 ปีนับตั้งแต่หนังสือ “The Art of Programming” ตีพิมพ์ครั้งแรกของ D. E. Knuth อย่างไรก็ตาม หนังสือเล่มนี้ไม่เพียงไม่ล้าสมัยเท่านั้น แต่ยังคงเป็นแนวทางหลักเกี่ยวกับศิลปะการเขียนโปรแกรม ซึ่งเป็นหนังสือที่ให้คุณเรียนรู้ที่จะเข้าใจแก่นแท้และคุณลักษณะของศิลปะนี้
ในช่วงหลายปีที่ผ่านมา เล่มที่ 1 และ 2 ฉบับที่สาม รวมถึงเล่มที่ 3 ฉบับที่สอง ได้รับการตีพิมพ์เป็นภาษาอังกฤษ ผู้เขียนได้ทำการเปลี่ยนแปลงที่สำคัญและเพิ่มเติมที่สำคัญ พอจะกล่าวได้ว่าจำนวนแบบฝึกหัดเพิ่มขึ้นเกือบสองเท่า และแบบฝึกหัดจำนวนมากที่รวมอยู่ในฉบับก่อน ๆ (โดยเฉพาะคำตอบ) ได้รับการแก้ไขแล้ว บทและส่วนต่างๆ ได้รับการเสริมและทำซ้ำอย่างมีนัยสำคัญ มีการแก้ไขความไม่ถูกต้องและการพิมพ์ผิด มีการเพิ่มการอ้างอิงใหม่จำนวนมากเกี่ยวกับวรรณกรรม และใช้ผลลัพธ์ทางทฤษฎีในช่วงไม่กี่ปีที่ผ่านมา
บทที่ 3 มีการเปลี่ยนแปลงอย่างมีนัยสำคัญ โดยเฉพาะส่วนที่ 3.5 และ 3.6 รวมถึงส่วนที่ 4.5.2, 4.7, 5.1.4, 5.3, 5.4.9, 6.2.2, 6.4, 6.5 เป็นต้น
โดยปกติแล้วความต้องการหนังสือเล่มนี้เกิดขึ้นใหม่
การแปลอิงตามฉบับพิมพ์ครั้งที่ 3 ของเล่มที่ 1 และ 2 และฉบับที่สองของเล่มที่ 3 นอกจากนี้ ยังได้คำนึงถึงการเพิ่มเติมและการแก้ไขโดยผู้เขียนด้วย
เมื่อแปล เราพยายามรักษาสไตล์ สัญกรณ์ และวิธีการนำเสนอของผู้เขียนไว้ ในกรณีส่วนใหญ่ มีการใช้คำศัพท์ที่นำมาใช้ในวรรณกรรมทางวิทยาศาสตร์ในภาษารัสเซีย มีการจัดเตรียมภาษาอังกฤษที่เทียบเท่าไว้ในกรณีที่จำเป็น ด้วยเหตุผลหลายประการ โดยเฉพาะอย่างยิ่งความซับซ้อนของบางส่วน The Art of Programming จึงเป็นหนังสือที่อ่านยาก สิ่งหนึ่งที่ทำให้หนังสือเล่มนี้เข้าใจยากคือรูปแบบการนำเสนอของผู้เขียน เมื่อคุณคุ้นเคยแล้ว คุณจะอ่านง่ายขึ้นมาก
เนื่องจากมีเนื้อหามากมาย (มักเชื่อมโยงกันเพียงเล็กน้อย) จึงเป็นไปไม่ได้ที่จะจัดโครงสร้างหนังสือในลักษณะที่แนวคิดและคำจำกัดความต่างๆ ได้รับการแนะนำทันทีเมื่อมีการกล่าวถึงครั้งแรก ดังนั้นบทที่ 1 อาจอภิปรายโดยไม่มีแนวคิดอ้างอิงซึ่งมีคำจำกัดความที่เข้มงวดระบุไว้ในเล่มที่ 3 นั่นคือเหตุผลที่บทบาทของดัชนีหัวเรื่องมีความสำคัญมาก หากไม่เข้าใจหนังสือก็จะเป็นเรื่องยากมาก เราหวังว่าผู้อ่านจะไม่แปลกใจที่พบการอ้างอิงถึงบทที่ 7, 8 และบทต่อๆ ไปที่ไม่รวมอยู่ในสามเล่มที่เสนอของบทนี้ เราร่วมกับผู้เขียนหวังว่าพวกเขาจะตีพิมพ์ในเร็ว ๆ นี้และแน่นอนว่าจะปรากฏเป็นภาษารัสเซียทันทีซึ่งเป็นความต่อเนื่องของสิ่งพิมพ์นี้
คุณควรใส่ใจกับสัญกรณ์มาตรฐานที่ผู้เขียนใช้ไม่เสมอไป เช่นเดียวกับคำจำกัดความ การกำหนดเหล่านี้อาจปรากฏในเล่มที่ 1 และนำมาใช้ในเล่มที่ 2 ดังนั้นหากไม่มีดัชนีสัญลักษณ์จึงเป็นเรื่องยากมากที่จะใช้หนังสือ ฉันอยากจะดึงความสนใจไปที่รายการ [A] โดยที่ A คือข้อความบางอย่าง รายการนี้พบได้ในสูตร และบางครั้งก็อยู่ในข้อความ และแสดงถึงค่าที่เท่ากับตัวบ่งชี้ A
- ศาสตราจารย์ Yu.V. Kozachenko
คำนำ
เรียนผู้อ่าน! คุณกำลังถือหนังสืออยู่ในมือ
เพื่อเผยแพร่ที่คุณถามเราเป็นพัน ๆ ฉบับ เราต้องใช้เวลาหลายปีในการตรวจสอบอย่างรอบคอบและตรวจสอบสูตรอาหารจำนวนนับไม่ถ้วนและเลือกสูตรที่ดีที่สุด น่าสนใจที่สุด และสมบูรณ์แบบที่สุดสำหรับคุณ
ไม่ต้องสงสัยเลยว่าหากคุณทำตามคำแนะนำ อาหารทุกจานก็จะออกมาเหมือนเดิมสำหรับคุณ แม้ว่าคุณจะไม่เคยทำอาหารมาก่อนก็ตาม
- ตำราอาหารของ McCall (1963)
กระบวนการเตรียมโปรแกรมสำหรับคอมพิวเตอร์ดิจิทัลถือเป็นกิจกรรมที่น่าตื่นเต้นมาก และประเด็นไม่ใช่แค่ว่ามันพิสูจน์ตัวเองจากมุมมองทางเศรษฐกิจและวิทยาศาสตร์เท่านั้น นอกจากนี้ยังสามารถทำให้เกิดประสบการณ์ด้านสุนทรียภาพที่คล้ายคลึงกับประสบการณ์ของบุคคลที่สร้างสรรค์เมื่อเขียนเพลงหรือบทกวี คุณกำลังถือหนังสือเล่มแรกของสิ่งพิมพ์หลายเล่มในมือโดยมีวัตถุประสงค์เพื่อให้ผู้อ่านมีความรู้และทักษะที่หลากหลายซึ่งประกอบขึ้นเป็นฝีมือของโปรแกรมเมอร์
บทต่อไปนี้ไม่ใช่บทนำเกี่ยวกับการเขียนโปรแกรมคอมพิวเตอร์ ถือว่าคุณมีประสบการณ์ในด้านนี้มาบ้างแล้ว ในความเป็นจริงข้อกำหนดสำหรับผู้อ่านนั้นง่ายมาก อย่างไรก็ตาม โปรแกรมเมอร์มือใหม่อาจต้องใช้เวลาและการฝึกฝนเพื่อทำความเข้าใจว่าคอมพิวเตอร์ดิจิทัลคืออะไร ดังนั้นผู้อ่านควรมี:
ก) ความเข้าใจบางประการเกี่ยวกับวิธีการทำงานของคอมพิวเตอร์โปรแกรมจัดเก็บดิจิทัล ในกรณีนี้ไม่จำเป็นต้องเข้าใจอุปกรณ์อิเล็กทรอนิกส์สิ่งสำคัญคือต้องเข้าใจว่าคำสั่งสามารถเก็บไว้ในหน่วยความจำคอมพิวเตอร์ได้อย่างไรแล้วดำเนินการตามลำดับ
b) ความสามารถในการระบุปัญหาด้วยเงื่อนไขที่ชัดเจนและกำหนดไว้ซึ่งคอมพิวเตอร์สามารถเข้าใจได้ (คอมพิวเตอร์ไม่มีสติปัญญาของมนุษย์ ดังนั้นพวกเขาจึงทำสิ่งที่พวกเขาบอกให้ทำอย่างแน่นอน ไม่มากไปไม่น้อย นี่เป็นข้อเท็จจริงที่ยากที่สุดสำหรับ ผู้ใช้มือใหม่ที่จะเข้าใจ) ;
c) ความรู้เกี่ยวกับเทคนิคคอมพิวเตอร์ที่ง่ายที่สุด เช่น การวนซ้ำ (การดำเนินการซ้ำของชุดคำสั่งบางชุด) รวมถึงการใช้รูทีนย่อยและตัวแปรที่จัดทำดัชนี
d) ความรู้เกี่ยวกับคำศัพท์คอมพิวเตอร์ทั่วไป เช่น "หน่วยความจำ" "รีจิสเตอร์" "บิต" "จุดลอยตัว" "ล้น" "ซอฟต์แวร์" คำศัพท์ส่วนใหญ่ที่ไม่ได้กำหนดไว้ในข้อความจะมีการอธิบายไว้ในดัชนีที่ส่วนท้ายของแต่ละเล่ม
เงื่อนไขทั้งสี่นี้อาจรวมกันเป็นข้อกำหนดเดียวได้: ผู้อ่านจะต้องมีประสบการณ์ในการเขียนและแก้ไขข้อบกพร่องอย่างน้อยสี่โปรแกรมสำหรับคอมพิวเตอร์อย่างน้อยหนึ่งเครื่อง
ฉันได้พยายามเขียนหนังสือเหล่านี้ในลักษณะที่สามารถตอบสนองวัตถุประสงค์ที่แตกต่างกันหลายประการ ประการแรกเป็นคู่มืออ้างอิงที่รวบรวมความรู้จากวิทยาศาสตร์ที่สำคัญหลายสาขา ประการที่สอง สามารถใช้เป็นสื่อช่วยในการศึกษาด้วยตนเองและตำราเรียนเกี่ยวกับการเขียนโปรแกรมหรือวิทยาการคอมพิวเตอร์สำหรับมหาวิทยาลัย ในเรื่องนี้ ฉันได้รวมแบบฝึกหัดจำนวนมากไว้ในข้อความและให้คำตอบส่วนใหญ่ นอกจากนี้ ฉันพยายามเน้นไปที่ข้อเท็จจริง แทนที่จะ "เทน้ำ" และพยายามใช้เหตุผลทั่วไป
เล่มที่สามนี้มีไว้สำหรับผู้ที่สนใจคอมพิวเตอร์อย่างจริงจัง ไม่ใช่แค่มืออาชีพ อันที่จริง หนึ่งในเป้าหมายหลักของฉันคือการทำให้ผู้คนในสาขาอื่นเข้าถึงเทคนิคการเขียนโปรแกรมได้มากขึ้น โดยทั่วไปแล้ว ผู้เชี่ยวชาญเหล่านี้จะได้รับประโยชน์มากมายจากการใช้คอมพิวเตอร์ แต่ไม่สามารถเสียเวลาค้นหาข้อมูลที่จำเป็นได้ ซึ่งข้อมูลบางส่วนกระจัดกระจายอยู่ในวารสารด้านเทคนิคจำนวนมาก
หัวข้อของหนังสือเหล่านี้สามารถกำหนดได้ดังนี้: “การวิเคราะห์ที่ไม่ใช่เชิงตัวเลข” คอมพิวเตอร์มักเกี่ยวข้องกับการแก้ปัญหาเชิงตัวเลข เช่น การหารากของสมการ การประมาณค่าเชิงตัวเลข การอินทิเกรต เป็นต้น แต่ในหนังสือสามเล่มนี้ไม่ได้กล่าวถึงหัวข้อดังกล่าว (ยกเว้นเมื่อจำเป็นต้องทำในรายวิชา) ของการนำเสนอ) การเขียนโปรแกรมคอมพิวเตอร์เชิงตัวเลขเป็นสาขาที่น่าสนใจอย่างยิ่งและมีการพัฒนาอย่างรวดเร็ว
มีการเขียนหนังสือดีๆ มากมายในหัวข้อนี้ แต่ตั้งแต่ทศวรรษ 1960 เป็นต้นมา คอมพิวเตอร์ถูกนำมาใช้มากขึ้นในการแก้ปัญหา โดยตัวเลขมีบทบาทรอง ความสามารถของคอมพิวเตอร์ในการตัดสินใจมากกว่าเพียงดำเนินการทางคณิตศาสตร์มาถึงจุดนี้แล้ว เมื่อแก้ปัญหาที่ไม่ใช่ตัวเลข บางครั้งจำเป็นต้องบวกและลบ แต่แทบไม่ต้องคูณและหารเลย แต่แน่นอนว่า แม้แต่ผู้ที่เกี่ยวข้องกับการเขียนโปรแกรมคอมพิวเตอร์เชิงตัวเลขเป็นหลักก็ยังได้ประโยชน์จากการเรียนรู้วิธีที่ไม่ใช่ตัวเลข เนื่องจากสิ่งเหล่านี้เป็นพื้นฐานของโปรแกรมตัวเลขด้วย
ผลการวิจัยในสาขาการวิเคราะห์ที่ไม่ใช่เชิงตัวเลขกระจัดกระจายอยู่ในวารสารด้านเทคนิคจำนวนมาก เป้าหมายของฉันคือการดึงข้อมูลจำนวนมหาศาลออกมาเฉพาะเทคนิคพื้นฐานที่สามารถนำไปใช้กับสถานการณ์การเขียนโปรแกรมที่หลากหลาย ข้าพเจ้าได้พยายามสรุปข้อมูลที่เลือกมาเพื่อให้ถึงสิ่งที่เรียกได้ว่าเป็น "ทฤษฎี" ไม่มากก็น้อย และเพื่อแสดงให้เห็นว่าจะนำทฤษฎีนี้ไปประยุกต์ใช้กับปัญหาเชิงปฏิบัติต่างๆ ได้อย่างไร
แน่นอนว่า “การวิเคราะห์ที่ไม่ใช่เชิงตัวเลข” เป็นชื่อที่โชคร้ายอย่างยิ่งสำหรับสาขาวิทยาศาสตร์นี้ มันไม่ประสบความสำเร็จในเบื้องต้นเพราะมันมีเพียงการปฏิเสธแนวคิดอื่นเท่านั้น จะดีกว่ามากหากเลือกคำที่มีความหมายมากกว่าซึ่งไม่มีคำนำหน้าว่า "ไม่" ชื่อ "การประมวลผลข้อมูล" ครอบคลุมพื้นที่กว้างกว่าเนื้อหาที่กล่าวถึงที่นี่ และ "วิธีการเขียนโปรแกรม" ครอบคลุมพื้นที่ที่แคบกว่า ฉันเชื่อว่าสำหรับหัวข้อที่กล่าวถึงในหนังสือเหล่านี้ ชื่อที่เหมาะสมที่สุดคือการวิเคราะห์อัลกอริธึม ซึ่งสามารถถอดรหัสได้ว่าเป็น “ทฤษฎีคุณสมบัติของอัลกอริธึมคอมพิวเตอร์บางอย่าง”
หนังสือทั้งชุดชื่อ The Art of Programming มีโครงสร้างพื้นฐานดังนี้
เล่มที่ 1 อัลกอริทึมพื้นฐาน
บทที่ 1 แนวคิดพื้นฐาน บทที่ 2 โครงสร้างข้อมูล
เล่มที่ 2 อัลกอริธึมที่ได้รับ
บทที่ 3 ตัวเลขสุ่ม บทที่ 4 เลขคณิต
เล่มที่ 3 การเรียงลำดับและการค้นหา
บทที่ 5 การเรียงลำดับ บทที่ 6 การค้นหา
เล่มที่ 4 อัลกอริธึมเชิงผสม
บทที่ 7 การค้นหาแบบผสมผสาน บทที่ 8 การเรียกซ้ำ
เล่มที่ 5 อัลกอริธึมทางวากยสัมพันธ์
บทที่ 9. การค้นหาพจนานุกรม บทที่ 10. การแยกวิเคราะห์
เล่ม 4 ครอบคลุมหัวข้อที่ใหญ่มาก ดังนั้นจริงๆ แล้วจึงประกอบด้วยหนังสือสามเล่มแยกกัน (เล่ม 4A, 4B และ 4C) นอกจากนี้ยังมีการวางแผนเล่มเพิ่มเติมอีกสองเล่มในหัวข้อเฉพาะทางอีกด้วย: เล่มที่ 6 ทฤษฎีภาษา (บทที่ 11) และเล่มที่ 7 คอมไพเลอร์ (บทที่ 12)
ฉันเริ่มงานนี้ในปี 1962 ด้วยความตั้งใจที่จะเขียนหนังสือเล่มเดียวที่มีบททั้งหมดที่ระบุไว้ แต่ในไม่ช้าฉันก็ตระหนักว่าจำเป็นต้องพิจารณาหัวข้อที่เลือกในเชิงลึก ไม่ใช่แค่อ่านคร่าวๆ ผลที่ได้คือข้อความที่มีความยาวมากจนมีเนื้อหาในแต่ละบทมากเกินพอที่จะศึกษาในช่วงภาคการศึกษาหนึ่งของมหาวิทยาลัย และเห็นได้ชัดว่าจำเป็นต้องแบ่งเนื้อหาออกเป็นหลายเล่มแยกกัน ฉันรู้ว่าหนังสือที่มีเพียงหนึ่งหรือสองบทดูค่อนข้างแปลก แต่ฉันตัดสินใจที่จะคงหมายเลขบทเดิมไว้เพื่อให้การอ้างอิงโยงง่ายขึ้น ฉบับย่อของเล่ม 1-5 ได้รับการวางแผนที่จะใช้เป็นข้อมูลอ้างอิงและ/หรือหนังสือเรียนทั่วไปสำหรับนักเรียน โดยจะมีเนื้อหาจำนวนมากในเล่มเหล่านี้ และจะละเว้นข้อมูลพิเศษเพิ่มเติม ฉบับย่อจะยังคงใช้หมายเลขบทเดียวกันกับฉบับเต็ม
เล่มที่ 1 ถือได้ว่าเป็น "การครอสโอเวอร์" ของบททั้งชุด ในแง่ที่ว่ามันประกอบด้วยข้อมูลพื้นฐานที่ใช้ในหนังสือเล่มอื่นๆ ทั้งหมด ในทางกลับกัน เล่ม 2-5 สามารถอ่านแยกกันได้ เล่มที่ 1 ไม่เพียงแต่เป็นหนังสืออ้างอิงเพื่อใช้เป็นแนวทางในการอ่านเล่มอื่นเท่านั้น นอกจากนี้ยังสามารถใช้เป็นตำราเรียนของมหาวิทยาลัยหรือคู่มือการศึกษาด้วยตนเองในหัวข้อโครงสร้างข้อมูล (เน้นบทที่ 2) หรือคณิตศาสตร์แยก (เน้นหัวข้อ 1.1, 1.2, 1.3.3 และ 2.3.4) หรือการเขียนโปรแกรมภาษาคำสั่งเครื่อง (เน้นที่หัวข้อ 1.3 และ 1.4)
บทเหล่านี้เขียนจากมุมมองที่แตกต่างจากหนังสือเขียนโปรแกรมสมัยใหม่ส่วนใหญ่ นั่นคือฉันไม่ได้พยายามสอนผู้อ่านถึงวิธีใช้ซอฟต์แวร์ของคนอื่น แต่ฉันมุ่งหวังที่จะสอนผู้อ่านถึงวิธีการเขียนโปรแกรมคุณภาพสูงของตนเอง
เป้าหมายเริ่มแรกของฉันคือการแนะนำให้ผู้อ่านได้รู้จักกับการวิจัยทางวิทยาศาสตร์ที่ล้ำหน้าในแต่ละความรู้ที่ครอบคลุม แต่เป็นเรื่องยากมากที่จะตามทันอุตสาหกรรมที่สร้างผลกำไรเชิงเศรษฐกิจได้ การเติบโตอย่างรวดเร็วของวิทยาการคอมพิวเตอร์ทำให้ฉันไม่สามารถทำตามความฝันได้ หากพูดโดยนัย ฉันพบว่าตัวเองอยู่บนชายฝั่งมหาสมุทรอันกว้างใหญ่ซึ่งเต็มไปด้วยผลลัพธ์เล็กๆ น้อยๆ นับหมื่นที่ได้รับจากผู้มีความสามารถหลายหมื่นคนทั่วโลก ดังนั้นฉันจึงต้องตั้งเป้าหมายใหม่ให้กับตัวเอง - มุ่งเน้นไปที่วิธีการ "คลาสสิก" ที่จะยังคงมีความเกี่ยวข้องมานานหลายทศวรรษ และอธิบายวิธีเหล่านี้ให้ดีที่สุดเท่าที่จะทำได้อย่างสุดความสามารถ โดยเฉพาะอย่างยิ่งฉันได้พยายามติดตามประวัติของแต่ละหัวข้อและวางรากฐานที่มั่นคงสำหรับการพัฒนาต่อไป ฉันพยายามใช้คำศัพท์ที่แม่นยำซึ่งสอดคล้องกับที่ใช้ในสิ่งพิมพ์ร่วมสมัย และพยายามรายงานแนวคิดการเขียนโปรแกรมตามลำดับที่รู้จักทั้งหมด ซึ่งโดดเด่นด้วยความเรียบง่ายและสง่างามของการกำหนดสูตร
ตอนนี้มีคำไม่กี่คำเกี่ยวกับเนื้อหาทางคณิตศาสตร์ของสิ่งพิมพ์หลายเล่มนี้ เนื้อหานี้นำเสนอในลักษณะที่สามารถเข้าถึงได้แม้แต่กับบุคคลที่มีการศึกษาระดับมัธยมศึกษา พวกเขาจะสามารถอ่านส่วนที่ซับซ้อนมากขึ้นหรือข้ามไปก็ได้ ในเวลาเดียวกัน ผู้ที่มีความโน้มเอียงทางคณิตศาสตร์จะสามารถเรียนรู้เทคนิคทางคณิตศาสตร์ที่น่าสนใจที่เกี่ยวข้องกับคณิตศาสตร์แยกส่วนได้ ความเป็นคู่ในการนำเสนอข้อมูลนี้บรรลุผลสำเร็จในอีกด้านหนึ่งโดยการกำหนดคะแนนให้กับแบบฝึกหัดแต่ละข้อ (เพื่อให้ผู้อ่านสามารถแยกแยะแบบฝึกหัดที่ซับซ้อนทางคณิตศาสตร์จากแบบง่าย ๆ ได้) และในทางกลับกันด้วยการจัดระเบียบส่วนต่าง ๆ ดังกล่าว โดยผลลัพธ์ทางคณิตศาสตร์หลักจะถูกกำหนดก่อนการพิสูจน์ เสนอให้ดำเนินการพิสูจน์ด้วยตนเองเป็นแบบฝึกหัด (คำตอบที่ให้ไว้ในส่วนแยกต่างหาก) หรือค้นหาในตอนท้ายของส่วน
ผู้อ่านที่สนใจการเขียนโปรแกรมเป็นหลักมากกว่าคณิตศาสตร์อาจต้องการหยุดอ่านหัวข้อนี้เมื่อเนื้อหาทางคณิตศาสตร์เข้าใจยากเกินไป ในทางกลับกันผู้อ่านทางคณิตศาสตร์จะพบข้อเท็จจริงที่น่าสนใจมากมายสำหรับตัวเขาเอง สิ่งพิมพ์ทางคณิตศาสตร์จำนวนมากเกี่ยวกับหัวข้อการเขียนโปรแกรมมีข้อผิดพลาด ดังนั้นหนึ่งในเป้าหมายของหนังสือเล่มนี้คือการให้เหตุผลทางคณิตศาสตร์ที่ถูกต้องแก่ผู้อ่านสำหรับเนื้อหาเรื่องนี้ และเนื่องจากฉันคิดว่าตัวเองเป็นนักคณิตศาสตร์ ความรับผิดชอบโดยตรงของฉันคือการนำเสนอเนื้อหาจากมุมมองทางคณิตศาสตร์อย่างถูกต้อง (เท่าที่ฉันทำได้)
หากต้องการอ่านเนื้อหาทางคณิตศาสตร์ส่วนใหญ่ ความรู้คณิตศาสตร์ระดับประถมศึกษาก็เพียงพอแล้ว เนื่องจากทฤษฎีที่เหลือเกือบทั้งหมดได้รับการพัฒนาที่นี่ แต่บางครั้งฉันต้องการทฤษฎีบทที่ลึกซึ้งยิ่งขึ้นของทฤษฎีตัวแปรที่ซับซ้อน ทฤษฎีความน่าจะเป็น ทฤษฎีจำนวน ฯลฯ ในกรณีเช่นนี้ ฉันจะอ้างถึงหนังสือที่มีการนำเสนอหัวข้อเหล่านี้โดยละเอียด
การตัดสินใจที่ยากที่สุดที่ฉันต้องทำในการเตรียมหนังสือเหล่านี้คือจะนำเสนอวิธีการต่างๆ อย่างไร ประโยชน์ของผังงานและคำอธิบายทีละขั้นตอนของอัลกอริธึมเป็นที่ทราบกันดี ปัญหาเหล่านี้จะกล่าวถึงในบทความ "ผังงานคอมพิวเตอร์ที่วาด" ใน ACM Communications, Vol. 6 (กันยายน 2506) หน้า 555-563. ในการอธิบายอัลกอริทึมของคอมพิวเตอร์ จำเป็นต้องใช้ภาษาที่เป็นทางการและแม่นยำด้วย ดังนั้นฉันจึงต้องตัดสินใจว่าจะใช้ภาษาใด: ภาษาพีชคณิต เช่น ALGOL หรือ FORTRAN หรือภาษาที่ใช้เครื่องจักร นักวิทยาศาสตร์คอมพิวเตอร์ในปัจจุบันหลายคนอาจไม่เห็นด้วยกับการตัดสินใจของฉันที่จะใช้ภาษาเชิงเครื่องจักร แต่ฉันเชื่อว่านี่เป็นทางเลือกที่ถูกต้อง มีเหตุผลดังต่อไปนี้
ก) โปรแกรมเมอร์ได้รับอิทธิพลอย่างมากจากภาษาที่ใช้เขียนโปรแกรม ในปัจจุบัน แนวโน้มที่มีอยู่คือการเลือกภาษาที่ง่ายที่สุดมากกว่าโครงสร้างภาษาที่เหมาะสมที่สุดสำหรับคอมพิวเตอร์ และโปรแกรมเมอร์ที่รู้ภาษาเชิงเครื่องจักรมีแนวโน้มที่จะใช้วิธีการที่มีประสิทธิภาพมากกว่าและสร้างโปรแกรมที่ดีกว่า
b) โปรแกรมทั้งหมดที่เราต้องการเขียนด้วยภาษาเครื่อง จะมีขนาดเล็ก โดยมีข้อยกเว้นน้อยมาก ซึ่งหมายความว่าหากเรามีคอมพิวเตอร์ที่มีกำลังประมวลผลน้อยที่สุด เราจะไม่มีปัญหาในการใช้โปรแกรมดังกล่าว
ค) ภาษาระดับสูงไม่เหมาะสำหรับการพูดคุยรายละเอียดที่สำคัญระดับต่ำ เช่น การสื่อสารแบบโครูทีน การสร้างตัวเลขสุ่ม เลขคณิตที่มีความแม่นยำสูง และประเด็นอื่น ๆ อีกมากมายที่เกี่ยวข้องกับการใช้หน่วยความจำอย่างมีประสิทธิภาพ
d) ใครก็ตามที่สนใจคอมพิวเตอร์อย่างจริงจังควรมีความรู้ภาษาเครื่องเป็นอย่างดี เนื่องจากเป็นพื้นฐานการทำงานของคอมพิวเตอร์
e) ความรู้บางอย่างเกี่ยวกับภาษาเครื่องเป็นสิ่งจำเป็นในทุกกรณีเพื่อทำความเข้าใจผลลัพธ์ของโปรแกรมที่ให้ไว้ในตัวอย่างจำนวนมาก
f) ภาษาพีชคณิตใหม่ๆ เข้ามาและล้าสมัยทุกๆ ห้าปีโดยประมาณ ในขณะที่ฉันกำลังพยายามพูดถึง "ความจริงนิรันดร์"
ในทางกลับกัน ฉันยอมรับว่าการเขียนโปรแกรมด้วยภาษาระดับสูงและการดีบักโปรแกรมเหล่านี้ง่ายกว่ามาก อันที่จริง ตั้งแต่ปี 1970 ฉันเองก็ไม่ค่อยได้ใช้ภาษาเครื่องระดับต่ำสำหรับโปรแกรมของตัวเอง เนื่องจากคอมพิวเตอร์สมัยใหม่มีหน่วยความจำจำนวนมากและมีความเร็วสูง แต่สำหรับการแก้ปัญหาหลายๆ ปัญหาที่กล่าวถึงในหนังสือเล่มนี้ ศิลปะของการเขียนโปรแกรมมีความสำคัญมากที่สุด ตัวอย่างเช่น การคำนวณเชิงผสมบางอย่างจำเป็นต้องทำซ้ำหลายล้านล้านครั้ง และเราจะประหยัดเวลาในการทำงานได้ประมาณ 11.6 วันโดยการลดเวลาในการคำนวณในวงในลงเพียงหนึ่งไมโครวินาที ในทำนองเดียวกัน ก็สมเหตุสมผลที่จะพยายามเป็นพิเศษในการเขียนโปรแกรมที่จะใช้หลายครั้งต่อวันบนคอมพิวเตอร์หลายๆ เครื่อง โดยเฉพาะอย่างยิ่งเมื่อต้องเขียนโปรแกรมเพียงครั้งเดียวเท่านั้น
และหากคุณตัดสินใจที่จะใช้ภาษาเชิงเครื่อง คุณควรเลือกภาษาใด ฉันสามารถเลือกภาษาสำหรับเครื่อง X เครื่องใดเครื่องหนึ่งได้ แต่ผู้ที่ใช้คอมพิวเตอร์เครื่องอื่นจะคิดว่าหนังสือเล่มนี้เขียนขึ้นโดยคำนึงถึงคอมพิวเตอร์ X เท่านั้น ยิ่งกว่านั้นเครื่อง X อาจมีคุณสมบัติพิเศษมากมายซึ่งเป็นเนื้อหาที่ไม่สามารถใช้ได้อย่างสมบูรณ์ของหนังสือเล่มนี้ แต่ก็ยังต้องนำเสนอ และในที่สุด ในอีกสองปี ผู้ผลิตเครื่องจักร X จะเปิดตัวเครื่องจักร X+1 หรือ 10X และจะไม่มีใครสนใจคอมพิวเตอร์ X อีกต่อไป
เพื่อแก้ไขปัญหานี้ ฉันพยายามพัฒนาคอมพิวเตอร์ "ในอุดมคติ" ที่มีกฎการทำงานที่เรียบง่ายมาก (ซึ่งสามารถเรียนรู้ได้ภายในเวลาหนึ่งชั่วโมง) และคล้ายกับเครื่องจักรจริงมาก ไม่มีเหตุผลใดที่นักเรียนจะต้องหลีกเลี่ยงการเรียนรู้คุณลักษณะของคอมพิวเตอร์ต่างๆ หลังจากเรียนภาษาหนึ่งแล้ว ภาษาอื่นๆ ทั้งหมดจะเรียนรู้ได้ง่ายขึ้นมาก นอกจากนี้โปรแกรมเมอร์ที่จริงจังจะต้องเตรียมพร้อมรับมือกับภาษาเครื่องต่าง ๆ ในระหว่างการทำงาน ดังนั้นจึงมีข้อเสียเปรียบเพียงข้อเดียวในการใช้เครื่องที่สมมติขึ้น - ความยากในการรันโปรแกรมที่เขียนขึ้นมา โชคดีที่นี่ไม่ใช่ปัญหาจริงๆ เนื่องจากอาสาสมัครจำนวนมากได้อาสาบริการของตนเพื่อเขียนเครื่องจำลองของเครื่องสมมุติ เครื่องจำลองดังกล่าวเหมาะอย่างยิ่งสำหรับวัตถุประสงค์ทางการศึกษาและการทำงานกับเครื่องจำลองดังกล่าวนั้นง่ายกว่าการทำงานกับคอมพิวเตอร์จริงอีกด้วย
ฉันได้พยายามเชื่อมโยงไปยังเอกสารเก่าที่ดีที่สุดในแต่ละหัวข้อ รวมถึงพูดถึงงานใหม่ด้วย เมื่ออ้างอิงข้อมูลอ้างอิง ฉันใช้คำย่อมาตรฐานสำหรับชื่อวารสาร ยกเว้นวารสารที่มีการอ้างอิงบ่อยที่สุด ซึ่งใช้คำย่อต่อไปนี้
CACM - การสื่อสารของสมาคมเครื่องจักรคอมพิวเตอร์
JACM - วารสารสมาคมเครื่องจักรคอมพิวเตอร์
สตร. เจ - The Computer Journal (British Computer Society)
คณิตศาสตร์. สตร. - คณิตศาสตร์คอมพิวเตอร์
AMM - คณิตศาสตร์อเมริกันรายเดือน
SICOMP - วารสารสยามคอมพิวเตอร์
FOCS - การประชุมสัมมนา IEEE เกี่ยวกับรากฐานของวิทยาการคอมพิวเตอร์
SODA - การประชุมวิชาการ ACM-SIAM เรื่อง Discrete Algorithms
STOC - ACM Symposium เรื่องทฤษฎีคอมพิวเตอร์
Crelle - วารสารขนตาย reine und angewandte Mathematik
ตัวอย่างเช่น "CASM 6 (1963), 555-563" หมายถึงวารสารที่อ้างอิงในย่อหน้าก่อนหน้าของคำนำนี้ ฉันยังใช้ตัวย่อ "CMatA" เพื่ออ้างถึงหนังสือ Concrete Mathematics ซึ่งมีการอ้างอิงในบทนำของหัวข้อ 1.2
เนื้อหาทางเทคนิคส่วนใหญ่ในหนังสือเหล่านี้มาจากแบบฝึกหัด หากความคิดเรื่องแบบฝึกหัดที่ไม่สำคัญไม่ได้เป็นของฉันฉันก็พยายามพูดถึงผู้เขียน การอ้างอิงวรรณกรรมมักจะระบุไว้ในเนื้อหาของส่วนนี้หรือในคำตอบของแบบฝึกหัด แต่ในหลายกรณี แบบฝึกหัดนี้อิงจากเนื้อหาที่ไม่ได้เผยแพร่ซึ่งไม่สามารถอ้างอิงได้
หลายๆ คนได้ช่วยเหลือฉันตลอดหลายปีที่ผ่านมาในขณะที่เขียนหนังสือเหล่านี้ ซึ่งฉันรู้สึกซาบซึ้งจากก้นบึ้งของหัวใจ ก่อนอื่น ฉันอยากจะแสดงความขอบคุณต่อจิล ภรรยาของฉันสำหรับความอดทนอันไม่มีที่สิ้นสุดของเธอ ในการเตรียมภาพประกอบบางส่วน และสำหรับความช่วยเหลือของเธอในทุกสิ่งมาโดยตลอด ฉันยังรู้สึกขอบคุณ Floyd Robert W. สำหรับการอุทิศเวลาอย่างมากในทศวรรษ 1960 เพื่อปรับปรุงและทำให้เนื้อหานี้ลึกซึ้งยิ่งขึ้น ผู้คนอีกหลายพันคนได้ให้ความช่วยเหลืออันล้ำค่าแก่ฉันเช่นกัน เพียงเพื่อที่จะระบุชื่อของพวกเขาก็จำเป็นต้องมีหนังสือเล่มอื่นอีก! หลายคนกรุณาอนุญาตให้ฉันใช้งานเก่าที่ไม่ได้ตีพิมพ์ของพวกเขา งานวิจัยของฉันที่มหาวิทยาลัยคาลเทคและสแตนฟอร์ดได้รับทุนสนับสนุนจากมูลนิธิวิทยาศาสตร์แห่งชาติและสำนักงานวิจัยกองทัพเรือ แอดดิสัน-เวสลีย์ให้ความช่วยเหลือและสนับสนุนอย่างมากนับตั้งแต่ฉันเริ่มทำงานในโครงการนี้ในปี 1962 สำหรับฉันดูเหมือนว่าสำหรับคนเหล่านี้ความกตัญญูที่ดีที่สุดคือสิ่งพิมพ์นี้ มันแสดงให้เห็นว่าการมีส่วนร่วมของพวกเขาส่งผลให้ฉันหวังว่าฉันสามารถเขียนสิ่งที่พวกเขาคาดหวังได้
คำนำฉบับพิมพ์ครั้งที่ 3
หลังจากใช้เวลาสิบปีในการพัฒนาระบบการพิมพ์ด้วยคอมพิวเตอร์ METAFONT และ TEX ตอนนี้ฉันสามารถตระหนักถึงความฝันของตัวเองในการใช้ระบบเหล่านี้ในการพิมพ์หนังสือ ศิลปะแห่งการเขียนโปรแกรม- ในที่สุด ฉันก็สามารถป้อนข้อความทั้งหมดของหนังสือเล่มนี้ลงในคอมพิวเตอร์ส่วนบุคคลได้ และได้เวอร์ชันอิเล็กทรอนิกส์มา ซึ่งจะช่วยให้ฉันสามารถเปลี่ยนแปลงเทคโนโลยีการพิมพ์และการแสดงผลหน้าจอได้ในอนาคต วิธีการทำงานนี้ทำให้ฉันสามารถปรับปรุงได้นับพันอย่างแท้จริง ฉันบรรลุสิ่งที่ฉันฝันมานาน
ในฉบับพิมพ์ใหม่นี้ ฉันสามารถตรวจสอบทุกคำในเนื้อหา โดยพยายามรักษาความกระตือรือร้นของเยาวชนในการค้นคว้าต้นฉบับของฉัน และในขณะเดียวกันก็ทำให้เกิดวิจารณญาณที่เป็นผู้ใหญ่มากขึ้น มีการเพิ่มแบบฝึกหัดใหม่หลายสิบแบบ และแบบฝึกหัดเก่าหลายสิบแบบได้รับคำตอบด้วยคำตอบใหม่หรือที่ได้รับการปรับปรุง
ดังนั้นงานหนังสือ “The Art of Programming” จึงดำเนินต่อไป นั่นคือเหตุผลที่บางส่วนของหนังสือเล่มนี้เริ่มต้นด้วยไอคอน "อยู่ระหว่างการปรับปรุง" (นี่เป็นการขอโทษสำหรับข้อเท็จจริงที่ว่าข้อมูลที่ให้ไว้ไม่ใช่ข้อมูลล่าสุด) แฟ้มของฉันเต็มไปด้วยเอกสารสำคัญที่ฉันวางแผนจะรวมไว้ในเล่มที่ 1 ฉบับที่สี่อันรุ่งโรจน์ฉบับสุดท้าย มันอาจจะออกมาใน 15 ปี แต่ก่อนอื่นผมต้องอ่านเล่ม 4 และ 5 ให้จบก่อน ผมอยากให้ตีพิมพ์ทันทีที่พร้อมจะออกสื่อ
งานหนักส่วนใหญ่ในการเตรียมฉบับใหม่นี้ดำเนินการโดย Phyllis Winkler และ Silvio Levy ซึ่งเป็นผู้เชี่ยวชาญในการพิมพ์และแก้ไขข้อความในฉบับพิมพ์ครั้งที่สอง และ Jeffrey Oldham ซึ่งแปลงภาพประกอบต้นฉบับเกือบทั้งหมดเป็นรูปแบบ METAP0ST ฉันได้แก้ไขข้อผิดพลาดทั้งหมดที่แจ้งเตือนผู้อ่าน (แบร์รี่) ที่พบในฉบับที่สอง (รวมถึงข้อผิดพลาดที่อนิจจาไม่มีใครสังเกตเห็น) และพยายามหลีกเลี่ยงการแนะนำข้อผิดพลาดใหม่ในเนื้อหาใหม่ อย่างไรก็ตามฉันยอมรับว่ายังมีข้อบกพร่องอยู่บ้างและฉันต้องการแก้ไขโดยเร็วที่สุด ดังนั้น ทุกครั้งที่พิมพ์ผิด* รวมถึงข้อผิดพลาดที่เกี่ยวข้องกับสาระสำคัญของเนื้อหาที่นำเสนอหรือข้อมูลในอดีตที่ให้ไว้ ฉันยินดีจะจ่ายเงิน $2.56 ให้กับคนแรกที่พบมัน หน้าเว็บที่อยู่ด้านหลังของหน้าชื่อเรื่องมีรายการข้อผิดพลาดทั้งหมดที่ได้รับการรายงานถึงฉันในปัจจุบัน**
* นี่หมายถึงต้นฉบับของเอกสารนี้ - ประมาณ. เอ็ด
** ข้อผิดพลาดที่ทราบในขณะที่จัดทำฉบับภาษารัสเซียได้รับการแก้ไขแล้ว -ประมาณ. เอ็ด
ดี.อี.เค.
สแตนฟอร์ด แคลิฟอร์เนีย
เมษายน 1997
โลกมีการเปลี่ยนแปลงในช่วงยี่สิบปีที่ผ่านมา
- บิล เกตส์ (1995)
บทที่ 1 แนวคิดพื้นฐาน............................................ ....... ... 27
1.1. อัลกอริทึม................................................ .. ...... 27
1.2. บทนำทางคณิตศาสตร์................................................ .... 37
1.2.1. การเหนี่ยวนำทางคณิตศาสตร์................................ 38
1.2.2. ตัวเลข กำลัง และลอการิทึม.................................... 49
1.2.3. จำนวนเงินและผลิตภัณฑ์............................................ .... 56
1.2.4. ฟังก์ชันจำนวนเต็มและทฤษฎีจำนวนเบื้องต้น......... 68
1.2.5. การเรียงสับเปลี่ยนและแฟกทอเรียล................................ 75
1.2.6. ค่าสัมประสิทธิ์ทวินาม................................ 82
1.2.7. ตัวเลขฮาร์มอนิก................................................ ... 105
1.2.8. ตัวเลขฟีโบนักชี................................................ .... 109
1.2.9. การสร้างฟังก์ชัน................................................ 118
1.2.10. การวิเคราะห์อัลกอริทึม............................................ 127
*1.2.11. การเป็นตัวแทนเชิงเส้นกำกับ........................ 138
*1.2.11.1. เครื่องหมาย เกี่ยวกับ .......................................... 138
*1.2.11.2. สูตรบวกของออยเลอร์.................................... 143
*1.2.11.3. การใช้สูตรซีมโทติค........................ 148
1.3. มิกซ์ .................................................. ....... ............ 156
1.3.1. คำอธิบายของ MIX .................................... 156
1.3.2. MIX ภาษาแอสเซมบลีของคอมพิวเตอร์ ...................................... 178
1.3.3. การประยุกต์ใช้พีชคณิต................................ 198
1.4. เทคนิคการเขียนโปรแกรมพื้นฐานบางประการ.................................... 221
1.4.1. รูทีนย่อย................................................ ....... 221
1.4.2. โครูทีน................................................................ ........ 229
1.4.3. โปรแกรมล่าม................................................ ... 237
1.4.3.1. มิกซ์ซิมูเลเตอร์ ....................................... 239
*1.4.3.2. โปรแกรมติดตาม............................................ 248
1.4.4. อินพุตและเอาต์พุต................................................ ........251
1.4.5. ประวัติศาสตร์และบรรณานุกรม................................ 266
บทที่ 2 โครงสร้างข้อมูล............................................ ....... 271
2.1. การแนะนำ................................................. ....... .... 271
2.2. รายการเชิงเส้น................................................ .... 277
2.2.1. กอง คิว และสำรับ................................................ ...... 277
2.2.2. การกระจายตามลำดับ...................................... 283
2.2.3. การกระจายแบบเชื่อมโยง................................ 295
2.2.4. รายการหนังสือเวียน............................................ 315
2.2.5. รายการที่เชื่อมโยงทวีคูณ............................................ 322
2.2.6. อาร์เรย์และรายการมุมฉาก............................................ 341
2.3. ต้นไม้................................................. ..... 352
2.3.1. การสำรวจต้นไม้ไบนารี่................................ 362
2.3.2. การแทนต้นไม้เป็นต้นไม้ไบนารี........ 380
2.3.3. ต้นไม้อื่นๆ.......................... 395
2.3.4. คุณสมบัติทางคณิตศาสตร์พื้นฐานของต้นไม้........................ 410
2.3.4.1. ต้นไม้ฟรี.................................... 410
2.3.4.2. ต้นไม้เชิงนิเวศน์.......................... 420
*2.3.4.3. เลมมาบนต้นไม้ที่ไม่มีที่สิ้นสุด.................................... 431
*2.3.4.4. การแจงนับต้นไม้........................ 435
2.3.4.5. ความยาวเส้นทาง................................ 449
*2.3.4.6. ประวัติศาสตร์และบรรณานุกรม........................ 456
2.3.5. รายการและการเก็บขยะ .................................... 459
2.4. โครงสร้างที่เชื่อมต่อหลายจุด ........................................... ...... 476
2.5. การจัดสรรหน่วยความจำแบบไดนามิก........................................ 488
2.6. ประวัติและบรรณานุกรม...................................................... 512
คำตอบของแบบฝึกหัด............................................ ..... ...... 521
ภาคผนวก A. ตารางค่าคงที่บางค่า.................................... 683
AI. ค่าคงที่พื้นฐาน (ทศนิยม) .................................... 683
ก.2. ค่าคงที่พื้นฐาน (ฐานแปด) .................................... 684
อ.ซ. ความหมายของเลขฮาร์มอนิก เลขเบอร์นูลลี และเลขฟีโบนัชชี...... 685
ภาคผนวก B. สัญกรณ์พื้นฐาน............................................. ....... 687
ดัชนีหัวเรื่อง................................................ ............ 692
ภาพรวมโดยย่อของเอกสารในตำนานของ Donald Knuth เรื่อง "The Art of Programming" ซึ่งเป็นงานพื้นฐานในสาขาวิทยาการคอมพิวเตอร์
เล่มที่ 1 อัลกอริทึมพื้นฐาน
เล่มแรกเป็นการแนะนำอัลกอริธึมพื้นฐานและโครงสร้างข้อมูล ซึ่งอธิบายแนวคิดและเทคนิคการเขียนโปรแกรมขั้นพื้นฐาน หัวข้อการแสดงข้อมูลในหน่วยความจำคอมพิวเตอร์และการทำงานกับข้อมูลอย่างมีประสิทธิภาพจะกล่าวถึงที่นี่ด้วย
หนังสือเล่มนี้ประกอบไปด้วยตัวอย่างการคำนวณเชิงสัญลักษณ์ วิธีการเชิงตัวเลข วิธีการจำลอง และอื่นๆ อีกมากมาย
โปรแกรมตัวอย่างเขียนด้วยภาษาที่เรียกว่า "MIX assembler" ซึ่งเป็นภาษาที่ออกแบบมาให้ทำงานบน "คอมพิวเตอร์ MIX" ตามสมมุติฐาน รุ่นที่สามแทนที่ MIX ดั้งเดิมด้วย MMIX ซึ่งมีซอฟต์แวร์อยู่เพื่อจำลอง
การใช้ภาษาระดับต่ำทำให้ผู้อ่านหลายคนท้อใจ แต่ผู้เขียนเองก็ให้เหตุผลในการเลือกของเขาด้วยเหตุผลที่ดี การเชื่อมโยงกับสถาปัตยกรรมทำให้เราสามารถตัดสินลักษณะของอัลกอริทึม เช่น ความเร็วและความซับซ้อน (เช่น การใช้หน่วยความจำ)
เล่มที่ 2 อัลกอริธึมที่ได้รับ
หนังสือเล่มที่สองเป็นการแนะนำอัลกอริทึมแบบกึ่งตัวเลข ส่วนที่แยกต่างหากมีไว้สำหรับเลขคณิต ตัวเลขสุ่ม และอัลกอริธึมสำหรับการสร้าง พื้นฐานของทฤษฎีอัลกอริธึมกึ่งตัวเลขได้รับการสนับสนุนโดยตัวอย่างมากมาย
การตีความใหม่เกี่ยวกับตัวสร้างตัวเลขสุ่มที่เสนอโดย Knuth ในฉบับนี้ ตลอดจนการพิจารณาวิธีการคำนวณโดยใช้อนุกรมกำลังแบบเป็นทางการ สมควรได้รับการกล่าวถึงเป็นพิเศษ
เล่มที่ 3 การเรียงลำดับและการค้นหา
เล่มที่ 3 นำเสนอภาพรวมที่ครอบคลุมของอัลกอริธึมการเรียงลำดับและการค้นหาแบบคลาสสิก เนื้อหานี้เติมเต็มข้อมูลเกี่ยวกับโครงสร้างข้อมูลที่นำเสนอในส่วนแรกซึ่งกลายเป็นความต่อเนื่องเชิงตรรกะของเล่มแรก
ในที่นี้ผู้เขียนพูดถึงหน่วยความจำภายในและภายนอก เกี่ยวกับการสร้างฐานข้อมูลขนาดใหญ่และขนาดเล็ก และการทำงานกับฐานข้อมูลเหล่านั้น สำหรับอัลกอริธึมทั้งหมดที่กล่าวถึงในหนังสือ จะมีการวิเคราะห์เปรียบเทียบประสิทธิผล ส่วนพิเศษมีไว้สำหรับวิธีการเรียงลำดับที่เหมาะสมที่สุดและคำอธิบายของทฤษฎีใหม่ของการเรียงสับเปลี่ยนและการแฮชแบบสากล
เล่มที่ 4 อัลกอริทึมแบบรวม
เล่มที่สี่นั้นเป็นชุดหลายเล่มเอง การค้นหาแบบผสมผสานเป็นหัวข้อที่สมบูรณ์และสำคัญ และ Knuth ได้จัดเตรียมเนื้อหาใหม่ น่าสนใจ และมีประโยชน์มากเกินไปที่จะรวมไว้ในหนึ่งหรือสองเล่ม (หรืออาจจะถึงสามเล่มด้วยซ้ำ) หนังสือเล่มนี้เพียงเล่มเดียวประกอบด้วยแบบฝึกหัดประมาณ 1,500 แบบฝึกหัดพร้อมคำตอบสำหรับงานอิสระ รวมถึงข้อเท็จจริงที่เป็นประโยชน์หลายร้อยข้อที่คุณจะไม่พบในสิ่งพิมพ์อื่นใด
ชื่อ:ศิลปะแห่งการเขียนโปรแกรม - เล่มที่ 1
หนังสือชุด The Art of Programming เล่มแรกเริ่มต้นด้วยคำอธิบายแนวคิดพื้นฐานและวิธีการเขียนโปรแกรม จากนั้นผู้เขียนจะพิจารณาโครงสร้างข้อมูล การเป็นตัวแทนของข้อมูลภายในคอมพิวเตอร์ ความสัมพันธ์เชิงโครงสร้างระหว่างองค์ประกอบข้อมูล และวิธีการทำงานร่วมกับองค์ประกอบเหล่านั้นอย่างมีประสิทธิภาพ ตัวอย่างของการใช้งานเบื้องต้นมีให้สำหรับวิธีการจำลอง การคำนวณเชิงสัญลักษณ์ วิธีการเชิงตัวเลข และวิธีการพัฒนาซอฟต์แวร์ เมื่อเทียบกับรุ่นก่อนหน้ามีการเพิ่มอัลกอริธึมที่เรียบง่าย แต่ในขณะเดียวกันก็มีความสำคัญมาก เพื่อให้สอดคล้องกับแนวทางการวิจัยสมัยใหม่ ส่วนการแนะนำทางคณิตศาสตร์ได้รับการแก้ไขอย่างมีนัยสำคัญ
หนังสือแต่ละเล่มมีชะตากรรมของตัวเอง บางส่วนดูเหมือนไม่มีใครสังเกตเห็นและหายไปตามกระแสเวลาจนแทบมองไม่เห็น และถูกปกคลุมไปด้วยฝุ่นบนชั้นวางของห้องสมุด คนอื่น ๆ เป็นที่ต้องการในช่วงระยะเวลาหนึ่งในหมู่ผู้เชี่ยวชาญในวงแคบ ๆ จนกว่าพวกเขาจะถูกแทนที่ด้วยหนังสืออ้างอิงใหม่ ส่วนคนอื่นๆ ที่อยู่เหนือกาลเวลา มีอิทธิพลอย่างมากต่อการพัฒนาทางเทคโนโลยีของสังคม มีหนังสือไม่มากนักที่อยู่ในประเภทหลัง การปรากฏตัวของพวกเขาในโลกนี้ถือเป็นวันหยุดเสมอ หลายปีผ่านไป เทคโนโลยีเปลี่ยนไป แต่คนรุ่นใหม่อ่านซ้ำหน้าต่างๆ ด้วยความสนใจอย่างต่อเนื่อง งานหลายเล่มที่เสนอให้กับผู้อ่านโดยนักวิทยาศาสตร์ชาวอเมริกันชื่อดังอย่าง Donald Erwin Knuth“ The Art of Programming” เป็นของหนังสือประเภทนี้อย่างแน่นอน
ความสำเร็จของ Art of Programming ของ D.E. Knuth คืออะไร:
ประการแรก หนังสือเล่มนี้เป็นตำราเรียนที่ยอดเยี่ยมเกี่ยวกับการออกแบบและการวิเคราะห์อัลกอริธึมคอมพิวเตอร์ หัวข้อต่างๆ สามารถรวมอยู่ในหลักสูตรของมหาวิทยาลัยหลายหลักสูตรเกี่ยวกับเทคโนโลยีการเขียนโปรแกรม ทฤษฎีอัลกอริทึม และคณิตศาสตร์แยกส่วน นักเรียนมัธยมปลายที่คุ้นเคยกับพื้นฐานของการเขียนโปรแกรมสามารถอ่านหนังสือนี้ได้ ผู้เขียนเลือกภาษาคำสั่งเครื่องของคอมพิวเตอร์สากล MIX สมมุติเป็นภาษาหลักสำหรับอัลกอริธึมการบันทึก สิ่งนี้ช่วยให้คุณสร้างโปรแกรมที่เหมาะสมที่สุดโดยคำนึงถึงลักษณะของคอมพิวเตอร์ การถ่ายโอนโปรแกรม MIX ไปยังคอมพิวเตอร์จริงหรือเขียนใหม่เป็นภาษาระดับสูงนั้นไม่ใช่เรื่องยากโดยเฉพาะ ตรรกะของโปรแกรมมักอธิบายโดยใช้บล็อกไดอะแกรมอย่างง่ายเกือบทุกครั้ง
ประการที่สอง เนื้อหาที่คัดสรรมาอย่างดีซึ่งรวมอยู่ในหนังสือเล่มนี้ประกอบด้วยคลาสพื้นฐานหลักของอัลกอริธึม ซึ่งมักพบในรูปแบบใดรูปแบบหนึ่งในการฝึกฝนการเขียนโปรแกรม
ประการที่สาม ปัจจัยสำคัญในความสำเร็จของหนังสือของ D.E. Knuth คือลักษณะสารานุกรมของการนำเสนอ ศาสตราจารย์คนุธมีความสามารถพิเศษในการติดตามปัญหาตั้งแต่ภูมิหลังทางประวัติศาสตร์ไปจนถึงสถานะปัจจุบัน การอ้างอิงถึงผลงานของปรมาจารย์ผู้เฒ่าจำนวนมาก (จนถึงสมัยโบราณ) ซึ่งวางไว้ในบริบทสมัยใหม่ทำให้ผู้อ่านรู้สึกถึงการมีส่วนร่วมเป็นพิเศษในการพัฒนาทางประวัติศาสตร์ของแนวคิดและวิธีการทางวิทยาศาสตร์
ดาวน์โหลด e-book ฟรีในรูปแบบที่สะดวกรับชมและอ่าน:
ดาวน์โหลดหนังสือ The Art of Programming - Volume 1 - Knut D. E. - fileskachat.com ดาวน์โหลดฟรีรวดเร็วและฟรี
ดาวน์โหลด djvu.dll
ด้านล่างนี้คุณสามารถซื้อหนังสือเล่มนี้ในราคาที่ดีที่สุดพร้อมส่วนลดพร้อมจัดส่งทั่วรัสเซีย
โครงการเขียนหนังสือเริ่มต้นโดยผู้เขียนในปี ในขั้นต้นมีการวางแผนที่จะเผยแพร่ในเล่มเดียว แต่ปริมาณของวัสดุกลับกลายเป็นว่ามีขนาดใหญ่มากจนจำนวนเล่มเพิ่มขึ้นเป็นเจ็ดเล่ม สามเล่มแรกได้รับการตีพิมพ์ค่อนข้างเร็ว ได้แก่ เล่ม 1 ในปี พ.ศ. 2511 เล่มที่ 2 ในปี พ.ศ. 2512 และเล่มที่ 3 ในปี พ.ศ. 2516 ตามมาด้วยการหยุดพักจนถึงเดือนกุมภาพันธ์ พ.ศ. 2548 ซึ่งผู้เขียนได้ตีพิมพ์ส่วนแรกของเล่มที่สี่ มีการตัดสินใจที่จะเผยแพร่ส่วนที่เหลือของเล่มที่สี่ประมาณปีละสองครั้งโดยแยกประเด็น หลังจากนั้นเล่มที่สี่ทั้งหมดจะได้รับการตีพิมพ์อย่างเป็นทางการ ระหว่างปี พ.ศ. 2548-2552 มีการเผยแพร่ฉบับที่ 0, 1, 2, 3 และ 4 และในปี พ.ศ. 2554 มีการออกเล่ม 4A ซึ่งรวมถึงข้อมูลจากประเด็นเหล่านี้ นอกจากนี้ในปี 2548 ฉบับที่ 1“ MMIX - คอมพิวเตอร์ RISC สำหรับสหัสวรรษใหม่” ได้รับการเผยแพร่ข้อมูลซึ่งจะรวมอยู่ในเล่มแรกฉบับใหม่ที่สี่ ฉบับที่ 6 ได้รับการเผยแพร่ในปี 2558 ความพึงพอใจซึ่งเป็นตัวแทนของเล่มที่ 4B ที่กำลังจะมาถึง
เนื่องจาก Knuth ถือว่าศิลปะของการเขียนโปรแกรมเป็นโครงการหลักในชีวิตของเขามาโดยตลอด เขาจึงเกษียณในปี 1993 ด้วยความตั้งใจที่จะมุ่งเน้นไปที่การเขียนส่วนที่ขาดหายไปและจัดเรียงส่วนที่มีอยู่ตามลำดับ เขาเชื่อว่าจะใช้เวลา 20 ปีจึงจะเสร็จสมบูรณ์
YouTube สารานุกรม
-
1 / 5
ในฐานะผู้เชี่ยวชาญที่ได้รับการยอมรับในด้านการออกแบบคอมไพเลอร์ Knuth เริ่มเขียนหนังสือเกี่ยวกับการออกแบบคอมไพเลอร์ในปี 1962 ในไม่ช้าเขาก็ตระหนักว่าขอบเขตของเนื้อหาจำเป็นต้องกว้างกว่านี้มาก ในเดือนมิถุนายน พ.ศ. 2508 เขาเขียนเวอร์ชันแรกของสิ่งที่เขาต้องการจะตีพิมพ์เป็นหนังสือเล่มเดียวในสิบสองส่วนเสร็จ ปริมาณข้อความที่เขียนด้วยลายมือคือ 3,000 หน้า จากการคำนวณของ Knuth หนังสือเล่มนี้ควรมีขนาดพอดีกับข้อความที่พิมพ์ 600 หน้า แต่ตามที่ผู้จัดพิมพ์แจ้งเขา ปริมาณจริงน่าจะอยู่ที่ 2,000 หน้า ทั้งนี้มีการปรับปรุงโครงสร้างของหนังสือให้มีหลายเล่ม เล่มละ 1-2 ตอน ตั้งแต่นั้นมา เนื่องจากการเติบโตอย่างต่อเนื่องของเนื้อหา จึงมีการตัดสินใจว่าเล่มที่สี่จะแบ่งออกเป็นเล่มแยกกัน: 4A, 4B, 4C และอาจเป็น 4D แต่เห็นได้ชัดว่าแผนกนี้จะไม่ถือเป็นที่สิ้นสุดเนื่องจากส่วนที่ 7.1 และ 7.2.1 มีทั้งหมดมากกว่า 650 หน้าแล้ว
ในปีพ.ศ. 2519 Knuth ได้เตรียมเล่มที่สองฉบับพิมพ์ครั้งที่สอง ซึ่งจำเป็นต้องพิมพ์ซ้ำ แต่การออกแบบตัวพิมพ์ (แบบโมโนไทป์) ที่ใช้ในฉบับพิมพ์ครั้งแรกไม่มีให้บริการอีกต่อไปในเวลานั้น เพื่อหลีกเลี่ยงความผิดหวังที่คล้ายกันในอนาคต ในปี 1977 Knuth เริ่มพัฒนาระบบเรียงพิมพ์คอมพิวเตอร์แบบพิมพ์ของตัวเอง ตามการคำนวณของเขา งานควรใช้เวลาไม่เกินหกเดือน แต่ใช้เวลาประมาณสิบปีจึงจะแล้วเสร็จ ระบบนี้เรียกว่า TeX และปัจจุบันใช้สำหรับเลย์เอาต์ของ The Art of Programming ทุกเล่ม นอกจากนี้ TeX ยังกลายเป็นมาตรฐานโดยพฤตินัยสำหรับการเขียนบทความและเอกสารในสาขาวิทยาศาสตร์ธรรมชาติ
เช่นเดียวกับหนังสือเล่มอื่นๆ ของ Knuth ศิลปะแห่งการเขียนโปรแกรมถูกทำเครื่องหมายด้วย "เครื่องหมายการค้า" ของเขา: สำหรับข้อผิดพลาดแต่ละข้อที่พบในข้อความ ผู้เขียนจะต้องจ่ายเงินเป็นเลขฐานสิบหกหนึ่งดอลลาร์ นั่นคือ 2.56 ดอลลาร์ (0x100 เซนต์ ในฐาน 16) คุณสมบัติที่โดดเด่นอีกประการหนึ่งของหนังสือเล่มนี้คือแบบฝึกหัดมากมายสำหรับการนำไปใช้อย่างอิสระ โดยมีระดับความยากต่างกัน ตั้งแต่ปัญหา "อุ่นเครื่อง" ง่ายๆ ไปจนถึงปัญหาเปิด ความยากของแบบฝึกหัดแต่ละครั้งได้รับการจัดอันดับตามระดับตัวเลขตั้งแต่ 0 ถึง 50 ดังนั้นในฉบับแรก ๆ ทฤษฎีบทสุดท้ายของแฟร์มาต์จึงได้รับการจัดอันดับที่ 50 แต่ในฉบับที่สามคะแนนนี้ "ลดค่า" เหลือ 45 เนื่องจากเมื่อถึงเวลานั้นการพิสูจน์ก็สิ้นสุดลง ให้เป็นปัญหาที่เปิดกว้าง
สรุปตำนานเล่ม 3 ปี 2521 "การเรียงลำดับและการสืบค้น" (ซ้าย - การประเมิน ขวา - คำอธิบายสั้น ๆ )
- สามเหลี่ยมสีดำ - แนะนำ
- M - มีอคติทางคณิตศาสตร์
- VM - ต้องการความรู้ "คณิตศาสตร์ขั้นสูง"
- 00 - ต้องการการตอบสนองทันที
- 10 - ง่าย (เป็นเวลา 1 นาที)
- 20 - ความยากปานกลาง (เป็นเวลา 15 นาที)
- 30 - ความยากเพิ่มขึ้น
- 40 - สำหรับ “เวิร์คช็อปคณิตศาสตร์”
- 50 - ปัญหาการวิจัย
แผนเดิมสำหรับการเขียนหนังสือเล่มนี้มีการแบ่งเนื้อหาดังต่อไปนี้
- เล่มที่ 1 อัลกอริธึมพื้นฐาน
- บทที่ 1 แนวคิดพื้นฐาน
- บทที่ 2 โครงสร้างข้อมูล
- เล่มที่ 2 อัลกอริธึมกึ่งตัวเลข
- บทที่ 3 ตัวเลขสุ่ม
- บทที่ 4 เลขคณิต
- เล่มที่ 3 การเรียงลำดับและการค้นหา
- บทที่ 5 การเรียงลำดับ
- บทที่ 6 ค้นหา
- เล่มที่ 4 อัลกอริธึมเชิงผสม
- บทที่ 7 การค้นหาแบบผสมผสาน
- บทที่ 8 การเรียกซ้ำ
- เล่มที่ 5 อัลกอริธึมทางวากยสัมพันธ์
- บทที่ 9 การค้นหาพจนานุกรม
- บทที่ 10 การค้นหาเชิงวากยสัมพันธ์
- เล่มที่ 6 ทฤษฎีภาษา
- เล่มที่ 7 คอมไพเลอร์
ในความเป็นจริง โครงการนี้ถูกนำมาใช้จนถึงเล่มที่สามด้วย
ปัจจุบันเล่ม 4A ได้รับการเผยแพร่แล้ว ซึ่งมีส่วนแรกของบทที่ 7 ส่วนใหม่ได้รับการวางแผนให้ตีพิมพ์ครั้งแรกเป็นฉบับแยกกัน (ประมาณ 128 หน้า) ประมาณสองฉบับต่อปี (ฉบับที่ 0, 1, 2, 3 และ 4 ได้รับการตีพิมพ์ในลักษณะเดียวกันก่อนการเปิดตัวเล่ม 4A)
ภาษาตัวอย่างเชิงเครื่องจักร
โปรแกรมตัวอย่างที่ให้ไว้ในหนังสือเล่มนี้ใช้ "แอสเซมเบลอร์ MIX" ที่ออกแบบมาเพื่อทำงานบนคอมพิวเตอร์ MIX สมมุติ ในฉบับที่สาม MIX ที่ล้าสมัยถูกแทนที่ด้วย MMIX ซึ่งมีสถาปัตยกรรม RISC เต็มรูปแบบ มีซอฟต์แวร์ที่ให้การจำลองเครื่อง (M)MIX บนคอมพิวเตอร์มาตรฐานที่เข้ากันได้กับ IBM GNU Compiler Collection มีความสามารถในการคอมไพล์โค้ด C/C++ บนสถาปัตยกรรม MMIX เป้าหมาย
ผู้อ่านหลายคนรู้สึกไม่พอใจกับความจริงที่ว่าพวกเขาใช้ภาษาระดับต่ำ แต่ Knuth ถือว่าตัวเลือกของเขานั้นสมเหตุสมผล เนื่องจากการลิงก์ไปยังสถาปัตยกรรมเป็นสิ่งจำเป็นเพื่อที่จะตัดสินคุณลักษณะของอัลกอริทึมเช่นความเร็ว การใช้หน่วยความจำ ฯลฯ ได้อย่างแม่นยำ จากตัวเลือกนี้ อย่างไรก็ตาม กลุ่มเป้าหมายจึงแคบลงอย่างมาก นอกจากนี้ ขอบเขตของการใช้เป็น “หนังสือสูตรอาหาร” สำหรับฝึกหัดโปรแกรมเมอร์นั้นมีจำกัด หลายคนไม่รู้จักภาษาแอสเซมบลี และหากรู้ พวกเขาก็ไม่มีความปรารถนาที่จะแปลอัลกอริธึมระดับต่ำจากหนังสือไปเป็น ภาษาระดับสูง คำแนะนำที่เป็นประโยชน์จำนวนมากซึ่งมีการนำเสนอเนื้อหาเดียวกันในลักษณะที่ได้รับความนิยมมากกว่าได้รับการตีพิมพ์อย่างชัดเจนด้วยเหตุนี้
การวิพากษ์วิจารณ์
ลักษณะสำคัญของเอกสารของ Knuth ซึ่งทำให้แตกต่างจากหนังสือเล่มอื่นๆ เกี่ยวกับการเขียนโปรแกรม คือคุณภาพของเนื้อหาและการนำเสนอทางวิชาการในระดับสูงเป็นพิเศษ ตลอดจนการวิเคราะห์เชิงลึกของประเด็นที่อยู่ระหว่างการพิจารณา ด้วยเหตุนี้จึงกลายเป็นหนังสือขายดีและเป็นหนังสืออ้างอิงสำหรับโปรแกรมเมอร์มืออาชีพทุกคน นิตยสาร American Scientist ได้รวม The Art of Programming ไว้ในรายชื่อเอกสารทางฟิสิกส์และคณิตศาสตร์ที่ดีที่สุด 12 เล่มของศตวรรษที่ 20 พร้อมด้วยผลงานของ Dirac เกี่ยวกับกลศาสตร์ควอนตัม, Einstein เกี่ยวกับทฤษฎีสัมพัทธภาพ, Russell และ Whitehead เกี่ยวกับรากฐานของคณิตศาสตร์ และอีกสองสามคน
หน้าปกของหนังสือเล่มแรกฉบับพิมพ์ครั้งที่ 3 มีคำพูดของบิล เกตส์: "ถ้าคุณคิดว่าคุณเป็นโปรแกรมเมอร์ที่ดีจริงๆ... อ่าน The Art of Programming (Knuth)... ถ้าคุณอ่านได้ทั้งหมด คุณควรส่งเรซูเม่ของคุณมาให้ฉันอย่างแน่นอน".
ฉบับ
ต้นฉบับ
สาม (ปัจจุบัน)
ตามลำดับหมายเลขเล่มจากน้อยไปหามาก:
- เล่มที่ 1: อัลกอริทึมพื้นฐาน- พิมพ์ครั้งที่สาม (Reading, Massachusetts: Addison-Wesley, 1997), xx+650pp. ISBN 0-201-89683-4
- เล่มที่ 1 Fascicle 1: MMIX - คอมพิวเตอร์ RISC สำหรับสหัสวรรษใหม่- (แอดดิสัน-เวสลีย์, 14 กุมภาพันธ์ 2548) ISBN 0-201-85392-2 (จะอยู่ในฉบับที่สี่ของเล่มที่ 1)
- เล่มที่ 2: อัลกอริทึมแบบกึ่งตัวเลข- พิมพ์ครั้งที่สาม (Reading, Massachusetts: Addison-Wesley, 1997), xiv+762pp. ISBN 0-201-89684-2
- เล่มที่ 3: การเรียงลำดับและการค้นหา- พิมพ์ครั้งที่สอง (Reading, Massachusetts: Addison-Wesley, 1998), xiv+780pp.+foldout. ISBN 0-201-89685-0
- เล่ม 4A: อัลกอริทึมแบบผสมผสาน ตอนที่ 1(อัปเปอร์แซดเดิลริเวอร์ รัฐนิวเจอร์ซีย์: แอดดิสัน-เวสลีย์ 2011) xvi+883pp. ISBN 0-201-03804-8
- เล่มที่ 4 Fascicle 6: ความพึงพอใจ- (แอดดิสัน-เวสลีย์มืออาชีพ, 2015), xiii+310pp. ISBN 978-0-13-439760-3
ก่อนหน้า
ตามวันที่ตีพิมพ์:
- เล่มที่ 1, พิมพ์ครั้งแรก 2511. 634หน้า. ISBN 0-201-03801-3 .
- เล่มที่ 2, พิมพ์ครั้งแรก, 1969, xi+624pp, ISBN 0-201-03802-1.
- เล่มที่ 3, พิมพ์ครั้งแรก, 1973, xi+723pp+พับกลาง, ISBN 0-201-03803-X
- เล่มที่ 1, พิมพ์ครั้งที่สอง, 1973, xiii+634pp, ISBN 0-201-03809-9.
- เล่มที่ 2, พิมพ์ครั้งที่สอง, 1981, xiii+ 688pp. ISBN 0-201-03822-6 .
- เล่มที่ 4 Fascicle 2: การสร้างสิ่งอันดับและการเรียงสับเปลี่ยนทั้งหมด, (แอดดิสัน-เวสลีย์ 14 กุมภาพันธ์ 2548) v+127pp, ISBN 0-201-85393-0
- เล่มที่ 4 Fascicle 3: การสร้างชุดค่าผสมและพาร์ติชันทั้งหมด- (แอดดิสัน-เวสลีย์ 26 กรกฎาคม 2548) vi+150pp, ISBN 0-201-85394-9
- เล่มที่ 4 Fascicle 4: การสร้างต้นไม้ทั้งหมด - ประวัติความเป็นมาของการสร้างแบบผสมผสาน, (แอดดิสัน-เวสลีย์ 6 กุมภาพันธ์ 2549) vi+120pp, ISBN 0-321-33570-8
- เล่มที่ 4 Fascicle 0: ความรู้เบื้องต้นเกี่ยวกับ Combinatorial Algorithms และ Boolean Functions, (Addison-Wesley Professional, 28 เมษายน 2551) vi+240pp, ISBN 0-321-53496-4
- เล่มที่ 4 Fascicle 1: เทคนิคและเทคนิคระดับ Bitwise แผนภาพการตัดสินใจแบบไบนารี(แอดดิสัน-เวสลีย์ โปรเฟสชันแนล, 27 มีนาคม 2552) viii+260pp,