[Tài liệu] Hướng dẫn sử dụng SkyDrive

Tài liệu hướng dẫn sử dụng SkyDrive của PGS TS Bùi Thế Tâm, được đăng trên tạp chí “Công nghệ thông tin và truyền thông” của Bộ Công nghệ thông tin, Kỳ 2 Tháng 12/2010, ISSN 1859-3550.

Download tại đây:

http://www.mediafire.com/?6010le2kttix0yp

Simulated Annealing – Thuật toán mô phỏng luyện kim

Tổng quan thuật toán mô phỏng luyện kim (Simulated Annealing (SA))

Giới thiệu chung về thuật toán SA

SA là một thuật toán tìm kiếm xác suất di truyền, là phương pháp tối ưu hoá có thể áp dụng để tìm kiếm tối ưu hoá toàn cục của hàm chi phí và tránh tối ưu hoá địa phương bằng việc chấp nhận một lời giải tồi hơn với một xác suất phụ thuộc nhiệt độ T.

Tiền thân của SA là thuật toán Monte Carlo năm 1953 của nhóm Metropolis. Thuật toán SA được đề xuất bởi S. Kirk _ partrick năm 1982 và được công bố trước công chúng năm 1983.

SA có nguồn gốc từ cơ học hệ thống. SA thực thi đơn giản và tương tự quá trình luyện kim vật lý. Trong luyện kim vật lý kim loại được đốt nóng tới nhiệt độ cao và làm lạnh từ từ để nó kết tinh ở cấu hình năng lượng thấp (tăng kích thước của tinh thể và làm giảm những khuyết điểm của chúng). Nếu việc làm lạnh không xảy ra từ từ thì chất rắn không đạt được trạng thái có cấu hình năng lượng thấp sẽ đông lạnh đến một trạng thái không ổn định (cấu trúc tối ưu địa phương)

Gọi E là năng lượng của trạng thái s, E’ là trạng thái năng lượng của trạng thái s’ và ∆E = E’ – E là sự chệnh lệch nhiệt độ giữa trạng thái s’ và trạng thái s. Nếu ∆E ≤ 0 thì sự thay đổi kết quả được chấp nhận với xác suất  trong  đó T  là nhiệt  độ, kB là một hằng số vật lý được gọi là hằng số Boltzmann.

SA sử dụng một biến điều khiển toàn cục là biến nhiệt độ T. Ban đầu T ở giá trị rất cao và sau đó được giảm dần xuống. Trong quá trình tìm kiếm SA thay lời giải hiện thời bằng cách chọn ngẫu nhiên lời giải láng giềng với một xác suất phụ thuộc vào sự chênh lệch giữa giá trị hàm mục tiêu và tham số điều khiển T.

Quá trình tối ưu hoá được tiếp tục cho tới khi cực tiểu toàn cục được tìm thấy hoặc tổng số bước chuyển vượt quá một số tối đa các bước chuyển đã được định trước. Sự chuyển tiếp ở một nhiệt độ kết thúc khi đạt tới trạng thái cân bằng nhiệt. Sau khi đạt tới trạng thái cân bằng nhiệt thì nhiệt độ được giảm thấp hơn. Nếu hệ thống không đông lạnh và cũng không tìm được cực tiểu toàn cục thì vòng lặp vẫn tiếp tục và chỉ số k tăng. Hệ thống đông lạnh khi T tiến tới nhiệt độ Tcuối do người dùng đưa ra.

Mã giả thuật toán:

 
s ← s0; e ← E(s) // Initial state, energy.
sbest ← s; ebest ← e // Initial "best" solution
k ← 0 // Energy evaluation count. 
while k < kmax and e > emax // While time left & not good enough: 
T ← temperature(k/kmax) // Temperature calculation. 
snew ← neighbour(s) // Pick some neighbour. 
enew ← E(snew) // Compute its energy. 
if P(e, enew, T) > random() then // Should we move to it? 
s ← snew; e ← enew // Yes, change state. 
if e < ebest then // Is this a new best? 
sbest ← snew; ebest ← enew // Save 'new neighbour' to 'best found'. 
k ← k + 1 // One more evaluation done 
return sbest // Return the best solution found.

