ปัญหาหลายมิติโดยธรรมชาติแล้วจะซับซ้อนและใช้เวลานานกว่าปัญหาในมิติเดียว และความยากลำบากในการแก้ปัญหามักจะเพิ่มขึ้นตามมิติที่เพิ่มขึ้น เพื่อให้คุณรู้สึกดีขึ้น เรามาใช้วิธีการประมาณค่าที่ง่ายที่สุดในแนวคิดเพื่อหาค่าที่น้อยที่สุดของฟังก์ชันกันดีกว่า มาครอบคลุมพื้นที่ที่พิจารณาด้วยตาราง G ​​ด้วยขั้นตอน h (รูปที่ 10.8) และกำหนดค่าของฟังก์ชันที่โหนด เมื่อเปรียบเทียบตัวเลขที่ได้รับเราจะหาค่าที่เล็กที่สุดและถือว่าเป็นค่าที่น้อยที่สุดของฟังก์ชันสำหรับทั้งภูมิภาคโดยประมาณ

ข้าว. 10.8.

ดังที่เราได้กล่าวไว้ข้างต้น วิธีนี้ใช้ในการแก้ปัญหามิติเดียว บางครั้งก็ใช้เพื่อแก้ปัญหาสองมิติและปัญหาสามมิติที่ไม่ค่อยพบบ่อยนัก อย่างไรก็ตาม สำหรับปัญหาที่มีขนาดใหญ่กว่านั้นถือว่าไม่เหมาะสมในทางปฏิบัติ เนื่องจากเวลาที่ต้องใช้ในการคำนวณนานเกินไป อันที่จริง สมมติว่าฟังก์ชันวัตถุประสงค์ขึ้นอยู่กับตัวแปร 5 ตัว และโดเมนของคำจำกัดความ G คือลูกบาศก์ห้ามิติ ซึ่งแต่ละด้านเมื่อสร้างตารางเราจะแบ่งออกเป็น 40 ส่วน จากนั้นจำนวนโหนดกริดทั้งหมดจะเท่ากับ ให้การคำนวณค่าของฟังก์ชัน ณ จุดหนึ่งต้องใช้การดำเนินการทางคณิตศาสตร์ 1,000 ครั้ง (ซึ่งถือว่าไม่มากสำหรับฟังก์ชันของตัวแปร 5 ตัว) ในกรณีนี้จำนวนการดำเนินการทั้งหมดจะเป็น 10 11 หากเรามีคอมพิวเตอร์ที่มีความเร็ว 1 ล้านการทำงานต่อวินาทีการแก้ปัญหาโดยใช้วิธีนี้จะต้องใช้เวลา 10 5 วินาทีซึ่งเกินหนึ่งวันของการทำงานต่อเนื่อง การเพิ่มตัวแปรอิสระตัวอื่นจะเพิ่มเวลานี้ 40 เท่า การประเมินแสดงให้เห็นว่าวิธีการค้นหาแบบละเอียดถี่ถ้วนไม่เหมาะสำหรับปัญหาการปรับให้เหมาะสมที่มีขนาดใหญ่ บางครั้งการค้นหาแบบละเอียดจะถูกแทนที่ด้วยการค้นหาแบบสุ่ม ในกรณีนี้ จุดกริดจะไม่ถูกดูเป็นแถว แต่จะเรียงลำดับแบบสุ่ม เป็นผลให้การค้นหาค่าที่เล็กที่สุดของฟังก์ชันวัตถุประสงค์นั้นเร็วขึ้นอย่างมาก แต่สูญเสียความน่าเชื่อถือ

4. วิธีประสานการสืบเชื้อสาย

