418531 ภาคต้น 2552/โจทยปัญหาการค้นหาด้วยพละกำลังเยี่ยงควายถึก/เฉลยข้อ 8 - ประวัติรุ่นแก้ไข

Aoy เมื่อ 09:49, 4 กันยายน 2552

2009-09-04T09:49:59Z

Aoy เมื่อ 09:02, 19 สิงหาคม 2552

2009-08-19T09:02:46Z

Aoy: หน้าที่ถูกสร้างด้วย 'อินพตุ:ประพจน์ที่มีตัวแปรไม่เกิน $n \,$ ตัว เอาพ…'

2009-08-19T08:56:25Z

หน้าที่ถูกสร้างด้วย 'อินพตุ:ประพจน์ที่มีตัวแปรไม่เกิน <math>n \,</math> ตัว เอาพ…'

หน้าใหม่

อินพตุ:ประพจน์ที่มีตัวแปรไม่เกิน <math>n \,</math> ตัว

เอาพุต:มีวิธีการกำหนดค่าตัวแปรให้ประพจน์เป็นจริงหรือไม่

แนวคิด ตัวแปรแต่ละตัวมีค่าได้สองค่า คือไม่จริงก็เท็จ การที่จะตรวจสอบว่า มีวิธีการกำหนดค่าตัวแปรให้ประพจน์เป็นจริงหรือไม่ต้องทำการลองกำหนดทุก ๆ แบบของตัวแปรที่เป็นไปได้ แต่ในห้องเรียน เราได้มีวิธีการสร้างซับเซตมาแล้ว และถ้าเราตีความใหม่ คือ ถ้า <math>g[i]=1 \,</math> หมายความว่า <math>x_i \,</math> เป็นสมาชิกของซับเซต แต่ถ้า<math>g[i]=2 \,</math> หมายความว่า <math>x_i \,</math> ไม่เป็นสมาชิกของซับเซต ดังนั้นเมื่อสร้างซับเซตได้แล้ว เราก็ทำการกำหนดว่า ถ้า <math>x_i \,</math> เป็นสมาชิกของซับเซตให้ ตัวแปร <math>x_i \,</math> มีค่าความจริงเป็นจริง ไม่เช่นนั้นให้มีค่าความจริงเป็นเท็จ หลังจากนั้นก็เอาวิธีการกำหนดค่าตัวแปรต่าง ๆ เหล่านี้ เรียกถาม subroutine (สมมติว่าชื่อ VERIFY เพื่อคำนวณหาค่าความจริงของประพจน์)

เวลาการทำงานของอัลกอริทึมข้างต้นก็จะเท่ากับเวลาการสร้างซับเซตทั้งหมด ซึ่งคือ<math> 2^n \,</math> และแต่ละซับเซตต้องเรียก VERIFY ซึ่งโจทย์กำหนดให้มีเวลาการทำงานเป็น M ดังนั้นเวลาการทำงานทั้งหมดของอัลกอริทึมคือ <math>O(2^n.M)\,</math>

@@ แถว 7: / แถว 7: @@
 เมื่อนำแนวคิดข้างต้นมาเขียนเป็น pseudocode จะได้ดังนี้
 GENERATE(X,k)
