เร็วกว่าเบราว์เซอร์!
17 ความสัมพันธ์: บิตกลุ่มความซับซ้อน พี และ เอ็นพีการค้นหาแบบทวิภาคการแยกตัวประกอบจำนวนเต็มลอการิทึมสัญกรณ์โอใหญ่สตริงหน่วยประมวลผลกลางจำนวนเฉพาะทฤษฎีการคำนวณทฤษฎีการคำนวณได้ปัญหาการตัดสินใจปัญหาความสอดคล้องแบบบูลเลขฐานสองเอ็นพี (ความซับซ้อน)เอ็นพีบริบูรณ์เครื่องทัวริง
บิต
ต (bit) เป็นหน่วยข้อมูลที่เล็กที่สุด ใช้ระบบคอมพิวเตอร์แบบดิจิทัลและทฤษฎีข้อมูล ข้อมูลหนึ่งบิต มีสถานะที่เป็นไปได้ 2 สถานะ คือ.
ใหม่!!: ทฤษฎีความซับซ้อนในการคำนวณและบิต · ดูเพิ่มเติม »
กลุ่มความซับซ้อน พี และ เอ็นพี
รูปแสดงความกลุ่มความซับซ้อนในกรณี '''P''' ≠ '''NP'''. ถ้า '''P'''.
ใหม่!!: ทฤษฎีความซับซ้อนในการคำนวณและกลุ่มความซับซ้อน พี และ เอ็นพี · ดูเพิ่มเติม »
การค้นหาแบบทวิภาค
ในสาขาวิทยาการคอมพิวเตอร์ การค้นหาแบบทวิภาค (binary search, half-interval search หรือ bisection search) เป็นขั้นตอนวิธีเพื่อหาตำแหน่งของค่าที่ต้องการ (ข้อมูลนำเข้า หรือ "key") ที่ใช้ในแถวลำดับที่ได้มีการเรียงลำดับข้อมูลแล้ว ขั้นตอนวิธีจะเริ่มจากเปรียบเทียบข้อมูลที่นำเข้ากับข้อมูลที่อยู่ตรงกลางของแถวลำดับ ถ้าข้อมูลมีค่าเท่ากันแสดงว่าพบ "คีย์" ที่ต้องการ อาจจะทำการคืนค่าตำแหน่งหรือในที่นี้คือ ดัชนี (index) กลับไป มิฉะนั้นถ้าค่าของข้อมูลนำเข้าที่ต้องการค้นหามีการน้อยกว่าค่าตรงกลางของแถวลำดับ ก็จะทำขั้นตอนวิธีนี้อีกครั้งแต่เปลี่ยนมาค้นหาในแถวลำดับย่อยของแถวลำดับที่ต้องการค้นหาโดยแถวลำดับย่อยจะมีจุดสิ้นสุดที่ตรงกลางของแถวลำดับหลัก หรือถ้าข้อมูลที่ต้องการค้นหามีค่ามากกว่าแล้วจะค้นหาในแถวลำดับย่อยเช่นกันแต่ย้ายจุดเริ่มต้นมาที่ตรงกลางของแถวลำดับหลัก เมื่อทำไปจนแถวลำดับไม่มีสมาชิกอยู่หรือจุดเริ่มต้นมากกว่าจุดสิ้นสุด แสดงว่าไม่มีสมาชิกในแถวลำดับตัวใดที่มีค่าเท่ากับข้อมูลนำเข้าที่ต้องการค้นหา อาจจะคืนค่าว่า "ไม่พบ" การค้นหาแบบทวิภาคจะแบ่งครึ่งชุดข้อมูลที่ต้องการค้นหา ดังนั้นจึงจัดให้การค้นหาแบบทวิภาคเป็นขั้นตอนวิธีแบ่งแยกและเอาชนะ และขั้นตอนวิธีการค้นห.
ใหม่!!: ทฤษฎีความซับซ้อนในการคำนวณและการค้นหาแบบทวิภาค · ดูเพิ่มเติม »
การแยกตัวประกอบจำนวนเต็ม
ในทฤษฎีจำนวน การแยกตัวประกอบจำนวนเต็ม (integer factorization) หรือ การแยกตัวประกอบเฉพาะ (prime factorization) คือการแบ่งย่อยจำนวนประกอบออกเป็นตัวหารไม่ชัด (ตัวหารที่ไม่ใช่ 1 กับ ตัวมันเอง) หลายๆ ตัว ซึ่งเมื่อคูณตัวหารไม่ชัดเหล่านั้นเข้าด้วยกันจะได้ผลลัพธ์ดังเดิม เมื่อจำนวนมีขนาดใหญ่มาก ไม่มีขั้นตอนวิธีการแยกตัวประกอบของจำนวนเต็มใดๆ ที่มีประสิทธิภาพเพียงพอ ในปี 2009 ความพยายามในการแยกตัวประกอบของเลข 232 หลัก ได้สำเร็จลง จากการใช้เครื่องจักรมากกว่า 100 เครื่องภายในระยะเวลา 2 ปี ความยากของปัญหาแหละนี้คือหัวใจของขั้นตอนวิธีบางอย่างในวิทยาการเข้ารหัสลับ เช่น RSA จำนวนที่มีความยาวเท่ากัน ใช่ว่าจะแยกตัวประกอบด้วยความยากเท่ากัน กรณีที่ยากที่สุดของปัญหาเหล่านี้ (สำหรับกลวิธีที่รู้กันในปัจจุบัน) คือจำนวนครึ่งเฉพาะ (semiprime) ซึ่งก็คือจำนวนที่เป็นผลคูณของจำนวนเฉพาะ 2 ตัว จากทฤษฎีบทมูลฐานของเลขคณิต จำนวนเต็มบวกทุกตัวจะมีการแยกตัวประกอบเฉพาะที่แตกต่างกัน.
ใหม่!!: ทฤษฎีความซับซ้อนในการคำนวณและการแยกตัวประกอบจำนวนเต็ม · ดูเพิ่มเติม »
ลอการิทึม
ีม่วงคือฐาน 1.7 กราฟทุกเส้นผ่านจุด (1, 0) เนื่องจากจำนวนใด ๆ ที่ไม่เป็นศูนย์ เมื่อยกกำลัง 0 แล้วได้ 1 และกราฟทุกเส้นผ่านจุด (''b'', 1) สำหรับฐาน ''b'' เพราะว่าจำนวนใด ๆ ยกกำลัง 1 แล้วได้ค่าเดิม เส้นโค้งทางซ้ายเข้าใกล้แกน ''y'' แต่ไม่ตัดกับแกน ''y'' เพราะมีภาวะเอกฐานอยู่ที่ ''x''.
ใหม่!!: ทฤษฎีความซับซ้อนในการคำนวณและลอการิทึม · ดูเพิ่มเติม »
สัญกรณ์โอใหญ่
ตัวอย่างของสัญกรณ์โอใหญ่ โดย ''f''(''x'') ∈ O(''g''(''x'')) ซึ่งหมายความว่ามี ''c'' > 0 (เช่น ''c''.
ใหม่!!: ทฤษฎีความซับซ้อนในการคำนวณและสัญกรณ์โอใหญ่ · ดูเพิ่มเติม »
สตริง
ตริง (string) อาจหมายถึง.
ใหม่!!: ทฤษฎีความซับซ้อนในการคำนวณและสตริง · ดูเพิ่มเติม »
หน่วยประมวลผลกลาง
หน่วยประมวลผลกลาง (central processing unit) หรือย่อว่า ซีพียู (CPU) เป็นวงจรอิเลคทรอนิกส์ที่ทำงาน หรือประมวลผล ตามชุดของคำสั่งเครื่องจากซอฟต์แวร์ คำนี้เริ่มใช้ในอุตสาหกรรมคอมพิวเตอร์ตั้งแต่ต้นศตวรรษ 1960s หน่วยประมวลผลเปรียบเสมือนเป็นสมองของคอมพิวเตอร์ ในการทำหน้าที่ตัดสินใจหรือคำนวณ จากคำสั่งที่ได้รับมา เช่น การเปรียบเทียบ การกระทำการทางคณิตศาสตร์ ฯลฯ โดยมีกระบวนการพื้นฐานคือ.
ใหม่!!: ทฤษฎีความซับซ้อนในการคำนวณและหน่วยประมวลผลกลาง · ดูเพิ่มเติม »
จำนวนเฉพาะ
ในคณิตศาสตร์ จำนวนเฉพาะ (อังกฤษ: prime number) คือ จำนวนเต็มบวกที่มีตัวหารที่เป็นบวกอยู่ 2 ตัว คือ 1 กับตัวมันเอง ตรงข้ามกับจำนวนประกอบ ลำดับของจำนวนเฉพาะเริ่มต้นด้วย ดูบทความ รายชื่อจำนวนเฉพาะ สำหรับจำนวนเฉพาะ 500 จำนวนแรก สำหรับเลข 1 ไม่ถือว่าเป็นจำนวนเฉพาะตามนิยาม เซตของจำนวนเฉพาะทั้งหมดมักเขียนแทนด้วย \mathbb P เนื่องจาก 2 เป็นจำนวนเฉพาะตัวเดียวที่เป็นเลขคู่ ดังนั้นคำว่า จำนวนเฉพาะคี่ จะถูกใช้เพื่อหมายถึงจำนวนเฉพาะทั้งหมดที่ไม่ใช่ 2.
ใหม่!!: ทฤษฎีความซับซ้อนในการคำนวณและจำนวนเฉพาะ · ดูเพิ่มเติม »
ทฤษฎีการคำนวณ
การศึกษาเกี่ยวกับ ทฤษฎีการคำนวณ เริ่มขึ้นเมื่อต้นศตวรรษที่ยี่สิบ ก่อนจะมีการคิดค้นคอมพิวเตอร์อิเล็กทรอนิกส์ขึ้น ในช่วงเวลาดังกล่าว นักคณิตศาสตร์ได้เริ่มศึกษาว่า ปัญหาทางคณิตศาสตร์ใดบ้างที่สามารถแก้ได้ด้วยวิธีพื้นฐาน และปัญหาใดที่ไม่สามารถแก้ได้ ขั้นตอนแรกก็คือการนิยามให้ได้ว่าวิธีพื้นฐานในการแก้ปัญหานั้นคืออะไรบ้าง นั่นคือ พวกเขาต้องการโมเดลอย่างเป็นทางการของการคำนวณ (formal model of computation) ได้มีการสร้างโมเดลในรูปแบบต่างๆ มากมาย โมเดลเครื่องจักรทัวริงมองการคำนวณเป็นการทำงานของเครื่องจักรที่ทำงานบนเทปเก็บตัวอักษรที่มีความยาวไม่จำกัด โดยมีหัวอ่าน/เขียนที่จะทำงานกับช่องบนเทปทีละช่อง อีกโมเดลหนึ่งพิจารณาการคำนวณผ่านทางฟังก์ชันเวียนบังเกิด ซึ่งใช้ฟังก์ชันและการประกอบกัน (composition) ของฟังก์ชันที่ทำงานบนตัวเลข โมเดลแลมดาแคลคูลัสใช้วิธีคล้ายๆกัน นอกจากนี้ยังมีโมเดลอื่นๆ เช่น ขั้นตอนวิธีของมาคอฟและระบบของโพสต์ที่ใช้ไวยากรณ์บนสตริง โมเดลทางการต่างๆเหล่านี้ได้รับการแสดงว่ามีความสามารถเทียบเท่ากัน นั่นคือ การคำนวณใดๆที่กระทำได้โดยโมเดลหนึ่งจะสามารถทำได้ในอีกโมเดลด้วยเช่นกัน โมเดลเหล่านี้ยังมีความสามารถเท่ากันกับเครื่องคอมพิวเตอร์ทั่วไปที่เราใช้อยู่ ถ้าเราสมมติว่าเครื่องคอมพิวเตอร์นั้นมีหน่วยความจำไม่รู้จบ นอกจากนี้ ยังเป็นที่เชื่อกันอีกว่า ทุกๆ โมเดลการคำนวณที่ "สมเหตุสมผล" จะมีความสามารถเทียบเท่ากับเครื่องจักรทัวริ่ง ซึ่งความเชื่อนี้เรียกว่า ข้อปัญหาของเชิร์ช-ทัวริง (Church-Turing thesis) ศาสตร์ที่ศึกษาเกี่ยวกับขอบเขตของปัญหาที่คำนวณได้ด้วยโมเดลของเครื่องจักรแบบต่างๆนั้นคือ ทฤษฎีการคำนวณได้ ทฤษฎีการคำนวณศึกษาโมเดลการคำนวณ พร้อมๆกับขีดจำกัดของการคำนวณ เช่น ปัญหาใดที่สามารถพิสูจน์ได้ว่าไม่สามารถแก้ได้ด้วยคอมพิวเตอร์? (ดู ปัญหาการยุติการทำงาน หรือ ปัญหาความสัมพันธ์ของโพสต์) ปัญหาใดบ้างที่สามารถแก้ไขได้ด้วยคอมพิวเตอร์ แต่ต้องการเวลามหาศาลจนทำให้การหาคำตอบนั้นเป็นไปไม่ได้ (ดู:en:Presburger arithmetic) การหาคำตอบยากกว่าการตรวจคำตอบของปัญหาหรือไม่ (ดู กลุ่มความซับซ้อน พี และ เอ็นพี) ศาสตร์ที่ศึกษาเกี่ยวกับเวลาและเนื้อที่ที่ต้องการสำหรับปัญหาต่างๆ คือ ทฤษฎีความซับซ้อนในการคำนวณ นอกจากโมเดลในการคำนวณทั่วไปแล้ว ยังมีรูปแบบในการคำนวณอื่นๆ ที่ง่ายกว่านั้น เช่น โมเดลของนิพจน์ปรกติ ที่เป็นวิธีที่ใช้กำหนดรูปแบบของสตริงในยูนิกซ์ และในบางภาษาคอมพิวเตอร์ เช่น ภาษาเพิร์ล โดยมีโมเดล เช่น เครื่องจักรสถานะจำกัดที่มีความสามารถเทียบเท่ากัน โมเดลที่มีความสามารถกว่าโมเดลนิพจน์ regular เช่น โมเดลที่อธิบายการคำนวณผ่านทางไวยากรณ์ที่ไม่ขึ้นกับสภาพรอบข้าง (context-free grammar) ใช้สำหรับระบุไวยากรณ์ของภาษาโปรแกรม โดยที่มีเครื่องจักรกดลง (pushdown automata) เป็นอีกรูปแบบที่เทียบเท่ากัน ฟังก์ชันเวียนบังเกิดพื้นฐานก็เป็นโมเดลย่อยของฟังก์ชันเวียนบังเกิด โมเดลที่แตกต่างกันอาจมีความสามารถที่แตกต่างกันได้ อีกวิธีหนึ่งที่จะวัดความสามารถของโมเดลต่างๆ ก็คือการศึกษากลุ่มของภาษาทางการ (formal language) ที่โมเดลเหล่านั้นสามารถสร้างได้ ยกตัวอย่างเช่น เครื่องจักรสถานะจำกัดสามารถสร้างได้เพียงภาษาที่เทียบเท่ากับนิพจน์ regular ส่วนเครื่องจักรกดลงนั้นสามารถสร้างภาษาที่ระบุด้วยไวยากรณ์ที่ไม่ขึ้นกับสภาพรอบข้างได้ด้วย ระดับความสามารถทางภาษาทางการของโมเดลเหล่านี้เป็นที่มาของระดับชั้นของ Chomsky ตารางด้านล่างแสดงกลุ่มของปัญหา (หรือภาษา หรือไวยากรณ์) ที่พิจารณาในทฤษฎีการคำนวณได้.
ใหม่!!: ทฤษฎีความซับซ้อนในการคำนวณและทฤษฎีการคำนวณ · ดูเพิ่มเติม »
ทฤษฎีการคำนวณได้
ทฤษฎีการคำนวณได้ คือส่วนหนึ่งของการศึกษาในทฤษฎีการคำนวณที่สนใจกับปัญหาที่ว่า ปัญหาใดที่สามารถหาคำตอบได้ด้วยขั้นตอนวิธี (หรือ—ในความหมายที่เหมือนกัน—โดยเครื่องจักรทัวริง) ภายใต้ข้อจำกัดและข้อเพิ่มเติมหลายๆ แบบ ทฤษฎีการคำนวณได้ศึกษาปัญหาหลักๆ สี่ปัญหาดังต่อไปนี้.
ใหม่!!: ทฤษฎีความซับซ้อนในการคำนวณและทฤษฎีการคำนวณได้ · ดูเพิ่มเติม »
ปัญหาการตัดสินใจ
ปัญหาการตัดสินใจ เป็นปัญหาในทฤษฎีการคำนวณได้และทฤษฎีความซับซ้อนในการคำนวณ ซึ่งพิจารณาค่าอินพุตและตอบเพียงว่า "ใช่" หรือ "ไม่ใช่" เท่านั้น เช่นปัญหาที่ถามว่าจำนวนเต็ม x เป็นจำนวนเฉพาะใช่หรือไม.
ใหม่!!: ทฤษฎีความซับซ้อนในการคำนวณและปัญหาการตัดสินใจ · ดูเพิ่มเติม »
ปัญหาความสอดคล้องแบบบูล
ปัญหาความสอดคล้องแบบบูล หรือ SAT (Boolean satisfiability) เป็นปัญหาการตัดสินใจอย่างหนึ่งที่ถูกกล่าวถึงบ่อย ๆ ในศาสตร์ทางด้านทฤษฎีความซับซ้อนในการคำนวณ ตัวอย่างของปัญหา (instance) สำหรับปัญหานี้ก็คือ นิพจน์บูลีน (boolean expression) ที่ประกอบด้วยตัวแปร ตัวเชื่อมต่าง ๆ และวงเล็บ ปัญหานี้ถามคำถามที่ว่า สำหรับนิพจน์บูลีนที่กำหนด เราสามารถทำให้นิพจน์เป็นจริงโดยการกำหนดค่าให้กับตัวแปรได้หรือไม่ ในกรณีที่เราสามารถกำหนดค่าความจริงให้กับตัวแปรแล้วทำให้นิพจน์เป็นจริงได้ เราจะกล่าวว่านิพจน์นั้น สามารถทำให้เป็นจริงได้ (satisfiable) ปัญหา SAT จัดอยู่ในกลุ่มของปัญหาเอ็นพีบริบูรณ์ (NP-complete) ในบางครั้งเราอาจจะสนใจศึกษาความซับซ้อนของรูปแบบที่ต่างกันออกไปของปัญหา SAT ยกตัวอย่างเช่นปัญหา SAT แบบที่นิพจน์บูลีนอยู่ในรูปมาตรฐานแบบเชื่อม (หรือ Conjunctive Normal Form---CNF) ในกรณีนี้ถ้าแต่ละประพจน์เลือก (disjunct) ประกอบด้วยตัวแปรไม่เกิน 3 ตัวแปรเราจะเรียกปัญหาว่า 3-SAT ซึ่งเป็นปัญหาเอ็นพีบริบูรณ์เช่นเดียวกัน อย่างไรก็ตาม ในกรณีที่ตัวแปรในแต่ละประพจน์เลือกมีไม่เกิน 2 ตัวแปร (เรียกว่าปัญหา 2-SAT) นั้น เรามีอัลกอริธึมที่มีประสิทธิภาพในการแก้ปัญหาได้ นั่นก็คือ 2SAT \in P หรือหากจะพูดให้ชัดเจนกว่านั้น 2SAT \in NL \subseteq P (ทั้งนี้เนื่องจากขั้นตอนวิธีที่ใช้แก้ปัญหา 2-SAT เป็นขั้นตอนวิธีที่ทำงานโดยใช้เนื้อที่เป็นลอการิธึมบนเครื่องจักรทัวริงเชิงไม่กำหนดเท่านั้น).
ใหม่!!: ทฤษฎีความซับซ้อนในการคำนวณและปัญหาความสอดคล้องแบบบูล · ดูเพิ่มเติม »
เลขฐานสอง
ลขฐานสอง (อังกฤษ: binary numeral system) หมายถึง ระบบเลขที่มีสัญลักษณ์เพียงสองตัวคือ 0 กับ 1 บางครั้งอาจหมายถึงการที่มีโอกาสเลือกได้เพียง 2 ทาง เช่น ปิดกับเปิด, ไม่ใช่กับใช่, เท็จกับจริง, ซ้ายกับขวา เป็นต้น ถ้าแปลงค่าเลขฐานสิบ มาเป็นเลขฐานสอง จะได้ดังนี้.
ใหม่!!: ทฤษฎีความซับซ้อนในการคำนวณและเลขฐานสอง · ดูเพิ่มเติม »
เอ็นพี (ความซับซ้อน)
ในทฤษฎีความซับซ้อนในการคำนวณ กลุ่มปัญหา เอ็นพี (NP: Non-deterministic Polynomial time) สามารถนิยามได้สองวิธี ซึ่งเราสามารถพิสูจน์ได้ไม่ยากนักว่านิยามทั้งสองแบบนี้สมมูลกัน.
ใหม่!!: ทฤษฎีความซับซ้อนในการคำนวณและเอ็นพี (ความซับซ้อน) · ดูเพิ่มเติม »
เอ็นพีบริบูรณ์
อ็นพี เอ็นพีบริบูรณ์ และเอ็นพีแบบยาก สำหรับทั้งสองกรณีที่พีเท่ากับเอ็นพี และพีไม่เท่ากับเอ็นพี ในทางทฤษฎีความซับซ้อนในการคำนวณ เอ็นพีบริบูรณ์ (NP-complete.) เป็นกลุ่มความซับซ้อนที่ยากที่สุดในเอ็นพี กล่าวคือปัญหาใด ๆ ในกลุ่มปัญหา เอ็นพี สามารถลดรูป (Reduce) มาเป็นปัญหาใน เอ็นพีบริบูรณ์ ได้ แม้ยังไม่ได้รับการพิสูจน์แต่เชื่อกันว่าเป็นกลุ่มปัญหาที่ไม่น่าจะมีขั้นตอนวิธีที่มีประสิทธิภาพใช้แก้ไขได้ ปัญหาในกลุ่มเอ็นพีบริบูรณ์สามารถเปลี่ยนแปลงไปมาเป็นปัญหาอื่นในกลุ่มเดียวกันได้ด้วย polynomial time ดังนั้นการที่มีขั้นตอนวิธีที่มีประสิทธิภาพสำหรับปัญหาใดปัญหาหนึ่งในเอ็นพีบริบูรณ์ ส่งผลให้เราสามารถแก้ปัญหาทั้งหมดในกลุ่มเอ็นพีได้อย่างมีประสิทธิภาพ กลุ่มความซับซ้อนเอ็นพีบริบูรณ์ในบางครั้งถูกเรียกสั้น ๆ ว่า NP-C.
ใหม่!!: ทฤษฎีความซับซ้อนในการคำนวณและเอ็นพีบริบูรณ์ · ดูเพิ่มเติม »
เครื่องทัวริง
รื่องจักรทัวริง (Turing machine) คือเครื่องจักรนามธรรมที่แอลัน ทัวริงได้คิดค้นขึ้นใน..
ใหม่!!: ทฤษฎีความซับซ้อนในการคำนวณและเครื่องทัวริง · ดูเพิ่มเติม »
