Tính toán song song và ứng dụng vào bài toán tổ hợp

ĐẠI HỌC ĐÀ NẴNG

TRƯỜNG ĐẠI HỌC SƯ PHẠM

-------------------------------------

HUỲNH LÊ ĐẠI NGỌC

TÍNH TOÁN SONG SONG VÀ

ỨNG DỤNG VÀO BÀI TOÁN TỔ HỢP

Chuyên ngành: Hệ thống thông tin

Mã số: 8480104

TÓM TẮT LUẬN VĂN THẠC SĨ HỆ THỐNG THÔNG TIN

Đà Nẵng - Năm 2019

Công trình được hoàn thành tại

TRƯỜNG ĐẠI HỌC SƯ PHẠM

Người hướng dẫn khoa học: TS. NGUYỄN ĐÌNH LẦU

Phản biện 1: PGS. TS. Võ Trung Hùng

Phản biện 2: GS. TS. Nguyễn Thanh Thủy

Luận văn đã được bảo vệ trước Hội đồng chấm Luận văn tốt

nghiệp thạc sĩ ngành Hệ thống thông tin họp tại trường Đại học

Sư phạm vào ngày 06 tháng 4 năm 2019.

Có thể tìm hiểu luận văn tại:

- Thư viện Trường Đại học Sư phạm – ĐHĐN

- Khoa Công nghệ thông tin, trường Đại học Sư phạm - ĐHĐN

1

MỞ ĐẦU

1. Lý do chọn đề tài

Toán học tổ hợp là một ngành toán học rời rạc, nghiên cứu về

các cấu hình kết hợp các phần tử của một tập hợp hữu hạn phần tử.

Toán tổ hợp có liên quan đến rất nhiều lĩnh vực khoa học như đại số,

xác xuất, thống kê, hình học, vật lý thông kê và đặt biệt được ứng

dụng nhiều trong ngành khoa học máy tính. Các bài toán cơ bản của

toán tổ hợp là cơ sở phát triển các thuật toán cho bài toán sắp xếp,

phân rã, hoán vị. Thế nhưng các bài toán tổ hợp thường là các bài

toán có độ phức tạp cao, khối lượng tính toán lớn và thời gian tính

toán khá dài gây ra những khó khăn cho việc tính toán.

Xã hội hiện đại, phát triển liên tục như hiện nay đặt ra cho

chúng ta nhiều vấn đề, nhiều bài toán ngày một phức tạp, nhu cầu

tính toán xử lý ngày càng lớn. Việc tính toán tuần tự theo truyền

thống không còn đáp ứng tốt nhu cầu lượng tính toán khổng lồ này

nữa. Cùng với đó là sự phát triển của các bộ xử lý đa nhân, đa luồng

có thể thực hiện đa nhiệm, đa tác vụ cùng lúc. Nhiều hệ thống máy

tính lớn là sự liên kết của rất nhiều máy tính với nhau để có thể xử lý

tính toán một bài toán phức tạp. Tất cả đã mở ra một thời đại mới,

thời đại của tính toán song song.

Tính toán song song là một hình thức tính toán, trong đó nhiều

phép tính được thực hiện đồng thời. Dựa trên nguyên tắc chính là một

bài toán lớn chia thành những phần nhỏ có thể tính toán độc lập với

nhau một cách đồng thời.

Tính toán song song và ứng dụng tính toán song song vào bài

toán tổ hợp mang lại nhiều ý nghĩa lớn cho ngành khoa học máy tính

cũng như các ngành khoa học liên quan khác. Trước đây đã có những

đề tài nghiên cứu về tính toán song song cũng như nghiên cứu về bài

2

toán tổ hợp, nhưng chỉ là những nghiên cứu tách biệt và việc nghiên

cứu ứng dụng tính toán song song vào bài toán tổ hợp vẫn chưa thực

sự được quan tâm theo đúng sự quan trọng của nó. Thế nên tôi, được

sự đồng ý của cán bộ hướng dẫn, lựa chọn đề tài này để làm luận văn.

2. Mục tiêu nghiên cứu

- Nghiên cứu tính toán song song và bài toán tổ hợp.

- Đề xuất giải pháp tính toán song song để tính toán bài toán

tổ hợp nhằm tăng hiệu quả tình toán, tăng hiệu suất tính toán trên

máy tính, hỗ trợ tính toán cho các lĩnh vực khác có liên quan.

