Tóm tắt Thuật toán hàm công việc giải quyết bài toán k-server

ĐẠI HỌC QUỐC GIA HÀ NỘI<br /> TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN<br /> ---------------------<br /> <br /> Lã Ngọc Hải<br /> <br /> THUẬT TOÁN HÀM CÔNG VIỆC<br /> GIẢI BÀI TOÁN K-SERVER<br /> <br /> LUẬN VĂN THẠC SĨ KHOA HỌC<br /> <br /> Hà Nội - 2016<br /> <br /> ĐẠI HỌC QUỐC GIA HÀ NỘI<br /> TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN<br /> ---------------------<br /> <br /> Lã Ngọc Hải<br /> <br /> THUẬT TOÁN HÀM CÔNG VIỆC<br /> GIẢI BÀI TOÁN K-SERVER<br /> <br /> Chuyên ngành: Cơ sở toán cho tin học<br /> Mã số:60460110<br /> <br /> LUẬN VĂN THẠC SĨ KHOA HỌC<br /> <br /> NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. Nguyễn Thị Hồng Minh<br /> <br /> Hà Nội – 2016<br /> <br /> Lời cảm ơn<br /> Em xin gửi lời cảm ơn tới các Thầy giáo, Cô giáo, Cán bộ khoa Toán - Cơ<br /> - Tin học, trường Đại học khoa học tự nhiên, Đại học Quốc gia Hà Nội đã tận<br /> tình dạy dỗ và giúp đỡ em trong suốt thời gian học cao học.<br /> Trong quá trình thực hiện luận văn này cũng như trong suốt những năm<br /> học vừa qua, em đã nhận được sự chỉ bảo và hướng dẫn nhiệt tình của TS.<br /> Nguyễn Thị Hồng Minh. Em xin gửi tới Cô lời cảm ơn chân thành nhất.<br /> Em cũng xin gửi lời cảm ơn tới gia đình, bạn bè đã động viên, khuyến<br /> khích và tạo điều kiện cho em trong quá trình học tập và thực hiện luận văn này.<br /> Mặc dù đã cố gắng để hoàn thành luận văn, nhưng do hạn chế về kinh<br /> nghiệm và thời gian, nên luận văn không thể tránh khỏi những thiếu sót. Em<br /> mong nhận được sự cảm thông và những ý kiến đóng góp của các Thầy, Cô và<br /> các bạn.<br /> Hà Nội, tháng 11 năm 2016<br /> Học viên<br /> <br /> Lã Ngọc Hải<br /> <br /> i<br /> <br /> Mục lục<br /> Mở đầu .................................................................................................................. 1<br /> Chương 1. Tổng quan về thiết kế thuật toán và thuật toán online ................. 3<br /> 1.1<br /> <br /> Thiết kế thuật toán..................................................................................... 3<br /> <br /> 1.1.1<br /> <br /> Định nghĩa thuật toán ......................................................................... 3<br /> <br /> 1.1.2<br /> <br /> Các đặc trưng cơ bản của thuật toán................................................... 6<br /> <br /> 1.1.3<br /> <br /> Các dạng biểu diễn thuật toán ............................................................ 6<br /> <br /> 1.1.4<br /> <br /> Các phương pháp thiết kế thuật toán .................................................. 7<br /> <br /> 1.2<br /> <br /> Thuật toán trực tuyến (Thuật toán online) ................................................ 8<br /> <br /> 1.2.1<br /> <br /> Giới thiệu ............................................................................................ 8<br /> <br /> 1.2.2<br /> <br /> Phân tích cạnh tranh ......................................................................... 12<br /> <br /> 1.2.3<br /> <br /> Một số bài toán điển hình ................................................................. 13<br /> <br /> Chương 2. Bài toán k-server và thuật toán hàm công việcError! Bookmark not defined<br /> 2.1<br /> <br /> Bài toán k-server ..................................... Error! Bookmark not defined.<br /> <br /> 2.1.1<br /> <br /> Định nghĩa ........................................ Error! Bookmark not defined.<br /> <br /> 2.1.2<br /> <br /> Tính online của bài toán k-server ..... Error! Bookmark not defined.<br /> <br /> 2.1.3<br /> <br /> Một số bài toán liên quan ................. Error! Bookmark not defined.<br /> <br /> 2.2<br /> <br /> Một số hướng giải quyết bài toán k-serverError! Bookmark not defined.<br /> <br /> 2.2.1<br /> <br /> Thuật toán tham lam ......................... Error! Bookmark not defined.<br /> <br /> 2.2.2<br /> <br /> Thuật toán ngẫu nhiên RANDOM-SlackError! Bookmark not defined.<br /> <br /> 2.2.3<br /> <br /> Thuật toán ngẫu nhiên Hamornic ..... Error! Bookmark not defined.<br /> <br /> 2.3<br /> <br /> Thuật toán hàm công việc (WFA) giải quyết bài toán k-serverError! Bookmark no<br /> <br /> 2.3.1<br /> <br /> Thuật toán hàm công việc................. Error! Bookmark not defined.<br /> <br /> 2.3.2<br /> <br /> Thuật toán hàm công việc cải tiến .... Error! Bookmark not defined.<br /> <br /> Chương 3. Ứng dụng của bài toán k-server .... Error! Bookmark not defined.<br /> 3.1<br /> <br /> Bài toán ................................................... Error! Bookmark not defined.<br /> <br /> 3.1.1<br /> <br /> Đặt bài toán ....................................... Error! Bookmark not defined.<br /> <br /> 3.1.2<br /> <br /> Bài toán tổng quát ............................. Error! Bookmark not defined.<br /> <br /> 3.2<br /> <br /> Phân tích yêu cầu bài toán....................... Error! Bookmark not defined.<br /> ii<br /> <br /> 3.3<br /> <br /> Thiết kế chương trình .............................. Error! Bookmark not defined.<br /> <br /> 3.3.1<br /> <br /> Phần cứng ......................................... Error! Bookmark not defined.<br /> <br /> 3.3.2<br /> <br /> Kết quả thực nghiệm......................... Error! Bookmark not defined.<br /> <br /> Kết luận ............................................................... Error! Bookmark not defined.<br /> Tài liệu tham khảo ............................................................................................. 18<br /> <br /> iii<br /> <br />