Về các giải thuật ĐỒ THỊ

Bài viết này trình bày về một số vấn đề liên quan tới các giải thuật ứng dụng trong các bài toán đồ thị. Bao gồm có các thuật toán tìm kiếm trên đồ thị ( BFS & DFS cùng các ứng dụng), thuật toán với DAG(Topological Sort), các thuật toán tối ưu và ứng dụng trong tin học & đời sống (tìm đường đi ngắn nhất, tìm cây khung nhỏ nhất,...). Mở rộng hơn nữa là các bài toán liên quan tới luồng cực đại .

Trước hết, cùng tìm hiểu về các thuật toán tìm kiếm trên đồ thị. Có 2 chiến thuật tìm kiếm trên đồ thị, hoặc tìm kiếm theo chiều rộng (BFS), hoặc tìm kiếm theo chiều sâu (DFS). Hai phương pháp này có những ưu điểm riêng và có những ứng dụng khác nhau trong các bài toán về đồ thị.

Ý tưởng cơ bản của chiến thuật tìm kiếm theo chiều rộng là tìm tất cả những đỉnh có thể tới từ 1 đỉnh đã chọn, rồi từ các đỉnh đó lại lặp lại như trên. Ứng dụng phổ biến nhất của BFS là xét tính liên thông của một đồ thị. Ta có thể kiểm tra một đồ thị có liên thông không, nếu không thì có mấy thành phần liên thông, và mỗi thành phần liên thông có những đỉnh nào.

"Please Wait..., May be will complete at the end of this month!"

Source :

1. The Algorithm Design Manual, Skiena

2. Cấu trúc dữ liệu và thuật toán,

cách tiếp cận định hướng đối tượng sử dụng C++,

Đinh Mạnh Tường.

3. DSAP - Lê Minh Hoàng

Web hay CNTT

I. Programming and Software Engineering

1. Up-Down Casting

http://forum.codecall.net/java-tutorials/20719-upcasting-downcasting.html

2. Template Method

http://www.vincehuston.org/dp/template_method.html

http://www.javacamp.org/designPattern/template.html

http://www.javapractices.com/topic/TopicAction.do?Id=164

3. Một số giải thích về Java Language

http://geekexplains.blogspot.com/2008/05/archives-from-category-java-10.html

4. Trang web cá nhân (Rất hay):
http://linuxfinances.info/info/total.html

5. How to think like a Computer Scientist
http://greenteapress.com/index.html

II. OS (Linux)

1. Setup Sofware

- python 2.7 by easy_install:

http://libraryofmike.org/python/install-python-2-7-easy_install-and-ipython/

- Install LAMP

http://nsviet.com.vn/forum/showthread.php?t=56

III. System Information and Database

IV. Web Applications
1. Tổng quan về Semantic Web
http://phpvn.org/index.php/topic,119.0.html

V. Prolog

1. Prolog tutorial
http://www.csupomona.edu/~jrfisher/www/prolog_tutorial/contents.html

2. The first 10 Prolog Programming Contests
http://dtai.cs.kuleuven.be/ppcbook/

3. Applications of Prolog
http://www.drdobbs.com/high-performance-computing/184405220;jsessionid=SRB2Q2JXZZG1HQE1GHRSKH4ATMY32JVN

VI. Java Technology
1. Hibernate
http://my.opera.com/mattroiden3012/blog/tong-quan-hibernate-framework


2. Spring Framework
http://vi.wikipedia.org/wiki/Spring_Framework

Một vài khía cạnh về Template Method

Thông thường Template Method  được sử dụng trong lớp trừu tượng và là phương thức phổ biến dùng  trong các mẫu thiết kế (Design Patterns), đặc biệt trong Factory và Strategy! 

    Điểm cốt lõi của Template Method là xây dựng một bộ khung, là tập hợp các hành động được biết trước chức năng, nhưng những hành động đó chưa được biết là sẽ thực thi thế nào (Điều này sẽ được định nghĩa ở subclass)! Nói một cách hình tượng, lớp cơ sở sẽ "Giữ chỗ" (bằng Template Method), và sau đó, lớp dẫn xuất sẽ thực thi đoạn đã được giữ. Phương thức trong template method sẽ được định nghĩa lại ở lớp dẫn xuất gọi là một hook-method hoặc một placeholder.

          Ví dụ: 

             