- Thử nghiệm các giải pháp trên môi trường java với thư viện

Thread tính toán song song song.

3. Đối tượng và phạm vi nghiên cứu

Đối tượng:

- Nghiên cứu lý thuyết tính toán song song, các mô hình máy

tính, các mô hình tính toán song song, các bước để xây dựng thuật

toán song song, các phương pháp phân rã bài toán.

- Các bài toán tổ hợp: Dãy bị chặn, tập con, hoán vị của tập

hợp.

- Ứng dụng tính toán song song vào bài toán tổ hợp, thử

nghiệm trên môi trường java với thư viện Thread.

Phạm vi nghiên cứu:

- Đề xuất giải pháp thuật toán tính toán song song trên bài

toán tổ hợp.

- Lập trình ứng dụng tính toán song song vào bài toán tổ hợp

bằng thư viện Thread để thử nghiệm thuật toán.

4. Phương pháp nghiên cứu

- Phương pháp nghiên cứu tài liệu

- Phương pháp phân tích

3

- Phương pháp tổng hợp

- Phương pháp thực nghiệm nêu ví dụ

5. Ý nghĩa khoa học và thực tiễn của đề tài

Luận văn trình bày lý thuyết tính toán song song, các mô hình

tính toán song song, cách xây dựng thuật toán song song, cách phân

tách bài toán phân rã để thực hiện song song và các bài toán tổ hợp.

Từ đó đề xuất các giải pháp tính toán bằng phương pháp song song

cho bài toán tổ hợp tăng hiệu xuất tính toán cho các máy tính. Thử

nghiệm thực tiễn trên môi trường Java sử dụng thư viện Thread.

4

CHƯƠNG 1. TỔNG QUAN TÍNH TOÁN SONG SONG

1.1. Tính toán song song và các mô hình tính toán song

song

1.1.1 . Mô hình SISD (Single Intruction, Single data):

1.1.2 . Mô hình SIMD (Single Intruction, Multiple data):

1.1.3 . Mô hình MISD (Multiple Intruction, Single data):

1.1.4 . Mô hình MIMD (Multiple Intruction, Multiple data):

1.2. Mô hình máy tính PRAM

1.3. Thuật toán song song

1.3.1 . Quy trình xây dựng thuật toán song song

Việc xây dựng, thiết kế một chương trình tính toán song song

từ một thuật toán tuần tự đã có chúng ta cần trải qua 4 giai đoạn là:

phân rã, truyền thông, tích tụ và ánh xạ.

Phân rã: Là công việc sau khi đã xác định và phân tích bài

toán. Các công việc tính toán cũng như các nguồn dữ liệu đầu vào,

đầu ra được phân rã thành nhiều tác vụ. Từ đó phân tích từng tác vụ

và tìm ra các tác vụ có thể tính toán độc lập với nhau về dữ liệu đầu

ra, đầu vào hoặc độc lập về cách tính toán…

Truyền thông: là công đoạn thể hiện các tác vụ qua từng

luồng thông tin sao cho các luồng đó có thể thực hiện độc lập, đồng

thời. Tính toán thực hiện một tác vụ kèm theo những dữ liệu đầu ra,

đầu vào. Sau đó được truyền giữa các tác vụ để thực hiện tính toán.

Tích tụ: giai đoạn này sẽ gom các tác vụ đã phân rã ở trên

thành những tác vụ lớn hơn giúp giảm chi phí truyền thông nhưng

cũng gây ra việc giảm tiềm năng thực hiện đồng thời.

Ánh xạ: là giai đoạn cuối cùng, mỗi tác vụ sẽ được ấn định

vào một bộ xử lý nào đó để tiến hành việc tính toán.

1.3.2 . Nguyên lý thiết kế thuật toán song song

5

Thuật toán song song là tập các tiến trình hoặc các tác vụ thực

hiện đồng thời có thể trao đổi dữ liệu với nhau kết hợp cùng giải

quyết một vấn đề lớn. Để thiết kế được thuật toán song song, ta cần

quan tâm đến các nguyên lý thiết kế sau:

- Nguyên lý tập lịch: Tạo lịch trình để giảm tối thiểu bộ xử lý

sử dụng nhưng vẫn giữ không tăng thời gian tính toán theo

độ phức tạp.

- Nguyên lý hình ống: Thực hiện khi bài toán xuất hiện một

