Divide and Conquer (Kĩ thuật chia để trị)

<Type to Remember>

<Theo “Kỹ thuật thiết kế giải thuật – Nguyễn Văn Linh”>

Chia để trị (divede and conquer) có thể nói là kĩ thuật quan trọng nhất, được áp dụng rộng rãi nhất để thiết kế các giải thuật có hiệu quả.

Nội dung kĩ thuật:

Để giải một bài toán kích thước n, ta chia bài toán đã cho thành một số bài toán con với kích thước nhỏ hơn. Giải các bài toán con này rồi tổng hợp lại kết quả để được lời giải của bài toán ban đầu.

Đối với các bài toán con, chúng ta lại sử dụng chia để trị để có được những bài toán có kích thước nhỏ hơn nữa. Quá trình trên sẽ dẫn đến những bài toán mà chúng ta dễ dàng thực hiện hoặc lời giải của nó là hiển nhiên, các bài toán này là các bài toán cơ sở.

Tóm lại, kĩ thuật chia để trị bao gồm 2 quá trình: Phân tích bài toán đã cho thành các bài toán cơ sở và tổng hợp kết quả của bài toán cơ sở để có được lời giải của các bài toán ban đầu. Tuy nhiên đối với một số bài toán, thì quá trình phân tích đã chứa đựng việc tổng hợp kết quả do đó nếu chúng ta đã giải xong các bài toán cơ sở thì bài toán ban đầu cũng được giải quyết. Ngược lại có những bài toán mà quá trình phân tích thì đơn giản nhưng việc tổng hợp lại kết quả rất khó khăn.

Kĩ thuật này sẽ cho ta một giải thuật đệ quy, mà việc xác định độ phức tạp của nó sẽ phải giải một phương trình đệ quy.

Các bài toán vi dụ: Các bạn tìm xem thêm về các bài toán như: “Bài toán xếp lịch thi đấu thể thao”, “Bài toán nhân 2 số nguyên lớn”, “Bài toán cân bằng”..

Advertisements

Tổng quan Visual Studio 11 Beta – Xây dựng ứng dụng Microsoft (Visual Studio 11 Beta Overview – Building Microsoft applications)

Nguồn: http://tbhung.wordpress.com/2012/03/05/gi%E1%BB%9Bi-thi%E1%BB%87u-t%E1%BB%95ng-quan-v%E1%BB%81-visual-studio-11-beta-v-xy-d%E1%BB%B1ng-%E1%BB%A9ng-d%E1%BB%A5ng-microsoft/

Sau khi Windows 8 Consumer Preview được Microsoft cho download rộng rãi, thì Microsoft cũng phát hành bộ công cụ dành cho lập trình viên là Visual Studio 11 beta, giúp cho cộng đồng lập trình viên được phép tạo ra các ứng dụng chất lượng cao, ứng dụng Metro style. Bên cạnh đó, bộ công cụ này còn cung cấp them các tính năng như kiến trúc ứng dụng, kiểm thử phần mềm, bảo đảm chất lượng phần mềm và làm việc trực tiếp với Team Foundation Server 11 giúp cho quản trị dự án phần mềm theo mô hình ALM một cách chuyên nghiệp hơn.

Chúng ta sẽ lướt qua về VS11 beta để khám khá các tính năng mới của nó.

Giao diện mới:

clip_image002 

Trong phiên bản này, Microsoft cải tiến và hỗ trợ xây dựng các giao diện Metro, hoặt động trên nền tảng Framework 4.5

clip_image004 

Metro Style Apps project Templates

Bạn có thể tạo ra các ứng dụng Metro phong phú bằng cách sử dụng một trong nhiều các mẫu dự án mặc định của Visual Studio 11, Các template sẽ tùy thuộc vào ngôn ngữ lập trình của bạn lựa chọn.

  • Metro style apps written using JavaScript.
  • Metro style apps written using C++, C#, or Visual Basic

Debugging

Visual Studio 11 cung cấp cho bạn một tập các công cụ giúp cho quá trình Debug ứng dụng một cách thuận tiện, bảo đảm ứng dụng Metro của bạn có chất lượng cao nhất. Bạn có thể debug ngay tại máy tính của bạn như kiểu truyền thống, hoặc có thể debug thong qua một máy ảo giả lập (Simulator).

