Tra loi cau hoi giai thuat nhom1

TRAÛ LÔØI CAÂU HOÛI MOÂN GIAÛI THUAÄT – NHOÙM 1

1. Khái niệm cây tự do, cây có gốc (được định hướng)
Trả lời:
-Cây tự do là một đồ thị liên thông và không có chu trình.
-Một cây có gốc là một cây tư do, trong đó có một đỉnh được chọn làm gốc và các cạnh được định hướng là hướng của các đường đi đơn ra khỏi gốc tới các đỉnh khác.
2.Các tính chất của cây
Traû lôøi:
Đồ thị T vô hướng n đỉnh là một cây nếu thỏa một trong các tính chất sau:
-T không chứa chu trình và có n-1 cạnh.
-T liên thông và có n-1 cạnh.
-T liên thông và mỗi cạnh của nó đều là cầu.
-Hai đỉnh bất kỳ được nối với nhau bằng một đường đi duy nhất.
-T không chứa chu trình nhưng nếu thêm vào một cạnh thì có một chu trình duy nhất.

3. Khái niệm cây bao trùm của đồ thị vô hướng
Trả lời:

Cây T=(V,F) được gọi là một cây bao trùm của đồ thị vô hướng liên thông G=(V,E) nếu FE.

4. Khái niệm cây bao trùm nhỏ nhất của đồ thị vô hướng có trọng số
Trả lời:
Cho G là một đồ thị vô hướng, liên thông có trọng số, n đỉnh và H là một đường đi, chu trình, cây, đồ thị con, … của G
-Trọng số của H, ký hiệu w(H), là tổng trọng số của tất cả các cạnh của nó:
W(H)=eH w(E)
Cây bao trùm nhỏ nhất của đồ thị vô hướng có trọng số là một tập hợp các cạnh nối tất cả các đỉnh sao cho tổng trọng số của tất cả các cạnh trong tập hợp này là nhỏ nhất so với tổng trọng số của các tập hợp cạnh khác thỏa điều kiện nối tất cả các đỉnh.

5. Ý tưởng, mã, cách thức làm việc và độ phức tạp của giải thuật Kruskal.
Trả lời:
* Ý tưởng:
-Tại mỗi bước, thuật toán tìm một cạnh có trọng số nhỏ nhất thêm vào tập cạnh của cây bao trùm sao cho không gây ra chu trình.
-Thuật toán dừng khi số cạnh của cây bằng số đỉnh của đồ thị trừ 1.