dãy các thao tác {T1,T2,…Tn} trong đó Ti+1 thực hiện sau

khi Ti kết thúc.

- Nguyên lý chia để trị: Chia bài toán thành nhiều phần nhỏ

hơn có tính độc lập với nhau để thực hiện song song.

- Nguyên lý đồ thị phụ thuộc dữ liệu: phân tích mối quan hệ

giữ các dữ liệu để xây dựng đồ thị phụ thuộc dữ liệu từ đó

xác định đúng được dữ liệu ra vào trong từng phần của thuật

toán song song.

- Nguyên lý điều kiện tương tranh: Nếu nhiều tiến trình cũng

muốn truy xuất vào cùng một vùng dữ liệu thì cần xem xét

điều kiện tương tranh, các tiến trình đó có cản trở nhau hay

hay không.

Ngoài ra chúng ta cũng cần chú ý thuật toán song song phải

được thiết kết dựa trên những kiến thức về kiến trúc máy tính, ngôn

ngữ lập trình song song và các phương pháp tính toán.

1.3.3 . Các cách tiếp cận trong thiết kế

Trong tính toán song song ta có ba cách tiếp cận để thiết kế:

- Thực hiện song song hóa từ những thuật toán tuần tự, biến

đổi những cấu trúc tuần tự để tận dụng được những khả năng

6

song song tự nhiên của tất cả các thành phần trong hệ thống

xử lý.

- Thiết kế những thuật toán song song cần phải phù hợp với

các kiến trúc song song.

- Xây dựng những thuật toán song song từ những thuật toán

song song có trước cho phù hợp với điều kiện và môi trường

song song thực tế.

1.3.4 . Phân rã

1.3.4.1 . Phân rã đệ quy

1.3.4.2 . Phân rã dữ liệu

1.3.4.3 . Phân rã thăm dò

1.4 . Phân tích và đánh giá thuật toán song song

Mức độ tăng tốc của thuật toán song song sử dụng p bộ xử lý

được xác định như sau: Sp = TS /Tp

Trong đó,

TS là thời gian thực hiện tính toán trên một bộ xử lý

Tp là thời gian thực hiện tính toán trên p bộ xử lý.

Thời gian thực hiện song song, ký hiệu là tp gồm hai phần tcomp

và tcomm.

tp = tcomp + tcomm

Trong đó, tcomp là thời gian tính toán và tcomm thời gian truyền

thông dữ liệu.

7

CHƯƠNG 2. TOÁN HỌC TỔ HỢP

2.1. Tập hợp và các nguyên lý cơ bản

2.1.1 . Tập hợp

2.1.2 . Các nguyên lý cơ bản

2.1.3 . Các cấu hình tổ hợp

2.1.3.1 . Chỉnh hợp

2.1.3.2 . Tổ hợp

2.1.3.3 . Hoán vị

2.2. Bài toán liệt kê

2.2.1 . Các phương pháp liệt kê

2.2.1.1 . Liệt kê từ điển

2.2.1.2 . Phương pháp sinh

2.2.2 . Các bài toán liệt kê thường gặp

2.2.2.1 . Dãy bị chặn

Ký hiệu Z là tập các số nguyên. Cho n là một số nguyên dương

nào đó, giả sử p và q là 2 dãy số nguyên có độ dài n và ký hiệu như

sau:

p=( p1 p2…pn), q=(q1 q2…qn)| pi

, qi ∈ Z, ∀i ∈ 1, …, n

Ta có định nghĩa sau:

1. p ≤ q khi và chỉ khi pi ≤ qi ∀i∈ (1 … n)

2. p < q khi và chỉ khi ∃ j∈ (1 … n) : pj<qj và pi ≤qi

:

∀i∈ (1 … n) và i≠j

Bài toán dãy bị chặn được phát biểu như sau:

Cho hai dãy số nguyên s và g có độ dài n, sao cho s < g, hãy

tìm tất cả các dãy số t độ dài n sao cho s ≤ t ≤ g.

Giả sử s=(s1 s2… sn) và g=(g1 g2…gn), hai dãy này được gọi là

các dãy biên. Các dãy cần tìm t=(t1 t2... tn) phải thỏa mãn:

ti ∈ Z ⋀ Si ≤ ti ≤ gi ∀ i ∈ (1 … n) (1)

8

Định lý 1: Cho s=(s1 s2…sn) và g=(g1 g2…gn) là hai dãy