ลองพิจารณาฟังก์ชันของตัวแปรสองตัวกัน เส้นระดับคงที่แสดงไว้ในรูปที่ 1 10.9 และค่าต่ำสุดอยู่ที่จุดนั้น (โปรดจำไว้ว่าเส้นระดับคงที่คือเส้นโค้งในส่วนสองมิติของพื้นที่พารามิเตอร์ (ในกรณีนี้ในระนาบ (x1, x2) ซึ่งเป็นค่าของฟังก์ชันที่เป็นค่าคงที่) การค้นหาที่ง่ายที่สุด วิธีการคือ ประสานวิธีการสืบเชื้อสาย- จากจุด A เราค้นหาค่าต่ำสุดตามทิศทางของแกน x1 และหาจุด Bat ซึ่งเส้นสัมผัสของเส้นระดับคงที่นั้นขนานกับแกน x1 จากนั้น เมื่อค้นหาจากจุด B ในทิศทางของแกน x2 เราจะได้จุด C ค้นหาแบบขนานกับแกน x1 เราได้จุด D เป็นต้น ดังนั้นเราจึงมาถึงจุดที่เหมาะสมที่สุด วิธีการหนึ่งมิติใดๆ ที่อธิบายไว้ในบทที่แล้วสามารถใช้ที่นี่เพื่อค้นหาตามแกน แน่นอนว่าแนวคิดนี้สามารถนำไปใช้กับฟังก์ชันของตัวแปร n ตัวได้

ข้าว. 10.9.

ลองพิจารณาวิธีนี้โดยละเอียดโดยใช้ตัวอย่างของฟังก์ชันเป้าหมายบางอย่าง

ให้คุณต้องค้นหาค่าที่เล็กที่สุดของฟังก์ชันวัตถุประสงค์ u=f(M)=f(x 1 ,x 2 ,...,x n) โดยที่ M หมายถึงจุดในพื้นที่ n มิติพร้อมพิกัด x 1 ,x 2 ,...,x n:M=(x 1 ,x 2 ,...,x n)- ลองเลือกจุดเริ่มต้นแล้วพิจารณาฟังก์ชัน f สำหรับค่าคงที่ของตัวแปรทั้งหมดยกเว้นตัวแรก: - จากนั้นจะกลายเป็นฟังก์ชันของตัวแปรตัวเดียว x 1 โดยการเปลี่ยนตัวแปรนี้ เราจะย้ายจากจุดเริ่มต้นไปในทิศทางของฟังก์ชันที่ลดลงจนกระทั่งถึงจุดต่ำสุดที่ หลังจากนั้นจะเริ่มเพิ่มขึ้น เราแสดงจุดด้วยพิกัดด้วย M 1 และ .

ตอนนี้ให้เราแก้ไขตัวแปรกัน: และพิจารณาฟังก์ชัน f เป็นฟังก์ชันของตัวแปรตัวหนึ่ง โดยการเปลี่ยน x 2 เราจะย้ายจากค่าเริ่มต้นไปสู่การลดลงของฟังก์ชันอีกครั้งจนกระทั่งถึงค่าต่ำสุดที่ เราแสดงจุดด้วยพิกัดด้วย M 2 และ - ขอให้เราดำเนินการย่อเล็กสุดของฟังก์ชันวัตถุประสงค์ให้เหลือน้อยที่สุดเหนือตัวแปร x 3 , x 4 ,...,x n . เมื่อถึงตัวแปร xn แล้ว ให้กลับไปที่ x 1 อีกครั้งแล้วดำเนินการต่อไป

ขั้นตอนนี้จะปรับชื่อของวิธีการอย่างสมบูรณ์ ด้วยความช่วยเหลือเราจะสร้างลำดับของจุด M 0 , M 1 , M 2 ,... . ซึ่งลำดับโมโนโทนิกของค่าฟังก์ชันสอดคล้องกัน โดยการยกเลิกที่ขั้นตอนหนึ่ง k เราสามารถนำค่าของฟังก์ชัน f(M k) มาเป็นค่าที่น้อยที่สุดในภูมิภาคที่พิจารณา (รูปที่ 10.10) .

โปรดทราบว่าวิธีนี้ช่วยลดปัญหาในการค้นหาค่าที่น้อยที่สุดของฟังก์ชันของตัวแปรหลายตัว เพื่อแก้ปัญหาการหาค่าเหมาะที่สุดมิติเดียวซ้ำๆ หากฟังก์ชันวัตถุประสงค์ f(x 1 ,x 2 ,\ldots,x n กำหนดไว้โดยสูตรที่ชัดเจนและสามารถหาอนุพันธ์ได้ เราก็สามารถคำนวณอนุพันธ์ย่อยของมันและใช้มันเพื่อกำหนดทิศทางการลดลงของฟังก์ชันในแต่ละตัวแปรและค้นหา สำหรับค่าต่ำสุดหนึ่งมิติที่สอดคล้องกัน

ในรูป 10.10. แสดงเส้นระดับของฟังก์ชันหนึ่งของตัวแปรสองตัว u=f(x,y) ตามบรรทัดเหล่านี้ฟังก์ชันจะรักษาค่าคงที่เท่ากับ 1, 3, 5, 7, 9 วิถีการค้นหาค่าที่น้อยที่สุดซึ่งทำได้ที่จุด O จะแสดงโดยใช้

วิธีเดรัจฉานเป็นวิธีที่ง่ายที่สุดในการแก้ปัญหาใดๆ วิธีเดียวที่ง่ายกว่าน่าจะเป็นวิธีการเลือก หากคุณไม่สามารถเลือกคำตอบได้ทันที (โดยไม่ได้ตั้งใจ) และมีปัญหาที่ไม่ทราบมากกว่าเงื่อนไขที่กำหนด ดังนั้นวิธีการค้นหาอย่างละเอียดถี่ถ้วนก็เหมาะสมแล้ว แน่นอน ขั้นแรก คุณต้องตรวจสอบให้แน่ใจว่าตัวเลือกโซลูชันอื่นๆ ทั้งหมดไม่เหมาะสม และมีการกำหนดเงื่อนไขที่ชัดเจนและโดยนัยทั้งหมดเพื่อจำกัดชุดค่าผสมที่กำลังลองใช้ มิฉะนั้น เวลาที่ใช้ในการลองใช้ตัวเลือกที่เป็นไปได้ทั้งหมดจะหมดเวลา

เรามาดูตัวอย่างการใช้วิธีกำลังเดรัจฉานในการแก้ปัญหาต่างๆ กัน

ค้นหาลำดับ

สมมติว่าเราเจอลำดับตัวเลข 141526418 และเรารู้ว่าคำบางคำถูกเข้ารหัสด้วยตัวอักษรละติน วิธีที่ง่ายที่สุดในการเข้ารหัสคำคืออะไร? แน่นอนใช้รหัสทดแทน! จำนวนหลักเป็นเลขคี่ ซึ่งหมายความว่ามีการเข้ารหัสตัวอักษรอย่างน้อยหนึ่งตัวด้วยตัวเลขเพียงหลักเดียว แต่จะแยกตัวอักษรสิบตัวแรกออกจากตัวถัดไปที่เข้ารหัสด้วยตัวเลขสองหลักได้อย่างไร? 14 AD หรือ N? นี่คือจุดที่วิธีกำลังเดรัจฉานมีประโยชน์ มาดูการผสมตัวเลขหนึ่งหรือสองหลักจากช่วงกัน

ในลำดับ 141526418 เราสามารถแยกแยะชุดค่าผสมต่อไปนี้ที่ตรงตามเงื่อนไขของเรา: 1,2,4,5,6,8,14,15,18,26 ตัวเลขเหล่านี้สอดคล้องกับตัวอักษร A,B,D,E,F,H,N,O,R,Z ชุดค่าผสม 41, 52 และ 64 ไม่เหมาะสำหรับเราเนื่องจากอักษรละตินมีเพียง 26 ตัวเท่านั้น

เราจะเรียงลำดับดังนี้ อันดับแรก เราจะนำลำดับที่ขยายมากที่สุด โดยที่ตัวอักษรทั้งหมดมาจากสิบตัวแรก จากนั้นเราจะเพิ่มจำนวนที่ใช้ทีละตัว นั่นคือแทนที่ลำดับ 1-4 ด้วย 14 , 1-5 กับ 15, 1-8 กับ 18, 2- 6 คูณ 26 ผ่านชุดค่าผสมที่เป็นไปได้ทั้งหมด

1-4-1-5-2-6-4-1-8 = อดาบีฟดาห์

1-4-1-5-2-6-4-18 = ADAEBFDR

1-4-1-5-26-4-1-8 = อดีซดาห์

1-4-1-5-26-4-18 = อดาเอซดีอาร์

1-4-15-2-6-4-1-8 = ADOBFDAH

1-4-15-2-6-4-18 = ADOBFDR

1-4-15-26-4-1-8 = อดอซดาห์

1-4-15-26-4-18 = ADOZDR

14-1-5-2-6-4-1-8 = แน็บฟดาห์

14-1-5-2-6-4-18 = NAEBFDR

14-1-5-26-4-1-8 = นาเอซดาห์

14-1-5-26-4-18 = เอ็นเอซดีอาร์

14-15-2-6-4-1-8 = NOBFDAH

14-15-2-6-4-18 = NOBFDR

14-15-26-4-1-8 = นอซดาห์

14-15-26-4-18 = นอซดีอาร์

โดยรวมแล้วเราได้รับ 16 ตัวเลือก คำเดียวที่อ่านได้ NOZDR (บางคนอ่านได้แต่บางคนอ่านไม่ได้) อยู่ตอนท้ายสุด นี่จะเป็นคำตอบ ตอนนี้หากในตอนแรกมีคำใบ้ว่าลำดับ 141526418 ควรมีตัวอักษร 5 ตัวแสดงว่าปัญหาจะได้รับการแก้ไขอย่างไม่น่าสงสัย และไม่จำเป็นต้องใช้กำลังดุร้ายเพราะมีเพียงวิธีเดียวเท่านั้นที่จะแยกลำดับ 141526418 ออกเป็น 5 ตัวอักษร แต่ไม่มีคำใบ้เช่นนั้น และวิธีการใช้กำลังดุร้ายก็มีประโยชน์

การแจงนับวิธีแก้ปัญหาเมื่อมีเงื่อนไขไม่เพียงพอ

บางครั้งในวิชาคณิตศาสตร์ก็มีปัญหาที่ดูเหมือนเป็นไปไม่ได้ที่จะแก้ไขแบบเผชิญหน้า ปัญหาดังกล่าวมักจะได้รับการแก้ไขที่การแข่งขันกีฬาโอลิมปิกและการแข่งขัน ซึ่งหมายความว่าเหมาะสำหรับเราสำหรับภารกิจ ตัวอย่างเช่น นี่คือปัญหา

ในระหว่างบทเรียนคณิตศาสตร์ ครูถามนักเรียนเกี่ยวกับปัญหาต่อไปนี้ “แม่มีลูกสาวสามคน ผลคูณของอายุของลูกสาว = 40 ผลรวมของอายุเท่ากับจำนวนนักเรียนในชั้นเรียน ลูกสาวแต่ละคนอายุเท่าไหร่?”นักเรียนคำนวณอย่างรวดเร็วว่ามีกี่คนในชั้นเรียนและเริ่มแก้ไขปัญหา พวกเขาตัดสินใจแล้วตัดสินใจ... ตัดสินใจไม่ได้ เราขอคำใบ้จากอาจารย์ ครูคิดแล้วพูดว่า: “โอ้แม่นเลย! น้องคนสุดท้องมีตาสีฟ้า!”- นักเรียนมีความสุขและแก้ไขปัญหาได้ และตอนนี้คำถามสำหรับคุณ: ลูกสาวแต่ละคนอายุเท่าไหร่?

หากคุณแก้ปัญหาแบบตรงหน้า (AxBxC=40, A+B+C=D, ดวงตาสีฟ้าเล็กๆ) คุณจะพบกับสิ่งที่ไม่ทราบจำนวนมากและการขาดเงื่อนไขทันที 4 สิ่งลึกลับ สองสมการ และแม้แต่ดวงตาสีฟ้าเล็กๆ น้อยๆ!!! ดังที่คุณทราบ มีสิ่งแปลกปลอมมากมายเท่าที่ต้องมี ก็ต้องมีเงื่อนไขที่เป็นอิสระมากมาย ในปัญหาของเรา เรามีเงื่อนไขปกติสองเงื่อนไขและเงื่อนไขหนึ่งที่เข้าใจยาก วิธีแก้ปัญหา?

และด้วยกำลังอันดุร้าย! ประการแรก ปัญหาดังกล่าวได้รับการแก้ไขเป็นจำนวนเต็มตามค่าเริ่มต้น ลองหาชุดค่าผสมของจำนวนเต็มสามจำนวนทั้งหมด ซึ่งผลคูณที่ได้ให้ 40 ในเวลาเดียวกัน ลองคำนวณผลรวมของตัวเลขเหล่านี้ ปรากฎว่ามีชุดค่าผสมดังกล่าวไม่มากนัก - มีเพียงหกชุดเท่านั้น

1x1x40=40, 1+1+40=42

1x2x20=40, 1+2+20=23

1x4x10=40, 1+4+10=15

1x5x8=40, 1+5+8= 14

2x2x10=40, 2+2+10= 14

2x4x5=40, 2+4+5=11

หากมีนักเรียนในชั้นเรียน 42, 23, 15 หรือ 11 คน พวกเขาจะแก้ไขปัญหาทันที แต่พวกเขาประสบปัญหา - มี 14 คนและพวกเขาไม่สามารถเลือกตัวเลือก 1-5-8 หรือ 2-2-10 ใดที่เหมาะสมได้ แต่เมื่อครูพูดถึงเรื่องตาสีฟ้าก็ช่วยให้พวกเขาตัดสินใจได้ คนสุดท้องมีตาสีฟ้าคือมีลูกสาวคนเล็กและในรุ่น 2-2-10 มีลูกสาวคนเล็กสองคน ซึ่งหมายความว่ามีเพียงตัวเลือกที่สี่ 1-5-8 เท่านั้นที่เหมาะกับเรา

ดูเหมือนจะเป็นปัญหาที่แก้ไขไม่ได้ในทางปฏิบัติ แต่วิธีกำลังดุร้ายทำให้สามารถแก้ไขได้อย่างรวดเร็ว ดังนั้นคุณจึงไม่ควรกลัวที่จะแก้ไขปัญหาโดยใช้กำลังอันดุร้าย บ่อยครั้งที่จำนวนตัวเลือกที่เป็นไปได้นั้นไม่มากเท่าที่ควรในตอนแรก

ในส่วนนี้เราจะดูปัญหาบางอย่างที่เกี่ยวข้องกับปัญหาการดึงข้อมูล นี่เป็นปัญหาระดับใหญ่ซึ่งอธิบายไว้อย่างละเอียดเพียงพอในวรรณกรรมคลาสสิกเกี่ยวกับการเขียนโปรแกรม (ดูตัวอย่างในหนังสือของ N. Wirth, D. Knuth และอื่น ๆ )

ความหมายทั่วไปของงานค้นหามีดังนี้: จากข้อมูลที่จัดเก็บไว้ในหน่วยความจำคอมพิวเตอร์ ให้เลือกข้อมูลที่จำเป็นที่ตรงตามเงื่อนไข (เกณฑ์) บางประการ

เราได้พิจารณาปัญหาที่คล้ายกันแล้ว ตัวอย่างเช่น การค้นหาจำนวนสูงสุดในอาร์เรย์ตัวเลข การค้นหาบันทึกที่ต้องการในไฟล์ข้อมูล ฯลฯ การค้นหาดังกล่าวดำเนินการโดยการแจกแจงองค์ประกอบทั้งหมดของโครงสร้างข้อมูล และตรวจสอบความพึงพอใจของเงื่อนไขการค้นหา การแจงนับที่มีการตรวจสอบองค์ประกอบทั้งหมดของโครงสร้างเรียกว่าการแจงนับที่สมบูรณ์

การค้นหาแบบละเอียดเป็นวิธีการค้นหาแบบใช้กำลังและแน่นอนว่าไม่ใช่วิธีที่ดีที่สุดเสมอไป

ลองดูตัวอย่าง ในอาร์เรย์ X หนึ่งมิติ พิกัดของจุด n จุดที่วางอยู่บนแกนจำนวนจริงจะได้รับ คะแนนมีเลขกำกับ ตัวเลขเหล่านี้สอดคล้องกับลำดับในอาร์เรย์ X กำหนดจำนวนของจุดแรกที่อยู่ห่างจากจุดเริ่มต้นมากที่สุด

เป็นเรื่องง่ายที่จะเข้าใจว่านี่เป็นปัญหาที่คุ้นเคยในการกำหนดจำนวนขององค์ประกอบโมดูโลที่ใหญ่ที่สุดของอาร์เรย์ X ซึ่งแก้ไขได้โดยการค้นหาอย่างละเอียดดังนี้:

การแจกแจงองค์ประกอบของอาร์เรย์หนึ่งมิติที่สมบูรณ์จะดำเนินการโดยใช้โครงสร้างแบบวนเดียว

และตอนนี้งานต่อไปนี้: ข้อมูลเริ่มต้นเหมือนกับข้อมูลก่อนหน้า คุณต้องกำหนดจุดคู่ที่มีระยะห่างระหว่างจุดเหล่านั้นมากที่สุด

เมื่อใช้วิธีการแจงนับ ปัญหานี้สามารถแก้ไขได้ดังนี้ แจกแจงจุดทั้งหมดจาก Ladanny และกำหนดจำนวนของจุดที่มีระยะห่างระหว่างจุดเหล่านั้นมากที่สุด (โมดูลัสที่ใหญ่ที่สุดของความแตกต่างของพิกัด) การค้นหาอย่างละเอียดนี้ดำเนินการผ่านสองลูปที่ซ้อนกัน:

เห็นได้ชัดว่าการแก้ปัญหาดังกล่าวไม่สมเหตุสมผล ในที่นี้แต่ละจุดจะถูกตรวจสอบสองครั้ง ตัวอย่างเช่น สำหรับ i = 1, j = 2 และ i = 2, j= 1 สำหรับกรณี n = 100 ลูปจะทำซ้ำการดำเนินการ 100 x 100 = 10,000 ครั้ง

การทำงานของโปรแกรมจะเร็วขึ้นหากไม่มีการทำซ้ำ ควรยกเว้นกรณีของความบังเอิญของค่า i และ j ด้วย จากนั้นจำนวนการวนซ้ำจะเท่ากับ

เมื่อ n = 100 ผลลัพธ์คือ 4950

เพื่อกำจัดการซ้ำซ้อน คุณต้องเปลี่ยนจุดเริ่มต้นของวงในจาก 1 เป็น i +1 ในโปรแกรมก่อนหน้า โปรแกรมจะมีลักษณะดังนี้:

เราจะเรียกอัลกอริธึมกำลังเดรัจฉานเวอร์ชันที่พิจารณาโดยไม่ต้องทำซ้ำ

ความคิดเห็น แน่นอนว่าปัญหานี้สามารถแก้ไขได้ด้วยวิธีอื่น แต่ในกรณีนี้ เราสนใจอัลกอริธึมแบบ brute-force ในกรณีของจุดที่ไม่ได้อยู่บนเส้นตรง แต่บนเครื่องบินหรือในอวกาศ การค้นหาทางเลือกอื่นแทนอัลกอริธึมดังกล่าวจะกลายเป็นปัญหามาก

ปัญหาต่อไปนี้จำเป็นต้องเลือกตัวเลขแฝดทั้งหมดโดยไม่มีการซ้ำซึ่งผลรวมเป็น 10 จากอาร์เรย์ X

ในกรณีนี้ อัลกอริธึมจะถูกสร้างขึ้นจากสามลูปที่ซ้อนกัน ห่วงด้านในมีความยาวผันแปรได้

สำหรับฉัน:=l ถึง N ทำ

สำหรับ J:=I+1 ถึง N Do

สำหรับ K:=J+1 ถึง N Do

ถ้า X[I]+X[J]+X[K]=10

จากนั้น WriteLn(X[I],X[J],X[K]);

ทีนี้ลองจินตนาการว่าจากอาร์เรย์ X คุณต้องเลือกกลุ่มตัวเลขทั้งหมดที่มีผลรวมเท่ากับสิบ กลุ่มสามารถมีตัวเลขได้ตั้งแต่ 1 ถึง n ในกรณีนี้จำนวนตัวเลือกการค้นหาจะเพิ่มขึ้นอย่างรวดเร็วและอัลกอริทึมเองก็กลายเป็นเรื่องไม่สำคัญ

ดูเหมือนว่าจะแล้วไงล่ะ? เครื่องทำงานเร็ว! และยังมานับกัน จำนวนกลุ่มที่แตกต่างกันของวัตถุ n อัน (รวมถึงวัตถุว่างด้วย) คือ 2n สำหรับ n = 100 จะเป็น 2100 ‐ 1,030 คอมพิวเตอร์ที่ทำงานด้วยความเร็วพันล้านการดำเนินการต่อวินาทีจะดำเนินการค้นหานี้เป็นเวลาประมาณ 10 ปี แม้แต่การกำจัดการเรียงสับเปลี่ยนซ้ำก็ไม่ทำให้อัลกอริธึมการค้นหาที่ละเอียดถี่ถ้วนดังกล่าวเป็นไปได้ในทางปฏิบัติ

เส้นทางสู่การแก้ไขปัญหาดังกล่าวในทางปฏิบัติคือการหาวิธีแยกออกจากตัวเลือกการค้นหาที่ไม่มีท่าว่าจะดีจากมุมมองของเงื่อนไขของปัญหา สำหรับปัญหาบางอย่าง สามารถทำได้โดยใช้อัลกอริทึมที่อธิบายไว้ในส่วนถัดไป

เกินกำลังกับผลตอบแทน ลองพิจารณาอัลกอริธึมการย้อนรอยโดยใช้ตัวอย่างปัญหาการผ่านเขาวงกต (รูปที่ 52)

มีเขาวงกต เมื่อเข้าไปข้างในแล้วคุณจะต้องหาทางออก คุณสามารถเคลื่อนที่ได้เฉพาะในแนวนอนและแนวตั้งเท่านั้น รูปนี้แสดงตัวเลือกทั้งหมดสำหรับเส้นทางออกจากจุดศูนย์กลางของเขาวงกต

หากต้องการรับโปรแกรมสำหรับแก้ไขปัญหานี้ คุณต้องแก้ไขปัญหาสองข้อ:

วิธีจัดระเบียบข้อมูล

วิธีสร้างอัลกอริทึม

เราจะจัดเก็บข้อมูลเกี่ยวกับรูปร่างของเขาวงกตไว้ใน LAB เมทริกซ์จัตุรัสประเภทสัญลักษณ์ขนาด N x N โดยที่ N เป็นเลขคี่ (เพื่อให้มีจุดศูนย์กลาง) ตารางถูกซ้อนทับบนโปรไฟล์ของเขาวงกตเพื่อให้ในแต่ละเซลล์มีทั้งผนังหรือทางเดิน

เมทริกซ์สะท้อนถึงการเติมตาราง: องค์ประกอบที่สอดคล้องกับเนื้อเรื่องเท่ากับช่องว่าง และผนังเท่ากับสัญลักษณ์บางอย่าง (เช่น ตัวอักษร M)

เส้นทางผ่านเขาวงกตจะมีเครื่องหมาย + กำกับไว้

ตัวอย่างเช่น รูปด้านบน (ตรงกลาง) สอดคล้องกับความสมบูรณ์ของเมทริกซ์ LAB ต่อไปนี้:

ข้อมูลเริ่มต้น - โปรไฟล์ของเขาวงกต (เมทริกซ์ LAB เริ่มต้นที่ไม่มีกากบาท) ผลลัพธ์คือวิถีทางออกที่เป็นไปได้ทั้งหมดจากจุดศูนย์กลางของเขาวงกต (สำหรับแต่ละเส้นทาง LAB matrix จะแสดงพร้อมกับวิถีที่มีเครื่องหมายกากบาท)

อัลกอริธึมการย้อนรอยเรียกอีกอย่างว่าวิธีทดลองใช้

สาระสำคัญของมันมีดังนี้:

1. จากแต่ละจุดที่ต่อเนื่องกันของวิถี ทิศทางการเคลื่อนที่ที่เป็นไปได้จะถูกดูในลำดับเดียวกัน เรายอมรับว่าการรับชมจะเกิดขึ้นทวนเข็มนาฬิกาในแต่ละครั้ง - ขวาบน-ซ้ายล่าง; ขั้นตอนจะถูกส่งไปยังเซลล์ข้างเคียงอิสระที่ตรวจพบเป็นเซลล์แรก เซลล์ที่ทำตามขั้นตอนนั้นจะมีเครื่องหมายกากบาทกำกับไว้

3. หากเซลล์ถัดไปที่ก้าวเข้าไปอยู่ที่ขอบของเขาวงกต (ที่ทางออก) เส้นทางที่พบจะถูกพิมพ์

เราจะสร้างโปรแกรมโดยใช้วิธีการแสดงรายละเอียดตามลำดับ ขั้นตอนแรกของรายละเอียด:

ขั้นตอน GO พยายามก้าวเข้าไปในเซลล์ที่มีพิกัด x, y หากเซลล์นี้อยู่ที่ทางออกจากเขาวงกต เส้นทางที่เดินทางจะถูกพิมพ์ ถ้าไม่เช่นนั้น ให้นำขั้นตอนเข้าไปในเซลล์ที่อยู่ติดกันตามลำดับที่กำหนดไว้ข้างต้น ถ้าเซลล์เป็นทางตัน ก็จะทำการถอยกลับ จากที่กล่าวมาข้างต้น กระบวนการดังกล่าวมีลักษณะเป็นแบบวนซ้ำ

ก่อนอื่นให้เราเขียนโครงร่างทั่วไปของขั้นตอนโดยไม่มีรายละเอียด:

เพื่อส่งออกวิถีที่พบ ขั้นตอน PRINTLAB จะถูกคอมไพล์

โปรแกรมสุดท้ายจะมีลักษณะดังนี้:

อีกตัวอย่างหนึ่งของโปรแกรมที่สวยงามที่ใช้คำจำกัดความขั้นตอนแบบเรียกซ้ำ (จำหอคอยแห่งฮานอย!)

อัลกอริธึมของโปรแกรมนี้เป็นเรื่องปกติสำหรับวิธีการย้อนรอย อัลกอริธึมที่คล้ายกันนี้ใช้เพื่อแก้ปัญหายอดนิยม เช่น การเคลื่อนย้ายหมากรอบๆ กระดานหมากรุก หรือการจัดเรียงหมากบนกระดานเพื่อไม่ให้ "ชน" กัน ชุดปัญหาทางเลือกที่ดีที่สุด (ปัญหาการเดินทางของพนักงานขาย ปัญหาการก่อสร้างถนนที่เหมาะสม ฯลฯ)

ความคิดเห็น เนื่องจากการใช้อาร์เรย์ LAB เป็นพารามิเตอร์ค่าในขั้นตอน GO ปัญหาหน่วยความจำอาจเกิดขึ้นเมื่อใช้งานโปรแกรมบนคอมพิวเตอร์ ในกรณีนี้ คุณสามารถดำเนินการถ่ายโอนอาเรย์ส่วนกลางได้

ตามวิธีเดรัจฉานฟอร์ซ เป็นวิธีสากลที่สุด แต่ก็ยาวที่สุดเช่นกัน

YouTube สารานุกรม

1 / 5

√ เกินกำลัง อัลกอริธึมโลภ: การใช้กำลังดุร้ายโดยใช้ลูป ศูนย์การเรียนรู้ออนไลน์ Foxford

út #82. ความก้าวหน้าทางคณิตศาสตร์ การหารและการแจกแจงตัวเลือกอย่างละเอียดถี่ถ้วน! ทฤษฎีจำนวนในการสอบ Unified State

√ อัลกอริทึม C ++ กำลังดุร้าย (ตอนที่ 1)

út #84. ปัญหาเรื่องทหารสองหมวด! ทางออกที่เข้มงวดและชัดเจน การสอบ Unified State ในวิชาคณิตศาสตร์ (โปรไฟล์)

√ เกินกำลัง อัลกอริธึมโลภ: ปัญหาการแลกเปลี่ยนเหรียญ ศูนย์การเรียนรู้ออนไลน์ Foxford

คำบรรยาย

วิธีหมดแรง

คำศัพท์เฉพาะทาง

ในภาษาอังกฤษ คำว่า "brute-force" ที่กล่าวถึงในบทความนี้มักหมายถึงการโจมตีประเภทหนึ่งของแฮ็กเกอร์ ในเวลาเดียวกัน แนวคิดทั่วไปซึ่งเป็นวิธีการทางคณิตศาสตร์ในการทำให้ตัวเลือกที่เป็นไปได้ทั้งหมดหมดหมดในการค้นหาวิธีแก้ไขปัญหา สอดคล้องกับคำว่า "พิสูจน์โดยหมดแรง"

คำอธิบาย

"วิธีการหมดแรง" รวมถึงวิธีการต่างๆ มากมาย โดยปกติแล้ว การกำหนดปัญหาเกี่ยวข้องกับการพิจารณาจำนวนสถานะของระบบตรรกะที่กำหนดเพื่อระบุความจริงของข้อความเชิงตรรกะผ่านการวิเคราะห์ที่เป็นอิสระของแต่ละรัฐ วิธีการพิสูจน์ข้อความประกอบด้วย 2 ส่วน คือ

1. พิสูจน์ความเป็นไปได้ที่จะทำให้ทุกสถานะของระบบหมดลง จำเป็นต้องแสดงให้เห็นว่าสถานะเฉพาะใดๆ ของระบบ (เช่น ค่าของนิพจน์เชิงตรรกะที่กำลังพิสูจน์) สอดคล้องกับโซลูชันที่อยู่ระหว่างการพิจารณาอย่างน้อยหนึ่งรายการ
2. ตรวจสอบแต่ละตัวเลือกและพิสูจน์ว่าตัวเลือกที่อยู่ระหว่างการพิจารณานั้นเป็นหรือไม่ใช่วิธีแก้ปัญหา

ปัญหาทั่วไปแก้ไขได้ด้วยวิธีการค้นหาอย่างละเอียดถี่ถ้วน

แม้ว่าการค้นหาอย่างละเอียดไม่ได้ใช้ในทางปฏิบัติกับปัญหาที่ใช้ส่วนใหญ่ (โดยเฉพาะอย่างยิ่งที่ไม่เกี่ยวข้องกับรหัสถอดรหัส) แต่ก็มีข้อยกเว้นหลายประการ โดยเฉพาะอย่างยิ่งเมื่อการค้นหาอย่างละเอียดถี่ถ้วนยังคงกลายเป็นสิ่งที่ดีที่สุดหรือเป็นตัวแทน ขั้นแรกในการพัฒนาอัลกอริธึมการใช้งานนั้นมีความสมเหตุสมผล ตัวอย่างของการค้นหาอย่างละเอียดถี่ถ้วนคืออัลกอริธึมสำหรับการประมาณเวลาของการคำนวณผลคูณของห่วงโซ่ของเมทริกซ์ ซึ่งไม่สามารถเร่งความเร็วได้เมื่อเปรียบเทียบกับอัลกอริธึมที่ใช้วิธีเดรัจฉานแรง อัลกอริทึมนี้ใช้เพื่อแก้ปัญหาคลาสสิกของการเขียนโปรแกรมแบบไดนามิก - กำหนดลำดับความสำคัญของการคำนวณผลคูณเมทริกซ์ในรูปแบบต่อไปนี้: A 1 A 2 A 3 ⋯ A n (\รูปแบบการแสดงผล A_(1)A_(2)A_(3)\cdots A_(n)).

ตัวอย่างการใช้กำลังดุร้าย

ปัญหาเบื้องต้นคือการคำนวณลูกโซ่ที่กำหนด (ผลคูณเมทริกซ์) ในระยะเวลาน้อยที่สุด เป็นไปได้ที่จะใช้อัลกอริธึมลำดับเล็กน้อยที่คำนวณผลิตภัณฑ์ที่ต้องการ เนื่องจากผลคูณเมทริกซ์เป็นการดำเนินการเชื่อมโยง จึงเป็นไปได้ที่จะคำนวณผลคูณลูกโซ่โดยการสุ่มเลือกคู่องค์ประกอบของลูกโซ่ (A i A i + 1) , i = 1.. n − 1 (\displaystyle (A_(i)A_(i+1)),i=1..n-1)และแทนที่ด้วยเมทริกซ์ผลลัพธ์ A i 1: A i 1 = (A i A i + 1) (\displaystyle A_(i)^(1)\โคลอน A_(i)^(1)=(A_(i)A_(i+1)) )- หากคุณทำซ้ำขั้นตอนที่อธิบายไว้ n − 1 (\displaystyle n-1)เท่า ดังนั้นเมทริกซ์ผลลัพธ์ที่เหลือคือ A k n − 1 (\displaystyle A_(k)^(n-1))และคำตอบจะเป็น: A k n − 1 = (A k n − 2 A k + 1 n − 2) = … = A 1 A 2 A 3 ⋯ A n , k = 1.. n − 1 (\displaystyle A_(k)^(n- 1)=(A_(k)^(n-2)A_(k+1)^(n-2))=\ldots =A_(1)A_(2)A_(3)\cจุด A_(n), k=1..n-1)- สูตรนี้สามารถแสดงได้ดังนี้ พิจารณาห่วงโซ่เมทริกซ์: ⟨ A 1 , A 2 , A 3 , A 4 ⟩ (\displaystyle \left\langle A_(1),A_(2),A_(3),A_(4)\right\rangle )- มี 5 วิธีต่อไปนี้ในการคำนวณผลิตภัณฑ์ที่สอดคล้องกับห่วงโซ่นี้: A 1 A 2 A 3 A 4 (\รูปแบบการแสดงผล A_(1)A_(2)A_(3)A_(4)):

(A 1 (A 2 (A 3 A 4))) , (\displaystyle (\color (Violet)()A_(1)(\color (BurntOrange)()A_(2)(\color (BrickRed)() A_(3)A_(4)(\color (BrickRed)))(\color (BurntOrange)))(\color (ม่วง))))) (A 1 ((A 2 A 3) A 4)) , (\displaystyle (\color (Violet)()A_(1)(\color (BurntOrange)()(\color (BrickRed)()A_(2) A_(3)(\color (BrickRed)))A_(4)(\color (BurntOrange)))(\color (สีม่วง))))) ((A 1 A 2) (A 3 A 4)) , (\displaystyle (\color (Violet)()(\color (BrickRed)()A_(1)A_(2)(\color (BrickRed))) (\color (BurntOrange)()A_(3)A_(4)(\color (BurntOrange)))(\color (สีม่วง))))) ((A 1 (A 2 A 3)) A 4) , (\displaystyle (\color (Violet)()(\color (BurntOrange)()A_(1)(\color (BrickRed)()A_(2) A_(3)(\color (BrickRed)))(\color (BurntOrange)))A_(4)(\color (ม่วง))))) (((ก 1 ก 2) ก 3) ก 4) . (\displaystyle (\color (Violet)()(\color (BurntOrange)()(\color (BrickRed)()A_(1)A_(2)(\color (BrickRed)))A_(3)(\color (BurntOrange)))A_(4)(\color (ม่วง))).)

