Luận văn "Ứng dụng thuật toán di truyền giải bài toán đóng thùng" tập trung vào xây dựng một thuật toán di truyền để giải bài toán đóng thùng (bin packing problem), một bài toán tối ưu tổ hợp thuộc lớp bài toán NP – khó có nhiều ứng dụng trong thực tế như thiết kế lập lịch tối ưu cho công việc; sắp xếp hàng hóa kho chứa và container tối ưu; cấp phát bộ nhớ hiệu quả; hỗ trợ thiết kế các vi mạch điện tử. | bé gi o dôc vµ µo t o tr êng i häc b ch khoa hµ néi - NGUYỄN NGỌC DƯƠNG NGUYỄN NGỌC DƯƠNG ngµnh CNTT ỨNG DỤNG THUẬT TOÁN DI TRUYỀN GIẢI BÀI TOÁN ĐÓNG THÙNG luËn v n th c sÜ NGµNH C NG NGHÖ TH NG TIN kho 2007-2009 Hµ néi 2009 bé gi o dôc vµ µo t o tr êng i häc b ch khoa hµ néi - NGUYỄN NGỌC DƯƠNG ỨNG DỤNG THUẬT TOÁN DI TRUYỀN GIẢI BÀI TOÁN ĐÓNG THÙNG luËn v n th c sÜ C NG NGHÖ TH NG TIN Ng êi h íng dÉn khoa häc . NGUYÔN øC NGHÜA Hµ Néi 2009 Lời cảm ơn Đầu tiên tôi xin bày tỏ sự biết ơn sâu sắc PGS. TS. Nguyễn Đức Nghĩa thầy đã tận tình giảng dạy chúng tôi các môn học chuyên ngành và nhiệt tình hướng dẫn giúp đỡ tôi hoàn thành luận văn này. Tôi cũng muốn bày tỏ lòng biết ơn các thầy cô khoa Công nghệ Thông tin trường Đại học Bách khoa Hà Nội đã giảng dạy cho chúng tôi các môn học chuyên đề trong khóa học. Cuối cùng gia đình đặc biệt người bạn đời của tôi là những người rất quan trọng đã một lòng động viên và tạo điều kiện giúp tôi tập trung hoàn thành luận văn này. Mặc dù đã có nhiều cố gắng nhưng vì kiến thức và thời gian hạn chế nên chắc chắn luận văn này còn nhiều thiếu sót. Tôi xin chân thành cảm ơn và rất mong nhận được những ý kiến đóng góp từ các thầy cô và các bạn. Những góp ý xin gửi về địa chỉ Nguyễn Ngọc Dương Bộ môn Khoa học máy tính khoa Công nghệ thông tin trường Đại học Bách Khoa Hà Nội. Email duongnn@ hoặc nguyenngocduong@ Hà Nội ngày 21 tháng 7 năm 2009 Nguyễn Ngọc Dương Học viên cao học Lớp Công nghệ thông tin 2007 2009 Trường Đại học Bách Khoa Hà Nội MỤC LỤC Danh mục hình Danh mục Danh mục thuật ngữ tiếng Anh. vii Chương 1. MỞ ĐẦU .1 . Lời mở đầu .1 . Các khái niệm và thuật ngữ cơ sở .3 . Bài toán tính toán thuật toán và độ phức tạp tính toán của thuật toán .3 . Các kí hiệu tiệm cận .6 . Độ phức tạp tính toán của bài toán .8 . NP- đầy đủ NP completeness .11 . Một số cách tiếp cận giải các bài toán NP-khó .18 . Phương pháp xấp xỉ .18 . Phương pháp xác xuất .19 . .
