Tổ chức dữ liệu cho lớp thuật toán chia để trị và ứng dụng

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

1

ĐẠI HỌC THÁI NGUYÊN

TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN&TRUYỀN THÔNG

Đỗ Tuấn Anh

TỔ CHỨC DỮ LIỆU CHO LỚP THUẬT TOÁN

CHIA ĐỂ TRỊ VÀ ỨNG DỤNG

Chuyên ngành: Khoa học máy tính

Mã số: 60.48.01

TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Thái Nguyên - 2014

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

2

LỜI CAM ĐOAN

Tôi xin cam đoan đây là công trình nghiên cứu của bản thân, được xuất phát từ yêu

cầu phát sinh trong công việc để hình thành hướng nghiên cứu. Các số liệu có nguồn gốc

rõ ràng tuân thủ đúng nguyên tắc và kết quả trình bày trong luận văn được thu thập được

trong quá trình nghiên cứu là trung thực chưa từng được ai công bố trước đây.

Thái Nguyên, ngày 19 tháng 5 năm 2014

Học viên thực hiên

Đỗ Tuấn Anh

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

3

LỜI CẢM ƠN

Đầu tiên, em xin gửi lời cảm ơn sâu sắc nhất đến cán bộ hướng dẫn khoa học, thầy

giáo, PGS.TSKH Nguyễn Xuân Huy, người đã truyền cho em nguồn cảm hứng nghiên cứu

khoa học, người đã định hướng cho em đến với lĩnh vực nghiên cứu này.

Em xin bày tỏ lời cảm ơn tới các thầy giáo, cô giáo đã giảng dạy em trong suốt hai

năm học qua. Em cũng muốn gửi lời cảm ơn tới những thành viên lớp đã có những góp ý

chuyên môn cũng như sự động viên về tinh thần rất đáng trân trọng.

Cuối cùng, em xin gửi lời cảm ơn sâu sắc tới tất cả người thân trong gia đình và

những bạn bè em với những động viên dành cho em trong công việc và trong cuộc sống.

Học viên thực hiện luận văn

Đỗ Tuấn Anh

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

4

MỤC LỤC

Trang

Lời cam đoan

Lời cảm ơn

Mục lục............................................................................................................................ iii

Danh mục các bảng ...........................................................................................................v

Danh mục các hình vẽ .......................................................................................................v

MỞ ĐẦU...........................................................................................................................1

CHƢƠNG 1. CÁC CHIẾN LƢỢC THIẾT KẾ THUẬT TOÁN................................2

1.1 Các bước cơ bản khi giải bài toán trên máy tính........................................................2

1.2 Phân tích thời gian thực hiện thuật toán......................................................................6

1.2.1 Độ phức tạp thuật toán .............................................................................................6

1.2.2 Xác định độ phức tạp của thuật toán ........................................................................9

1.2.3 Ký hiệu Big-O và biểu diễn thời gian chạy của thuật toán ....................................10

1.2.4 Độ phức tạp thuật toán với tình trạng dữ liệu vào..................................................13

1.2.5 Chi phí thực hiện thuật toán ...................................................................................13

CHƢƠNG 2. TỔ CHỨC DỮ LIỆU CHO LỚP THUẬT TOÁN CHIA ĐỂ TRỊ ...14

2.1 Chiến lược chia để trị ...............................................................................................14

2.2 Tổ chức dữ liệu cho lớp thuật toán chia để trị..........................................................15

2.3 Định lý tổng quát tính độ phức tạp các thuật toán chia để trị...................................16

2.4 Một số lớp bài toán điển hình...................................................................................17

2.4.1 Lớp bài toán tìm kiếm ............................................................................................18

2.4.1.1 Thuật toán tìm kiếm nhị phân .............................................................................18

2.4.1.2 Bài toán tìm Max và min.....................................................................................20

2.4.2 Lớp bài toán sắp xếp...............................................................................................22

2.4.2.1 Thuật toán sắp xếp trộn (Merge Sort) .................................................................22

2.4.2.2 Thuật toán sắp xếp nhanh (Quick Sort)...............................................................24

2.4.3 Lớp bài toán tối ưu .................................................................................................27

2.4.3.1 Bài toán dãy con dài nhất ....................................................................................27

2.3.3.2 Bài toán tháp Hà Nội...........................................................................................29

2.3.3.5 Bài toán xếp lịch thi đấu......................................................................................30

CHƢƠNG 3. ỨNG DỤNG THUẬT TOÁN CHIA ĐỂ TRỊ GIẢI BÀI TOÁN

NHÂN HAI SỐ NGUYÊN LỚN ..................................................................................32

3.1 Mô tả bài toán............................................................................................................32

3.2 Thuật toán nhân tự nhiên...........................................................................................32

3.3 Thuật toán nhân cơ bản .............................................................................................33

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

