The wildly popular Spanish-language

The wildly popular Spanish-language search engine El Goog needs to do a serious
amount of computation every time it recompiles its index. Fortunately, the company
has at its disposal a single large supercomputer, together with an essentially unlimited
supply of high-end PCs.
They’ve broken the overall computation into n distinct jobs, labeled J1; J2; : : : ; Jn,
which can be performed completely independently of one another. Each job consists
of two stages: first it needs to be prepocessed on the supercomputer, and then it needs
to be finished on one of the PCs. Let’s say that job Ji needs pi seconds of time on the
supercomputer, followed by fi seconds of time on a PC.
Since there are at least n PCs available on the premises, the finishing of the jobs can be
performed fully in parallel – all the jobs can be processed at the same time. However,
the supercomputer can only work on a single job at a time, so the system managers
need to work out an order in which to feed the jobs to the supercomputer. As soon as
the first job in order is done on the supercomputer, it can be handled off to a PC for
finishing; at that point in time a second job can be fed to the supercomputer; when the
second job is done on the supercomputer, it can proceed to a PC regardless of whether
or not the first job is done (since the PCs work in parallel); and so on.
Let’s say that a schedule is an ordering of the jobs for the supercomputer, and the
completion time of the schedule is the earliest time at which all jobs will have finished
processing on the PCs. This is an important quantity to minimize, since it determines
how rapidly El Goog can generate a new index.
Give a polynomial-time algorithm that finds a schedule with as small a completion
time as possible. Prove your answer.

ผลลัพธ์ (ไทย) 1:

อาละวาดนิยมภาษาสเปนค้นหาเอลได้เลยต้องทำการร้ายแรงจำนวนคำนวณทุกครั้งจะ recompiles ตัว บริษัทโชคดีมีที่ของตัวเดียวขนาดใหญ่ซูเปอร์คอมพิวเตอร์ พร้อมกับเป็นการไม่จำกัดจัดหาเครื่องคอมพิวเตอร์คุณภาพสูงพวกเขาได้แบ่งการคำนวณโดยรวมงานทั้งหมด n ป้าย J1 J2 : : : ; Jnซึ่งสามารถดำเนินการได้ทั้งหมดแยกกัน แต่ละงานประกอบด้วยขั้นตอนที่สอง: ก่อน มันต้องเป็น prepocessed บนซูเปอร์คอมพิวเตอร์ที่ และจากนั้น ก็จะแล้วเสร็จในหนึ่งชิ้น สมมติว่า งานจิต้องปี่วินาทีเวลาในการซูเปอร์คอมพิวเตอร์ ตาม ด้วยสายวินาทีเวลาบนพีซีเนื่องจากมี n น้อยชิ้นในสถานที่ การสิ้นสุดของงานได้อย่างดำเนินการทั้งหมดพร้อมกัน – งานสามารถประมวลผลพร้อมกัน อย่างไรก็ตามซูเปอร์คอมพิวเตอร์ที่สามารถทำงานงานหนึ่งครั้ง ดังนั้นผู้จัดการระบบจำเป็นต้องออกใบสั่งในการเลี้ยงงานซูเปอร์คอมพิวเตอร์ที่ ทันทีงานแรกในใบสั่งจะทำบนที่ซูเปอร์คอมพิวเตอร์ มันสามารถจัดการปิดพีซีสำหรับสิ้นสุด ที่จุดในเวลา งานที่สองที่สามารถจะเลี้ยงให้ซูเปอร์คอมพิวเตอร์ เมื่อการงานที่สองจะทำบนที่ซูเปอร์คอมพิวเตอร์ มันสามารถดำเนินต่อไปพีซีไม่ว่าหรือไม่งานแรก เสร็จ (นับตั้งแต่ชิ้นงานพร้อมกัน); และอื่น ๆลองบอกว่า กำหนดการเป็นการจัดลำดับงานสำหรับซูเปอร์คอมพิวเตอร์ และเวลาเสร็จสิ้นของกำหนดการเป็นเวลาเร็วที่สุดซึ่งงานทั้งหมดจะเสร็จสิ้นการประมวลผลในเครื่องคอมพิวเตอร์ นี่คือปริมาณสำคัญลด เนื่องจากกำหนดอย่างรวดเร็ววิธีใช้เอลสามารถสร้างดัชนีใหม่ให้อัลกอริทึมแบบพหุนามเวลาที่ค้นหาตารางเวลาด้วยเป็นขนาดเล็กที่สมบูรณ์เวลาเป็นไปได้ พิสูจน์คำตอบของคุณ

ผลลัพธ์ (ไทย) 2:

