Đến nội dung


perfectstrong

Đăng ký: 30-09-2010
Offline Đăng nhập: Hôm qua, 22:11
****-

Chủ đề của tôi gửi

Bài toán sắp xếp

01-10-2021 - 03:39

BÀI TOÁN SẮP XẾP

 

 

 

Richard Walter Conway, William L. Maxwell, et Louis W. Miller.
Theory of Scheduling. Dover, 2003.

 

 

Chúng ta gặp những bài toán sắp xếp cực kỳ thường xuyên. Chúng xuất hiện mỗi khi chúng ta phải quyết định thực hiện các công việc theo thứ tự nào. Mỗi bài toán có thể liên quan tới một thứ khác nhau, ví dụ: lô hàng ở một nhà máy sản xuất, máy bay chờ đợi lệnh hạ cánh, khách khứa ngồi trước cửa kính ở quầy tiếp khách trong ngân hàng, chương trình để chạy trong máy tính, hay đơn giản là công việc dọn nhà chiều thứ bảy. Luận điểm của chúng tôi đó là, bất kể tính chất của một công việc cụ thể cần xác định thứ tự thực hiện, thì luôn luôn tồn tại sự tương đồng căn bản với bài toán sắp xếp.

 

Bài toán sắp xếp rõ ràng sẽ được giải quyết, bởi vì hầu hết các công việc đều được thực hiện: máy bay hạ cánh, khách ngân hàng nhận/chuyển tiền, và chúng ta làm xong ít nhất vài việc nhà chiều thứ bảy. Tuy nhiên, đa số các bài toán này được giải theo cách ngẫu nhiên hoặc theo lề thói. Chúng ta còn không nhận ra cả sự tồn tại của bài toán đó, chứ đừng nói đến lời giải. Đôi khi, sự sắp xếp được quyết định hoàn toàn bừa bãi; nhiều lúc công việc được thực hiện theo thứ tự chúng xuất hiện. Khao khát công bằng cố hữu đã nâng cao giá trị của giải pháp "tới trước làm trước" (first-come, first-served) trong các bài toán sắp xếp tới một mức độ vô cùng bất xứng với hiệu năng vốn có của nó. Giải pháp ấy có thể thích hợp với những ông chủ bán vé xem phim, song không hẳn sẽ áp dụng tốt với các lô hàng bất động trên sàn nhà máy.

 

Phát biểu vấn đề và lời giải một cách chuẩn tắc cho một bài toán sắp xếp có lẽ là chuyện hiếm. Nếu có thì đại để sẽ như sau:

  • $\alpha$ là chuỗi hành động thực hiện $A$ trước rồi $B$.
  • $\beta$ là chuỗi hành động thực hiện $B$ trước rồi $A$.
  • Vì $\alpha$ được ưa thích hơn $\beta$ nên ta chọn "làm $A$ rồi $B$".

Dĩ nhiên chúng ta sẽ không biện luận rằng phân tích chuẩn tắc trên là thích đáng cho toàn thể bài toán sắp xếp trong đời sống thường nhật, tuy nhiên, đối với những vấn đề trong hoạt động công nghiệp, vận tải, cơ quan chính phủ cũng như tổ chức thì kết quả sắp xếp không phải là chuyện nhỏ nhặt, và chúng ta nên bỏ công sức để suy ngẫm một cách bài bản. Ấy thế các vấn đề đó lại bị giải quyết quá thường xuyên bằng thói quen chứ không phải giải thuật. Điều phối viên máy móc trong công xưởng, dầu là người quyết định những lô hàng nào trong dãy hàng chờ sẽ được làm, lại hay dùng các tiêu chí không liên quan mấy tới mục đích của công ty. Chương trình trên máy tính sẽ chạy theo thứ tự gửi tới CPU, một quy trình công bằng không thể cãi, nhưng ai cũng sẽ thấy rằng làm như vậy còn lâu mới đạt được tới tối ưu. Các chương sách tiếp theo sẽ chứng minh bằng lập luận đại số, ví dụ bằng số cụ thể và thử nghiệm trên máy tính, để cho chúng ta thấy có sự khác biệt đáng kể giữa các thứ tự sắp xếp khác nhau. Ít nhất thì trong một số bài toán thực tế, những khác biệt này ắt hẳn sẽ tạo ra sai khác phí tổn hoặc giá trị thành phẩm đủ lớn để chúng ta cân nhắc. Vấn đề ở đây không phải là quyết định xem có nên giải quyết một bài toán sắp xếp cụ thể nào đó, nên chọn thứ tự nào. Vấn đề là chúng ta sẽ xác định xem quyết định được đưa ra bằng phương pháp nào, bởi ai, và cho tiêu chí gì.

 

 

Vấn đề sắp xếp có lẽ không thiết yếu bằng các quyết định xem tác vụ nào kế tiếp, hoặc tác vụ đó được thực hiện ra sao khi việc tới. Tuy nhiên, nếu lựa chọn thứ tự hợp lý có thể cải thiện kết quả phần nào, thì chúng ta không nên bỏ qua cơ hội như thế. Dẫn chứng trong những chương kế tiếp sẽ chỉ ra rằng nếu áp dụng một cách phân loại, dù là đơn giản nhất, vào hệ thống đa nhiệm, thì chúng ta vẫn sẽ luôn tìm ra những khác biệt thú vị chỉ có thể xuất hiện do thay đổi thứ tự tác vụ. Trong nhiều trường hợp, nhiều giải thuật mặc dù hữu dụng và thực tiễn ngang nhau, lại có những đặc tính hiệu năng khác nhau đáng kể.

 

 