Visual Studio 11 IDE

  • Store Menu: Bạn có thể sử dụng menu mới là STORE để tạo một tài khoản developer trên Windows Store và đặt tên cho ứng dụng của bạn.
  • Đóng gói và tải ứng dụng: Bạn có thể tạo một ứng dụng và đóng gói tất cả các file cần thiết với nhau sau đó tải lên Windows Store.

Công cụ quản trị chất lượng

  • Profiling: Giúp bạn tạo một bảng thong tin cho ứng dụng của bạn, chỉ rõ các thao tác xử lý trong ứng dụng, tìm kiếm những đoạn mã, module chiếm nhiều tài nguyên hệ thống để từ đó có thể khắc phục và bảo đảm kiểm soát hoàn toàn ứng dụng.
  • Code Analysis: Sử dụng để phân tích mã, tính phức tạp của mã, sự rang buộc lẫn nhau giữa các hàm giúp cho bạn có thể kiểm soát mã một cách tốt hơn.

Một số tính năng khác:

  • Vẫn phát triển theo lộ trình một giải pháp ALM hoàn chỉnh – Visual Studio – Team Foundation Server.
  • Giải pháp ALM với các tính năng cải tiến như Feedback, Scrum 2.0, Architect.
  • Hỗ trợ nền tảng .NET Framework 4.5
  • MSBuild 4.5 giúp biên dịch ứng dụng tập trung và tự động
  • Xây dựng ứng dụng Data với Visual Studio 11.
  • Xây dựng ứng dụng LightSwich
  • Xây dựng các ứng dụng SharePoint
  • Công cụ quản lý thành phần mở rộng hỗ trợ cho Visual Studio 11 – Extension Manager.

Blend for Visual Studio 11 Beta

Cảm nhận đầu tiên về BLEND

Giao diện làm việc chính của Blend có thể có sự pha trộn và khác nhau đối với mỗi người dung. Với một người dung mới, mặc dù cách bố trí chung của Workspace sẽ giống nhau tương đối với tất cả các loại dư án mà bạn làm việc

clip_image006 

1. Menus: Tạo mới dự án và quản lý các setting của dự án

2. Tools Panel – Tạo và điều chỉnh các đối tượng trong ứng dụng

3. Assets Panel – Hiển thị tất cả các thực thể và tài nguyên có tồn tại trong dự án

4. Artboard – Đây là nơi mà bạn làm việc với hầu hết các thao tác chỉnh sửa layout cho dự án. Ở đây sẽ hiển thị sẳn khung y hệt như là một màn hình của thiết bị máy tính bảng ảo.

5. Additional panels – Là một khung đặt biệt chứa các thay đổi đang diễn ra trong quá trình làm việc trong dự án.

clip_image007 

1. Document Tab: Hiển thị tất cả các file đang mở của dự án, kể cả html, css và java script

2. View controls: Thể hiện 3 kiểu để bạn điều khiển ứng dụng

a. Interactive mode: Sử dụng chế độ này để kích hoạt các trạng thái khác nhau của ứng dụng.

b. Error Indicator: Cho bạn biết nếu có lỗi trong ứng dụng của bạn và hiển thị danh sách lỗi trên khung Result.

c. Refesh: Sử dụng để phục hồi trạng thái ban đầu của ứng dụng trước khi có sự thay đổi trạng thái mà bạn đã sử dụng ở chế độ tương tác.

3. Views: Hiển thị các tùy chọn cửa sổ làm việc

Cách vào facebook bằng file host (cập nhật tháng 04/2012)

Cách vào Facebook bằng file hosts

Cập nhật tháng 04/2012

Các bước chỉnh sửa: xem phần dưới.

Cập nhật dải ip: (Upload hình thoải mái)

31.13.79.7 http://www.facebook.com
31.13.79.7 facebook.com
31.13.79.7 http://www.login.facebook.com
31.13.79.7 login.facebook.com
31.13.79.7 apps.facebook.com
31.13.79.7 upload.facebook.com
31.13.79.7 graph.facebook.com
31.13.79.7 register.facebook.com
31.13.79.7 vi-vn.connect.facebook.com
31.13.79.7 vi-vn.facebook.com
31.13.79.7 static.ak.connect.facebook.com
31.13.79.7 developers.facebook.com
31.13.79.7 error.facebook.com
31.13.79.7 channel.facebook.com
31.13.79.7 upload.facebook.com
31.13.79.7 register.facebook.com
31.13.79.7 bigzipfiles.facebook.com
31.13.79.7 pixel.facebook.com
31.13.79.7 upload.facebook.com
31.13.79.7 register.facebook.com
31.13.79.7 bigzipfiles.facebook.com
31.13.79.7 pixel.facebook.com