ด้วยการเลือกลำดับการคำนวณที่ถูกต้อง คุณสามารถเร่งความเร็วการคำนวณได้อย่างมาก หากต้องการดูสิ่งนี้ ลองพิจารณาตัวอย่างง่ายๆ ของสายโซ่ของเมทริกซ์ 3 ตัว สมมติว่าขนาดเท่ากันตามลำดับ 10 × 100, 100 × 5, 5 × 50 (\รูปแบบการแสดงผล 10\คูณ 100,100\คูณ 5.5\คูณ 50)- อัลกอริธึมมาตรฐานสำหรับการคูณเมทริกซ์สองตัวด้วยขนาด p × q , q × r (\displaystyle p\times q,q\times r)ต้องใช้เวลาคำนวณตามสัดส่วนของตัวเลข pqr (\displaystyle pqr)(จำนวนผลิตภัณฑ์สเกลาร์ที่จะคำนวณ) ดังนั้นให้คำนวณลูกโซ่ตามลำดับ ((A 1 A 2) A 3) (\รูปแบบการแสดงผล ((A_(1)A_(2))A_(3))), เราได้รับ 10 ⋅ 100 ⋅ 5 = 5000 (\displaystyle 10\cdot 100\cdot 5=5000)ผลิตภัณฑ์จุดที่จะคำนวณ (A 1 A 2) (\displaystyle (A_(1)A_(2)))บวกเพิ่ม 10 ⋅ 5 ⋅ 50 = 2500 (\displaystyle 10\cdot 5\cdot 50=2500)ดอทโปรดัคเพื่อคำนวณผลคูณเมทริกซ์ตัวที่สอง จำนวนผลิตภัณฑ์สเกลาร์ทั้งหมด: 7500 ด้วยตัวเลือกลำดับการคำนวณที่แตกต่างกัน เราได้รับ 100 ⋅ 5 ⋅ 50 = 25000 (\displaystyle 100\cdot 5\cdot 50=25000)บวก 10 ⋅ 100 ⋅ 50 = 50000 (\displaystyle 10\cdot 100\cdot 50=50000)ผลิตภัณฑ์ดอท ซึ่งก็คือ 75,000 ผลิตภัณฑ์ดอท

