Tôi có thắc mắc nhỏ ở slide số 49, khi nghe thầy giảng có giải thích công thức:
cont(Ai,Ak,Aj)=2bond(Ai,Ak)+2bond(Ak,A<span style=‘color:green’>j</span>)-2bond(Ai,Aj)
trong đó <span style=‘color:red’>Ai,A<span style=‘color:blue’>k</span> là 2 thuộc tính có sẵn và A<span style=‘color:blue’>j</span> là thuộc tính chèn thêm</span>.
Vậy không biết tôi có nghe nhầm không, nếu đúng thầy nói như vậy thì theo tôi có lẽ thầy nhầm, mà phải là:
<span style=‘color:red’>Ai,A<span style=‘color:blue’>j</span> là 2 thuộc tính có sẵn và A<span style=‘color:blue’>k</span> là thuộc tính chèn thêm</span>
Vì dựa theo bài tập ví dụ ở slide số 50 mà tôi thấy cần phải hiểu như vậy.
Mong các bạn và thầy có ý kiến.
Chào các bạn .
theo tôi thì bạn Thủy nói đúng. Chèn Ak vào giữa Ai và Aj mới đúng theo công thức được chứng minh từ Độ đo ái lực toàn cục AM. Thuật toán BEA dùng để tìm tìm vị trí chèn Ak sao cho AM là cực đại. Theo tôi thì thầy chỉ nói nhầm thôi.
Chào
<!–QuoteBegin-CH0903087+12 Jul 2010, 10:10 PM–></div><table border=‘0’ align=‘center’ width=‘95%’ cellpadding=‘3’ cellspacing=‘1’><tr><td><b>QUOTE</b> (CH0903087 @ 12 Jul 2010, 10:10 PM)</td></tr><tr><td id=‘QUOTE’><!–QuoteEBegin–> Giả sử đã tồn tại 2 thuộc tính <b>có thứ tự</b> Ai và Aj và cần chèn thêm thuộc tính Ak vào trong nhóm trên (lưu ý là phải bảo toàn thứ tự Ai và Aj), ta có 3 cách chèn như sau :
Cách 1 : Ak Ai Aj (chèn Ak vào trước)
Cách 2 : Ai Ak Aj (chèn Ak vào giữa)
Cách 3 : Ai Aj Ak (chèn Ak vào sau)
Với mỗi cách đó, ta sẽ tính cont()
Cont_1(Ak,Ai,Aj) = 2bond(Ak,Ai)+2bond(Ai,Aj)-2bond(Ak,Aj)
Cont_2(Ai,Ak,Aj) = 2bond(Ai,Ak)+2bond(Ak,Aj)-2bond(Ai,Aj)
Cont_3(Ai,Aj,Ak) = 2bond(Ai,Aj)+2bond(Aj,Ak)-2*bond(Ai,Ak)
và chọn ra cách chèn có cont() lớn nhất. <!–QuoteEnd–> </td></tr></table><div class=‘postcolor’> <!–QuoteEEnd–>
3 cách chèn phải như sau:
Cách 1 :A(i-1)Ak Ai (chèn Ak vào trước)
Cách 2 : Ai Ak Aj (chèn Ak vào giữa)
Cách 3 : Aj Ak A(j+1)(chèn Ak vào sau)
công thức tính cont tương ứng với 3 cách:
Cont_1(A(i-1),Ak,Aj) = …
Cont_2(Ai,Ak,Aj) = …
Cont_3(Aj,Ak,A(j+1)) = …
Đó là theo suy nghĩ của tôi, mong bạn Khiêm kiểm tra lại và các bạn có ý kiến.
Cảm ơn bạn Khiêm có ý kiến. Nói như bạn thì tôi chỉ đồng ý ở chỗ là sau đó lấy cont cao nhất.
Nếu nói vậy công thức của bạn sẽ không khớp với nội dung của thầy trong slide 50.
Và tôi thấy rằng thứ tự thuộc tính có ảnh hưởng đến công thức tính cont. Mong bạn xem lại vì phần giải thích của bạn tôi chưa đồng ý.
Vậy là vấn đề đã rõ. Cảm ơn các bạn đã trao đổi ý kiến.
<!–QuoteBegin-CH0901052+13 Jul 2010, 03:23 PM–></div><table border=‘0’ align=‘center’ width=‘95%’ cellpadding=‘3’ cellspacing=‘1’><tr><td><b>QUOTE</b> (CH0901052 @ 13 Jul 2010, 03:23 PM)</td></tr><tr><td id=‘QUOTE’><!–QuoteEBegin–> 3 cách chèn phải như sau:
Cách 1 :A(i-1)Ak Ai (chèn Ak vào trước)
Cách 2 : Ai Ak Aj (chèn Ak vào giữa)
Cách 3 : Aj Ak A(j+1)(chèn Ak vào sau)
công thức tính cont tương ứng với 3 cách:
Cont_1(A(i-1),Ak,Aj) = …
Cont_2(Ai,Ak,Aj) = …
Cont_3(Aj,Ak,A(j+1)) = …
Đó là theo suy nghĩ của tôi, mong bạn Khiêm kiểm tra lại và các bạn có ý kiến. <!–QuoteEnd–> </td></tr></table><div class=‘postcolor’> <!–QuoteEEnd–>
Tôi đồng ý với ý kiến của chị Thủy, bạn Khiêm đã có nhầm lẫn và Thầy đã nói nhầm 1 xíu chỗ này.
<!–QuoteBegin–></div><table border=‘0’ align=‘center’ width=‘95%’ cellpadding=‘3’ cellspacing=‘1’><tr><td><b>QUOTE</b> </td></tr><tr><td id=‘QUOTE’><!–QuoteEBegin–>
3 cách chèn phải như sau:
Cách 1 :A(i-1)Ak Ai (chèn Ak vào trước)
Cách 2 : Ai Ak Aj (chèn Ak vào giữa)
Cách 3 : Aj Ak A(j+1)(chèn Ak vào sau)
công thức tính cont tương ứng với 3 cách:
Cont_1(A(i-1),Ak,Aj) = …
Cont_2(Ai,Ak,Aj) = …
Cont_3(Aj,Ak,A(j+1)) = …
<!–QuoteEnd–></td></tr></table><div class=‘postcolor’><!–QuoteEEnd–>
Với thuật toán này, giả sử ta đã có A1 và A2 được đặt ở cột 1 và 2. Khi đó ta tìm vị trí đề chèn thêm cột A3 vào. Có 3 cách đăt
(Mình nói tiếp nhé… <!–emo&:P–><img src=‘http://www.uit.edu.vn/forum/html/emoticons/tongue.gif’ border=‘0’ style=‘vertical-align:middle’ alt=‘tongue.gif’ /><!–endemo–> )
Khi đó có 3 cách chèn:
- TH1: A3-A1-A2. ta phải tính: Cont(A0, A3, A1)
Cont(A0,A3,A1) = 2bond(A0,A3)+2bond(A3,A1)-2bond(A0,A1)
Mà bond(A0,A3)=bond(A0,A1)=0
Nên Cont_1(A0,A3,A1) = 2bond(A3,A1)
TH2: A1-A3-A2:
Cont(A1,A3,A2) = 2bond(A1,A3)+2bond(A3,A2)-2bond(A1,A2)
TH2: A1-A2-A3: Khi đó ta cần tính Cont(A2, A3, A4)
Cont(A2,A3,A4) = 2bond(A2,A3)+2bond(A3,A4)-2bond(A2,A4)
Các bạn thử xem lại nhé!
Có lẽ bạn Thủy nghe không rõ thầy giảng, mình xin giải thích lại thế này, nếu có chỗ nào chưa chính xác mong thầy và các bạn góp ý thêm.
Thuộc tính chèn thêm chỉ dùng để xác định các trường hợp có thể chèn, còn khi tính cont thì không cần quan tâm đâu là thuộc tính chèn thêm và đâu là thuộc tính đã có nữa, khi ấy chỉ quan tâm đến thứ tự các thuộc tính mà thôi. Cụ thể như sau :
Giả sử đã tồn tại 2 thuộc tính <b>có thứ tự</b> Ai và Aj và cần chèn thêm thuộc tính Ak vào trong nhóm trên (lưu ý là phải bảo toàn thứ tự Ai và Aj), ta có 3 cách chèn như sau :
Cách 1 : Ak Ai Aj (chèn Ak vào trước)
Cách 2 : Ai Ak Aj (chèn Ak vào giữa)
Cách 3 : Ai Aj Ak (chèn Ak vào sau)
Với mỗi cách đó, ta sẽ tính cont()
Cont_1(Ak,Ai,Aj) = 2bond(Ak,Ai)+2bond(Ai,Aj)-2bond(Ak,Aj)
Cont_2(Ai,Ak,Aj) = 2bond(Ai,Ak)+2bond(Ak,Aj)-2bond(Ai,Aj)
Cont_3(Ai,Aj,Ak) = 2bond(Ai,Aj)+2bond(Aj,Ak)-2*bond(Ai,Ak)
và chọn ra cách chèn có cont() lớn nhất.
<!–QuoteBegin-CH0903087+12 Jul 2010, 10:10 PM–></div><table border=‘0’ align=‘center’ width=‘95%’ cellpadding=‘3’ cellspacing=‘1’><tr><td><b>QUOTE</b> (CH0903087 @ 12 Jul 2010, 10:10 PM)</td></tr><tr><td id=‘QUOTE’><!–QuoteEBegin–> còn khi tính cont thì không cần quan tâm đâu là thuộc tính chèn thêm và đâu là thuộc tính đã có nữa, khi ấy <b>chỉ quan tâm đến thứ tự các thuộc tính </b>mà thôi. <!–QuoteEnd–> </td></tr></table><div class=‘postcolor’> <!–QuoteEEnd–>
Mình có ghi rõ là khi tính cont() thì quan tâm đến thứ tự thuộc tính mà, bạn Thủy có thể xem kỹ lại và chỉ rõ là mình viết chỗ nào chưa hợp lý không ? Cảm ơn bạn Thủy nhiều <!–emo&:D–><img src=‘http://www.uit.edu.vn/forum/html/emoticons/biggrin.gif’ border=‘0’ style=‘vertical-align:middle’ alt=‘biggrin.gif’ /><!–endemo–>
Xin lỗi bà con <!–emo&:D–><img src=‘http://www.uit.edu.vn/forum/html/emoticons/biggrin.gif’ border=‘0’ style=‘vertical-align:middle’ alt=‘biggrin.gif’ /><!–endemo–> vì tập trung vào nguyên lý thứ tự ban đầu và các phương án chèn mà quên mất việc tính cont() phải xét khi thuộc tính chèn ở giữa, vấn đề đã rõ, chắc là không có gì phải thắc mắc thêm <!–emo&:D–><img src=‘http://www.uit.edu.vn/forum/html/emoticons/biggrin.gif’ border=‘0’ style=‘vertical-align:middle’ alt=‘biggrin.gif’ /><!–endemo–>