Cập nhật tháng 01 /2011

Các bước chỉnh sửa file hosts để vào Facebook không bị chặn:

Bước 1:

Mở thư mục này: C:\WINDOWS\system32\drivers\etc, cách mở nhanh nhất là nhấn phím Windows+R sau đó copy paste dòng C:\WINDOWS\system32\drivers\etc vào  >> Enter

Bước 2:

Mở file hosts trong thư mục đó ra  >> Click phải chọn Openwith >>Chọn Notepad (hoặc double-click vào nó rồi cũng chọn Notepad)

Bước 3: Thêm vào cuối các dòng trong file đó các dòng sau:

Mạng FPT
60.254.175.42 facebook.com
60.254.175.42 http://www.facebook.com
60.254.175.42 register.facebook.com
60.254.175.42 http://www.logins.facebook.com
60.254.175.42 blog.facebook.com
60.254.175.42 logins.facebook.com
60.254.175.42 login.facebook.com
60.254.175.42 apps.facebook.com
153.16.15.71 upload.facebook.com
60.254.175.42 graph.facebook.com
60.254.175.42 profile.ak.fbcdn.net
60.254.175.42 photos-a.ak.fbcdn.net
60.254.175.42 photos-b.ak.fbcdn.net
60.254.175.42 photos-c.ak.fbcdn.net
60.254.175.42 photos-d.ak.fbcdn.net
60.254.175.42 photos-e.ak.fbcdn.net
60.254.175.42 photos-f.ak.fbcdn.net
60.254.175.42 photos-g.ak.fbcdn.net
60.254.175.42 photos-h.ak.fbcdn.net
60.254.175.42 static.ak.connect.facebook.com
60.254.175.42 static.ak.fbcdn.net
60.254.175.42 b.static.ak.fbcdn.net
60.254.175.42 error.facebook.com
60.254.175.42 developers.facebook.com
60.254.175.42 pixel.facebook.com
60.254.175.42 api.facebook.com
60.254.175.42 chanel.facebook.com
60.254.175.42 0.50.chanel.facebook.com
60.254.175.42 external.ak.fbcdn.net
60.254.175.42 profile.ak.fbcdn.net
60.254.175.42 creative.ak.fbcdn.net
60.254.175.42 chat.facebook.com
60.254.175.42 vupload.facebook.com
60.254.175.42 secure.facebook.com
60.254.175.42 connect.facebook.com
60.254.175.42 channel.facebook.com

Mạng VNPT
96.17.180.162 http://www.facebook.com
96.17.180.162 http://www.login.facebook.com
96.17.180.162 facebook.com
153.16.15.71 apps.facebook.com
153.16.15.71 login.facebook.com
96.17.180.162 upload.facebook.com
96.17.180.162 graph.facebook.com
96.17.180.162 register.facebook.com
96.17.180.162 vi-vn.connect.facebook.com
96.17.180.162 vi-vn.facebook.com
96.17.180.162 static.ak.connect.facebook.com
96.17.180.162 developers.facebook.com
96.17.180.162 error.facebook.com
96.17.180.162 channel.facebook.com
96.17.180.162 upload.facebook.com
96.17.180.162 register.facebook.com
96.17.180.162 bigzipfiles.facebook.com
96.17.180.162 pixel.facebook.com
96.17.180.162 upload.facebook.com
96.17.180.162 register.facebook.com
96.17.180.162 bigzipfiles.facebook.com
96.17.180.162 pixel.facebook.com

Bước 4:

Save file đó lại.

Nếu không save lại được các bạn chọn save as ở nơi nào khác, (Desktop chẳng hạn) với tên “hosts” (nhớ có 2 dấu “) rồi sau đó copy file đó lại vào thư mục  C:\WINDOWS\system32\drivers\etc vừa rồi. chọn Copy đè lên file cũ.