ดังนั้นการแก้ปัญหานี้สามารถลดเวลาที่ใช้ในการคำนวณลูกโซ่เมทริกซ์ได้อย่างมาก โซลูชันนี้สามารถหาได้จากการค้นหาอย่างละเอียด: จำเป็นต้องพิจารณาลำดับการคำนวณที่เป็นไปได้ทั้งหมดและเลือกลำดับที่ใช้ผลิตภัณฑ์สเกลาร์จำนวนน้อยที่สุดเมื่อคำนวณลูกโซ่ อย่างไรก็ตาม จะต้องคำนึงว่าอัลกอริทึมนี้ต้องใช้เวลาในการคำนวณแบบเอ็กซ์โปเนนเชียล ดังนั้นสำหรับเมทริกซ์เชนแบบยาว ผลได้จากการคำนวณเชนด้วยวิธีที่มีประสิทธิภาพมากที่สุด (กลยุทธ์ที่เหมาะสมที่สุด) อาจสูญหายไปโดยสิ้นเชิงเมื่อต้องใช้เวลาในการค้นหาสิ่งนี้ กลยุทธ์.

เชื่อมโยงกับแนวคิด “แบ่งแยก พิชิต”

ตัวอย่างที่ชัดเจนอีกประการหนึ่งของแนวคิดพื้นฐานในทฤษฎีอัลกอริธึมคือหลักการ "แบ่งแยกและพิชิต" แนวคิดนี้ใช้ได้เมื่อระบบสามารถแบ่งออกเป็นระบบย่อยจำนวนมากซึ่งมีโครงสร้างคล้ายกับระบบดั้งเดิม ในกรณีเช่นนี้ ระบบย่อยยังสามารถแยกออกจากกันหรือไม่สำคัญก็ได้ สำหรับระบบดังกล่าว ปัญหาที่เกิดขึ้นในตอนแรกนั้นไม่สำคัญนัก ดังนั้น การนำแนวคิด "แบ่งแยกและพิชิต" ไปใช้จึงมีลักษณะเป็นแบบวนซ้ำ