Xem thêm tại: http://en.wikipedia.org/wiki/Simulated_annealing
 

Kĩ thuật nhánh cận

<Just type to remember>

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

Với các bài toán tìm phương án tối ưu, nếu chúng ta xét hết tất cả phương án thì mất rất nhiều thời gian, nhưng nếu sử dụng phương pháp tham ăn thì phương án tìm được chưa hẳn đã tối ưu. Nhánh cận là kĩ thuật xây dựng cây tìm kiếm phương án tối ưu, nhưng không xây dựng toàn bộ cây mà sử dụng giá trị cận để hạn chế bớt các nhánh.

Cây tìm kiếm phương án có nút gốc biểu diễn cho tập tất cả các phương án có thể có, mỗi nút lá biểu diễn cho một phương án nào đó. Nút n có các nút con tương ứng với các khả năng có thể lựa chọn tập phương án xuất phát từ n.Kĩ thuật này gọi là phân nhánh.

Với mỗi nút trên cây ta sẽ xác định một giá trị cận. Giá trị cận là một giá trị gần với giá của các phương án.Với bài toán tìm min ta sẽ xác định cận dưới còn với bài toán tìm max ta sẽ xác định cận trên. Cận dưới là giá trị nhỏ hơn hoặc bằng giá của phương án, ngược lại cận trên là giá trị lớn hơn hoặc bằng giá của phương án.

Bài toán đường đi người giao hàng

Phân nhánh

Cây tìm kiếm phương án là cây nhị phân trong đó:

  • Nút gốc là nút biểu diễn cho cấu hình bao gồm tất cả các phương án.
  • Mỗi nút sẽ có 2 con, con trái biểu diễn cho cấu hình bao gồm tất cả các phương án chứa một cạnh nào đó, con phải biểu diễn cho cấu hình bao gồm tất cả các phương án không chứa cạnh đó (các cạnh để xét phân nhánh được lập tuân theo một thứ tự nào đó, chẳng hạn thứ tự từ điển).
  • Mỗi nút sẽ kế thừa các thuộc tính của tổ tiên của nó và có thêm một thuộc tính mới (chứa hay không chứa một cạnh nào đó).
  • Nút lá biểu diễn cho một cấu hình chỉ bao gồm một phương án.
  • Để quá trình phân nhánh mau chóng tới nút lá, tại mỗi nút ta cần có một quyết định bổ sung dựa trên nguyên tắc là mọi đỉnh trong chu trình đều có cấp 2 và không tạo ra một chu trình thiếu.

Bí quyết luyện nghe TOEIC (từng phần)

<Trong lúc đi tìm cách nghe TOEIC để test thì thấy bài này.. post lại cho mọi người tham khảo>

<Nguồn: Moon blog>

Section I: Listening Comprehension (100 câu hỏi, khoảng 45 phút làm bài)

Bạn sẽ xem một ảnh chụp và được yêu cầu lựa chọn trả lời mô tả đúng những gì đang diễn ra trong hình. Các lựa chọn trả lời sẽ được đọc cho bạn; chúng sẽ không được in trong quyển đề thi.

Các câu hỏi đặt ra sẽ hỏi về người (people) hoặc vật (things). Để làm tốt phần này , ngay khi bạn nhìn thấy bức tranh bạn cần phải trả lời ngay các câu hỏi sau:
Photos for People: 

Who are they?
Where are they?
What are they doing?
What do thay look like?

Photos for things

What are they?
Where are they?
What was done to them
What do they look like

Đây là phần bạn rất dễ bị ” lừa” khi nghe. Các câu miêu tả sẽ hoặc là có nội dung sát với bức tranh nhưng không chính xác hoặc các câu đó phát âm tương tự nên bạn rất dễ bị nhầm. Hãy tỉnh táo khi nghe phần này nhé!