(Còn nữa)


Tìm số dương $k$ lớn nhất sao cho khoảng cách từ mọi điểm nguyên trên mặt phẳ...

20-06-2021 - 14:27

Một điểm trên mặt phẳng nếu có tọa độ đều là số nguyên thì được gọi là điểm nguyên.

Cho đường thẳng $(d): y=ax+b$, trong đó $a$ là một số hữu tỷ khác 0 và $d$ không chứa bất kì điểm nguyên nào. Tìm số dương $k$ lớn nhất sao cho khoảng cách từ mọi điểm nguyên trên mặt phẳng tới đường thẳng $d$ đều không nhỏ hơn $k$.

 

Câu hỏi mở rộng: chúng ta có thể giải bài toán trong trường hợp $a$ vô tỷ không?


${x_m} = 0 \Rightarrow \sum\limits_{k = 0}^m...

09-05-2021 - 14:32

Một biến số $x$ được gọi là biến nhị phân nếu $x$ chỉ có thể nhận giá trị $0$ hoặc $1$.

Cho $n + 1 (n \ge 0)$ biến nhị phân $x_0, x_1, \ldots, x_n$ và một số tự nhiên $p$ không lớn hơn $n+1$. Hãy tìm một hệ bất phương trình bậc nhất biểu diễn mệnh đề sau:

$$\forall m \in [0; n+1]: \, {x_m} = 0 \Rightarrow \sum\limits_{k = 0}^m {{x_k}}  = 0 \vee \sum\limits_{k = 0}^m {{x_k}}  = p$$


$f(x,y)$ liên tục trên $D \subset \mathbb{R}^2$

08-12-2017 - 02:05

(Sáng tác)

Cho $D \subset \mathbb{R}^2$ là một miền liên thông đóng (tức với mọi cặp điểm $A, B$ trong $D$, kể cả biên giới, thì luôn tồn tại một đường đi "liền nét" từ $A$ tới $B$ sao cho đường đi không cắt ra ngoài $D$.)

Định nghĩa $f: D \rightarrow \mathbb{R}$ như sau: Vẽ một đường tròn có tâm $(x,y)$ và bán kính $f(x,y)$ sao cho đường tròn lớn nhất có thể có và tiếp xúc với viền của $D$.

Chứng minh rằng $f(x,y)$ liên tục.


Tuần 1 tháng 12/2017

04-12-2017 - 00:54

Như vậy lời giải cho hai bài Tuần 5 tháng 11/2017 đã được đưa tại đây kèm theo đó là 4 bài toán mới của thầy Trần Quang Hùng, thầy Nguyễn Tiến Dũng, Ngô Quang Dương và I.Frolov. Xin được trích dẫn lại bài toán:
 
Bài 1. (Trần Quang Hùng)
Cho $ABCDEF$ là lục giác lồi thỏa mãn $AB=CD=EF$ và $BC=DE=FA$ đồng thời $\angle A + \angle B = \angle C + \angle D = \angle E + \angle F$. Chứng minh rằng $\angle B = \angle D = \angle F$.

File gửi kèm  001.JPG   13.47K   48 Số lần tải

 
Bài 2. (Ngô Quang Dương)
Cho tam giác $ABC$ nội tiếp đường tròn $(O)$. $D$ là một điểm nằm trên cạnh $BC$. Một đường tròn tiếp xúc đoạn thẳng $DA, DB$ và tiếp xúc trong $(O)$ tại $F$. Một đường tròn tiếp xúc các đoạn thẳng $DA, DC$ và tiếp xúc trong $(O)$ tại $E$. Chứng minh rằng đường tròn ngoại tiếp tam giác $IEF$ luôn trực giao với $(O)$ và đi qua một điểm cố định khác $I$.

@halloffame: anh Hân xem lại hình như bài này ghi thiếu dữ kiện $I$ là tâm nội tiếp.

File gửi kèm  002.JPG   22.42K   49 Số lần tải


Bài 3. (Nguyễn Minh Hà, trường xuân 2015)
Cho tam giác $ABC$, trực tâm $H$, tâm đường tròn Euler $N$, điểm Lemoine $L$. $AH, BH, CH$ theo thứ tự cắt $BC, CA, AB$ tại $D, E, F$. $X, Y, Z$ theo thứ tự là tâm đường tròn ngoại tiếp các tam giác $HBC, HCA, HAB$. Chứng minh rằng $DX, EY, FZ$ đồng quy tại một điểm thuộc $NL$.


File gửi kèm  003.JPG   20.2K   44 Số lần tải

 
Bài 4. (I.Frolov, Sharygin Olympiad 2017 Final Round)
Cho tam giác $ABC$ có đường cao $BE, CF$ và đường tròn bàng tiếp góc $A$ là $(J)$. Hai tiếp tuyến chung trong của các đường tròn $(AEF)$ và $(J)$ cắt $BC$ tại $M, N$. Chứng minh rằng $BM = CN$.

File gửi kèm  004.JPG   19.56K   51 Số lần tải