ในทางกลับกัน การเรียกซ้ำเป็นการค้นหาแบบละเอียดถี่ถ้วน ดังนั้นการเรียกซ้ำจึงใช้ได้กับเท่านั้น ระบบที่ไม่ต่อเนื่อง- อย่างไรก็ตาม ข้อกำหนดนี้ใช้ไม่ได้กับสถานะของระบบที่กำหนด แต่ใช้กับระบบของมัน โครงสร้างย่อย- การพิจารณาอย่างสอดคล้องกันของทุกระดับจะให้แนวทางแก้ไขปัญหาที่ครอบคลุมสำหรับระบบแยกทั้งหมด

เมื่อเปรียบเทียบกับตัวอย่างอื่นๆ ของการค้นหาอย่างละเอียด คุณลักษณะหนึ่งของวิธีการเรียกซ้ำก็คือ วิธีแก้ปัญหาขั้นสุดท้ายไม่ได้ขึ้นอยู่กับระบบย่อยเล็กๆ น้อยๆ เพียงระบบเดียว ในกรณีทั่วไป การแก้ปัญหาจะเกิดขึ้นบนพื้นฐานของระบบย่อยทั้งชุด

สำหรับตัวอย่างปัญหาการแบ่งแยกและพิชิตแบบคลาสสิกต่อไปนี้ การค้นหาอย่างละเอียดอาจเป็นวิธีการแก้ปัญหาเดียวที่ทราบหรือการดำเนินการดั้งเดิมที่ได้รับการปรับปรุงให้เหมาะสมเพิ่มเติม:

การโจมตีด้วยกำลังอันดุร้าย

จำนวนตัวอักษร	จำนวนตัวเลือก	ความทนทาน	เวลาค้นหา
1	36	5 บิต	น้อยกว่าหนึ่งวินาที
2	1296	10 บิต	น้อยกว่าหนึ่งวินาที
3	46 656	15 บิต	น้อยกว่าหนึ่งวินาที
4	1 679 616	21 บิต	17 วินาที
5	60 466 176	26 บิต	10 นาที
6	2 176 782 336	31 บิต	6 ชั่วโมง
7	78 364 164 096	36 บิต	9 วัน
8	2,821 109 9x10 12	41 บิต	11 เดือน
9	1.015 599 5x10 14	46 บิต	32 ปี
10	3.656 158 4x10 15	52 บิต	1,162 ปี
11	1.316 217 0x10 17	58 บิต	41,823 ปี
12	4,738 381 3x10 18	62 บิต	1,505,615 ปี

