Luận văn Thuật toán hàm công việc giải bài toán K - Server

iệu vào sau thời điểm đó sẽ ra sao. Các bài toán có đặc trưng như vậy được gọi là bài toán trực tuyến (online problem).Thuật toán để giải quyết các bài toán trực tuyến được gọi là thuật toán trực tuyến (onlinealgorithm), trong luận văn này chúng tôi gọi là thuật toán 2 online. Như vậy, thuật toán trực tuyến sẽ thực hiện và đưa ra kết quả đầu ra của bài toán chỉ dựa trên dữ liệuđầu vào tại mỗi thời điểm cung cấp và trước đó, mà không biết đến thông tin về đầu vào trong tương lai. Thuật toán trực tuyến đã được nhiều nhà khoa học và nhóm nghiên cứu quan tâm và phát triển. Tuy nhiên việc thiết kế và đánh giá thuật toán trực tuyến vẫn còn nhiều thách thức trong nghiên cứu lí thuyết cũng như triển khai ứng dụng.Trong bản luận văn nàychúng tôi sẽ trình bày những kết quả nghiên cứu xung quanh việc tìm hiểu bài toán trực tuyến, tập trung chính vào bài toán k- server, một dạng tương đối điển hình của bài toán trực tuyến, vàchiến lược thiết kế thuật toántrực tuyếncho bài toán này thông qua hàm công việc (working function). Với chủ đề “Thuật toán hàm công việc giải quyết bài toán k-server”, luận văn được cấu trúc gồm có 3 chương:  Chương 1. Tổng quan: Là chương trình bày về các khái niệm cơ bản trong thiết kế thuật toán. Trong đó, tập trung vào trình bày về thuật toán trực tuyến, các yếu tố cơ bản của việc thiết kế thuật toán trực tuyến và một số ví dụ điển hình.  Chương 2. Bài toán k-server và thuật toán hàm công việc: Là chương trình bày về một bài toán điển hình trong lớp thuật toán trực tuyến, đó là bài toán k-server. Định nghĩa về bài toán, phân tích bài toán và thiết kế một số thuật toán trong lớp thuật toán trực tuyến để giải quyết bài toán này.  Chương 3. Ứng dụng: Là chương trình bày về một số ứng dụng của thuật toán trực tuyến và bài toán k-server. Trong đó, thực nghiệm và đưa ra kết quả đánh giá đối với các thuật toán đã trình bày trong Chương 2. 3 Chương 1. Tổng quan về thiết kế thuật toán và thuật toán trực tuyến Chương này sẽ trình bày các kiến thức cơ bản sử dụng trong các phần sau, đặc biệt là các kiến thức liên quan đến thiết kế thuật toán và thuật toán trực tuyến. Kiến thức trong chương này được trình bày dựa vào các tài liệu [1], [7],[16], [17]. 1.1 Thiết kế thuật toán Khoa học máy tính là ngành nghiên cứu các cơ sở lý thuyết về thông tin và tính toán cùng sự thực hiện và ứng dụng của chúng trong các hệ thống máy tính. Khoa học máy tính gồm nhiều ngành hẹp, một số ngành tập trung vào các ứng dụng thực tiễn cụ thể chẳng hạn như đồ họa máy tính, trong khi một số ngành khác lại tập trung nghiên cứu đến tính chất cơ bản của các bài toán tính toán như lý thuyết độ phức tạp tính toán. Ngoài ra còn có những ngành khác nghiên cứu các vấn đề trong việc thực thi các phương pháp tính toán. Ví dụ, ngành lý thuyết ngôn ngữ lập trình nghiên cứu những phương thức mô tả cách tính toán khác nhau, trong khi ngành lập trình nghiên cứu cách sử dụng các ngôn ngữ lập trình và các hệ thống phức tạp, và ngành tương tác người-máy tập trung vào những thách thức trong việc làm cho máy tính và công việc tính toán hữu ích, và dễ sử dụng đối với mọi người dùng. Trong khoa học máy tính, thuật toán là một trong những khái niệm nền tảng. Đầu tiên, thuật toán được hiểu như là các quy tắc thực hiện các phép toán số học với các con số được viết trong hệ thập phân. Cùng với sự phát triển của máy tính, các khái niệm thuật toán được hiểu theo nghĩa rộng hơn. 1.1.1 Định nghĩa thuật toán Theo Niklaus Wirththì: “Thuật toán + Cấu trúc dữ liệu = Chương trình” (Algorithms + Data Structures = Programs) 4 Thuật toán là một dãy hữu hạn các thao tác cơ bản được sắp xếp theo một trình tự xác định dùng để giải một bài toán. Một thuật toán, một thủ tục tính toán được định nghĩa chính xác, là lấy một giá trị hoặc một tập các giá trị, được gọi là đầu vào hay dữ liệu vào và tạo ra một giá trị, hoặc một tập các giá trị, và gọi là đầu ra. Miêu tả một vấn đề thường được xác định nói chung qua quan hệ đầu vào/đầu ra. Một thuật toán là một dãy bước xác định để chuyển đổi dữ liệu đầu vào thành dữ liệu đầu ra. Chúng ta có thể xem một thuật toán như một công cụ để giải quyết một vấn đề tính toán. Việc trình bày rõ ràng một vấn đề nói chung hình thành mối quan hệ mong muốn đầu vào/đầu ra. Dãy thao tác đơn giản, có thể “giao cho máy tính làm được” để từ đầu vào có thể dẫn ra đầu ra một cách tường minh. Một thuật toán được gọi là chính xác nếu với mọi dữ liệu vào, nó kết thúc với kết quả chính xác. Chúng ta nói rằng một thuật toán chính xác giải quyết một vấn đề đã cho chính xác. Một thuật toán không chính xác có thể không dừng tại mọi bộ dữ liệu vào, hoặc cho kết quả không chính xác. Đối lập với nhiều suy nghĩ, một thuật toán không chính xác đôi khi có ích, nếu tỉ lệ lỗi có thể quản lý được. Mỗi thao tác trong thuật toán hay còn gọi là tác vụ, phép toán, chỉ thị hay lệnh là một hành động cần được thực hiện bởi cơ chế thực hiện của thuật toán. Mỗi thao tác biến đổi bài toán từ một trạng thái trước sang trạng thái sau. Thực tế, mỗi thao tác thường sử dụng một số đối tượng trong trạng thái nhập và sản sinh ra các đối tượng mới trong trạng thái xuất. Quan hệ giữa hai trạng thái xuất và nhập cho thấy tác động của thao tác. Dãy thao tác của thuật toán nối tiếp nhau nhằm biến đổi bài toán từ trạng thái ban đầu đến trạng thái kết thúc. Khi một thuật toán đã hình thành thì ta không xét đến việc chứng minh thuật toán đó mà chỉ chú trọng đến việc áp dụng các bước theo sự hướng dẫn sẽ có kết quả đúng. Việc chứng minh tính đầy đủ và tính đúng của các thuật toán phải được tiến hành xong trước khi có thuật toán. Nói rõ hơn, thuật toán có thể chỉ là việc áp dụngcác công thức hay quy tắc, quy trình đã được công nhận là đúng hay 5 đã được chứng minh về mặt toán học."Thuật toán" hiện nay thường được dùng để chỉ thuật toán giải quyết các vấn đề tin học. Hầu hết các thuật toán tin học đều có thể viết thành các chương trình máy tính mặc dù chúng thường có một vài hạn chế (vì khả năngcủa máy tính và khả năng của người lập trình). Trong nhiều trường hợp, một chương trình khi thiết kế bị thất bại là do lỗi ở các thuật toán mà người lập trình sử dụng không chính xác, không đầy đủ, hay không ước định được trọn vẹn lời giải của vấn đề. Tuy nhiên cũng có một số bài toán mà hiện nay người ta chưa tìm được lời giải triệt để, những bài toán ấy gọi là những bài toán NP-không đầy đủ. Như trên,thuật toán ngoài ra còn chỉ những phương pháp đem lại được kết quả một cách tối ưu,giảm lượng tài nguyên bỏ ra để đạt được.Những phương pháp này có thể được rút ra từ thực nghiệm và có thể giải được bằng toán học hoặc không,tuy nhiên mọi thuật toán đáp ứng tính logic tối hậu của tự nhiên mà là nguyên do của nhiều loại logic mờ. Khi nghiên cứu về thuật toán, người ta quan tâm đến các vấn đề sau:  Giải được bằng thuật toán: Lớp bài toán nào giải được bằng thuật toán, lớp bài toán không giải được bằng thuật toán.  Tối ưu hóa thuật toán: Tìm những thuật toán tốt hơn.  Triển khai thuật toán: Sử dụng các ngôn ngữ lập trình để thực hiện thuật toán trên máy tính. Thời gian mà máy tính khi thực hiện một thuật toán không chỉ phụ thuộc vào bản thân thuật toán đó, ngoài ra còn tùy thuộc từng máy tính. Để đánh giá hiệu quả của một thuật toán, có thể xét số các phép tính phải thực hiện khi thực hiện thuật toán này. Thông thường số các phép tính được thực hiện phụ thuộc vào cỡ của bài toán, tức là độ lớn của đầu vào. Vì thế độ phức tạp thuật toán là một hàm phụ thuộc đầu vào. Tuy nhiên trong những ứng dụng thực tiễn, chúng ta không cần biết chính xác hàm này mà chỉ cần biết một ước lượng đủ tốt của chúng. 6 1.1.2 Các đặc trưng cơ bản của thuật toán Thuật toán có một số đặc trưng cơ bản sau: a. Tính khách quan: Các thao tác, đối tượng trong thuật toán phải có ý nghĩa rõ ràng, không gây nhầm lẫn. Nói cách khác, dù cho thực hiện theo người hay theo máy, thuật toán đều phải đưa ra cùng một kết quả. b. Tính dừng: Thuật toán phải dừng và cho kết quả sau một số bước hữu hạn. c. Tính đúng đắn: Thuật toán đúng là thuật toán cho kết quả thỏa mãn yêu cầu đặc tả của mọi trường hợp đối tượng và đầu vào. Thuật toán là sai nếu kết quả đưa ra sai trong ít nhất một trường hợp. d. Tính phổ dụng: Thuật toán dùng để giải một lớp bài toán gồm nhiều bài toán cụ thể, lớp đó được xác định bởi đặc tả. Thuật toán không chỉ áp dụng cho một bài toán nhất định mà có thể áp dụng cho một lớp các bài toán có đầu vào tương tự nhau. 1.1.3 Các dạng biểu diễn thuật toán Trong ngành khoa học máy tính, thuật toán được thể hiện thông qua một chương trình máy tính (hay một tập hợp các chương trình máy tính) và được thiết kế để giải quyết một số bài toán một cách có hệ thống.Thuật toán có thể diễn đạt dưới ba dạng: liệt kê từng bước, sơ đồ khối, mã giả. a. Dạng liệt kê từng bước: Là dạng thuật toán được trình bày theo ngôn ngữ tự nhiên theo trình tự các bước thực hiện trong thuật toán. b. Dạng sơ đồ khối: Là dạng dùng các hình vẽ để diễn đạt thuật toán. Cho hình ảnh trực quan và tổng thể của thuật toán, dễ hiểu và dễ sử dụng. c. Dạng mã giả: Là dạng thuật toán trình bày trong một văn bản, tuy không ràng buộc nhiều như dạng ngôn ngữ lập trình nhưng cũng tuân theo một số quy ước ban đầu. Tùy theo việc định hướng cài đặt thuật toán theo ngôn ngữ lập trình nào mà ta diễn đạt thuật toán gần với ngôn ngữ lập trình ấy. 7 1.1.4 Các phương pháp thiết kế thuật toán Các bài toán giải được trên máy tính ngày càng phức tạp và đa dạng. Các thuật toán đòi hỏi có quy mô lớn, tốn nhiều thời gian và công sức. Tuy nhiên, công việc sẽ đơn giản hơn nếu ta chia bài toán ra thành các bài toán nhỏ. Cách thiết kế thuật toán này gọi là Modul hóa và thiết kế từ trên xuống. Chiến thuật thiết kế này là chia để trị, tức là nhìn nhận vấn đề một cách tổng quát, sau đó chia nhỏ bài toán thành các bài toán nhỏ và dần dần giải quyết các bài toán nhỏ đó. Đây thường là cách tiếp cận của con người với hầu hết các vấn đề trong cuộc sống.Ví dụ: Hình 1: Mô hình thiết kế thuật toán từ trên xuống. Thông thường, ta chia được các bài toàn thành hai lớp không giao nhau: Lớp bài toán giải được bằng thuật toán và lớp không giải được bằng thuật toán. Đối với lớp các bài toán giải được bằng thuật toán, dựa vào các đặc trưng của quá trình thiết kế, người ta phân thành một số phương pháp điển hình sau:  Phương pháp chia để trị  Phương pháp quay lui  Phương pháp nhánh cận A A1 A11 A12 A2 A3 A31 A32 A33 8  Phương pháp tham lam  Phương pháp quy hoạch động  Phương pháp trực tuyến  Phương pháp ngẫu nhiên  Phương pháp xấp xỉ Khi xây dựng các thuật toán theo các phương pháp trên, có hàng loạt vấn đề cần được giải quyết. Thường là: yêu cầu về tính đúng đắn của thuật toán, yêu cầu về thời gian, không gianHầu hết các phương pháp trên đều đã được phân tích và nghiên cứu rất rõ ràng. Tuy nhiên các phương pháp vẫn tiếp tục được nghiên cứu để đưa ra lời giải tốt hơn. 1.2 Thuật toán trực tuyến (Thuật toán online) 1.2.1 Giới thiệu Phân tích và thiết kế thuật toán luôn luôn liên quan đến vấn đề tối ưu hóa. Thông thường, người ta thường hi vọng rằng một thuật toán sẽ thực thi với số lần tính toán ít nhất. Ví dụ, mục tiêu của người thiết kế thuật toán là giảm tổng thời gian cần thiết để giải quyết một bài toán nhất định. Trong một số trường hợp khác, người ta quan tâm nhiều hơn đến việc giảm thiểu bộ nhớ được sử dụng trong thuật toán đó. Ngoài ra, có một số bài toán đòi hỏi các thuật toán đề ra một giải pháp để có thể giảm thiểu chi phí qua các giải pháp khả thi – ví dụ như bài toán lập lịch và bài toán định tuyến mạng. Lý thuyết về các thuật toán trực tuyến cũng tập trung vào việc cung cấp các thuật toán, các phương pháp để giải quyết vấn đề tối ưu hóa khi đầu vào được cung cấp theo thời gian. Sự phát triển của lý thuyết tối ưu cổ điển được dựa trên giả định rằng tất cả dữ liệu đầu vào đều có sẵn cho các thuật toán. Tuy nhiên, với nhiều vấn đề thực tế, dữ liệu đầu vào chỉ có sẵn từng mảng và sau đó tiến triển dần. Ví dụ như bài toán phân trang (Paging Problem) [8], một trong những vấn đề cổ điển trong việc thiết kế hệ thống điều hành: Bộ nhớ của một hệ thống máy tính điển hình 9 bao gồm một bộ nhớ nhanh được chia thành một số phần bằng nhau gọi là các trang và bộ nhớ thứ cấp là bộ nhớ lớn hơn nhưng chậm hơn. Các đơn vị xử lí trung tâm có thể truy cập chỉ có bộ nhớ nhanh, ở đây thường chứa các bản sao của các trang nhất định trong bộ nhớ thứ cấp. Vì chỉ có dữ liệu trong bộ nhớ nhanh được truy cập, nên một chính sách quyết định là cần thiết để xác định và thiết lập một tập các trang để duy trì trong bộ nhớ nhanh mỗi lần sử dụng. Đặc biệt, một chính sách thay thế trang là cần thiết để quyết định trang ra khỏi bộ nhớ nhanh để nhường chỗ cho một trang được yêu cầu. Từ quan điểm của lý thuyết tối ưu hóa thông thường, các đầu vào cho một thuật toán cho bài toán phân trang là một chuỗi các yêu cầu trang và mục đích là để giảm thiểu số lượng trang lỗi – số trang bị loại ra khỏi bộ nhớ nhanh. Một thuật toán tham lam đơn giản là tối ưu cho bài toán này: Hoãn trang lỗi tiếp theo càng lâu càng tốt bằng cách loại bỏ trang đó cuối cùng từ các trang trong bộ nhớ nhanh để có thể yêu cầu thêm một lần nữa. Vấn đề xảy ra đối với thuật toán này là chuỗi trang yêu cầu là trong tương lai. Thực tế thì trình tự các trang yêu cầu trong tương lai là chưa biết và nó không thể được tính từ quá khứ. Do đó, bất kì thuật toán nào để phân trang cũng có căn cứ quyết định của mình về trình tự đã được tiết lộ của trang yêu cầu. Bài toán phân trang là một bài toán đặc trưng của thuật toán trực tuyến: Một vấn đề tối ưu hóa không phải tất cả các dữ liệu đầu vào liên quan đều được biết trước, mà sẽ tiến triển theo thời gian. Nói chung, một bài toán trực tuyến là một bộ ba (I, O, c) trong đó:  I là tập các kí hiệu đầu vào  O là một tập các kí hiệu đầu ra  c: {In× On+1: n ≥ 0} → R+ là một hàm chi phí. Một thuật toán trực tuyếnA cho một bài toán (I, O, c) là một hàm A: I* → O. Khi đó, với một chuỗi đầu vào r = (r1, , rn) ∈ 𝐼, A đưa ra một chuỗi đầu ra y = (y0,y1, , yn) ∈ 𝑂. Với: 10 yj = A(r1, , rj) Tức là, với mỗi kí tự đầu vào, thuật toánAcho kết quả là một kí tự đầu ra. Chi phí của thuật toán A cho mỗi đầu vào rkí hiệucostA(r)= cost(r,y). Với bài toán phân trang với một bộ nhớ nhanh gồm k trang, I là một tập tất cả các trang, O là tập tất cả các trạng thái của k trang. Khi đó, yj là tập các trang trong bộ nhớ nhanh tại bước thứ j. Hàm chi phí c là chi phí di chuyển các trang trong bộ nhớ nhanh được tính như sau: Tại bước j, chi phí tỉ lệ thuận với sự khác nhau đối xứng yj-1 và yjvới điều kiệnyj chứa trang được yêu cầu cuối cùng là rj, đây là số trang chúng ta phải di chuyển theo thứ tự để thay đổi trạng thái của bộ nhớ nhanh từ yj-1 sang yj. Từ trang rj phải di chuyển vào trong bộ nhớ nhanh, chúng tôi muốn yj chứa rj và điều này được thực hiện bằng cách thiết lập một chi phí của bước j cao tùy ý khi mà nó không phải là các trường hợp. Các chi phí cost(r,y) là tổng chi phí cho tất cả các bước. Chú ý rằng, có một đầu ra y0là trạng thái ban đầu, trong bài toán phân trang, nó là thiết lập ban đầu của các trang trong bộ nhớ nhanh. Đối với mỗi bài toán trực tuyến, đều có một bài toán offline liên quan, trong đó đầu ra yjcủa thuật toán offline B bây giờ có thể phụ thuộc vào đầu vào trong tương lai: yj = B(r1, , rj) Chi phí tối ưu của thuật toán offline, kí hiệu là OPT(r), là chi phí nhỏ nhất đạt được của các thuật toán offline đối với đầu vào r. Trong tối ưu hóa tổ hợp cổ điển, luôn luôn có một thuật toán mà có thể tính toán một giải pháp tối ưu cho tất cả các đầu vào và khó khăn là làm thế nào để điều đó hiệu quả nhất. Ngược lại đối với các bài toán trực tuyến với tài nguyên thông tin khan hiếm, và không có sức tính toán cao. Kết quả là, việc nghiên cứu các thuật toán trực tuyến cho đến nay chủ yếu tập trung vào chất lượng của các giải pháp và không tập trung vào hiệu quả của thuật toán. Mặt khác, đối với một 11 đầu vào cố định có một thiết kế thuật toán trực tuyến đặc biệt mà khi đó sẽ có một chi phí tối ưu. Điều này cho thấy rằng không có một thuật toán trực tuyến tốt nhất thực hiện trên tất cả các đầu vào khác nhau. Tuy nhiên, sự phát triển của một lí thuyết thuật toán cho các bài toán trực tuyến chỉ có thể dựa vào đánh giá về chất lượng của các thuật toán trực tuyến đó. Một đánh giá đưa ra bởi Sleator và Tarjan [7] đề xuất tỉ lệ cạnh tranh của một thuật toán đó là: Tỉ lệ trong trường hợp xấu nhất của chi phí đạt được bằng chi phí của thuật toán trực tuyếnchia cho chi phí tối ưu. Như vậy, tỉ lệ cạnh tranh của một thuật toán A được tính là: 𝑐 = 𝑚𝑎𝑥𝑟 𝑐𝑜𝑠𝑡 𝐴 (𝑟) 𝑂𝑃𝑇(𝑟) (1) Trong đó, r là tập tất cả các đầu vào. Thông thường,sẽ tồn tại một hằng số độc lập với đầu vào r để loại bỏ sự phụ thuộc vào trạng thái ban đầu. Một thuật toán được gọi là c – cạnh tranh hoặc chỉ đơn giản là cạnh tranh nếu nó có hữu hạn cạnh tranh với tỉ lệ c. Cuối cùng, các nghiên cứu về các bài toán trực tuyến sử dụng tỉ lệ cạnh tranh tốt nhất được gọi là phân tích cạnh tranh. Phân tích cạnh tranh đã được áp dụng thành công cho nhiều vấn đề trực tuyến tự nhiên. Hơn nữa, nó phục vụ như là một biện pháp thống nhất cho việc nghiên cứu các thuộc tính chung của các bài toán trực tuyến. Các bài toán trực tuyến đã và đang được nghiên cứu đối với nhiều vấn đề tự nhiên. Một trong số đó là các hệ thống nhiệm vụ trong không gian mêtric, nổi bật là các bài toán quản lí dữ liệu và quản lí bộ nhớ trực tuyến như bài toán phân trang. Một hệ thống nhiệm vụ cung cấp một chuỗi các kí hiệu đầu vào, gọi là nhiệm vụ, các chi phí thực hiện một nhiệm vụ phụ thuộc vào trạng thái nội bộ của hệ thống và các loại nhiệm vụ yêu cầu. Một hệ thống nhiệm vụ metric là một hệ thống nhiệm vụ với các chi phí của việc thay đổi trạng thái đáp ứng các bất đẳng thức tam giác: Nếu thay đổi từ trạng thái A sang trạng thái C thì chi phí không quá thay đổi từ A đến B và từ B đến C. Trong trường hợp của bài toán phân trang, trong trạng thái nội 12 tại của hệ thống đều là tập các trang của bộ nhớ nhanh, rất dễ dàng để thấy rằng chi phí của việc thay đổi trạng thái nội bộ đáp ứng các bất đẳng thức tam giác. Khi tất cả các nhiệm vụ được yêu cầu thực hiện, tỉ lệ cạnh tranh là 2n-1, trong đó n là số các trạng thái nội bộ. Tóm lại, đối với thuật toán ngoại tuyến (thuật toán offline), các dữ liệu đầu vào được nhập một lần toàn bộ trước khi thuật toán thực hiện. Tuy nhiên đối với các thuật toán trực tuyến (thuật toán online), các dữ liệu đầu vào không được nhập một lần toàn bộ trước khi thuật toán thực hiện do điều kiện không gian nhớ hoặc do tính chất dữ liệu. Tại mỗi bước thực hiện thuật toán phải có phương án kết quả mà không biết dữ liệu tiếp theo sẽ ra sao. Vì thế, thuật toán trực tuyến phải dự đoán được quy luật phân bố dữ liệu và xử lí trong trường hợp xấu nhất. Độ phức tạp của thuật toán trực tuyến là tuyến tính dựa theo kích thước dữ liệu đầu vào do xử lí lần lượt, liên tiếp. Thuật toán trực tuyến không cho ra kết quả chính xác duy nhất, tuy nhiên các thuật toán này thường giảm thiểu các lỗi chiến lược. Vì thế, đối với thuật toán trực tuyến, chúng ta quan tâm tới việc đánh giá hiệu năng của thuật toán, đó là kết quả tốt nhất trong điều kiện (thời gian, không gian) cho phép. 1.2.2 Phân tích cạnh tranh Việc phân tích hiệu suất của một thuật toán trực tuyến là vấn đề luôn được quan tâm. Đối với một bài toán tối ưu hóa, hiệu suất của một thuật toán trực tuyến có thể được đo lường bằng cách so sánh chi phí thuật toán đó với một thuật toán tối ưu đã có. Tại thời điểm này, người ta có thể tự hỏi suy luận như thế nào về các chi phí cho một thuật toán trực tuyến, vì nếu đã biết thuật toán tối ưu để giải quyết bài toán đó, thì đơn giản nhất là có thể dùng luôn thuật toán này. Giả thuyết rằng đã có một thuật toán tối ưu giả OPT đối với một bài toán trực tuyến. 13 Hiệu suất của một thuật toán trực tuyến có thể được đo lường bằng tỉ lệ cạnh tranh của nó. Cho r = r1, r2, , rn là dãy đầu vào của một thuật toán trực tuyếnA và với OPT là hiệu suất của thuật toán offline tối ưu. Khi đó tỉ lệ cạnh tranh c được xác định là tỉ lệ trong trường hợp tồi tệ nhất của chi phí đạt được bằng chi phí của thuật toántrực tuyếnA chia cho chi phí tối ưu (theo (1)). Một thuật toántrực tuyếnA là c-cạnh tranh nếu như với bất kì chuỗi đầu vào r nào thì sẽ tồn tại một hằng số b sao cho: 𝑐𝑜𝑠𝑡𝐴(𝑟) ≤ c. OPT(r)+b. Nếu A là c-cạnh tranh thì chúng ta nói rằng A có tỉ lệ cạnh tranh là c. Bằng trực giác, điều này có nghĩa là chi phí cho các thuật toán A là không nhiều hơn một yếu tố không đổi lần của c và lớn hơn so với chi phí cho một thuật toán tối ưu ẩn giả của chuỗi đầu vào lên đến một hằng số phụ. Một chiến thuật phổ biến trong thiết kế và phân tích thuật toán là sử dụng ngẫu nhiên để cải thiện hiệu suất. Một ví dụ điển hình cho nguyên tắc này là lựa chọn ngẫu nhiên một phần tử làm trục trong thuật toán sắp xếp nhanh (Quick sort). Chúng ta có thể mở rộng việc sử dụng tính ngẫu nhiên để phân tích và thiết kế thuật toán trực tuyến. Với biến ngẫu nhiên X, E(X) là giá trị kì vọng của X. Khi đó, một thuật toán trực tuyến ngẫu nhiên A là c-cạnh tranh nếu như với bất kì chuỗi đầu vào r, luôn tồn tại một hằng số b sao cho: E(𝑐𝑜𝑠𝑡𝐴(𝑟)) ≤ c. OPT(r)+b. Trong cả hai cách thiết kế ngẫu nhiên và xác định, chúng tôi luôn mong muốn thiết kế một thuật toán trực tuyến nhằm làm giảm tối thiểu tỉ lệ cạnh tranhc. Điều này cho chúng ta một sự đảm bảo về hiệu suất của một thuật toán trực tuyến so với một thuật toán tối ưu [9]. 1.2.3 Một số bài toán điển hình Tương tự như đối với các phương pháp khác, có một số bài toán điển hình cho thuật toán trực tuyến. Đặc biệt phải kể đến là bài toán thuê hay mua, bài toán 14 thư kí, bài toán k-server. Trong phần này, luận văn sẽ trình bày về hai bài toán ban đầu. Chương II sẽ trình bày chi tiết về bài toán k-server. 1.2.3.1 Bài toán thuê hay mua (rent-or-buy problem)1 Bài toán thuê hay mua (rent-or-buy problem) [14] được mô tả như sau: Một người quyết định học môn trượt tuyết do yêu thích. Đây là một môn thể thao cần có một số thiết bị chuyên sâu như giày trượt, ván trượt, gậy,.... Nếu người đó mua giày trượt tuyết thì một đôi có giá lày$ (y là một số tiền khá lớn) và nếu như thuê đôi giày đó vào ngày cuối tuần sẽ có giá là x$/1 ngày. Nếu như người chơi học trượt tuyết và đi chơi trong t lần, khi đó số tiền phải bỏ ra là m = t*x. Vậy vấn đề đưa ra là người chơi nên mua hay nên thuê giày để số tiền phải bỏ ra là ít nhất (y$ hoặc m$)?Việc thuê hay mua giày phụ thuộc vào số lần người chơi sẽ đi trượt tuyết trong tương lai. Tuy nhiên, số lần đi trượt tuyết này sẽ không biết trước do có nhiều lí do: người chơi bận công việc, thời tiết xấu, người chơi không may bị tai nạn hoặc sau một số lần chơi thì người chơi mất hứng, không muốn chơi trượt tuyết nữa,... Mỗi lần đi chơi, người chơi phải quyết định xem nên mua hay thuê giày. Nếu biết trước số lần đi mua giày, người chơi có thể tính toán được chi phí tối thiểu. Tại mỗi lần chơi, nếu lần trước đã mua giày thì thuật toán này kết thúc, nếu chưa thì sẽ quyết định thuê hay mua dựa vào dữ kiện là số lần chơi. Đây là một trong những bài toán tối ưu, đầu vào lần lượt được đưa vào ở mỗi lần thực hiện thuật toán. Vì thế bài toán này sẽ được giải quyết bằng thuật toán trực tuyến. Như vậy, có thể hiểu bài toán theo cách phân tích sau: o Input: Giá thuê, giá mua. o Output: Thời điểm mua giày để đạt hiệu quả cao nhất. Sử dụng thuật toán trực tuyến để giải quyết bài toán thuê hay mua, cần sử dụng phân tích cạnh tranh và xác định tỉ lệ cạnh tranh cho bài toán này theo công thức: 1https://www.ima.umn.edu/~mali/Online_Brown-Bag_Slides.pdf 15 𝑐 = 𝑂𝑛𝑙𝑖𝑛𝑒𝐴𝑙𝑔𝑜𝑟𝑖𝑡ℎ𝑚𝑆𝑜𝑙𝑢𝑡𝑖𝑜𝑛 𝑂𝑝𝑡𝑖𝑚𝑎𝑙𝑆𝑜𝑙𝑢𝑡𝑖𝑜𝑛 Như vậy, thuật toán trực tuyến cần tìm ra thời điểm t(số lần chơi) để giá trịc tối ưu nhất. Giả sử số tiền mua một đôi giày trượt tuyết là 500$ và mỗi lần thuê giày tốn 50$. Khi đó, nếu người chơi đi trượt tuyết 1 lần, khi đó t = 1 và c = 500/50 = 10. Nếu người chơi đi trượt tuyết 2 lần, khi đó t = 2, c = 550/100 = 5.5.  Tổng quát: o Khi t ≤ 10, c = 500+50(𝑡−1) 50𝑡 = 1 + 9 𝑡 o Khi t ≥ 10, c = 500+50(𝑡−1) 500 = 0.9 + 𝑡 10 o Vậy, tỉ lệ cạnh tranh tối ưu c = 1.9 khi t = 10. Như vậy, nếu người chơi đi trượt tuyết 11 hoặc hơn 11 lần, thì tốt nhất là nên mua giày. Nếu như đi trượt tuyết 9 lần hoặc ít hơn thì thuê sẽ là tốt hơn. Và nếu như đi trượt tuyết 10 lần thì thuê hay mua cũng như nhau. 1.2.3.2 Bài toán thư kí (Secretary_problem)2 Bài toán thư ký là m