สารบัญ
16 ความสัมพันธ์: พี (ความซับซ้อน)กลุ่มความซับซ้อน พี และ เอ็นพีภาษาราชการภาษาเพิร์ลยูนิกซ์ทฤษฎีการคำนวณได้ทฤษฎีความซับซ้อนในการคำนวณปัญหาการยุติการทำงานปัญหาการตัดสินใจนักคณิตศาสตร์นิพจน์ปรกติแบบจำลองเอ็นพี (ความซับซ้อน)เอ็นพีบริบูรณ์เครื่องสถานะจำกัดเครื่องทัวริง
พี (ความซับซ้อน)
ในเชิงของ ทฤษฎีความซับซ้อนในการคำนวณ พี เป็นกลุ่มความซับซ้อนที่ประกอบด้วยปัญหาการตัดสินใจที่สามารถหาคำตอบได้ในเวลาที่เป็นฟังก์ชันพหุนามกับขนาดของอินพุต (polynomial time) พี ประกอบด้วย ปัญหาที่สำคัญหลายอย่างที่มีประโยชน์ในชีวิต เช่น ปัญหาการหาตัวหารร่วมมากระหว่างจำนวนสองจำนวน ปัญหาการจับคู่มากที่สุด (Maximum Matching) ปัญหาจำนวนเฉพาะ ปัญหากำหนดการเชิงเส้น (Linear program) พี เป็นกลุ่มความซับซ้อนที่นักวิจัยเรียกว่า "ง่าย" แม้ว่าในความเป็นจริงแล้วปัญหาที่ใช้เวลาในการหาคำตอบ n^ ไม่น่าจะถือว่าง่ายก็ตาม.
ดู ทฤษฎีการคำนวณและพี (ความซับซ้อน)
กลุ่มความซับซ้อน พี และ เอ็นพี
รูปแสดงความกลุ่มความซับซ้อนในกรณี '''P''' ≠ '''NP'''. ถ้า '''P'''.
ดู ทฤษฎีการคำนวณและกลุ่มความซับซ้อน พี และ เอ็นพี
ภาษาราชการ
ษาทางการ หรือ ภาษาราชการ คือภาษาที่มีการกำหนดให้เป็นภาษาหลักในการติดต่อสื่อสารภายในประเทศและเขตแดนที่ติดต่อกับประเทศนั้น บางครั้งภาษาท้องถิ่นถูกเข้าใจผิดว่าเป็นภาษาทางการเพราะมีการใช้การติดต่อกับทางส่วนการปกครองของท้องที่นั้น ในขณะที่ประเทศส่วนใหญ่มีภาษาทางการ 1 ภาษา บางประเทศมีภาษาทางการ 2 ภาษาขึ้นไป เช่น เบลเยียม แคนาดา ฟินแลนด์ สวิตเซอร์แลนด์ ฯลฯ ขณะเดียวกันบางประเทศไม่มีภาษาทางการ เช่น สหรัฐอเมริกา สวีเดน ฯลฯ ภาษาทางการของบางประเทศที่อยู่ภายใต้อาณานิคม เช่น ภาษาอังกฤษ และ ภาษาฝรั่งเศส ถูกใช้เป็นภาษาทางการ ถึงแม้ว่าไม่ใช่ภาษาที่มีการใช้เป็นหลักในประเทศนั้นๆ ในประเทศไอร์แลนด์ ภาษาไอร์แลนด์ (ไอริช) เป็นภาษาทางการและเป็นภาษาประจำชาติของประเทศ แต่มีผู้ใช้ภาษาไอร์แลนด์น้อยกว่า 1 ใน 3 ของประชากรประเทศ ขณะที่ผู้คนส่วนมากใช้ภาษาอังกฤษเป็นภาษาหลัก ในบางประเทศมีการโต้เถียงอย่างรุนแรง ในประเด็นที่ว่าควรใช้ภาษาใดเป็นภาษาทางการของประเทศ สำหรับประเทศไทยนั้น ใช้ภาษาไทยมาตรฐาน เป็น "ภาษากลาง" ที่ได้พัฒนารูปแบบขึ้นมาจากภาษาไทยถิ่นกลางมาโดยลำดับ จนมีลักษณะเฉพาะที่แตกต่างจากภาษาไทยถิ่นกลางอื่นๆ เรียกอีกอย่างว่าเป็นภาษาหนังสือ เป็นภาษาที่ใช้ในเอกสารราชการ การประชุมที่เป็นทางการ หนังสือ และตำราต่างๆ โดยปรากฏแนวการพัฒนาเป็นภาษากลางตั้งแต่สมัยรัชกาลที่ 5.
ภาษาเพิร์ล
right ภาษาเพิร์ล (Perl) (ย่อมาจาก Practical Extraction and Report Language) เป็นภาษาโปรแกรมแบบไดนามิก พัฒนาโดยนายแลร์รี วอลล์ (Larry Wall) ในปี ค.ศ. 1987 เพื่อใช้งานกับระบบปฏิบัติการยูนิกซ์ ภาษาเพิร์ล นั้นถูกออกแบบมาให้ใช้งานได้ง่าย โครงสร้างของภาษาจึงไม่ซับซ้อน มีลักษณะคล้ายกับภาษาซี นอกจากนี้เพิร์ลยังได้แนวคิดบางอย่างมาจากเชลล์สคริปต์, ภาษา AWK, sed และ Lisp ปัจจุบันเวอร์ชันล่าสุดคือ 5.18.0.
ยูนิกซ์
ูนิกซ์ (Unix แต่ชื่อตามเครื่องหมายการค้าคือ UNIX) เป็นระบบปฏิบัติการคอมพิวเตอร์แบบหลายงาน หลายผู้ใช้ ที่เริ่มพัฒนาโดยกลุ่มพนักงานของห้องปฏิบัติการ AT&T Bell Labs โดยกลุ่มนักพัฒนาที่เป็นที่รู้จัก คือ Ken Thompson, Dennis Ritchie และ Douglas McIlroy.
ทฤษฎีการคำนวณได้
ทฤษฎีการคำนวณได้ คือส่วนหนึ่งของการศึกษาในทฤษฎีการคำนวณที่สนใจกับปัญหาที่ว่า ปัญหาใดที่สามารถหาคำตอบได้ด้วยขั้นตอนวิธี (หรือ—ในความหมายที่เหมือนกัน—โดยเครื่องจักรทัวริง) ภายใต้ข้อจำกัดและข้อเพิ่มเติมหลายๆ แบบ ทฤษฎีการคำนวณได้ศึกษาปัญหาหลักๆ สี่ปัญหาดังต่อไปนี้.
ดู ทฤษฎีการคำนวณและทฤษฎีการคำนวณได้
ทฤษฎีความซับซ้อนในการคำนวณ
ทฤษฎีความซับซ้อนในการคำนวณ (Computational Complexity Theory) เป็นสาขาหนึ่งของทฤษฎีการคำนวณ ที่มุ่งเน้นไปในการวิเคราะห์เวลาและเนื้อที่สำหรับการแก้ปัญหาหนึ่ง ๆ โดยปกติแล้วคำว่า "เวลา" ที่เราพูดถึงนั้น จะเป็นการนับจำนวนขั้นตอนที่ใช้ในการแก้ปัญหา ส่วนในเรื่องของ "เนื้อที่" เราจะพิจารณาเนื้อที่ ๆ ใช้ในการทำงานเท่านั้น (ไม่นับเนื้อที่ ๆ ใช้ในการเก็บข้อมูลป้อนเข้า).
ดู ทฤษฎีการคำนวณและทฤษฎีความซับซ้อนในการคำนวณ
ปัญหาการยุติการทำงาน
ในทฤษฎีการคำนวณได้นั้น ปัญหาการยุติการทำงาน คือปัญหาการตัดสินใจที่ถามว่า แอลัน ทัวริง (Alan Turing) พิสูจน์ในปี..
ดู ทฤษฎีการคำนวณและปัญหาการยุติการทำงาน
ปัญหาการตัดสินใจ
ปัญหาการตัดสินใจ เป็นปัญหาในทฤษฎีการคำนวณได้และทฤษฎีความซับซ้อนในการคำนวณ ซึ่งพิจารณาค่าอินพุตและตอบเพียงว่า "ใช่" หรือ "ไม่ใช่" เท่านั้น เช่นปัญหาที่ถามว่าจำนวนเต็ม x เป็นจำนวนเฉพาะใช่หรือไม.
ดู ทฤษฎีการคำนวณและปัญหาการตัดสินใจ
นักคณิตศาสตร์
นักคณิตศาสตร์ (mathematician) คือบุคคลที่ศึกษาและ ทำงานวิจัยเกี่ยวกับคณิตศาสตร.
ดู ทฤษฎีการคำนวณและนักคณิตศาสตร์
นิพจน์ปรกติ
นิพจน์ปรกติ (regular expression สามารถย่อได้เป็น regexp หรือ regex) ในวิทยาการคอมพิวเตอร์ คือ สตริงที่อธิบายถึงรูปแบบของสตริงตามโครงสร้างรูปแบบที่กำหนด นิพจน์ปรกตินั้นใช้อยู่แพร่หลายในโปรแกรมประเภท Text editor ในการค้นหาและปรับเปลี่ยนข้อความ ภาษาโปรแกรมหลายภาษายังรองรับการใช้นิพจน์ปรกติสำหรับการจัดการและปรับเปลี่ยนสตริง.
ดู ทฤษฎีการคำนวณและนิพจน์ปรกติ
แบบจำลอง
แบบจำลอง หรือ โมเดล (มอเดิล หรือ โมเดิล, และมีการเรียกว่า ตุ๊กตา) อาจหมายถึง.
เอ็นพี (ความซับซ้อน)
ในทฤษฎีความซับซ้อนในการคำนวณ กลุ่มปัญหา เอ็นพี (NP: Non-deterministic Polynomial time) สามารถนิยามได้สองวิธี ซึ่งเราสามารถพิสูจน์ได้ไม่ยากนักว่านิยามทั้งสองแบบนี้สมมูลกัน.
ดู ทฤษฎีการคำนวณและเอ็นพี (ความซับซ้อน)
เอ็นพีบริบูรณ์
อ็นพี เอ็นพีบริบูรณ์ และเอ็นพีแบบยาก สำหรับทั้งสองกรณีที่พีเท่ากับเอ็นพี และพีไม่เท่ากับเอ็นพี ในทางทฤษฎีความซับซ้อนในการคำนวณ เอ็นพีบริบูรณ์ (NP-complete.) เป็นกลุ่มความซับซ้อนที่ยากที่สุดในเอ็นพี กล่าวคือปัญหาใด ๆ ในกลุ่มปัญหา เอ็นพี สามารถลดรูป (Reduce) มาเป็นปัญหาใน เอ็นพีบริบูรณ์ ได้ แม้ยังไม่ได้รับการพิสูจน์แต่เชื่อกันว่าเป็นกลุ่มปัญหาที่ไม่น่าจะมีขั้นตอนวิธีที่มีประสิทธิภาพใช้แก้ไขได้ ปัญหาในกลุ่มเอ็นพีบริบูรณ์สามารถเปลี่ยนแปลงไปมาเป็นปัญหาอื่นในกลุ่มเดียวกันได้ด้วย polynomial time ดังนั้นการที่มีขั้นตอนวิธีที่มีประสิทธิภาพสำหรับปัญหาใดปัญหาหนึ่งในเอ็นพีบริบูรณ์ ส่งผลให้เราสามารถแก้ปัญหาทั้งหมดในกลุ่มเอ็นพีได้อย่างมีประสิทธิภาพ กลุ่มความซับซ้อนเอ็นพีบริบูรณ์ในบางครั้งถูกเรียกสั้น ๆ ว่า NP-C.
ดู ทฤษฎีการคำนวณและเอ็นพีบริบูรณ์
เครื่องสถานะจำกัด
รื่องสถานะจำกัด หรือ ไฟไนต์สเตตแมชชีน (finite state machine) คือวงจรเชิงลำดับซึ่งออกแบบเป็นสถานะการทำงาน (state) ของวงจรออกเป็นหลายๆ สถานะ แต่ละสถานะมีลอจิกการทำงานที่ต่างกัน เพื่อกำเนิดค่าเอาต์พุตและค่าสถานะถัดไป มีสัญญาณสถานะที่กำหนดว่าสถานะปัจจุบันเป็นสถานะไหน สัญญาณของสถานะจะถูกเก็บไว้ในเรจิสเตอร์ ดังนั้นสถานะจะสามารถเปลี่ยนแปลงได้ที่ขอบขาของ clock เท่านั้น.
ดู ทฤษฎีการคำนวณและเครื่องสถานะจำกัด
เครื่องทัวริง
รื่องจักรทัวริง (Turing machine) คือเครื่องจักรนามธรรมที่แอลัน ทัวริงได้คิดค้นขึ้นใน..