-:if k=0
-:: return(VERIFY(g)) // ทำการเรียก VERIFY โดยส่งอะเรย์ g ไปให้ซึ่งค่าแต่ละช่องของ g เก็บ 1 หรือ 2 ซึ่งใน VERIFY จะทำการตรวจสอบเองว่าถ้าเท่ากับ 1 คือจริง 2 คือเท็จ
+     if k=0
-:else
+         return(VERIFY(g)) // ทำการเรียก VERIFY โดยส่งอะเรย์ g ไปให้ซึ่งค่าแต่ละช่องของ g เก็บ 1 หรือ 2 ซึ่งใน VERIFY จะทำการตรวจสอบเองว่าถ้าเท่ากับ 1 คือจริง 2 คือเท็จ
-:: for g[k-1] = 1 to g[k-1] <= 2
+           else{
-::: GENERATE(k-1)
+         for g[k-1] = 1 to g[k-1] <= 2
 เวลาการทำงานของอัลกอริทึมข้างต้นก็จะเท่ากับเวลาการสร้างซับเซตทั้งหมด ซึ่งคือ<math> 2^n \,</math> และแต่ละซับเซตต้องเรียก VERIFY ซึ่งโจทย์กำหนดให้มีเวลาการทำงานเป็น M ดังนั้นเวลาการทำงานทั้งหมดของอัลกอริทึมคือ <math>O(2^n.M)\,</math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 09:02, 19 สิงหาคม 2552
แถว 5:		แถว 5:
	แนวคิด ตัวแปรแต่ละตัวมีค่าได้สองค่า คือไม่จริงก็เท็จ การที่จะตรวจสอบว่า มีวิธีการกำหนดค่าตัวแปรให้ประพจน์เป็นจริงหรือไม่ต้องทำการลองกำหนดทุก ๆ แบบของตัวแปรที่เป็นไปได้ แต่ในห้องเรียน เราได้มีวิธีการสร้างซับเซตมาแล้ว และถ้าเราตีความใหม่ คือ ถ้า <math>g[i]=1 \,</math> หมายความว่า <math>x_i \,</math> เป็นสมาชิกของซับเซต แต่ถ้า<math>g[i]=2 \,</math> หมายความว่า <math>x_i \,</math> ไม่เป็นสมาชิกของซับเซต ดังนั้นเมื่อสร้างซับเซตได้แล้ว เราก็ทำการกำหนดว่า ถ้า <math>x_i \,</math> เป็นสมาชิกของซับเซตให้ ตัวแปร <math>x_i \,</math> มีค่าความจริงเป็นจริง ไม่เช่นนั้นให้มีค่าความจริงเป็นเท็จ หลังจากนั้นก็เอาวิธีการกำหนดค่าตัวแปรต่าง ๆ เหล่านี้ เรียกถาม subroutine (สมมติว่าชื่อ VERIFY เพื่อคำนวณหาค่าความจริงของประพจน์)		แนวคิด ตัวแปรแต่ละตัวมีค่าได้สองค่า คือไม่จริงก็เท็จ การที่จะตรวจสอบว่า มีวิธีการกำหนดค่าตัวแปรให้ประพจน์เป็นจริงหรือไม่ต้องทำการลองกำหนดทุก ๆ แบบของตัวแปรที่เป็นไปได้ แต่ในห้องเรียน เราได้มีวิธีการสร้างซับเซตมาแล้ว และถ้าเราตีความใหม่ คือ ถ้า <math>g[i]=1 \,</math> หมายความว่า <math>x_i \,</math> เป็นสมาชิกของซับเซต แต่ถ้า<math>g[i]=2 \,</math> หมายความว่า <math>x_i \,</math> ไม่เป็นสมาชิกของซับเซต ดังนั้นเมื่อสร้างซับเซตได้แล้ว เราก็ทำการกำหนดว่า ถ้า <math>x_i \,</math> เป็นสมาชิกของซับเซตให้ ตัวแปร <math>x_i \,</math> มีค่าความจริงเป็นจริง ไม่เช่นนั้นให้มีค่าความจริงเป็นเท็จ หลังจากนั้นก็เอาวิธีการกำหนดค่าตัวแปรต่าง ๆ เหล่านี้ เรียกถาม subroutine (สมมติว่าชื่อ VERIFY เพื่อคำนวณหาค่าความจริงของประพจน์)

		+	เมื่อนำแนวคิดข้างต้นมาเขียนเป็น pseudocode จะได้ดังนี้
		+
		+	GENERATE(X,k)
		+	:if k=0
		+	:: return(VERIFY(g)) // ทำการเรียก VERIFY โดยส่งอะเรย์ g ไปให้ซึ่งค่าแต่ละช่องของ g เก็บ 1 หรือ 2 ซึ่งใน VERIFY จะทำการตรวจสอบเองว่าถ้าเท่ากับ 1 คือจริง 2 คือเท็จ
		+	:else
		+	:: for g[k-1] = 1 to g[k-1] <= 2
		+	::: GENERATE(k-1)

	เวลาการทำงานของอัลกอริทึมข้างต้นก็จะเท่ากับเวลาการสร้างซับเซตทั้งหมด ซึ่งคือ<math> 2^n \,</math> และแต่ละซับเซตต้องเรียก VERIFY ซึ่งโจทย์กำหนดให้มีเวลาการทำงานเป็น M ดังนั้นเวลาการทำงานทั้งหมดของอัลกอริทึมคือ <math>O(2^n.M)\,</math>		เวลาการทำงานของอัลกอริทึมข้างต้นก็จะเท่ากับเวลาการสร้างซับเซตทั้งหมด ซึ่งคือ<math> 2^n \,</math> และแต่ละซับเซตต้องเรียก VERIFY ซึ่งโจทย์กำหนดให้มีเวลาการทำงานเป็น M ดังนั้นเวลาการทำงานทั้งหมดของอัลกอริทึมคือ <math>O(2^n.M)\,</math>

418531 ภาคต้น 2552/โจทยปัญหาการค้นหาด้วยพละกำลังเยี่ยงควายถึก/เฉลยข้อ 8 - ประวัติรุ่นแก้ไข

Aoy เมื่อ 09:49, 4 กันยายน 2552

Aoy เมื่อ 09:02, 19 สิงหาคม 2552

Aoy: หน้าที่ถูกสร้างด้วย 'อินพตุ:ประพจน์ที่มีตัวแปรไม่เกิน n \, ตัว เอาพ…'

Aoy: หน้าที่ถูกสร้างด้วย 'อินพตุ:ประพจน์ที่มีตัวแปรไม่เกิน $n \,$ ตัว เอาพ…'