biên. Các dãy t=(t1t2...tn) là dãy bị chặn. gọi C là số lượng các dãy t.

Khi đó ta có:

C=∏

(2)

Chứng minh:

Ta có: ở vị trí đầu tiên t1 có thể chọn một trong các giá trị s1,

s1+1, s1+2, …, g1. Nên thành phần t1 có g1-s1+1 cách chọn.

Tương tự như vậy, thành phần t2 có g2-s2+1 cách chọn, thành

phần n có gn-sn+1 cách chọn. Tương tự lập luận cho ti với i=1..n kết

hợp với nguyên lý nhân ta có số lượng các dãy của t là C=(g1-

s1+1)x(g2-s2+1)x…x(gn-sn+1)= ∏

2.2.2.2 . Bài toán tập con

2.2.2.3 . Hoán vị n phần tử

2.2.2.4 . Bài toán phân hoạch

9

CHƯƠNG 3. ỨNG DỤNG TÍNH TOÁN SONG SONG VÀO

BÀI TOÁN TỔ HỢP

3.1. Bài toán sinh dãy bị chặn

3.1.1 . Xây dựng thuật toán tuần tự:

Thuật toán 1: sinh tất cả dãy bị chặn

1. BEGIN

2. Nhập n, s[i], g[i], i=1,…,n //s, g là hai biên nhỏ nhất

và lớn nhất

3. t[i]:=s[i], i=1,…,n

4. Repeat

5. Print t[i], i=1,…,n

6. i:=n;

7. While t[i] =g[i] do

8. Begin

9. t[i]:=s[i];

10. i:=i-1;

11. End;

12. If i>=1 then t[i]:=t[i]+1;

13. Untill i=0

14. END

Độ phức tạp của thuật toán sinh tất cả dãy bị chặn này xấp xỉ

bằng O(n*an

) với a = max {(g1-s1+1),(g2-s2+1),…,(gn-sn+1)}.

3.1.2 . Xây dựng thuật toán song song:

Ta xây dựng thuật toán tính toán song song tìm tất cả các dãy

bị chặn n phần tử với cách chọn k=(g1-s1+1)*(g2-s2+1),…,(gp-sp+1) là

tổng số bộ xử lý của chương trình (1<p<n) như sau:

Thuật toán 2: song song sinh tất cả dãy bị chặn

1. Begin

2. Nhập n, p (p∈ {2,3, … , n − 1})

10

3. Nhập s[i] và g[i], i = 1, … , n

4. k=(g1-s1+1)*(g2-s2+1)*…*(gp-sp+1); p=(2, 3,…,n-1) //k

là số bộ xử lý

5. //Bộ xử lý đầu tiên tìm k đoạn con, rồi phân cho các bộ

xử lý khác

Begin

//tìm dãy bị chặn theo thuật toán 1 và gửi dữ liệu đến

các bộ xử lý

5.1. s’[i]=s[i], i=1,…,p

5.2. g’[i]=g[i], i=1,…,p

5.3. cj

:=Sinh dãy bị chặn(s’(i), g’(i)), j=1,…,k

//theo thuật toán 1.

5.4. Gửi s[i], g[i] ở bước 3 đến tất cả các bộ xử lý

phụ