5

3.4 Thuật toán nhân Karatsuba-Ofman ...........................................................................35

3.5 Thuật toán nhân dựa trên biến đổi Fourier nhanh .....................................................37

3.6 Thuật toán nhân chia để trị........................................................................................40

3.6.1 Ý tưởng chung........................................................................................................40

3.6.2 Phân tích thuật toán ................................................................................................41

3.6.3 Mô hình thuật toán chia để trị cho bài toán nhân hai số nguyên lớn .....................44

3.6.4 So sánh độ phức tạp giữa các thuật toán ................................................................46

3.7 Tổ chức dữ liệu cho thuật toán chia để trị.................................................................46

3.7.1 Biểu diễn dưới dạng bit ..........................................................................................46

3.7.2 Biểu diễn dùng mảng và xâu ..................................................................................47

3.8 Thực nghiệm và đánh giá ..........................................................................................51

3.8.1 Cài đặt trên C..........................................................................................................51

3.8.2 Cài đặt trên C#........................................................................................................59

KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ...................................................................64

TÀI LIỆU THAM KHẢO ............................................................................................65

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

6

DANH MỤC CÁC BẢNG

Bảng 1.1 Các lớp độ phức tạp tính toán ..............................................................................11

Bảng 1.2 Thời gian chạy của các lớp thuật toán..................................................................12

Bảng 2.1 Độ phức tạp của thuật toán tìm kiếm nhị phân ....................................................20

Bảng 2.2 Độ phức tạp của thuật toán sắp xếp nhanh...........................................................26

Bảng 3.1 So sánh độ phức tạp tính toán của các thuật toán nhân .......................................46

DANH MỤC CÁC HÌNH

Hình 2.1 Thuật toán chia để trị............................................................................................14

Hình 2.2 Tổ chức dữ liệu cho lớp bài toán chia để trị........................................................ 15

Hình 2.3 Ví dụ thuật toán sắp xếp trộn................................................................................23

Hình 3.1 Thuật toán nhân Brute-force.................................................................................33

Hình 3.2 Thuật toán nhân chuẩn..........................................................................................34

Hình 3.3 Thuật toán nhân SRMA........................................................................................35

Hình 3.4 Thuật toán nhân Karatsuba-Ofman ......................................................................37

Hình 3.5 Thuật toán nhân FFT ............................................................................................39

Hình 3.6 Thuật toán nhân chia để trị ...................................................................................45

Hình 3.7 Phép nhân chia để trị tổ chức dưới dạng bit.........................................................46

Hình 3.8 Thuật toán nhân chia để trị biểu diễn bit..............................................................47

Hình 3.9 Ví dụ về phép chia Ấn Độ

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

7

MỞ ĐẦU

.Ngày nay phương pháp này vẫn còn được áp dụng trong nhiều lĩnh vực của đời

sống. Đặc biệt, phương pháp này rất hiệu quả khi thiết kế thuật toán giải các bài toán lớn,

phức tạp. Với bài toán đầu vào rất lớn ta chia thành những phần nhỏ hơn và tìm lời giải

cho các bài toán nhỏ riêng biệt này, rồi sau đó tổng hợp các nghiệm riêng rẽ thành nghiệm

bài toán toàn cục.

Trong luận văn này, tôi sẽ tập trung phân tích việc tổ chức dữ liệu cho lớp thuật toán

chia để trị và cách đánh giá độ phức tạp đối với các thuật toán chia để trị.Với mục tiêu

chính là áp dụng thiết kế thuật toán chia để trị để giải quyết bài toán nhân hai số nguyên

lớn, luận văn được trình bày trong 3 chương với bố cục như sau:

Chƣơng 1: Các chiến lƣợc thiết kế thuật toán. Giới thiệu tổng quan về các bước

giải bài toán trên máy tính và phân tích đánh giá thời gian thực hiện thuật toán cùng các

chiến lược thiết kế thuật toán cơ bản.

Chƣơng 2: Tổ chức dữ liệu cho lớp thuật toán chia để trị.Trình bày ý tưởng, cơ sở

khoa học của thuật toán chia để trị và cách thức tổ chức dữ liệu cho thuật toán chia để trị

với các bài toán kinh điển.

Chƣơng 3: Ứng dụng thuật toán chia để trị giải bài toán nhân hai số nguyên lớn.

Tập trung phân tích các cách tiếp cận giải bài toán nhân hai số nguyên lớn. Từ đó đề xuất

thuật toán dựa trên tư tưởng chia để trị để giải quyết và thực nghiệm so sánh với các cách

tiếp cận trước đó.

Cuối cùng là kết luận và hƣớng phát triển:Tóm tắtnhững kết quả đạt được, những

hạn chế và nêu lên các hướng phát triển trong tương lai.