Part 2- Question and Response- 30câu (3 lựa chọn)

Bạn sẽ nghe một câu hỏi và được yêu cầu chọn câu trả lời đúng cho câu hỏi. Cả câu hỏi lẫn các lựa chọn trả lời đều sẽ được đọc nhưng không được in trong quyển đề thi.

Vấn đề đặt ra là nếu bạn sao nhãng không nghe được câu hỏi thì những đoạn phía sau thật là vô nghĩa. Khi bạn đã tập trung và nghe rõ được câu hỏi , hãy định hình ngay trong đầu xem nó đang đề cập đến cái gì. Điều này bạn có thể làm được nhờ bắt được một số key word như:

  • Identifying Time: When , How long, What time, Yet, still, late , early , morning,… , at 6.am,… today , this week,… yesterday, tomorrow…
  • Identifying People: Who , Whom , Whose, Who’s , Name, An Occupation title
  • Identifying a suggestion : Why don’t we… , Why don’t you…, Let’s…, What about…
  • Identifying a choice : What , which, or , prefer , rather ….
  • Identifying a reason: Why …, Why didn’t…, Excuse , reason…
  • Identifying a location : What , where , how far, next to, beside, left, right, near , far ,at , …, name of place….
  • Identifying an opinion : What , how , think , believe , your opinion, like

Part 3- Short Conversations- 30câu (4 lựa chọn)

Bạn sẽ được nghe đoạn hội thoại sau đó trả lời câu hỏi, phần này lại khoai hơn phần trước một tí. Để làm tốt được phần này bạn phải nhanh chóng đọc câu hỏi của đoạn hội thoại đó và chú ý nghe nội dung từ đầu đến cuối cố gắng không bỏ sót chữ nào vì bạn không thể tưởng tượng được đâu chính những từ bị phát âm lướt qua lại là đáp án cho câu trả lời đấy. Phần này đòi hỏi cả tư duy logic để phán đoán câu trả lời

Phần này cũng tương tự phần trên , sau khi bạn đọc câu hỏi để biết được hỏi về cái gì , bạn hãy chú ý lúc nghe thấy các từ key word như trên

Part 4- Short Talks- 20câu (4 lựa chọn)

Phần này gồm 20 câu hỏi cho khoảng 7 đến 9 đoạn, mỗi đoạn văn sẽ có tối thiểu 2 câu hỏi, phần này là phần khó nhất trong bài nghe, nhưng lại là phần ít lừa đảo và đánh đố nhất, nó chỉ đòi hỏi bạn khả năng ghi nhận thông tin nhanh thôi. Để làm tốt phần này bạn cần phải đọc lướt nhanh các câu hỏi (như nói ở trên kia) …. Bạn cũng cần phải luyện nghe đoạn văn thường xuyên để quen với các ghi nhận các thông tin chính, vì các câu hỏi trong đề thi thường tậ trung hỏi các vấn đề chính, với cả nghe thường xuyên bạn đỡ bị căng thẳng hơn, không bị bỏ sót thông tin hơn.

Dynamic Programming (Kĩ thuật quy hoạch động)

<Just Type to Remember>

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

Nội dung kĩ thuật:

Như trong https://vuonghienuit.wordpress.com/2012/04/10/divide-and-conquer-ki-thu%E1%BA%ADt-chia-d%E1%BB%83-tr%E1%BB%8B/ đã nói, kĩ thuật chia để trị thường dẫn chúng ta đến một giải thuật đệ quy. Trong các giải thuật đó, có thể có một số giải thuật có độ phức tạp thời gian mũ. Tuy nhiên, thường chỉ có một số đa thức các bài toán con, điều đó có nghĩa là chúng ta đã phải giải bài toán con nào đó nhiều lần. Để tránh việc giải dư thừa một số bài toán con, chúng ta tạo ra một bảng để lưu trữ kết quả của các bài toán con và khi cần chúng ta sẽ sử dụng kết quả đã được lưu trữ trong bảng mà không cần phải giải lại bài toán đó. Lấp đầy bảng kết quả của bài toán con theo một quy luật nào đó để nhận được kết quả của bài toán ban đầu (cũng đã được lưu trong một số ô nào đó của bảng) được gọi là quy hoạch động (dynamic programming). Trong một số trường hợp để tiết kiệm ô nhớ, thay vì dùng một bảng, ta chỉ dùng 1 vectơ.