Mở trình duyệt lên và đã có thể lướt Face thoải mái rồi ^^.

Chúc các bạn thành công!

Binomial Heap – Heap nhị thức (P2)

Trong phần tiếp theo này chúng ta sẽ tìm hiểu cách cài đặt Binomial Heap và các thao tác xử lí trên nó, gồm có: Trộn 2 heap, Chèn,  tìm key nhỏ nhất, xóa key nhỏ nhất, giảm key, xóa heap.

Bởi vì không có hoạt động nào yêu cầu truy nhập ngẫu nhiên các nút gốc trên cây nhị thức , nên ta lưu trữ các nút gốc trên một danh sách liên kết, sắp xếp theo thứ tự tăng dần của cây.

Các thuật toán tạo Heap mới, lấy phần tử nhỏ nhất của heap, Heap-Union… :

Make-Binomial-Heap()
head[H] = NIL
return H


Binomial-Heap-Minimum(H)
y := NIL
x := head[H]
min := infinity
while x <> NIL
      do if key[x] < min             then min := key[x]
                 y := x          x := sibling[x]
return y Binomial-Link(y,z) p[y] := z sibling[y] := child[z]
child[z] := y degree[z] := degree[z] + 1





Binomial-HeapMerge(H1,H2)
a = head[H1]
b = head[H2]
head[H1] = Min-Degree(a, b)
if head[H1] = NIL
    return if head[H1] = b    then b = a a = head[H1]
while b <> NIL
    do if sibling[a] = NIL
          then sibling[a] = b                return           else if degree[sibling[a]] < degree[b]
                  then a = sibling[a]
                  else c = sibling[b]
                       sibling[b] = sibling[a]
                       sibling[a] = b                        a = sibling[a]
                       b = 




Binomial-Heap-Union(H1,H2)
H := Make-Binomial-Heap()
head[H] := Binomial-Heap-Merge(H1,H2)
free the objects H1 and H2 but not the lists they point to
if head[H] = NIL
   then return H prev-x := NIL
x := head[H]
next-x := sibling[x]
while next-x <> NIL
      do if (degree[x] <> degree[next-x]) or
                (sibling[next-x] <> NIL
                and degree[sibling[next-x]] = degree[x])
            then prev-x := x                  x := next-x             else if key[x] <= key[next-x]
                 then sibling[x] := sibling[next-x]
                      Binomial-Link(next-x,x)
                 else if prev-x = NIL
                         then head[H] = next-x                          else sibling[prev-x] := next-x                       Binomial-Link(x,next-x)
                      x := next-x          next-x := sibling[x]
return 




Binomial-Heap-Insert(H,x)
H' := Make-Binomial-Heap()
p[x] := NIL
child[x] := NIL
sibling[x] := NIL
degree[x] := 0
head[H'] := x H := Binomial-Heap-Union(H,H')





Binomial-Heap-Extract-Min(H)
find the root x with the minimum key in the root list of H,
         and remove x from the root list of H H' := Make-Binomial-Heap()