abstract class CheckBackground {
/*Các phương thức này phải đượcđịnh nghĩa lại ở lớp dẫn xuất*/
public abstract void checkBank();
public abstract void checkCredit();
public abstract void checkLoan();
public abstract void checkStock();
public abstract void checkIncome();

/*Đây là một template method,chú ý rằng,
nó không phải là phương thức trừu tượng*/
 public void check() {
checkBank();
checkCredit();
checkLoan();
checkStock();
checkIncome();
}
}

    

    Ứng dụng:   - Sử dụng phổ biến trong các Framework. Những đoạn mã có thể tái định nghĩa sẽ được vào lớp cơ sở của Framework. Sau đó, các hệ thống khách (clients) sẽ thoải mái tùy biến bằng cách tạo ra các lớp dẫn xuất. 

                       -  Sử dụng nhiều trong các mẫu thiết kế (Design Patterns), đặc biệt là Factory và Strategy(Sẽ thảo luận ở một bài khác)!

  Tài liệu tham khảo: 

    1.  http://www.vincehuston.org/dp/template_method.htm

    2.  http://www.javapractices.com/topic/TopicAction.do?Id=164

    3.  http://www.javacamp.org/designPattern/template.html

Giọt nước mắt!

Một bộ phim, đã từng không thèm quan tâm! Một bộ phim, đã từng cho rằng chỉ là một trò lố, và, chưa bao giờ xem, dù chỉ lướt qua!

Trớ trêu thay, chính nó lại lấy đi quá nhiều nước mắt của một con người trẻ! Không biết có phải là vô tình không nữa???! Tại sao lại bắt được nó vào đúng lúc này?

Vài tập cuối, đủ để giáng vào suy nghĩ của ta!

Lần đầu tiên, một bộ phim giọng Nam để lại cho ta nhiều cảm xúc và một triết lý sâu sắc như vậy! Bộ phim là hai mặt của xã hội hiện tại, và nó đánh mạnh vào tâm lý người trẻ, chỉ tiếc thay, không biết có bao nhiêu người trẻ xem xong phim này ngộ ra được triết lý đáng kính kia!

Khi giọt nước mắt tuôn rơi, là lúc ta biết rằng, ta phải làm gì đó, dù nhỏ bé, hay tầm thường, chỉ miễn sao, "đó là công sức mình làm ra", để ta tự hào về nó, để nó có ích, với đời!

Hãy suy nghĩ và hành động! Nhớ về cái title đó, "BDMK"!!!

Cảm ơn VNĐ, cảm ơn TTH, cảm ơn LMH, cảm ơn VTV6, và cuối cùng, xin cảm ơn đấng sinh thành đã sinh ra tôi, cho tôi một cuộc đời, và cho tôi biết suy nghĩ! Xin cảm ơn, tất cả!

Nhớ lấy, học hành thế này thì chết!

Ngồi ôn, tại sao bao lần mà không rút được kinh nghiệm gì là sao?

Cóp nhặt từng ngày sẽ có một kho lớn! Hiểu rõ điều đó, tại sao lại không làm theo đúng điều đó???NGU!!!!!!!!!!!

Trong năm thì không học cẩn thận, nên nhớ, chỉ cần 30 phút cho một buổi học với 1 môn, chỉ cần chừng đó, thì cuối kỳ, quá đơn giản! Ngay cái đoạn từ mới của tiếng Anh, nếu chịu khó tra từ, cả các từ loại của chúng nữa, viết ra một bảng, thì đâu phải tới mức cuối kỳ, ngồi chỉ viết ra chúng, mà đâu có thể thuộc hết chúng! NGU, again!

Một phép tính: 3o' x 10 buổi/tuần = 300' = 5 h

1 tuần = 168 h

Ngủ: 8h/ngày => 8 x 7 = 56

Ăn chơi nhảy múa: tính 5 h đê => 5 x 7 = 35 h

Di chuyển : tính 1h30'/ ngày => 90 x 7 = 630' = 10h30'

Tới lớp, tính 4h/buổi, tầm 10 buổi, => 40 h

Vị chi mất 147 h, còn lại 21 h, mỗi ngày dư ra 3h.