Có thể tóm tắt giải thuật quy hoạch động như sau:

1. Tạo bảng bằng 2 cách:

    • Gán giá trị cho một số ô nào đó.
    • Gán giá trị cho các ô khác nhờ vào giá trị của các ô trước đó.

2. Tra bảng và xác định kết quả của bài toán ban đầu.

Ưu điểm của phương pháp quy hoạch động là chương trình thực hiện nhanh do không phải tốn thời gian giải lại một bài toán con đã được giải.

Kỹ thuật quy hoạch động có thể dùng để giải các bài toán tối ưu, các bài toán có công thức truy hồi.

Phương pháp quy hoạch động sẽ không đem lại hiệu quả trong các trường hợp sau:

  • Không tìm được công thức truy hồi.
  • Số lượng các bài toán con cần giải quyết và lưu giữ kết quả lả rất lớn.
  • Sự  kết hợp lời giải của bài toán con chưa chắc cho ta lời giải của bài toán ban đầu.

 

Một số bài toán có thể giải bằng quy hoạch động: “Bài toán tính số tổ hợp”, “Bài toán cái ba lô”, “Bài toán đường đi người giao hàng”,…

 

Greedy algorithm (Kĩ thuật tham lam)

<Just Type to Remember>

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

 

1. Bài toán tối ưu tổ hợp:

Là một dạng của bài toán tối ưu, nó có dạng tổng quát như sau:

  • Cho hàm f(X) xác định trên một tập hữu hạn các phần tử D. Hàm f(X) được gọi là hàm mục tiêu.
  • Mỗi phần tử X thuộc D có dạng X = (x1, x2,…xn) được gọi là một phương án.
  • Cần tìm một phương án X thuộc D sao cho hàm  f(X) đạt min (max). Phương án X như vậy gọi là tối ưu.

Ta có thể tìm thấy phương án tối ưu bằng “vét cạn” nghĩa là xét tất cả các phương án trong tập D (hữu hạn) để tìm phương án tốt nhất. Mặc dù tập D là hữu hạn nhưng để tìm phương án tối ưu cho một bài toán kích thước n bằng vét cạn ta có thể cần một thời gian hàm mũ.

2. Nội dung kĩ thuật tham lam (tham ăn):

Tham ăn hiểu một cách dân gian là: trong một mâm có nhiều món ăn, món nào ngon nhất ta sẽ ăn trước và ăn cho hết món đó thì chuyển sang ăn món ngon thứ hai, lại ăn hết món ngon thứ hai và chuyển sang món ngon thứ 3..

Kĩ thuật tham lam thường được vận dụng để giải bài toán tối ưu tổ hợp bẳng cách xây dựng một phương án X. Phương án X này được xây dựng bằng cách lựa chọn từng thành phần  Xi của X cho đến khi hoàn chỉnh (đủ n thành phần). Với mỗi Xi, ta sẽ chọn Xi tối ưu. Với cách này thì có thể ở bước cuối cùng ta sẽ phải chấp nhận giá trị cuối cùng còn lại.

Áp dụng kĩ thuật tham lam sẽ cho ta một giải thuật thời gian đa thức, tuy nhiên nói chung chúng ta chỉ đạt được một phương án tốt chứ chưa hẳn là tối ưu.

Có rất nhiều bài toán mà ta có thể giải bằng kĩ thuật này.

Các bài toán ví dụ: Các bạn tìm hiểu các bài toán như: “Bài toán trả tiền của máy rút tiền tự động ATM”, “Bài toán cái balô”, “Bài toán đường đi của người giao hàng”, …