reverse the order of the linked list of x's children
        and set head[H'] to point to the head of the resulting list
H := Binomial-Heap-Union(H,H')
return 






Binomial-Heap-Decrease-Key(H,x,k)
if k > key[x]
   then error "hew key is greater than current key"
key[x] := k y := x z := p[y]
while z <> NIL and key[y] < key[z]
    do exchange key[y] and key[z]
       if y and z have satellite fields, exchange them, too.
       y := z        z := p[y]



Binomial-Heap-Delete(H,x) 
Binomial-Heap-Decrease-Key(H,x,-infinity)
Binomial-Heap-Extract-Min(H)


Binomial Heap – Heap nhị thức

Hôm nay ta sẽ tìm hiểu về cấu trúc dữ liệu mới là Binomial Heap (Heap nhị thức).

Phần 1: Khái niệm

Trong khoa học máy tính, một Binomial heap là một heap tương tự như binary heap nhưng được hỗ trợ việc trộn 2 heap lại với nhau một cách nhanh chóng. Điều này đạt được bằng cách sử dụng một cấu trúc cây đặc biệt, là cây nhị thức (Binomial Tree)

1. Cây nhị thức:(Binomial Tree)

1.1 Định nghĩa

Một heap nhị thức được tạo nên từ một collection các cây nhị thức. Cây nhị thức được định nghĩa đệ quy như sau:

– cây nhị thức bậc 0 là một node đơn

– cây nhị thức bậc K có một node gốc mà con của nó là những gốc của các cây nhị thức có bậc k-1, k-2, …, 2,1,0.

Ví dụ trên cây bậc 3 sẽ có nút gốc và các con của nó là các cây bậc 2, 1 và 0.

1.2 Tính chất

Cây nhị thức Bk (Binomial  Heap) thỏa mãn các tính chất sau đây:

  1.  Có  2^k nodes
  2.  Chiều cao của cây là Height=k;
  3.  Có chính xác C(k,i) nodes ở độ sâu i, với  i = 0,1,…k-1,k
  4.  Node gốc có bậc k và lớn hơn bất cứ node nào trong cây.
Bởi vì tính độc đáo trong cấu trúc của nó, một cây nhị thức mức k có thể được xây dựng từ 2 cây ở mức k-1 bằng cách gắn một trong 2 cây là cây con ngoài cùng bên trái của node gốc của cây còn lại. Đặc điểm này cũng chính là hành động cơ bản trong việc trộn heap.
2. Heap nhị thức (Binomial heap)
Một heap nhị thức H là một tập hợp các cây nhị thức thỏa mãn các tính chất của binomial heap sau đây:
1. Mỗi cây nhị thức trong H là những cây đã được sắp xếp thứ tự:  khóa của một node phải lớn hơn hoặc bằng khóa của cho nó trong cây.
2. có nhiều nhất chỉ là một cây nhị thức trong H mà có bậc cho trước.
Thuộc tính đầu tiên đảm bảo rằng gốc của mỗi cây trong heap chưa khóa nhỏ nhất trong cây đó.
Thuộc tính thứ hai chỉ ra rằng một heap nhị thức với n nodes bao gồm nhiều nhất log n + 1 cây nhị thức.
Thật ra số lượng và bậc của mỗi cây nhị thức trong heap nhị thức được xác định một cách duy nhất bởi số lượng node n : mỗi cây nhị thức tương ứng với một chữ số trong biểu diễn nhị phân của số n.
Ví dụ, số 13 là 1101 trong hệ nhị phân, 23 + 22 + 20, và vì vậy một binomial heap với 13 nodes sẽ bao gồm 3 cây nhị thức có bậc 0, 2 và 3.
Minh họa:
                                 

Giải thuật A*

Thuật giải A*, tìm đường đi cực tiểu trong đồ thị.

1. Về bài toán tìm đường đi ngắn nhất

Ta đã biết trong lí thuyết đồ thị bài toán tìm đường đi ngắn nhất nguồn đơn là bài toán tìm đường đi ngắn nhất  giữa 2 đỉnh sao cho tổng trọng số các cạnh tạo nên đường đi đó là nhỏ nhất.

Định nghĩa một cách hình thức, cho trước một đồ thị có trọng số (nghĩa là một tập đỉnh V, một tập cạnh E, và một hàm trọng số có giá trị thực f : E → R), cho trước một đỉnh v thuộc V, tìm một đường đi P từ v tới mỗi đỉnh v’ thuộc V sao cho

\sum_{p\in P} f(p)

là nhỏ nhất trong tất cả các đường nối từ v tới v’ .     <Wikipedia>

Có nhiều thuật toán để giải quyết bài toán này:

  • Thuật toán Dijkstra — giải bài toán nguồn đơn nếu tất cả các trọng số đều không âm. Thuật toán này có thể tính toán tất cả các đường đi ngắn nhất từ một đỉnh xuất phát cho trước s tới mọi đỉnh khác mà không làm tăng thời gian chạy.
  • Thuật toán Bellman-Ford — giải bài toán nguồn đơn trong trường hợp trọng số có thể có giá trị âm.
  • Giải thuật tìm kiếm A* giải bài toán nguồn đơn sử dụng heuristics để tăng tốc độ tìm kiếm
  • Thuật toán Floyd-Warshall — giải bài toán đường đi ngắn nhất cho mọi cặp đỉnh.
  • Thuật toán Johnson — giải bài toán đường đi ngắn nhất cho mọi cặp đỉnh, có thể nhanh hơn thuật toán Floyd-Warshall trên các đồ thị thưa.
  • Lý thuyết nhiễu (Perturbation theory); tìm đường đi ngắn nhất địa phương (trong trường hợp xấu nhất)    <Wikipedia>
Trong bài này ta sẽ quan tâm đến thuật toán tìm đường đi ngắn nhất A* (được cải tiến từ thuật toán Dijkstra)
2. Giải thuật tìm kiếm A*
A* là một thuật toán tìm kiếm trong đồ thị, tìm đường đi từ một nút khởi đầu đến một nút đích cho trước sử dụng một hàm heuristic ước lượng khoảng cách từ nút hiện tại đến nút đích (trạng thái đích), và nó sẽ duyệt đồ thị theo thứ tự ước lượng Heuristic này.
Ý tường:
Xét bài toán tìm đường, A* sẽ xây dựng tăng dần các tuyến đường từ đỉnh xuất phát đến khi nó tìm thấy đường đi chạm đến đích. Để xác định khả năng dẫn đến đích, A* sử dụng một đánh giá heuristic về khoảng cách từ một điểm bất kì cho trước đến đích. Trong ví dụ về bài toán tìm đường đi giao thông  này thì đánh giá heuristic là khoảng cách đường chim bay từ điểm cho trước đến điểm đích.
A* đảm bảo tính đầy đủ và tối ưu, nó luôn tìm thấy đường đi ngắn nhất nếu tồn tại một đường đi như thế. Đầy đủ và tối ưu hơn các thuật toán tìm đường đi khác ở chỗ nó không chỉ ước lượng khoảng cách còn lại (nhờ đánh giá heuristic) mà còn tính khoảng cách đã đi qua để tìm được đường đi ngắn nhất.
Mô tả thuật toán:

A* lưu giữ một tập các đường đi qua đồ thị, bắt đầu từ nút xuất phát. Tập lời giải này được lưu trong một hàng đợi ưu tiên (priority queue). Thứ tự ưu tiên gán cho một đường đi x được quyết định bởi hàm f(x) = g(x) + h(x).

Trong đó, g(x) là chi phí của đường đi cho đến thời điểm hiện tại, nghĩa là tổng trọng số của các cạnh đã đi qua. h(x) là hàm đánh giá heuristic về chi phí nhỏ nhất để đến đích từ x. Ví dụ, nếu “chi phí” được tính là khoảng cách đã đi qua, khoảng cách đường chim bay giữa hai điểm trên một bản đồ là một đánh giá heuristic cho khoảng cách còn phải đi tiếp.

f(x) có giá trị càng thấp thì độ ưu tiên của x càng cao, ta sử dụng f(x) này để xác định nút tiếp theo.

Ta có thể tham khảo mã giả cho thuật giải A* dưới đây: (nguồn)

function A*(start,goal)
     closedset := the empty set    // The set of nodes already evaluated.
     openset := {start}    // The set of tentative nodes to be evaluated, initially containing the start node
     came_from := the empty map    // The map of navigated nodes.

     g_score[start] := 0    // Cost from start along best known path.
     h_score[start] := heuristic_cost_estimate(start, goal)
     f_score[start] := g_score[start] + h_score[start]    // Estimated total cost from start to goal through y.

     while openset is not empty
         x := the node in openset having the lowest f_score[] value
         if x = goal
             return reconstruct_path(came_from, came_from[goal])

         remove x from openset
         add x to closedset
         foreach y in neighbor_nodes(x)
             if y in closedset
                 continue
             tentative_g_score := g_score[x] + dist_between(x,y)

             if y not in openset
                 add y to openset
                 tentative_is_better := true
             else if tentative_g_score < g_score[y]
                 tentative_is_better := true
             else
                 tentative_is_better := false

             if tentative_is_better = true
                 came_from[y] := x
                 g_score[y] := tentative_g_score
                 h_score[y] := heuristic_cost_estimate(y, goal)
                 f_score[y] := g_score[y] + h_score[y]

     return failure

 function reconstruct_path(came_from, current_node)
     if came_from[current_node] is set
         p = reconstruct_path(came_from, came_from[current_node])
         return (p + current_node)
     else
         return current_node
Ví dụ:
AstarExample

nguồn ví dụ: wikipedia

 ví dụ ở bên
Nút màu green là nút bắt đầu, nút màu blue là nút đích.
Các nút đã duyệt qua màu orange.