5.5. Gửi (cj đến pj (j=1,…,k)

End;

6. // k bộ xử lý phụ thực hiện đồng thời,

Begin

6.1. Nhận dữ liệu

6.2. Tạo sj bằng cách chèn các phần tử s[i] vào bên

phải của cj (j=1,…,k) //j là chỉ số của k bộ xử

lý phụ

6.3. Tạo gj bằng cách chèn các phần tử g[i] vào bên

phải của cj (j=1,…,k) //j là chỉ số của k bộ xử

lý phụ

6.4. tj[i]:=Sinh dãy bị chặn (sj(i), gj(i)), j=1,…,k,

i=1,…,n //theo thuật toán 1.

6.5. In kết quả

6.6. Gửi thông tin về bộ xử lý chính.

11

End;

7. End.

3.2. Bài toán tìm tập con

3.2.1 . Xây dựng thuật toán tuần tự

Thuật toán 3: tìm tập con

1. Begin

2. Nhập n và tập hợp X ={x1 x2 … xn}

3. s[i]:=0, i = 1, … , n

4. g[i]:=1, i = 0, … , n

5. Thuật toán 1 sinh tất cả các dãy số bị chặn t thỏa s

≤ t ≤ g

6. Thuật toán 4 chuyển các dãy số bị chặn t thành

các tập hợp con của X

7. End

Ở bước 6 ta có thuật toán riêng để xử lý như sau:

Thuật toán 4: chuyển các dãy bị chặn t thành các tập con

X

1. Begin

2. t:=(t1t2…tn) //t dãy nghịch thế ngược đã được sinh ra

ở trên

3. Khởi tạo danh sách L = ϕ

4. For i=0 to n do

5. If ti=1 then chèn phần tử xi vào dãy L

6. X1:=L //s là 1 tập con của X

7. End.

Áp dụng công thức (2) của định lý 1 cho 2 dãy biên si và gi

ta

có độ phức tạp của thuật toán xấp xỉ ∏

= 2n

.

3.2.2 . Xây dựng thuật toán song song

12

Thuật toán 5: song song tìm tập con của tập có n phần tử

1. Begin

2. Nhập n, p (p∈ {2,3, … , n − 1})

3. s[i]:=0, i = 1, … , n

4. g[i]:=1, i = 1, … , n

5. k:=2p

; p=(2, 3,…,n-1) // k là số bộ xử lý

6. //Bộ xử lý đầu tiên tìm k đoạn con, rồi phân cho các bộ

xử lý khác

Begin

//tìm dãy bị chặn theo thuật toán 1 và gửi dữ liệu đến

các bộ xử lý

6.1. s’[i]=s[i], i=1,…,p

6.2. g’[i]=g[i], i=1,…,p

6.3. cj

:=Sinh dãy bị chặn(s’(i), g’(i)), j=1,…,k //theo

thuật toán 1.

6.4. Gửi s[i], g[i] ở bước 3 đến tất cả các bộ xử lý phụ

6.5. Gửi (cj đến pj (j=1,…,k)

End;

7. //k bộ xử lý phụ thực hiện đồng thời,

Begin

7.1. Nhận dữ liệu

7.2. Tạo sj bằng cách chèn các phần tử s[i] vào bên phải

của cj (j=1,…,k) //j là chỉ số của k bộ xử lý phụ

7.3. Tạo gj bằng cách chèn các phần tử g[i] vào bên phải

của cj (j=1,…,k) //j là chỉ số của k bộ xử lý phụ

7.4. tj[i]:=Sinh dãy bị chặn (sj(i), gj(i)), j=1,…,k,

i=1,…,n //theo thuật toán 1.

7.5. Chuyển tất cả các dãy bị chặn tj[i] thành các tập con

theo thuật toán 4.

13

7.6. In kết quả

7.7. Gửi thông tin về bộ xử lý chính.

End;

8. End.

3.2.3 . Ví dụ minh họa tìm tất cả tập con con của tập có 4

phần tử

3.2.4 . Phân tích

Với cách chọn số bộ xử lý k=2p

(1<p<n)

Vì các dãy bị chặn con cho từng bộ xử lý tạo ra bằng cách lấy

p phần tử đầu trong dãy nhị phân ban đầu và thêm 0 vào cho đủ n

phần tử nên các dãy chặn con điều nằm trong khoản từ s=(0…0) và

g=(1…1) (n phần tử).

Số dãy bị chặn tại mỗi bộ xử lý phụ là 2n-p

dãy. Đồng thời số

bộ xử lý là k=2

p

nên ta có tổng số dãy con tạo ra là 2p

* 2n-p =2n

dãy.

Vậy độ phức tạp của thuật toán 5 song song tìm tập con của tập

có n phần tử xấp xỉ 2n-p

+T với T là thời gian truyển thông giữa các

bộ xử lý. T phụ thuộc vào từng hệ thống vật lý thực tế.

3.3. Bài toán liệt kê hoán vị

3.3.1 . Phép thế, nghịch thế

Một phép thế σ trên tập Xn được gọi là một chuyển trí hai phần

tử i, j thuộc Xn nếu σ(i) = j, σ(j) = i và σ(k) = k, với mọi k ∈ Xn, k ≠ i,

k ≠ i.

Giải sử tập hợp Xn = {1,2,3,..,n}, (n>1) Một song ánh σ:

Xn→Xn được gọi là phép thế trên tâp Xn. Tập tất cả các phép thế ký

hiệu là Sn.

Phép thế σ: Xn→ Xn được biểu diễn như sau:

(

)