EITC/IS/CCTF พื้นฐานทฤษฎีความซับซ้อนทางคอมพิวเตอร์
สถานะปัจจุบัน
ราคา
เริ่มต้นดำเนินการ
EITC/IS/CCTF Computational Complexity Theory Fundamentals เป็นโปรแกรม European IT Certification ในด้านทฤษฎีพื้นฐานของวิทยาการคอมพิวเตอร์ ซึ่งเป็นพื้นฐานของการเข้ารหัสคีย์สาธารณะแบบอสมมาตรแบบคลาสสิกที่ใช้กันอย่างแพร่หลายในอินเทอร์เน็ต
หลักสูตรพื้นฐานทฤษฎีความซับซ้อนในการคำนวณ EITC/IS/CCTF ครอบคลุมถึงความรู้ทางทฤษฎีเกี่ยวกับรากฐานของวิทยาการคอมพิวเตอร์และแบบจำลองการคำนวณบนแนวคิดพื้นฐาน เช่น เครื่องสถานะจำกัดแบบกำหนดและไม่กำหนด ภาษาปกติ ทฤษฎีไวยากรณ์และภาษาที่ปราศจากบริบท ทฤษฎีออโตมาตา เครื่องทัวริง ความสามารถในการตัดสินใจของปัญหา การเรียกซ้ำ ตรรกะ และความซับซ้อนของอัลกอริทึมสำหรับแอปพลิเคชันความปลอดภัยพื้นฐานภายในโครงสร้างต่อไปนี้ ซึ่งรวมถึงเอกสารการเรียนรู้ด้วยตนเองของหลักสูตรการรับรอง EITCI ที่ครอบคลุมและมีโครงสร้างที่รองรับโดยเนื้อหาการสอนวิดีโอแบบเปิดที่อ้างอิงเป็นพื้นฐานสำหรับการเตรียมความพร้อมในการได้รับการรับรอง EITC นี้โดยการผ่านการสอบที่เกี่ยวข้อง
ความซับซ้อนในการคำนวณของอัลกอริธึมคือปริมาณทรัพยากรที่จำเป็นในการดำเนินการ ทรัพยากรเวลาและหน่วยความจำได้รับความสนใจเป็นพิเศษ ความซับซ้อนของปัญหาถูกกำหนดให้เป็นความซับซ้อนของอัลกอริธึมที่ดีที่สุดสำหรับการแก้ปัญหา การวิเคราะห์อัลกอริธึมคือการศึกษาความซับซ้อนของอัลกอริธึมที่กำหนดอย่างชัดเจน ในขณะที่ทฤษฎีความซับซ้อนเชิงคำนวณคือการศึกษาความซับซ้อนของการแก้ปัญหาด้วยอัลกอริธึมที่รู้จักกันดีที่สุด โดเมนทั้งสองมีความเกี่ยวพันกันเนื่องจากความซับซ้อนของอัลกอริธึมมักเป็นข้อจำกัดบนความซับซ้อนของปัญหาที่จะแก้ไข นอกจากนี้ บ่อยครั้งจำเป็นต้องเปรียบเทียบความซับซ้อนของอัลกอริธึมบางอย่างกับความซับซ้อนของปัญหาที่จะแก้ไขในขณะที่สร้างอัลกอริธึมที่มีประสิทธิภาพ ในสถานการณ์ส่วนใหญ่ ข้อมูลเดียวที่มีเกี่ยวกับความยากของปัญหาคือน้อยกว่าความซับซ้อนของเทคนิคที่รู้จักมีประสิทธิภาพมากที่สุด ด้วยเหตุนี้ การวิเคราะห์อัลกอริทึมและทฤษฎีความซับซ้อนจึงมีความทับซ้อนกันเป็นอย่างมาก
ทฤษฎีความซับซ้อนมีบทบาทสำคัญไม่เพียงแต่ในพื้นฐานของแบบจำลองการคำนวณที่เป็นพื้นฐานสำหรับวิทยาการคอมพิวเตอร์เท่านั้น แต่ยังรวมถึงพื้นฐานของการเข้ารหัสแบบอสมมาตรแบบคลาสสิกด้วย (เรียกว่าการเข้ารหัสคีย์สาธารณะ) ซึ่งเผยแพร่อย่างกว้างขวางในเครือข่ายสมัยใหม่ โดยเฉพาะอย่างยิ่งในอินเทอร์เน็ต การเข้ารหัสคีย์สาธารณะขึ้นอยู่กับความยากในการคำนวณของปัญหาทางคณิตศาสตร์ที่ไม่สมมาตร เช่น การแยกตัวประกอบของตัวเลขจำนวนมากเป็นปัจจัยเฉพาะ (การดำเนินการนี้เป็นปัญหาที่ยากในการจำแนกทฤษฎีความซับซ้อน เนื่องจากไม่มีอัลกอริธึมแบบคลาสสิกที่มีประสิทธิภาพให้แก้ มันด้วยการปรับขนาดทรัพยากรแบบพหุนามมากกว่าแบบทวีคูณด้วยการเพิ่มขนาดอินพุตของปัญหา ซึ่งตรงกันข้ามกับการดำเนินการย้อนกลับที่ง่ายมากของการคูณกับปัจจัยเฉพาะที่ทราบเพื่อให้ได้จำนวนที่มากดั้งเดิม) การใช้ความไม่สมมาตรนี้ในสถาปัตยกรรมของการเข้ารหัสแบบพับลิกคีย์ (โดยการกำหนดความสัมพันธ์แบบอสมมาตรเชิงคำนวณระหว่างพับลิกคีย์ ซึ่งสามารถคำนวณได้ง่ายจากไพรเวตคีย์ ในขณะที่คีย์ส่วนตัวไม่สามารถเป็นคอมพิวเตอร์จากคีย์สาธารณะได้ง่ายๆ ประกาศคีย์สาธารณะและเปิดใช้งานด้านการสื่อสารอื่นๆ เพื่อใช้สำหรับการเข้ารหัสข้อมูลแบบอสมมาตร ซึ่งสามารถถอดรหัสได้ด้วยคีย์ส่วนตัวที่จับคู่กันเท่านั้น ไม่สามารถใช้กับบุคคลที่สามได้ ซึ่งทำให้การสื่อสารมีความปลอดภัย)
ทฤษฎีความซับซ้อนในการคำนวณได้รับการพัฒนาขึ้นโดยเน้นที่ความสำเร็จของวิทยาการคอมพิวเตอร์และผู้บุกเบิกอัลกอริธึม เช่น อลัน ทัวริง ซึ่งงานของเขามีส่วนสำคัญในการทำลายรหัสอินิกมาของนาซีเยอรมนี ซึ่งมีบทบาทสำคัญในพันธมิตรที่ชนะสงครามโลกครั้งที่สอง การเข้ารหัสมุ่งเป้าไปที่การคิดค้นและทำให้กระบวนการคำนวณของการวิเคราะห์ข้อมูลเป็นไปโดยอัตโนมัติ (การสื่อสารที่เข้ารหัสเป็นหลัก) เพื่อเปิดเผยข้อมูลที่ซ่อนอยู่ถูกใช้เพื่อละเมิดระบบการเข้ารหัสและเข้าถึงเนื้อหาของการสื่อสารที่เข้ารหัสซึ่งมักจะมีความสำคัญเชิงกลยุทธ์ทางทหาร นอกจากนี้ยังเป็นการเข้ารหัสลับซึ่งกระตุ้นการพัฒนาคอมพิวเตอร์สมัยใหม่เครื่องแรก (ซึ่งในขั้นต้นนำไปใช้กับเป้าหมายเชิงกลยุทธ์ของการทำลายโค้ด) British Colossus (ถือเป็นคอมพิวเตอร์อิเล็กทรอนิกส์และโปรแกรมสมัยใหม่เครื่องแรก) นำหน้าด้วย "bomb" ของโปแลนด์ ซึ่งเป็นอุปกรณ์คำนวณอิเล็กทรอนิกส์ที่ออกแบบโดย Marian Rejewski เพื่อช่วยในการทำลายรหัส Enigma และส่งมอบให้กับสหราชอาณาจักรโดยหน่วยข่าวกรองโปแลนด์พร้อมด้วย เครื่องเข้ารหัส Enigma ของเยอรมันที่ถูกจับได้ หลังจากที่โปแลนด์ถูกรุกรานโดยเยอรมนีในปี 1939 บนพื้นฐานของอุปกรณ์นี้ Alan Turing ได้พัฒนาอุปกรณ์คู่ที่ล้ำหน้ากว่าเพื่อทำลายการสื่อสารที่เข้ารหัสของเยอรมันได้สำเร็จ ซึ่งต่อมาได้พัฒนาเป็นคอมพิวเตอร์สมัยใหม่
เนื่องจากจำนวนทรัพยากรที่จำเป็นในการรันอัลกอริธึมนั้นแตกต่างกันไปตามขนาดของอินพุต ความซับซ้อนมักจะแสดงเป็นฟังก์ชัน f(n) โดยที่ n คือขนาดอินพุต และ f(n) เป็นความซับซ้อนของกรณีที่เลวร้ายที่สุด ( จำนวนทรัพยากรสูงสุดที่ต้องการจากอินพุตทั้งหมดที่มีขนาด n) หรือความซับซ้อนของตัวพิมพ์เฉลี่ย (ค่าเฉลี่ยของจำนวนทรัพยากรสำหรับอินพุตทั้งหมดที่มีขนาด n) จำนวนของการดำเนินการพื้นฐานที่จำเป็นสำหรับอินพุตขนาด n โดยทั่วไปจะระบุเป็นความซับซ้อนของเวลา โดยที่การดำเนินการเบื้องต้นเชื่อว่าจะใช้เวลาคงที่บนคอมพิวเตอร์เครื่องใดเครื่องหนึ่ง และเปลี่ยนแปลงโดยปัจจัยคงที่เท่านั้นเมื่อเรียกใช้บนเครื่องอื่น จำนวนหน่วยความจำที่อัลกอริทึมต้องการสำหรับอินพุตขนาด n เรียกว่าความซับซ้อนของพื้นที่
เวลาเป็นทรัพยากรที่มีการพิจารณามากที่สุด เมื่อใช้คำว่า "ความซับซ้อน" โดยไม่มีตัวระบุ มักจะหมายถึงความซับซ้อนของเวลา
หน่วยเวลาดั้งเดิม (วินาที นาที และอื่นๆ) ไม่ได้ใช้ในทฤษฎีความซับซ้อน เนื่องจากหน่วยเวลาเหล่านี้อาศัยคอมพิวเตอร์ที่เลือกไว้และความก้าวหน้าของเทคโนโลยีมากเกินไป ตัวอย่างเช่น คอมพิวเตอร์ในปัจจุบันสามารถรันอัลกอริธึมได้เร็วกว่าคอมพิวเตอร์ในทศวรรษที่ 1960 อย่างมาก แต่นี่เป็นเพราะความก้าวหน้าทางเทคโนโลยีในฮาร์ดแวร์คอมพิวเตอร์มากกว่าคุณภาพของอัลกอริธึมโดยธรรมชาติ เป้าหมายของทฤษฎีความซับซ้อนคือการหาปริมาณความต้องการด้านเวลาโดยธรรมชาติของอัลกอริทึม หรือข้อจำกัดด้านเวลาพื้นฐานที่อัลกอริทึมจะกำหนดในคอมพิวเตอร์ทุกเครื่อง ทำได้โดยการนับจำนวนการดำเนินการพื้นฐานระหว่างการคำนวณ ขั้นตอนเหล่านี้มักเรียกว่าขั้นตอน เนื่องจากถือว่าใช้เวลาคงที่ในเครื่องเฉพาะ (กล่าวคือ ไม่ได้รับผลกระทบจากปริมาณอินพุต)
ทรัพยากรที่สำคัญอีกประการหนึ่งคือจำนวนหน่วยความจำคอมพิวเตอร์ที่ต้องใช้ในการทำอัลกอริธึม
ทรัพยากรที่ใช้บ่อยอีกอย่างหนึ่งคือจำนวนการดำเนินการทางคณิตศาสตร์ ในสถานการณ์สมมตินี้ จะใช้คำว่า "ความซับซ้อนทางคณิตศาสตร์" ความซับซ้อนของเวลาโดยทั่วไปเป็นผลคูณของความซับซ้อนทางคณิตศาสตร์โดยปัจจัยคงที่ ถ้าทราบข้อจำกัดบนของขนาดของการแสดงเลขฐานสองของตัวเลขที่เกิดขึ้นระหว่างการคำนวณ
ขนาดของจำนวนเต็มที่ใช้ระหว่างการคำนวณไม่มีข้อจำกัดสำหรับวิธีการต่างๆ มากมาย และไม่สมจริงที่จะถือว่าการดำเนินการเลขคณิตต้องใช้เวลาในระยะเวลาที่แน่นอน เป็นผลให้ความซับซ้อนของเวลาหรือที่เรียกว่าความซับซ้อนของบิตอาจสูงกว่าความซับซ้อนทางคณิตศาสตร์อย่างมีนัยสำคัญ ความยากทางคณิตศาสตร์ของการคำนวณดีเทอร์มีแนนต์ของเมทริกซ์จำนวนเต็ม nn คือ O(n^3) สำหรับเทคนิคมาตรฐาน (การกำจัดแบบเกาส์เซียน) เนื่องจากขนาดของสัมประสิทธิ์อาจขยายตัวแบบทวีคูณในระหว่างการคำนวณ ความซับซ้อนของบิตของวิธีการเดียวกันจึงเป็นเลขชี้กำลังใน n หากเทคนิคเหล่านี้ใช้ร่วมกับเลขคณิตหลายโมดูล ความซับซ้อนของบิตจะลดลงเหลือ O(n^4)
ความซับซ้อนของบิต ในแง่ที่เป็นทางการ หมายถึงจำนวนการดำเนินการบนบิตที่จำเป็นในการรันอัลกอริธึม มันเท่ากับความซับซ้อนชั่วคราวจนถึงปัจจัยคงที่ในกระบวนทัศน์การคำนวณส่วนใหญ่ จำนวนการดำเนินการของคำเครื่องที่คอมพิวเตอร์ต้องการเป็นสัดส่วนกับความซับซ้อนของบิต สำหรับแบบจำลองการคำนวณที่เหมือนจริง ความซับซ้อนของเวลาและความซับซ้อนของบิตจึงเหมือนกัน
ทรัพยากรที่มักจะพิจารณาในการเรียงลำดับและการค้นหาคือจำนวนของการเปรียบเทียบรายการ หากมีการจัดเรียงข้อมูลอย่างดี นี่เป็นตัวบ่งชี้ที่ดีของความซับซ้อนของเวลา
สำหรับอินพุตที่เป็นไปได้ทั้งหมด การนับจำนวนขั้นตอนในอัลกอริธึมเป็นไปไม่ได้ เนื่องจากความซับซ้อนของอินพุตเพิ่มขึ้นตามขนาด โดยทั่วไปจะแสดงเป็นฟังก์ชันของขนาดของอินพุต n (เป็นบิต) ดังนั้นความซับซ้อนจึงเป็นฟังก์ชันของ n อย่างไรก็ตาม สำหรับอินพุตที่มีขนาดเท่ากัน ความซับซ้อนของอัลกอริธึมอาจแตกต่างกันอย่างมาก เป็นผลให้มีการใช้ฟังก์ชันความซับซ้อนที่หลากหลายเป็นประจำ
ความซับซ้อนของกรณีที่เลวร้ายที่สุดคือผลรวมของความซับซ้อนทั้งหมดสำหรับอินพุต n ทุกขนาด ในขณะที่ความซับซ้อนของเคสเฉลี่ยคือผลรวมของความซับซ้อนทั้งหมดสำหรับอินพุต n ทุกขนาด (เป็นเรื่องที่สมเหตุสมผล เนื่องจากจำนวนอินพุตที่เป็นไปได้ของขนาดที่กำหนดคือ จำกัด) เมื่อใช้คำว่า "ความซับซ้อน" โดยไม่มีการกำหนดเพิ่มเติม ความซับซ้อนของเวลาที่แย่ที่สุดจะถูกนำมาพิจารณาด้วย
ความซับซ้อนกรณีที่เลวร้ายที่สุดและกรณีเฉลี่ยเป็นเรื่องยากที่จะคำนวณอย่างถูกต้องอย่างฉาวโฉ่ นอกจากนี้ ค่าที่แน่นอนเหล่านี้ยังนำไปใช้ได้จริงเพียงเล็กน้อย เนื่องจากการเปลี่ยนแปลงใดๆ ในเครื่องจักรหรือกระบวนทัศน์การคำนวณจะทำให้ความซับซ้อนแตกต่างกันเล็กน้อย นอกจากนี้ การใช้ทรัพยากรไม่สำคัญสำหรับค่า n เล็กน้อย ดังนั้นความง่ายในการนำไปปฏิบัติมักจะน่าสนใจมากกว่าความซับซ้อนต่ำสำหรับ n เล็กน้อย
ด้วยเหตุผลเหล่านี้ ความสนใจส่วนใหญ่จะจ่ายให้กับพฤติกรรมของความซับซ้อนสำหรับ n สูง นั่นคือพฤติกรรมเชิงซีมโทติกเมื่อ n เข้าใกล้อนันต์ ด้วยเหตุนี้ จึงมักใช้สัญกรณ์ O ขนาดใหญ่เพื่อระบุความซับซ้อน
แบบจำลองการคำนวณ
การเลือกแบบจำลองการคำนวณ ซึ่งประกอบด้วยการระบุการดำเนินการที่จำเป็นซึ่งดำเนินการในหน่วยเวลา เป็นสิ่งสำคัญในการพิจารณาความซับซ้อน บางครั้งเรียกว่าเครื่องทัวริงแบบมัลติเทปเมื่อไม่ได้อธิบายกระบวนทัศน์การคำนวณไว้โดยเฉพาะ
แบบจำลองการคำนวณเชิงกำหนดเป็นแบบจำลองที่สถานะต่อมาของเครื่องและการดำเนินการที่จะดำเนินการถูกกำหนดโดยสถานะก่อนหน้าทั้งหมด ฟังก์ชันแบบเรียกซ้ำ แคลคูลัสแลมบ์ดา และเครื่องจักรทัวริงเป็นแบบจำลองที่กำหนดขึ้นครั้งแรก เครื่องสุ่มเข้าถึง (หรือที่เรียกว่าเครื่อง RAM) เป็นกระบวนทัศน์ที่นิยมสำหรับการจำลองคอมพิวเตอร์ในโลกแห่งความเป็นจริง
เมื่อไม่ได้กำหนดรูปแบบการคำนวณ ปกติเครื่องมัลติเทปทัวริงจะถือว่า สำหรับเครื่อง Turing แบบมัลติเทป ความซับซ้อนของเวลาจะเหมือนกับบนเครื่อง RAM สำหรับอัลกอริธึมส่วนใหญ่ แม้ว่าอาจต้องให้ความสนใจอย่างมากกับวิธีที่ข้อมูลถูกจัดเก็บไว้ในหน่วยความจำเพื่อให้ได้ความเท่าเทียมกันนี้
อาจมีทางเลือกหลายอย่างในขั้นตอนการคำนวณในรูปแบบการคำนวณที่ไม่ได้กำหนดไว้ล่วงหน้า เช่น เครื่องทัวริงที่ไม่ได้กำหนดไว้ล่วงหน้า ในทฤษฎีความซับซ้อน ตัวเลือกที่เป็นไปได้ทั้งหมดจะได้รับการพิจารณาในเวลาเดียวกัน และความซับซ้อนของเวลาที่ไม่สามารถกำหนดได้คือระยะเวลาที่ต้องใช้เมื่อมีการเลือกตัวเลือกที่ดีที่สุดเสมอ ในอีกทางหนึ่ง การคำนวณจะทำพร้อมกันบนโปรเซสเซอร์ (ตัวเดียวกัน) ได้มากเท่าที่จำเป็น และเวลาการคำนวณที่ไม่ได้กำหนดคือเวลาที่โปรเซสเซอร์ตัวแรกใช้ในการคำนวณให้เสร็จสิ้น ความขนานนี้สามารถใช้ในการคำนวณควอนตัมโดยใช้สถานะพัวพันทับซ้อนเมื่อรันอัลกอริธึมควอนตัมเฉพาะเช่นการแยกตัวประกอบของ Shor ของจำนวนเต็มขนาดเล็ก
แม้ว่าแบบจำลองการคำนวณดังกล่าวจะไม่สามารถทำได้ในปัจจุบัน แต่ก็มีนัยสำคัญทางทฤษฎี โดยเฉพาะอย่างยิ่งในความสัมพันธ์กับปัญหา P = NP ซึ่งถามว่าคลาสความซับซ้อนที่สร้างขึ้นโดยใช้ "เวลาพหุนาม" และ "เวลาพหุนามแบบไม่กำหนด" อย่างน้อยที่สุด ขอบเขตเหมือนกัน ในคอมพิวเตอร์ที่กำหนดขึ้นเอง การจำลองอัลกอริทึม NP ต้องใช้ "เวลาแบบเอ็กซ์โปเนนเชียล" หากงานสามารถแก้ไขได้ในเวลาพหุนามบนระบบที่ไม่กำหนดไว้ งานนั้นจะอยู่ในคลาสความยาก NP หากปัญหาอยู่ใน NP และไม่ง่ายกว่าปัญหา NP อื่นๆ จะเรียกว่า NP-complete ปัญหาเป้ ปัญหาพนักงานขายที่เดินทาง และปัญหาความพึงพอใจแบบบูลีน ล้วนเป็นปัญหาแบบผสมผสานที่สมบูรณ์ของ NP อัลกอริธึมที่เป็นที่รู้จักมากที่สุดมีความซับซ้อนแบบทวีคูณสำหรับปัญหาเหล่านี้ทั้งหมด หากปัญหาใด ๆ เหล่านี้สามารถแก้ไขได้ในเวลาพหุนามบนเครื่องที่กำหนดขึ้นเอง ปัญหา NP ทั้งหมดก็สามารถแก้ไขได้ในเวลาพหุนามเช่นกัน และ P = NP จะถูกสร้างขึ้น ณ ปี 2017 เป็นที่สันนิษฐานกันอย่างกว้างขวางว่า P NP หมายความว่าสถานการณ์ที่เลวร้ายที่สุดของปัญหา NP นั้นยากต่อการแก้ไขโดยพื้นฐาน กล่าวคือ ใช้เวลานานกว่าช่วงระยะเวลาที่เป็นไปได้ (ทศวรรษ) มาก เนื่องจากมีความยาวอินพุตที่น่าสนใจ
การคำนวณแบบขนานและแบบกระจาย
การคำนวณแบบขนานและแบบกระจายเกี่ยวข้องกับการแบ่งการประมวลผลในโปรเซสเซอร์หลายตัวที่ทำงานพร้อมกันทั้งหมด ความแตกต่างพื้นฐานระหว่างรุ่นต่างๆ คือวิธีการส่งข้อมูลระหว่างโปรเซสเซอร์ การส่งข้อมูลระหว่างโปรเซสเซอร์มักจะรวดเร็วมากในการประมวลผลแบบคู่ขนาน ในขณะที่การถ่ายโอนข้อมูลระหว่างโปรเซสเซอร์ในการคำนวณแบบกระจายนั้นทำผ่านเครือข่ายและทำให้ช้าลงอย่างมาก
การคำนวณบนตัวประมวลผล N จะใช้เวลาอย่างน้อยผลหารโดย N ของเวลาที่ใช้กับโปรเซสเซอร์ตัวเดียว ในความเป็นจริง เนื่องจากงานย่อยบางงานไม่สามารถขนานกันได้ และตัวประมวลผลบางตัวอาจต้องรอผลลัพธ์จากตัวประมวลผลอื่น การผูกมัดในอุดมคติทางทฤษฎีนี้จะไม่มีวันบรรลุผล
ปัญหาความซับซ้อนที่สำคัญคือต้องพัฒนาอัลกอริธึมเพื่อให้ผลคูณของเวลาในการคำนวณตามจำนวนโปรเซสเซอร์ใกล้เคียงกับเวลาที่ต้องใช้ในการคำนวณแบบเดียวกันบนโปรเซสเซอร์ตัวเดียว
การคำนวณควอนตัม
คอมพิวเตอร์ควอนตัมคือคอมพิวเตอร์ที่มีรูปแบบการคำนวณที่ใช้กลศาสตร์ควอนตัม วิทยานิพนธ์ของศาสนจักร–ทัวริงเป็นความจริงสำหรับคอมพิวเตอร์ควอนตัม หมายความว่าปัญหาใดๆ ที่คอมพิวเตอร์ควอนตัมสามารถแก้ไขได้อาจแก้ไขได้ด้วยเครื่องทัวริง อย่างไรก็ตาม งานบางอย่างในทางทฤษฎีอาจแก้ไขได้โดยใช้คอมพิวเตอร์ควอนตัมมากกว่าคอมพิวเตอร์แบบคลาสสิกที่มีความซับซ้อนทางโลกที่ต่ำกว่าอย่างเห็นได้ชัด ในขณะนี้ นี่เป็นทฤษฎีที่เคร่งครัด เนื่องจากไม่มีใครรู้วิธีพัฒนาคอมพิวเตอร์ควอนตัมที่ใช้งานได้จริง
ทฤษฎีความซับซ้อนของควอนตัมถูกสร้างขึ้นเพื่อตรวจสอบปัญหาประเภทต่างๆ ที่คอมพิวเตอร์ควอนตัมสามารถแก้ไขได้ ใช้ในการเข้ารหัสหลังควอนตัม ซึ่งเป็นกระบวนการสร้างโปรโตคอลการเข้ารหัสที่ทนทานต่อการโจมตีด้วยคอมพิวเตอร์ควอนตัม
ความซับซ้อนของปัญหา (ขอบเขตล่าง)
ความซับซ้อนของอัลกอริธึมที่อาจช่วยแก้ปัญหาได้ รวมถึงเทคนิคที่ยังไม่ได้ค้นพบคือความซับซ้อนของปัญหา เป็นผลให้ความซับซ้อนของปัญหาเท่ากับความซับซ้อนของอัลกอริธึมที่แก้ปัญหาได้
ด้วยเหตุนี้ ความซับซ้อนใดๆ ที่ระบุในสัญกรณ์ O ขนาดใหญ่แสดงถึงความซับซ้อนของทั้งอัลกอริทึมและปัญหาที่เกี่ยวข้อง
ในทางกลับกัน การได้มาซึ่งขอบเขตล่างที่ไม่สำคัญเกี่ยวกับความซับซ้อนของปัญหามักจะเป็นเรื่องยาก และมีกลยุทธ์บางอย่างสำหรับการทำเช่นนั้น
ในการแก้ปัญหาส่วนใหญ่ ต้องอ่านข้อมูลที่ป้อนเข้าไปทั้งหมด ซึ่งต้องใช้เวลาตามสัดส่วนของขนาดของข้อมูล ด้วยเหตุนี้ ปัญหาดังกล่าวจึงมีความซับซ้อนเชิงเส้นเป็นอย่างน้อย หรือในสัญกรณ์โอเมก้าขนาดใหญ่ ความซับซ้อนคือ Ω(n)
ปัญหาบางอย่าง เช่น ปัญหาในพีชคณิตคอมพิวเตอร์และเรขาคณิตเชิงพีชคณิตเชิงคำนวณ มีวิธีแก้ปัญหาที่ใหญ่มาก เนื่องจากต้องเขียนเอาต์พุต ความซับซ้อนจึงถูกจำกัดด้วยขนาดสูงสุดของเอาต์พุต
จำนวนการเปรียบเทียบที่จำเป็นสำหรับอัลกอริธึมการเรียงลำดับมีขอบเขตล่างที่ไม่เป็นเชิงเส้นของ Ω(nlogn) ด้วยเหตุนี้ อัลกอริธึมการเรียงลำดับที่ดีที่สุดจึงมีประสิทธิภาพมากที่สุด เนื่องจากความซับซ้อนของอัลกอริธึมคือ O(nlogn) ความจริงที่ว่ามี n! วิธีจัดระเบียบสิ่งของ n อย่างนำไปสู่ขอบเขตล่างนี้ เพราะการเปรียบเทียบแต่ละครั้งแบ่งคอลเลกชันนี้ของ n! คำสั่งออกเป็นสองชิ้น จำนวน N การเปรียบเทียบที่จำเป็นในการแยกแยะคำสั่งซื้อทั้งหมดต้องเป็น 2N > n! ซึ่งหมายถึง O(nlogn) ตามสูตรของสเตอร์ลิง
การลดปัญหาไปสู่ปัญหาอื่นเป็นกลยุทธ์ทั่วไปในการรับข้อจำกัดด้านความซับซ้อนที่ลดลง
การพัฒนาอัลกอริทึม
การประเมินความซับซ้อนของอัลกอริธึมเป็นองค์ประกอบสำคัญของกระบวนการออกแบบ เนื่องจากมีข้อมูลที่เป็นประโยชน์เกี่ยวกับประสิทธิภาพที่คาดหวัง
เป็นความเข้าใจผิดอยู่บ่อยครั้งว่า จากผลของกฎของมัวร์ ซึ่งทำนายการเติบโตแบบทวีคูณของพลังคอมพิวเตอร์สมัยใหม่ การประเมินความซับซ้อนของอัลกอริธึมจะมีความเกี่ยวข้องน้อยลง สิ่งนี้ไม่ถูกต้อง เนื่องจากกำลังที่เพิ่มขึ้นทำให้สามารถประมวลผลข้อมูลจำนวนมหาศาลได้ (ข้อมูลขนาดใหญ่) ตัวอย่างเช่น อัลกอริธึมใด ๆ ควรทำงานได้ดีในเวลาไม่ถึงวินาทีเมื่อเรียงลำดับตามตัวอักษรของรายการสองสามร้อยรายการ เช่น บรรณานุกรมของหนังสือ ในทางกลับกัน สำหรับหนึ่งล้านรายการ (เช่น หมายเลขโทรศัพท์ของเมืองใหญ่) อัลกอริธึมพื้นฐานที่ต้องมีการเปรียบเทียบ O(n2) จะต้องทำการเปรียบเทียบหลายล้านล้านรายการ ซึ่งจะใช้เวลาสามชั่วโมงที่ความเร็ว 10 ล้านการเปรียบเทียบต่อวินาที ในทางกลับกัน Quicksort และ merge sort ต้องการการเปรียบเทียบ nlogn เท่านั้น (เป็นความซับซ้อนของตัวพิมพ์เฉลี่ยสำหรับอดีต สิ่งนี้สร้างการเปรียบเทียบประมาณ 30,000,000 สำหรับ n = 1,000,000 ซึ่งจะใช้เวลาเพียง 3 วินาทีที่ 10 ล้านการเปรียบเทียบต่อวินาที
ด้วยเหตุนี้ การประเมินความซับซ้อนอาจช่วยให้สามารถขจัดอัลกอริธึมที่ไม่มีประสิทธิภาพจำนวนมากได้ก่อนที่จะนำไปปฏิบัติ นอกจากนี้ยังสามารถใช้เพื่อปรับแต่งอัลกอริธึมที่ซับซ้อนโดยไม่ต้องทดสอบตัวแปรที่เป็นไปได้ทั้งหมด การศึกษาความซับซ้อนช่วยให้มุ่งเน้นความพยายามในการเพิ่มประสิทธิภาพของการนำไปใช้โดยกำหนดขั้นตอนที่แพงที่สุดของอัลกอริทึมที่ซับซ้อน
หากต้องการทราบรายละเอียดเกี่ยวกับหลักสูตรการรับรอง คุณสามารถขยายและวิเคราะห์ตารางด้านล่างได้
หลักสูตรการรับรองพื้นฐานทฤษฎีความซับซ้อนในการคำนวณ EITC/IS/CCTF อ้างอิงถึงเนื้อหาการสอนแบบเปิดในรูปแบบวิดีโอ กระบวนการเรียนรู้แบ่งออกเป็นโครงสร้างแบบทีละขั้นตอน (โปรแกรม -> บทเรียน -> หัวข้อ) ครอบคลุมส่วนต่างๆ ของหลักสูตรที่เกี่ยวข้อง ผู้เข้าร่วมสามารถเข้าถึงคำตอบและถามคำถามที่เกี่ยวข้องเพิ่มเติมได้ในส่วนคำถามและคำตอบของอินเทอร์เฟซการเรียนรู้ทางอิเล็กทรอนิกส์ภายใต้หัวข้อหลักสูตรของโปรแกรม EITC ที่กำลังดำเนินการอยู่ในปัจจุบัน นอกจากนี้ ยังสามารถเข้าถึงคำปรึกษากับผู้เชี่ยวชาญในสาขาโดยตรงและไม่จำกัดได้ผ่านระบบส่งข้อความออนไลน์ที่บูรณาการกับแพลตฟอร์ม รวมถึงผ่านแบบฟอร์มติดต่อ
สำหรับรายละเอียดการตรวจสอบขั้นตอนการรับรอง มันทำงานอย่างไร.
เอกสารประกอบการอ่านหลักสูตรปฐมวัยที่สนับสนุน
S. Arora, B. Barak, ความซับซ้อนของการคำนวณ: แนวทางสมัยใหม่
https://theory.cs.princeton.edu/complexity/book.pdf
เอกสารประกอบการอ่านหลักสูตรสนับสนุนระดับมัธยมศึกษา
O. Goldreich ทฤษฎีความซับซ้อนเบื้องต้น:
https://www.wisdom.weizmann.ac.il/~oded/cc99.html
เอกสารสนับสนุนการอ่านหลักสูตรเกี่ยวกับคณิตศาสตร์ที่ไม่ต่อเนื่อง
J. Aspnes หมายเหตุเกี่ยวกับคณิตศาสตร์แบบไม่ต่อเนื่อง:
https://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf
เอกสารสนับสนุนการอ่านหลักสูตรเกี่ยวกับทฤษฎีกราฟ
R. Diestel ทฤษฎีกราฟ:
https://diestel-graph-theory.com/
ดาวน์โหลดเอกสารเตรียมการเรียนรู้ด้วยตนเองแบบออฟไลน์ฉบับสมบูรณ์สำหรับโปรแกรม EITC/IS/CCTF Computational Complexity Theory Fundamentals ในรูปแบบไฟล์ PDF
เอกสารการเตรียมการ EITC/IS/CCTF – เวอร์ชันมาตรฐาน