ดังนั้นรหัสผ่านที่มีความยาวไม่เกิน 8 ตัวอักษรโดยทั่วไปจึงไม่เข้มงวด สำหรับคอมพิวเตอร์สมัยใหม่ ตัวเลขนี้สูงกว่ามาก ดังนั้น คีย์ 64 บิต (รหัสผ่าน) จึงสามารถค้นหาบนคอมพิวเตอร์สมัยใหม่ได้ภายในเวลาประมาณ 2 ปี และสามารถกระจายการค้นหาไปยังคอมพิวเตอร์หลายเครื่องได้อย่างง่ายดาย

หมายถึงการโจมตี

คอมพิวเตอร์ส่วนบุคคลสมัยใหม่ช่วยให้คุณสามารถถอดรหัสรหัสผ่านโดยใช้วิธีการแบบ Brute Force ได้อย่างมีประสิทธิภาพตามที่แสดงในตารางด้านบน อย่างไรก็ตาม ด้วยการเพิ่มประสิทธิภาพแบบเดรัจฉานโดยอิงจากการคำนวณแบบขนาน ประสิทธิภาพของการโจมตีจึงสามารถเพิ่มขึ้นได้อย่างมาก ซึ่งอาจต้องใช้คอมพิวเตอร์ที่ปรับให้เหมาะกับการประมวลผลแบบมัลติเธรด ในช่วงไม่กี่ปีที่ผ่านมา โซลูชันการประมวลผลที่ใช้ GPU เช่น Nvidia Tesla แพร่หลายมากขึ้น ตั้งแต่ Nvidia สร้างสถาปัตยกรรม CUDA ในปี 2550 ก็มีโซลูชันมากมายปรากฏขึ้น (ดูตัวอย่าง Cryptohaze Multiforcer, Pyrit) ซึ่งช่วยให้สามารถเลือกคีย์ได้เร็วขึ้นโดยใช้เทคโนโลยีเช่น CUDA, FireStream, OpenCL

ทนต่อการโจมตีด้วยกำลังดุร้าย

ในกระบวนการปรับปรุงระบบความปลอดภัยของข้อมูลที่สัมพันธ์กับการโจมตีแบบ brute-force สามารถแยกแยะได้สองทิศทางหลัก:

1. ข้อกำหนดที่เพิ่มขึ้นสำหรับคีย์การเข้าถึงจากข้อมูลที่ได้รับการคุ้มครอง
2. เพิ่มความน่าเชื่อถือของส่วนประกอบทั้งหมดของระบบรักษาความปลอดภัย

ดังนั้นจึงเป็นไปไม่ได้ที่จะได้รับการป้องกันในระดับสูงโดยการปรับปรุงพารามิเตอร์เหล่านี้เพียงตัวเดียว - มีตัวอย่างว่าระบบการตรวจสอบสิทธิ์ตามความซับซ้อนของรหัสผ่านที่เหมาะสมที่สุดกลายเป็นช่องโหว่ในการคัดลอกฐานข้อมูลไปยังเครื่องคอมพิวเตอร์ของผู้โจมตีได้อย่างไร หลังจากนั้นจึงถูกโจมตีแบบดุร้ายโดยใช้การเพิ่มประสิทธิภาพเฉพาะที่และเครื่องมือคำนวณที่ไม่สามารถใช้งานได้กับระยะไกล การเข้ารหัส สถานการณ์เช่นนี้ทำให้ผู้เชี่ยวชาญด้านความปลอดภัยคอมพิวเตอร์บางคนแนะนำให้ใช้มุมมองที่สำคัญยิ่งขึ้นเกี่ยวกับแนวทางปฏิบัติด้านความปลอดภัยมาตรฐาน เช่น การรักษารหัสผ่านให้นานที่สุด ด้านล่างนี้คือรายการวิธีการบางอย่างที่ใช้ในทางปฏิบัติเพื่อเพิ่มความน่าเชื่อถือของระบบเข้ารหัสที่เกี่ยวข้องกับการโจมตีแบบเดรัจฉาน:

วิธีการเพิ่มประสิทธิภาพแบบเดรัจฉาน

สาขาและวิธีการผูกมัด

การคำนวณแบบขนาน

วิธีหนึ่งในการเพิ่มความเร็วของการเลือกคีย์คือการคำนวณแบบขนาน มีสองวิธีในการขนาน:

• แนวทางแรกคือการสร้างไปป์ไลน์ ปล่อยให้อัลกอริทึมอัตราส่วน E k (x) = y (\displaystyle E_(k)\ (x)=y)สามารถแสดงเป็นลูกโซ่ของการกระทำง่าย ๆ (การดำเนินการ): โอ 1, โอ 2, . -- , O N (\รูปแบบการแสดงผล (O_(1)\ ,O_(2),...,O_(N)))- เอาล่ะ ยังไม่มีข้อความ (\displaystyle N\ )โปรเซสเซอร์ ก 1 , 2 , . -- , O N (\รูปแบบการแสดงผล (O_(1)\ ,O_(2),...,O_(N))), A N (\displaystyle (A_(1)\ ,A_(2),...,A_(N))) ให้เรากำหนดลำดับและสันนิษฐานว่าฉัน (\displaystyle i\ ) - โปรเซสเซอร์ตัวที่ 3 ดำเนินการสามอย่างในเวลาเดียวกัน: จากนั้นไปป์ไลน์จากโปรเซสเซอร์ที่เชื่อมต่อแบบอนุกรม ขนานและซิงโครนัสทำงานด้วยความเร็ว
• v / 3 (\displaystyle v/3\ ) , ที่ไหนโวลต์ (\displaystyle v\ ) - ความเร็วในการดำเนินการหนึ่งการดำเนินการโดยโปรเซสเซอร์ตัวเดียวแนวทางที่สองก็คือชุด K (\รูปแบบการแสดงผล K\ )คีย์ที่เป็นไปได้ทั้งหมดจะถูกแบ่งออกเป็นชุดย่อยที่ไม่ต่อเนื่องกัน ก 1 , 2 , . -เค 1 เค 2 , . - -, K N (\รูปแบบการแสดงผล (K_(1)\,K_(2),...,K_(N))) - ระบบจากถาม (\displaystyle Q\ ) -เค | (\displaystyle |K|\ ) , O N (\รูปแบบการแสดงผล (O_(1)\ ,O_(2),...,O_(N)))คือจำนวนองค์ประกอบในชุดคีย์ และ

- จำนวนโปรเซสเซอร์

โต๊ะสายรุ้ง

ข้อกำหนดเบื้องต้นสำหรับการปรากฏตัว

ระบบคอมพิวเตอร์ที่ใช้รหัสผ่านในการตรวจสอบความถูกต้องจะต้องตรวจสอบว่ารหัสผ่านที่ป้อนนั้นถูกต้องหรือไม่ วิธีแก้ไขเล็กๆ น้อยๆ สำหรับปัญหานี้คือการจัดเก็บรายการรหัสผ่านที่ถูกต้องทั้งหมดสำหรับผู้ใช้แต่ละราย แต่วิธีนี้ไม่ปลอดภัย วิธีหนึ่งที่ต้องการคือการคำนวณฟังก์ชันแฮชที่เข้ารหัสจากข้อความรหัสผ่าน ตารางสายรุ้งเป็นการเพิ่มประสิทธิภาพของวิธีนี้ ข้อได้เปรียบหลักคือลดจำนวนหน่วยความจำที่ใช้ลงอย่างมาก

การใช้งาน

ตารางสายรุ้งถูกสร้างขึ้นโดยการสร้างกลุ่มรหัสผ่านที่เป็นไปได้ แต่ละห่วงโซ่เริ่มต้นด้วยรหัสผ่านผู้สมัครแบบสุ่ม จากนั้นอยู่ภายใต้ฟังก์ชันแฮชและฟังก์ชันลด ฟังก์ชันนี้จะแปลงผลลัพธ์ของฟังก์ชันแฮชเป็นรหัสผ่านที่เป็นไปได้ (เช่น ถ้าเราถือว่ารหัสผ่านมีความยาว 64 บิต ฟังก์ชันลดขนาดอาจใช้ 64 บิตแรกของแฮช โดยเพิ่มบล็อกแฮช 64 บิตทั้งหมด ระดับบิต เป็นต้น) รหัสผ่านระดับกลางในห่วงโซ่จะถูกละทิ้ง และเฉพาะองค์ประกอบแรกและสุดท้ายของห่วงโซ่เท่านั้นที่ถูกเขียนลงในตาราง การสร้างตารางดังกล่าวต้องใช้เวลามากกว่าที่ใช้ในการสร้างตารางการค้นหาปกติ แต่มีหน่วยความจำน้อยกว่ามาก (มากถึงหลายร้อยกิกะไบต์ ในขณะที่ไดรฟ์ข้อมูลสำหรับตารางปกติคือ N คำ ตารางสายรุ้งต้องการเพียง N 2/3 เท่านั้น) ในเวลาเดียวกันแม้ว่าจะต้องใช้เวลามากขึ้น (เมื่อเทียบกับวิธีทั่วไป) ในการกู้คืนรหัสผ่านเดิม แต่ก็มีความเป็นไปได้มากกว่าในทางปฏิบัติ (เพื่อสร้างตารางปกติสำหรับรหัสผ่าน 6 ตัวอักษรที่มีอักขระไบต์ 256 6 = 281,474,976,710,656 บล็อกหน่วยความจำ จะต้องใช้ในขณะที่สายรุ้ง - เพียง 256 6 ·⅔ = 4,294,967,296 บล็อก)