* Mã:
KRUSKAL(G, w) // G có n đỉnh, thực hiện cho đến khi F = n-1
1. F ←
2. Sort the edges of E into nondecreasng order by weight w
3. while F< n-1 and E≠ 
4. do e ← x  w(x) = min{w(y), yE)} e có trọng số bé nhất
5. E ← E-{e}
6. if F{e} not contain cycle then F ←F{e}
7. if F< n-1
8. then G is not connected
9. else return T T= (V, F)
* Cách thức làm việc:
• Khi lập trình cài đặt giải thuật Kruskal có hai điểm mấu chốt cần chú ý:
-Trong mỗi lần lặp ta chọn cạnh có trọng số nhỏ nhất đưa vào T.
-Cạnh được chọn đưa vào T phải không tạo thành chu trình với các cạnh đã có trong T.
• Vấn đề thứ nhất được giải quyết là tạo một hàng đợi có ưu tiên trên danh sách các cạnh. Tuy nhiên có thể ngay từ đầu sắp xếp các cạnh theo thứ tự tăng dần của trọng số.
.Để giải quyết vần đề thứ hai,tại mỗi bước của giải thuật Kruskal, tập các đỉnh và các cạnh đã được đưa vào T chưa là cây mà chỉ thỏa mã tính không chu trình. Như vậy tại mỗi bước T là một rừng, T = .
• -Bây giờ xét một cạnh e = (u,v) của G chưa nằm trong T có 3 khả năng xảy ra:
-Cả u,v chưa thuộc T. Khi đó nếu bổ sung e vào T thì không có chu trình, nhưng chính cạnh e tạo thành một cây con mới.
-Một đỉnh chẳng hạn u thuộc T, còn đỉnh kia v không thuộc T. Việc bổ sung cạnh e và đỉnh v vào T (vào cây con chứa đỉnh u) không tạo ra chu trình.
-Cả u,v đều nằm trong T. Khi đó
+ Nếu u,v nằm trong cùng một cây con Tk ta không thể bổ sung canh e vào T.
+ Nếu u,v nằm trong hai cây con khác nhau thì có thể bổ sung cạnh e vào T (hai đỉnh u, v đã nằm trong T không cần bổ sung, sau khi bổ sung hai cây con sẽ hợp lại thành một cây.
* Độ phức tạp:
-Thời gian sắp xếp là O (ElgE)S
-Chi phí cho tất cả các lần lặp trong vòng lặp while không quá O (VlgE)
-Do đó, tổng chi phí là O (ElgE + V lg E) = O (E lgE)
6. Ý tưởng, mã, cách thức làm việc và độ phức tạp của giải thuật Prim
* Ý tưởng:
-Khởi đầu, thuật toán chọn một đỉnh bất kỳ của đồ thị làm đỉnh gốc của cây bao trùm bé nhất.
-Tại mỗi bước chọn thêm một đỉnh của đồ thị mà trọng số cạnh nối nó với một đỉnh của cây là nhỏ nhất.
-Thuật toán kết thúc khi tất cả các đỉnh của đồ thị đã được chọn.
* Mã:








* Cách thức làm việc:
Bắt đầu từ một đỉnh tùy ý của đồ thị s, đầu tiên ta nối với đỉnh lân cận gần nó nhất, chẳng hạn là đỉnh y. Nghĩa là trong số các cạnh kề của đình s, cạnh (s,y) có độ dài nhỏ nhất. Tiếp theo, trong số các cạnh kề với hai đỉnh s hoặc y ta tìm cạnh có độ dài nhỏ nhất, cạnh này dẫn đến đỉnh thứ ba z, và ta thu được cây có bộ phận gồm ba đỉnh và hai cạnh. Quá trình này sẽ được tiếp tục cho đến khi ta thu được cây gồm n đỉnh và n – 1 cạnh sẽ chính là cây khung nhỏ nhất cần tìm.
Giả sử đồ thị cho bởi ma trận trọng số C={c[i,j] , i,j = 1,2..n}. Trong quá trình thực hiện thuật toán, ở mỗi bước để có thể nhanh chóng chọn đỉnh và cạnh cần bổ sung vào cây khung, các đỉnh của đồ thị sẽ được gán cho các nhãn. Nhãn của một đỉnh v sẽ gồm hai phần và có dạng [d[v], near[v]], trong đó d[v] dùng để ghi nhận độ dài của cạnh có độ dài nhỏ nhất trong số các cạnh nối từ đỉnh v với các đỉnh của cây khung đang xây dựng (ta sẽ gọi là khoảng cách từ đỉnh v đến tập đỉnh của cây khung ), nois một cách khác chính xác
D[v]:= min{ c[v,w] : w thuộc Vh } (= c[v,z])
Còn near[v] ghi nhận đỉnh của cây khung gần v nhất (near[v]:= z)
* Độ phức tạp:
-Tổng thời gian cho tất cả các lần EXTRACT – MIN trong vòng lặp While là O (V lg V).
-Chi phí cho tất cả các lần lặp của vòng lặp For 8-11 trong vòng lặp While là O (E lg V)
-Do đó tổng chi phí là: O (V lg V + E lg V) = O (E lg V)
7. So sánh giải thuật KrusKal và Prim
Trả lời:
-Cả hai thuật toán đều tìm cây bao trùm nhỏ nhất.
-Thuật toán Kruskal: Để xây dựng tập n-1 cạnh của cây khung nhỏ nhất? tạm gọi là tập K, Kruskal đề nghị cách kết nạp lần lượt các cạnh vào tập đó theo nguyên tắc như sau: Ưu tiên các cạnh có trọng số nhỏ hơn, kết nạp cạnh khi nó không tạo chu trình với tập cạnh đã kết nạp trước đó. Đó là một nguyên tắc chính xác và đúng đắn, đảm bảo tập K nếu thu đủ n-1 cạnh sẽ là cây khung nhỏ nhất.
-Thuật toán Prim: Do thuật toán Kruskal làm việc trên các cạnh nên sẽ kém hiệu quả nếu có quá nhiều cạnh? như các đồ thị dày (số cạnh m ≈ n(n-1)/2).
- Đối nghịch với Kruskal, thuật toán Prim làm việc trên các đỉnh, sẽ hiệu quả hơn với các đồ thị dày. Có thế thấy đa số các đồ thị trong thực tế có số đỉnh không lớn còn số cạnh rất lớn nên Prim tỏ ra hiệu quả hơn và?đắt giá? hơn Kruskal, mặc dù cài đặt có phức tạp hơn. Ngoại lệ, trong các trường hợp số cạnh rất ít còn số đỉnh rất nhiều thì Prim kém hiệu quả hơn Kruskal.
- Prim đề xuất cách xây dựng đồng thời tập đỉnh đã kết nạp (VH) và tập cạnh đã kết nạp T cho cây khung nhỏ nhất theo nguyên tắc như sau: Lần lượt kết nạp một đỉnh u thuộc VVH vào VH sao cho tồn tại v thuộc VH mà trọng số (u,v) là nhỏ nhất trong m-i cặp đỉnh nối VH và VVH.:
8. Ý nghĩa ứng dụng của cây bao trùm nhỏ nhất trong thực tế
Trả lời:
-Nó có thể là bài toán tìm hệ thống liên thông với chi phí nhỏ nhất, hoặc ngược lại, vói lợi nhuân lớn nhất.
- Các bài toán trên đồ thị có nhiều ứng dụng trong các lĩnh vực khác nhau như mạng thông tin, đồ họa, ứng dụng lập kế hoạch làm việc. Các bài toán đặt ra trong các ứng dụng như vậy thường có cơ sở dữ liệu lớn nên việc rút ngắn độ phức tạp thời gian để trả lời một câu truy vấn có ý nghĩa thực tiễn cao. Ngoài ra trong thực tế, các đồ thị được sử dụng trong các bài toán đó thường liên tục thay đổi theo thời gian, ví dụ như các đỉnh hay các cạnh của nó có thể được thêm hay xóa đi (đồ thị động).
Mỗi lần có một hành động thay đổi như vậy thì cấu trúc dữ liệu của bài toán lưu trữ thông tin về các đỉnh cũng như các cạnh đã bị thay đổi. Trong khi đó yêu cầu đặt ra là phải liên tục trả lời các câu hỏi về thông tin trong đồ thị như tính liên thông của đồ thị, rừng bao trùm tối thiểu, 2 đỉnh bất kỳ có nằm trên cùng một cây bao trùm tối thiểu hay không...Một cách tiếp cận để giải quyết các bài toán trên đồ thị động là sử dụng các cấu trúc dữ liệu và thuật toán truyền thống trong đồ thị tĩnh và chạy lại chúng mỗi khi có sự thay đổi trong đồ thị. Tuy nhiên cách tiếp cận như vậy không tận dụng được thông tin của đồ thị trước khi thay đổi dẫn đến độ phức tạp để trả lời một câu truy vấn về đồ thị sau mỗi bước thay đổi là lớn.
Dựa trên các cấu trúc dữ liệu này, một số bài toán trên đồ thị động như kiểm tra tính liên thông, xây dựng cây bao trùm, tìm đường đi ngắn nhất được giải quyết với độ phức tạp thời gian nhỏ hơn so với việc chạy lại các thuật toán truyền thống trên đồ thị tĩnh mỗi khi có sự thay đổi trong đồ thị.
9. Ý tưởng, mã, cách thức làm việc, độ phức tạp của các giải thuật Counting Sort và BucketSort.
Trả lời:
* Ý tưởng:
+ Counting Sort:
-Đếm số phần tử nhỏ hơn phần tử x trong mảng nhập để đặt x trực tiếp vào vị trí của nó trong mảng xuất.
-Chẳng hạn, nếu có 17 phần tử nhỏ hơn hoặc bằng x thì x được đặt vào vị trí 17.
+ BucketSort:
-Phân bố mảng input vào n khoảng con (lô) của khoảng [0,1)
-Sắp xếp các phần tử trong mỗi lô và nối các lô để có mảng được sắp.
* Mã:
+ Counting Sort:








+ BucketSort:






* Cách thức làm việc:
+ Counting Sort:
-Dòng 1-2 khởi tạo các C[i]=0
-Dòng 3-4 xác định số phần tử có giá trị là i=A[j] trong A
-Dòng 6-7 xác định số phần tử trong A nhỏ hơn hoặc bằng i, đó là tổng của C[i] và C[i-1]

-Dòng 9-10 đặt A[j]vào trong vị trí được sắp chính xác của nó trong mảng B căn cứ vào số phần tử nhỏ hơn hoặc bằng A[j] trong C[A[j]]
-Giảm C[A[j]] đi 1 trong dòng 10 để các phần tử còn lại bằng A[j] sẽ được đặt chính xác vào mảng B lần lặp sau.
+ BucketSort:
-Xét hai phần tử A[i] và A[j]
. Nếu A[i] và A[j] cùng rơi vào một lô, chúng có thứ tự nhờ giải thuật chèn trực tiếp.
. Ngược lại, gọi các lô tương ứng của A[i] và A[j] là B[i’] và B[j’], nếu i’<j’ thì lô B[i’] được nối trước lô B[j’] và khi đó A[i]≤ A[j]
.Mảng output có thứ tự khi giải thuật kết thúc.
-Thật vậy, giả sử ngược lại A[i] A[j] thì i’=[nA[i]] ≥[nA[j]]=j’
-điều này mâu thuẫn với i’<j’, nghĩa là A[i]≤A[j]
-Như vậy giải thuật đảm bảo thứ tự của mảng Output
* Độ phức tạp:
+ Counting Sort:
-Chi phí cho lệnh 1-2 là O(k)
-Chi phí cho lệnh 3-4 là O(n)
-Chi phí cho lệnh 6-7 là O(k)
-Chi phí cho lệnh 9-11 là O(n)
Vì vậy tổng chi phí thời gian là O(k+n)
Nếu k=O(n)thì tổng chi phí là O(n)
+ BucketSort:
-Do phân bố ngẫu nhiên n phần tử vào n khoảng con nên trung bình mỗi lô có 1 phần tử, vì vậy thời gian sắp xếp chèn là O(1)
-Từ đó chi phí toàn bộ của giải thuật là O(n)

10. Nêu các hạn chế của Counting Sort và BucketSort. Đề xuất hướng giải quyết khắc phục các điểm hạn chế của Counting Sort và BucketSort.
Trả lời:
*Các hạn chế của Counting Sort và BucketSort:
-Counting Sort chỉ sắp xếp các phần tử có khóa trong một miền nhất định (nhỏ hơn hoặc bằng k cho trước)
-CountingSort phải sử dụng thêm các mảng trung gian.
-BucketSort chỉ sắp xếp các phần tử có khóa trong khoảng [0,1)
-Không phải mọi phân bố sẽ cho mỗi lô chứa một phần tử.
* Hướng giải quyết khắc phục các điểm hạn chế của CountingSort và BucketSort:

---

Bạn ơi, bạn có thể upload kém file word lên được không bạn, chứ bạn up dạng text lên thì một số ký tự bị mất. Cảm ơn bạn.

Bạn ơi ,

gửi cho mình file word vào địa chỉ tuanduyinfo@yahoo.com với nha ?
hay post lại lên diễn đàn cho chữ khỏi mất để mọi người ôn lại bài với nha ?

Thanks

Bạn thuydung02cm ơi! Bạn post bài xong rồi đi đâu mất tiêu rồi! Có thể nào host lên 1 file word ko? Mình cũng thuộc nhóm 1, cảm ơn bạn đã post bài giải này cho mọi người. Mà bạn Dung là ai vậy ta?

Các bạn co thể download o đây:
http://www.4shared.com/file/102003162/ff22a609/giai_thuat.html