ค้นหาความนิยมเป็นอย่างภาษาสเปนเครื่องยนต์เอ Goog ต้องทำอย่างจริงจัง
จำนวนของการคำนวณทุกครั้งที่มัน recompiles ดัชนี โชคดีที่ บริษัท
มีการกำจัดของซูเปอร์คอมพิวเตอร์ขนาดใหญ่พร้อมกับไม่ จำกัด เป็นหลัก
. อุปทานของเครื่องคอมพิวเตอร์ระดับ high-end
พวกเขาได้หักคำนวณโดยรวมลงไปในงานที่แตกต่างกัน n ป้าย J1; J2; :::; ยอห์น,
ซึ่งสามารถดำเนินการได้อย่างสมบูรณ์เป็นอิสระจากกัน แต่ละงานจะประกอบด้วย
สองขั้นตอนแรกจะต้องมีการ prepocessed ในซูเปอร์คอมพิวเตอร์และจากนั้นจะต้อง
จะแล้วเสร็จในหนึ่งของเครื่องคอมพิวเตอร์ สมมติว่างานจีที่ต้องการวินาทีปี่เวลาใน
ซูเปอร์คอมพิวเตอร์ตามวินาทีไฟของเวลาในเครื่องคอมพิวเตอร์.
เนื่องจากมีอย่างน้อย n พีซีที่มีอยู่ในสถานที่การตกแต่งของงานที่สามารถ
ดำเนินการได้อย่างเต็มที่ในแบบคู่ขนาน - ทั้งหมด งานที่สามารถประมวลผลได้ในเวลาเดียวกัน แต่
ซูเปอร์คอมพิวเตอร์สามารถทำงานในงานเดียวในเวลาดังนั้นผู้บริหารระบบ
ต้องทำงานออกคำสั่งในการที่จะเลี้ยงเพื่องานซูเปอร์คอมพิวเตอร์ ทันทีที่
งานแรกเพื่อที่จะทำในซูเปอร์คอมพิวเตอร์ที่จะสามารถจัดการออกไปยังเครื่องคอมพิวเตอร์สำหรับ
การตกแต่ง; ที่จุดในเวลาที่งานที่สองสามารถป้อนให้กับซูเปอร์คอมพิวเตอร์; เมื่อ
งานที่สองจะทำในซูเปอร์คอมพิวเตอร์ที่จะสามารถดำเนินการต่อไปยังเครื่องคอมพิวเตอร์ไม่ว่าจะ
ได้หรือไม่งานแรกที่จะทำ (ตั้งแต่เครื่องคอมพิวเตอร์ที่ทำงานในแบบคู่ขนาน); และอื่น ๆ .
ขอบอกว่าเป็นช่วงเวลาที่การสั่งซื้อของงานสำหรับซูเปอร์คอมพิวเตอร์และ
เวลาแล้วเสร็จของตารางเป็นเวลาที่เร็วที่สุดที่งานทั้งหมดจะเสร็จสิ้น
การประมวลผลบนเครื่องพีซี นี้เป็นสิ่งสำคัญที่จะมีปริมาณลดเพราะมันเป็นตัวกำหนด
วิธีการอย่างรวดเร็วเอ Goog สามารถสร้างดัชนีใหม่.
ให้ขั้นตอนวิธีพหุนามเวลาที่พบช่วงเวลาที่มีขนาดเล็กเสร็จสิ้น
เวลาที่เป็นไปได้ พิสูจน์คำตอบของคุณ

ผลลัพธ์ (ไทย) 3:

ที่ป่าที่เป็นที่นิยมเครื่องมือค้นหาภาษาสเปน El กุ๊กต้องทำยอดเงินร้ายแรง
การคำนวณทุกครั้งที่มัน recompiles ดัชนีของ โชคดีที่บริษัท
มีการจัดการที่เดี่ยวขนาดใหญ่ ซูเปอร์คอมพิวเตอร์ของ ด้วยกันกับอุปทานหลักของเครื่องคอมพิวเตอร์สูงไม่จำกัด

มันหักในการคำนวณโดยรวมแตกต่างกัน งานป้าย n , J1 ; j2 ; : : : ; ชุมทาง
,ซึ่งสามารถดำเนินการได้อย่างสมบูรณ์อิสระของอีกคนหนึ่ง งานแต่ละงานประกอบด้วย
2 ขั้นตอน มันต้อง prepocessed บนซูเปอร์คอมพิวเตอร์ และจากนั้น มันต้องการ
จะเสร็จในหนึ่งของชิ้น สมมติว่าต้องการงานจีพีวินาทีของเวลาบน
ซูเปอร์คอมพิวเตอร์ตาม Fi วินาทีของเวลาในเครื่องคอมพิวเตอร์
เนื่องจากมีอย่างน้อย n ชิ้น ที่มีอยู่ในสถานที่การตกแต่งของงานสามารถดำเนินการอย่างเต็มที่ใน–ขนาน
งานทั้งหมดที่สามารถประมวลผลได้ในเวลาเดียวกัน อย่างไรก็ตาม
ซูเปอร์คอมพิวเตอร์สามารถทํางานในงานเดียวในเวลาเพื่อให้ผู้บริหารระบบต้องทำงาน
ออกเพื่อที่จะให้งานกับซูเปอร์คอมพิวเตอร์ ทันทีที่
งานก่อนเพื่อที่จะทำในซูเปอร์คอมพิวเตอร์ มันสามารถจัดการปิดคอมพิวเตอร์สำหรับ
เสร็จ ;ที่จุดในเวลางานที่สองสามารถไปซูเปอร์ เมื่อ
งานที่สองเสร็จบนซูเปอร์คอมพิวเตอร์ มันสามารถดำเนินการกับเครื่องคอมพิวเตอร์ไม่ว่า
หรือไม่ก่อนงานเสร็จ ( เนื่องจากคอมพิวเตอร์ทำงานในแบบขนาน ) ; และอื่น ๆ .
สมมติว่า ตารางคือ การสั่งซื้อของงานสำหรับซูเปอร์คอมพิวเตอร์และ
เวลาแล้วเสร็จของตารางเป็นครั้งแรกที่งานทั้งหมดจะเสร็จสิ้น
การประมวลผลในคอมพิวเตอร์นี้เป็นปริมาณที่สำคัญในการลด เนื่องจากจะกำหนดวิธีการอย่างรวดเร็ว
เอล GOOG สามารถสร้างดัชนีใหม่ .
ให้พหุนามเวลาขั้นตอนวิธีการที่พบว่าช่วงเวลาที่มีขนาดเล็กเมื่อ
เวลาเป็นไปได้ พิสูจน์คำตอบ