ในการกู้คืนรหัสผ่าน ค่าแฮชนี้อยู่ภายใต้ฟังก์ชันการลดขนาดและค้นหาในตาราง หากไม่พบรายการที่ตรงกัน ฟังก์ชันแฮชและฟังก์ชันลดจะถูกใช้อีกครั้ง การดำเนินการนี้จะดำเนินต่อไปจนกว่าจะพบรายการที่ตรงกัน เมื่อพบรายการที่ตรงกัน สายโซ่ที่บรรจุข้อมูลจะถูกสร้างขึ้นใหม่เพื่อค้นหาค่าที่ถูกละทิ้ง ซึ่งจะเป็นรหัสผ่านที่ค้นหา

ผลลัพธ์ที่ได้คือตารางที่สามารถกู้คืนรหัสผ่านได้ในเวลาอันสั้นซึ่งมีความเป็นไปได้สูง

แม้ว่าการป้องกันระบบข้อมูลใดๆ ประการแรกจะต้องเชื่อถือได้ต่อการโจมตีแบบเดรัจฉาน แต่กรณีการใช้งานการโจมตีนี้โดยผู้โจมตีสำเร็จนั้นค่อนข้างเป็นเรื่องปกติ

การโจมตีของปริศนา

เครื่องเข้ารหัสที่เรียกว่า Enigma ประดิษฐ์ขึ้นในปี พ.ศ. 2461 และถูกใช้อย่างแพร่หลายโดยกองทัพเรือเยอรมัน โดยเริ่มตั้งแต่ปี พ.ศ. 2472 ในอีกไม่กี่ปีถัดมา ระบบก็ได้รับการแก้ไข และตั้งแต่ปี 1930 เป็นต้นมา ระบบนี้ก็ถูกใช้อย่างแข็งขันโดยกองทัพและรัฐบาลเยอรมันในช่วงสงครามโลกครั้งที่สอง

การสกัดกั้นข้อความครั้งแรกที่เข้ารหัสด้วยรหัส Enigma ย้อนกลับไปในปี 1926 อย่างไรก็ตาม พวกเขาไม่สามารถอ่านข้อความได้เป็นเวลานาน ตลอดช่วงสงครามโลกครั้งที่สอง มีการเผชิญหน้ากันระหว่างนักเข้ารหัสชาวโปแลนด์และชาวเยอรมัน ชาวโปแลนด์ซึ่งได้รับผลอีกประการหนึ่งในการแฮ็กระบบเข้ารหัสลับของเยอรมัน ต้องเผชิญกับปัญหาใหม่ที่นำเสนอโดยวิศวกรชาวเยอรมัน ผู้ซึ่งปรับปรุงระบบ Enigma ให้ทันสมัยอยู่ตลอดเวลา ในฤดูร้อนปี พ.ศ. 2482 เมื่อการรุกรานโปแลนด์กลายเป็นเรื่องหลีกเลี่ยงไม่ได้ สำนักงานจึงส่งมอบผลงานให้กับหน่วยข่าวกรองของอังกฤษและฝรั่งเศส

มีการจัดงานแฮ็กเพิ่มเติมที่ Bletchley Park เครื่องมือหลักของนักวิเคราะห์การเข้ารหัสคือเครื่องถอดรหัสระเบิด ต้นแบบของมันถูกสร้างขึ้นโดยนักคณิตศาสตร์ชาวโปแลนด์ในช่วงก่อนสงครามโลกครั้งที่สองสำหรับกระทรวงกลาโหมโปแลนด์ จากการพัฒนานี้และด้วยการสนับสนุนโดยตรงของผู้สร้าง หน่วย "ขั้นสูง" ได้รับการออกแบบในอังกฤษ

ส่วนทางทฤษฎีของงานนี้ดำเนินการโดย Alan Mathieson Turing งานของเขาเกี่ยวกับการวิเคราะห์การเข้ารหัสของอัลกอริธึมที่ใช้ในเครื่องเข้ารหัส Enigma มีพื้นฐานมาจากการวิเคราะห์การเข้ารหัสก่อนหน้านี้ของเครื่องรุ่นก่อนๆ ซึ่งดำเนินการในปี 1938 โดย Marian Rejewski นักวิเคราะห์การเข้ารหัสชาวโปแลนด์ หลักการทำงานของตัวถอดรหัสที่พัฒนาโดยทัวริงคือการแจกแจงตัวแปรที่เป็นไปได้ของคีย์ตัวเลขและพยายามถอดรหัสข้อความหากทราบโครงสร้างของข้อความที่ถูกถอดรหัสหรือเป็นส่วนหนึ่งของข้อความธรรมดา

จากมุมมองสมัยใหม่ รหัส Enigma นั้นไม่น่าเชื่อถือมากนัก แต่เพียงการรวมกันของปัจจัยนี้กับการมีอยู่ของข้อความที่ถูกดัก หนังสือรหัส รายงานข่าวกรอง ผลของความพยายามทางทหาร และแม้แต่การโจมตีของผู้ก่อการร้ายเท่านั้นที่ทำให้สามารถ " ทำลาย” รหัส

การแฮ็กเครือข่ายในบ้านครั้งใหญ่โดยใช้ WASP

ดูสิ่งนี้ด้วย

หมายเหตุ

วรรณกรรม

• รีด, ดี.เอ. และคณะ การพิสูจน์ ใน คณิตศาสตร์ การศึกษา: การวิจัย  การเรียนรู้ และ การสอน- - John Wiley & SSense Publishersons, 2010. - หน้า 266. - ISBN 978-9460912443.
• พาร์, คริสตอฟ และคณะ.

3) การเลือกเครื่องมือทางคณิตศาสตร์ เครื่องมือทางคณิตศาสตร์ที่ใช้สร้างแบบจำลองจะขึ้นอยู่กับประเภทของแบบจำลอง ดังนั้น เพื่อจัดอัลกอริธึมแบบจำลองการคำนวณ จึงมีการใช้สูตรวิเคราะห์ของความซับซ้อนใดๆ ระบบสมการเชิงเส้นหรือสมการเชิงอนุพันธ์ (กฎของ Kirchhoff วิธีของกระแสที่สำคัญและแรงดันไฟฟ้าของลูป)

ในการกำหนดอัลกอริธึมแบบจำลองการทำนาย จะใช้อัลกอริธึมที่รู้จักกันดีของแบบจำลองการคำนวณ โดยเน้นข้อมูลเริ่มต้นและพารามิเตอร์ที่คาดการณ์ของระบบ

สำหรับคำอธิบายทางคณิตศาสตร์ของแบบจำลองการปรับให้เหมาะสมนั้นใช้วิธีการทางคณิตศาสตร์พิเศษ - วิธีการปรับให้เหมาะสม

3. ขั้นตอนที่สามคือการใช้อัลกอริธึมโมเดลที่สร้างขึ้นบนคอมพิวเตอร์

4. ศึกษาผลลัพธ์ของการสร้างแบบจำลองเชิงตัวเลข การประเมินความเพียงพอ และความเหมาะสมทั่วไปของแบบจำลองในการใช้งาน

5. การตีความผลการสร้างแบบจำลองและการตัดสินใจเกี่ยวกับการใช้แบบจำลองทางคณิตศาสตร์หรือความจำเป็นในการพัฒนา ที่นี่จะพิจารณาวงจรชีวิตของโมเดลและความจำเป็นในการอัปเดตโมเดลนั่นคือการเปลี่ยนแปลงพารามิเตอร์เนื่องจากการเปลี่ยนแปลงสภาพการทำงาน

วิธีการเพิ่มประสิทธิภาพ

เมื่อเริ่มดำเนินกิจกรรมผู้คนจะประเมินผลที่ตามมาและตัดสินใจเลือกไม่ทางใดก็ทางหนึ่งหรือพารามิเตอร์อื่นที่ขึ้นอยู่กับพวกเขา - วิธีการจัดกิจกรรมและกระบวนการ ทฤษฎีการตัดสินใจใช้แบบจำลองการปรับให้เหมาะสมและแก้ไขปัญหาการปรับให้เหมาะสม

เป้าหมายของการเพิ่มประสิทธิภาพคือการปรับปรุงตัวบ่งชี้ของระบบหรือกระบวนการที่เป็นแบบจำลองโดยการเลือกเงื่อนไขสำหรับกระบวนการหรือการเลือกพารามิเตอร์ของระบบบางอย่าง

ฟังก์ชันบางอย่าง F(x) เรียกว่าฟังก์ชันวัตถุประสงค์ ถือเป็นเกณฑ์การหาค่าเหมาะที่สุด ฟังก์ชั่นวัตถุประสงค์แสดงการวิเคราะห์การพึ่งพาตัวบ่งชี้ที่ปรับให้เหมาะสมที่สุดในพารามิเตอร์บางตัว x ซึ่งค่าที่สามารถเปลี่ยนแปลงได้เรียกว่าพารามิเตอร์ควบคุม

