[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.