3h một ngày, đủ để làm ra chuyện rồi, tận dụng nào! Come on!

Sắp chiến đấu, vì danh dự, vì gia đình, vì tố quốc, gắng sức!

Nhanh thật, lại một tháng 6 nữa! Tháng 6 thứ 20 trong cuộc đời!

Bé, tháng 6 thật là thích! Nghỉ hè này, chạy nhảy quanh làng này, được đi câu cá này!

Lớn một chút, 8 tuổi, tháng 6 thật là vui, có World Cup. Kỳ World Cup đầu tiên, à, theo papa, mình cũng xem theo. Nhớ một buổi đêm, 12h, bảo bố gọi dậy xem trận Brazil và... đội nào đó( chả nhớ nữa!, mà cũng chả hiểu sao đi thích Brazil!!!), bố không gọi, phút thứ 94' (đoán thế!), bật dậy, lao ra, bố vừa khéo tắt TV. Ấm ức, nằm ngủ tiếp giàn giụa nước mắt và.....tức bố!(Sau mới biết, bố không lỡ gọi mình dậy, ngủ say thế cơ mà!).

12 tuổi, lại WorldCup, lần này thì ngóng đợi từng ngày, vì, nó tổ chức ở Châu Á ta, hơ hơ, chả phải lo thức đêm rồi, cả ngày chỉ ngồi xem WC mệt nghỉ! Lúc đó nghĩ mình cũng lạ, một quyển vở, chi chít chữ, đầy đủ tên các player của từng đội một trong kỳ WC đó, chả hiểu sao mình lại có thể nhớ hết tên bọn đó, gần nửa trong số 32 đội mình viết đủ 23 cái tên không thiếu tên nào! (Mình phục mình quá!!!). Lần này, Brazil của mình chiến thắng, vui, rất vui, còn nhớ 4 năm trước, Bra của ta bị thua nhục!

12 tuổi, hè vẫn còn rất thơ và tràn đầy phấn khích!

13 tuổi, vốn là dân quê, nhưng lại không biết bơi, bố dẫn 2 anh em đi học bơi. Hôm đầu, sợ! Ngại nữa! Bọn trẻ lon ton còn bơi như cá, mình thì ôm phao! Hôm thứ hai, cũng hay hay! Từ hôm thứ ba, ngại qué giề, bơi thôi, sướng, nhất là được bố dìu ra chỗ sâu, mát thế! Thằng em còn bắt chước mấy lão choai, làm vận động viên nhảy cầu, vui phết!

Tới đây, hè vẫn còn vui chán!

14 tuổi, hè không còn vui nữa! Bắt đầu nhận thức được rằng, học không đơn giản chỉ là 8,9 phẩy trên lớp. Mua sách, ôn thi, hy vọng vào trường xịn. Niềm hy vọng lớn lao của một cậu bé 14 tuổi!

Hè tuổi 15, chả còn buổi đi chơi nào nữa! Tháng 6 tuổi 15, còn nhớ mãi! Lần đầu đi học xa nhà! Bắt đầu bằng đĩa cơm rang mà giờ, kể lại cả nhà ai cũng phải cười. Cảm giác thất thểu ở đường giữa những ngày nắng gắt, quả thật cuộc sống không phải lúc nào cũng là vòng tay của bố mẹ. Lần đầu biết nhìn sâu vào cuộc sống! Tiếp thêm niềm tin, ta sẽ cố gắng, mái trường kia phải có bước chân ta trong đó! Lại hy vọng, và cố gắng! Đằng đẵng gần 1 tháng, mưa như trút có, nắng đổ lửa có, ta vẫn kiên gan (sự thật!). Tới ngày bước vào phòng thi, vẫn hy vọng, giờ thêm tự tin. Ta chỉ chuẩn bị thực sự có 1 tháng, không dám so với 4 năm của những bạn nơi khác cùng tới ôn, nhưng ta dám tin ta làm được. Chí ít, đó đã là thành công của ta, tin vào chính mình! Buổi thi thứ nhất, Văn, OK, bịa như đúng rồi, kiểu gì cũng ăn 7, ít nhất! Ta thầm nhủ! Buổi thi thứ 2, Toán, đọc đề xong, cũng OK, duy phần 1 điểm là có lẽ không xơi được ( dù trưa vừa đọc xong, không hiểu, không nhớ!). Làm xong, chí ít cũng ăn 7. Tin là thế đi! Buổi thứ 3, sáng, lúc này tràn đầy khí thế, là môn tủ! Thầm hứa với bố mẹ, con sẽ làm được! Chỉ cần làm tốt như hai bài kia, con dám chắc chắn con đã đậu! Lên đường! Vào phòng, khoan khoái thế! Đọc đề, chết lặng! Phần kém nhất thì có tới 3 bài (Chưa bao giờ thấy ra đề kiểu này!)! Ôi, còn đâu lời hứa! 2 bài còn lại, một bài trong 5 phút (nhớ, cứ thế phang!). Bài còn lại ta xin 20 phút! Thế là mất 25 phút! Còn 125 phút nữa, gặm nhấm 3 nỗi tủi hờn! Cố gắng tới phút cuối cùng, cũng kín trang giấy, nhưng ta biết chắc, ta đã thất bại! Hy vọng đầu tiên tắt ngấm! Ta còn phải vật lộn với nó một thời gian dài! (Điều đó chứng tỏ trong năm học lớp 10, thật tồi tệ!).