xi, i = 1,2,...,n.

พารามิเตอร์ที่ควบคุม xi นั้นเป็นอิสระจากกัน และในระหว่างกระบวนการปรับให้เหมาะสม พารามิเตอร์เหล่านั้นสามารถเปลี่ยนแปลงได้ภายในขีดจำกัดที่ทราบ (ขอบเขตที่อนุญาต) Dx ในเชิงวิเคราะห์สามารถระบุช่วงของค่าที่ยอมรับได้ในเชิงวิเคราะห์ในรูปแบบของชุดฟังก์ชัน

Ψ k (x 1 ,...,xn )= 0

โดยทั่วไป ปัญหาการหาค่าเหมาะที่สุดทางคณิตศาสตร์สามารถกำหนดได้ดังนี้:

ย่อเล็กสุด (ขยายใหญ่สุด) ฟังก์ชั่นวัตถุประสงค์โดยคำนึงถึงข้อจำกัดของตัวแปรที่ถูกควบคุม

โดยการลด (ขยายใหญ่สุด) ฟังก์ชันของตัวแปร n ตัว F(x)=F(x1, ... ,xn) บนชุด Dx ที่กำหนด เราหมายถึงการกำหนดค่าต่ำสุดโดยรวม (สูงสุด) ของฟังก์ชันนี้บนชุด Dx ที่กำหนด

ช่วงการเปลี่ยนแปลงที่อนุญาตในพารามิเตอร์ควบคุมไม่ได้นูนเสมอไปและอาจไม่ได้เชื่อมต่อกันง่ายๆ มักเป็นไปไม่ได้ที่จะแก้ระบบข้อจำกัดแบบไม่เชิงเส้นในเชิงวิเคราะห์ และหาจุดปลายสุดของฟังก์ชันวัตถุประสงค์ที่ไม่เชิงเส้นที่ซับซ้อนในเชิงวิเคราะห์

การเพิ่มฟังก์ชันวัตถุประสงค์ให้สูงสุด (F(x) -> สูงสุด) เทียบเท่ากับการลดปริมาณตรงข้ามให้เหลือน้อยที่สุด (−F(x) -> min) ดังนั้นจึงพิจารณาเฉพาะปัญหาการย่อให้เล็กที่สุดเท่านั้น

ไม่มีวิธีการที่เป็นสากลในการแก้ปัญหาการปรับให้เหมาะสมแบบไม่เชิงเส้น แต่มีการพัฒนาแล้ว จำนวนมากวิธีที่ใช้ในการแก้ปัญหาการหาค่าเหมาะที่สุดของฟังก์ชันวัตถุประสงค์ยูนิโมดัลหนึ่งมิติ ยูนิโมดัลหลายมิติ มัลติโมดัลหนึ่งมิติ หรือหลายมิติหลายมิติ

วิธีการเชิงตัวเลขสำหรับการแก้ปัญหาการหาค่าเหมาะที่สุดมิติเดียว

ปัญหาการย่อเล็กสุดหนึ่งมิติแสดงถึงแบบจำลองการหาค่าเหมาะที่สุดทางคณิตศาสตร์ที่ง่ายที่สุด ซึ่งฟังก์ชันวัตถุประสงค์ขึ้นอยู่กับตัวแปรตัวเดียว และเซตที่ยอมรับได้คือส่วนของแกนจริง:

F(x) -> min , x เป็นของ

ปัญหาการปรับให้เหมาะสมที่ประยุกต์กับตัวแปรควบคุมตัวเดียวนำไปสู่ปัญหาทางคณิตศาสตร์ของการย่อเล็กสุดหนึ่งมิติ นอกจากนี้ ความจำเป็นในการลดฟังก์ชันของตัวแปรหนึ่งให้เหลือน้อยที่สุดเกิดขึ้นเมื่อใช้วิธีการบางอย่างในการแก้ปัญหาการปรับให้เหมาะสมที่ซับซ้อนมากขึ้น

เพื่อแก้ปัญหาการลดฟังก์ชัน F(x) บนเซกเมนต์ให้เหลือน้อยที่สุด ในทางปฏิบัติมักใช้วิธีการโดยประมาณ ช่วยให้สามารถค้นหาวิธีแก้ไขปัญหานี้ด้วยความแม่นยำที่ต้องการโดยการกำหนดค่าจำนวน จำกัด ของฟังก์ชัน F(x) และอนุพันธ์ของมันในบางจุดของเซ็กเมนต์ วิธีที่ใช้เฉพาะค่าของฟังก์ชันและไม่จำเป็นต้องคำนวณอนุพันธ์เรียกว่าวิธีการย่อขนาดโดยตรง

ข้อได้เปรียบที่สำคัญของวิธีการโดยตรงก็คือ ฟังก์ชันเป้าหมายไม่จำเป็นต้องสร้างความแตกต่าง และยิ่งไปกว่านั้น อาจไม่สามารถระบุในรูปแบบการวิเคราะห์ได้ สิ่งเดียวที่ใช้อัลกอริธึมของวิธีการย่อขนาดโดยตรงคือความสามารถในการกำหนดค่าของ F(x) ณ จุดที่กำหนด

ข้อกำหนดที่อ่อนแอที่สุดสำหรับฟังก์ชัน F(x) ซึ่งอนุญาตให้ใช้เมธอดเหล่านี้ได้คือสภาวะแบบยูนิโมดิกชัน (การมีค่าต่ำสุดหนึ่งค่าในช่วงของค่าที่อนุญาต) ดังนั้น เราจะสมมติต่อไปว่าฟังก์ชัน F(x) เป็นแบบยูนิโมดัลในช่วงเวลา

วิธีใช้กำลังดุร้าย

วิธีค้นหาแบบกำลังเดรัจฉานหรือแบบสม่ำเสมอเป็นวิธีที่ง่ายที่สุดในบรรดาวิธีการย่อขนาดโดยตรง และประกอบด้วยสิ่งต่อไปนี้

ลองแบ่งส่วนออกเป็น n ส่วนเท่าๆ กันโดยใช้จุดหาร:

xi =A+i·(B − A)/n, i=0,...n

เมื่อคำนวณค่าของ F(x) ที่จุด xi โดยการเปรียบเทียบเราจะพบจุด xm โดยที่ m คือตัวเลขตั้งแต่ 0 ถึง n ดังนั้น

F(xm) = นาที F(xi) สำหรับ i ทั้งหมดตั้งแต่ 0 ถึง n

ข้อผิดพลาดในการกำหนดจุดต่ำสุด xm ของฟังก์ชัน F(x) โดยใช้วิธีการแจงนับไม่เกินค่า ε = (B − A)/n

วิธีการแบ่งขั้ว

วิธีการนี้ใช้เพื่อค้นหาค่าสูงสุด-ปลายสุดหรือต่ำสุด-ปลายสุดของฟังก์ชันวัตถุประสงค์ยูนิโมดัลหนึ่งมิติแบบไม่เชิงเส้น

สาระสำคัญของวิธีการมีดังนี้ ให้ระบุฟังก์ชันวัตถุประสงค์ F(x) ในช่วงเวลา A≤ x ≤ B โดยแบ่งครึ่งในแต่ละระยะ สำหรับการค้นหาสองครั้งแรก

ด้วยการคำนวณฟังก์ชันวัตถุประสงค์ F(x) ที่จุด x1, x2 ทิศทางการค้นหาจึงได้รับการขัดเกลา ถ้าหาค่าต่ำสุดสุดขีดและ F(x1)< F(х2 ), то смещается правая граница первоначального интервала неопределенности , т.е. полагается В = x2 , если F(х1 ) >F(x2) จากนั้นขอบเขตด้านซ้าย A = x1 จะถูกเลื่อน หากช่วงความไม่แน่นอนใหม่ [В−А] มากกว่าค่าความคลาดเคลื่อนของสารละลายที่กำหนด ε แล้ว

การลดลงครึ่งหนึ่งยังคงดำเนินต่อไป ถ้า B−A ≤ ε แล้วคำตอบคือ x* =A + 2 B , F(x) = F(x*)

วิธีฟีโบนัชชี

วิธีการแบ่งขั้วในขณะที่อนุญาตให้ลดช่วงความไม่แน่นอนได้อย่างต่อเนื่องนั้นจำเป็นต้องมีการคำนวณค่าสองค่าของฟังก์ชันวัตถุประสงค์ที่มักจะซับซ้อนหรือการตั้งค่าการทดลองค้นหาสองครั้งเมื่อปรับโมเดลการระบุให้เหมาะสม ข้อเสียนี้ไม่มีอยู่ในการค้นหา Fibonacci วิธีฟีโบนัชชีจะขึ้นอยู่กับการใช้ลำดับของตัวเลขฟีโบนัชชีเพื่อสร้างช่วงความไม่แน่นอนที่ลดลงซึ่งเป็นช่วงที่คำตอบอยู่ ลำดับของตัวเลขฟีโบนัชชีถูกกำหนดโดยสูตรที่เกิดซ้ำ

Nn =Nn-1 +Nn-2 โดยที่ N1 =N2 =1

ช่วงความไม่แน่นอนเริ่มต้น [В−А] จะถือว่าเป็นสัดส่วนกับจำนวนฟีโบนัชชี Fn ที่กำหนดตาม