Hè tuổi 16, đã biết đâu là việc cần phải làm tiếp theo! Vẫn ham chơi, nhưng ta biết, ta cần làm gì! À, mà còn WC của ta, tý quên, lần này cũng vui, 3 bố còn toàn thâu đêm "nhậu" và xem. Còn nhớ, tập BDG về, mệt muốn chết, thầy ép như ép giò, vậy mà, vẫn xem thâu đêm được. 10h sáng lấy làm bình minh!

Hè tuổi 18, không được phép làm gì, ngoài học! Từ đây, và tới vài năm sau nữa, có lẽ tháng 6 sẽ là những ký ức khó phai. Tháng 6 - tháng ôn thi! Phải đỗ, phải đi tới, ta phải làm! Chưa thực sự cố gắng, bởi vậy, kết quả dù có khả quan, nhưng ta không hài lòng. Hy vọng nhỏ nhoi nữa không thành hiện thực. Lại rơi vào trạng thái 3 năm trước! Nhưng chỉ mất 2 tháng để ta quên nó, và thêm 2 tháng nữa, để ta quyết tâm!

Tháng 6 của tuổi 19, cái tuổi "teen" cuối cùng. Có lẽ, tới giờ đây và mãi mãi mai sau, ta ghi nhớ nó là tháng 6 tồi tệ nhất cuộc đời! Tại sao là tháng 6, mà không là tháng 7, dù chỉ còn vài ngày nữa sẽ bước qua tháng 6??? Trả lời: tại ta, tất cả là tại ta! Không oán trách, không hận thù! Một tháng 6 đem lại những thất bại nặng nề! Hãy quên nó đi, hỡi con người nhỏ và hoài bão lớn! Chỉ là một vết xước da, không hơn!

20, tháng 6 chính là lúc này đây, quá bình thường, đủ sức để thấy được rằng, chuyện nào là chuyện bt, có nhất thiết phải khó hóa mọi chuyện. Nhìn đời, bằng con mắt khinh thường, ta muốn thế, vì, không có gì là không thể!

Ta sẽ viết tiếp tháng 6, của ta!

12h, ngày mới bắt đầu!

3h đi ngủ, 10h dậy, 11h30' ăn trưa xong, và 12h, ngày mới của ta bắt đầu!

Hôm nay ôn gì đây, nhìn mà chán ngắt! Kiếp ôn thi!

Mùa ôn thi thứ tư, cảm giác bình thướng quá đỗi.

Lần 1, hồi hộp &thấp thỏm. Lần 2, lo lắng! Lần 3, áp lực quá! Lần 4, cũng bình thường thôi!!!

Và ngày mai, ta sẽ chờ, và ta sẽ đợi, và cũng sẽ nghe, tiếng gọi từ đỉnh núi kia, ta sẽ đi tới, ta sẽ vươn lên. Ngày mai ta chiến thắng!

Nào, bắt đầu ngày mới nào!

Come on!!!

Lời nói đầu!

     Khai trương blog, hy vọng nó sẽ lưu giữ những kỷ niệm, những kiến thức theo năm tháng trong cuộc đời tôi!