Gỡ rối tơ lòng

Các thắc mắc về KHMT, về toán học máy tính, về cách ghi bình luận trên blog, … xin post ở đây. Chúng tôi sẽ cố gắng trả lời nếu khả năng và thời gian cho phép. Các bạn đọc cũng có thể trả lời và thảo luận các câu hỏi. Nếu câu hỏi có liên hệ sâu hơn thì ta chuyển thành một bài mới.

525 Comments

  1. Ngô Quang Hưng
    Posted 22/10/2008 at 6:52 am | Permalink

    @vermouth187,

    Tùy theo kiến thức nền, tôi nghĩ bạn có thể làm đề tài về định lý PCP chẳng hạn (viết một survey). Định lý PCP có tầm của định lý Cook/Levin về NP-Completeness, nhưng có lẽ ít sách giáo khoa viết về nó.

    Reply
  2. TQKhoat
    Posted 05/11/2008 at 2:05 am | Permalink

    Chào anh Hưng và mọi người. Em có một câu hỏi nhỏ hy vọng anh và mọi người chỉ giáo. Số là thế này: em đã đọc nhiều tài liệu về toán, thế nhưng vẫn chưa hiểu hai khái niệm “nhỏ” là Proposition và Theorem. Lemma thì có thể hiểu là một theorem nhỏ, bổ trợ. Thế còn hai khái niệm kia em chưa tài nào phân biệt nổi khi nào thì dùng chúng. Có nhiều tài liệu vừa dùng Proposition và cả Theorem.

    Theo em thấy thì hai cái này dùng để phát biểu một điều gì đó đúng. Thế nhưng khi nào thì dùng Theorem, khi nào dùng Prop. Liệu có phải Prop. hàm ý mạnh hơn Theorem hay ngược lại? Em chưa phân biệt nổi :) ) (pó tay)

    Em thấy anh Hưng cũng hay dùng thì chắc là anh hiểu rõ. Rất mong anh (và mọi người) chỉ rõ cho một người lờ mờ như em. Thanks a lots.

    TQK

    Reply
  3. Ngô Quang Hưng
    Posted 05/11/2008 at 5:38 pm | Permalink

    Hello TQK, Proposition đại loại dùng để chỉ những quan sát đơn giản, chưa xứng đáng làm định lý, nhưng cần phát biểu ra cụ thể để dùng ở nhiều chỗ sau đó trong sách/bài báo.

    Reply
  4. TQKhoat
    Posted 06/11/2008 at 9:30 am | Permalink

    Nếu theo anh nói về Proposition và theo em nghĩ về Lemma thì chúng giống nhau. Lemma cũng là để trình bày những quan sát nhỏ về vấn đề nào đó và dùng nó để bổ trợ cho các định lý khác, dùng được ở nhiều nơi. Như vậy vẫn chưa rõ lắm về hai khái niệm này. Anh có thể giải thích nhiều hơn được không?

    Best regards

    Reply
  5. Ngô Quang Hưng
    Posted 06/11/2008 at 8:17 pm | Permalink

    À, Proposition là cái gì đó “dễ hơn”, “cơ bản” hơn Lemma. Nói chung, tất cả đều chủ quan, mình muốn đặt tên sao cũng được.

    Reply
  6. MHThanh
    Posted 13/11/2008 at 11:41 pm | Permalink

    Chào anh Hưng,

    Hồi lâu rồi em có đọc được một đoạn trên blog của anh trong đó nói rằng một người làm về KHMT, muốn giỏi, thì ít nhất phải giỏi một trong các nhánh kiến thức X, Y, Z…. Em thấy rất chí lý, nhưng ỷ y không ghi chú lại, giờ không làm sao search lại được, chỉ nhớ là ít nhất có Graph Theory và Probability. Mong anh chỉ ra lại giúp.

    Reply
  7. Ngô Quang Hưng
    Posted 15/11/2008 at 1:13 pm | Permalink

    Chào MHThanh,

    Tôi cũng nhớ là có viết về đề tài này, nhưng tìm rồi cũng không ra là ở bài nào. Chắc sẽ viết một post khác.

    Reply
  8. MHThanh
    Posted 16/11/2008 at 5:02 am | Permalink

    Chào anh Hưng,

    Thế em đợi bài post của anh vậy :D . Em nghĩ là nó sẽ rất có ích cho những ai sẽ học phd, hoặc sắp bắt đầu học phd (như em).

    Ngoài lề, em mới làm quen với một nhánh nhỏ bên Graph Theory là Extremal Graph Theory, vì prof em bắt học (ổng cũng không biết, nhưng nghe tên thấy hay !). Nhưng không biết do mình quá tệ hay vì vấn đề này thuần túy là Maths, mà em không cảm thấy nó có ứng dụng gì cho computer science (em học ở lab Databases, nên cũng chỉ rành một chút về databases, chứ những hướng khác thì em không rõ lắm, nên cảm thấy thế). Mong anh chia sẻ kinh nghiệm về những ứng dụng thực tế của thể loại Graph Theory này.

    Cám ơn anh :)

    Reply
  9. Nhiệt Huyết
    Posted 19/11/2008 at 9:44 am | Permalink

    Chúc mừng thầy nhân ngày nhà giáo Việt Nam, và xin cảm ơn thầy vì tất cả những gì tụi em đã được học qua blog này.

    Reply
  10. Ngô Quang Hưng
    Posted 19/11/2008 at 10:23 am | Permalink

    Cảm ơn Nhiệt Huyết.

    Reply
  11. xiuaj
    Posted 20/11/2008 at 9:32 am | Permalink

    chúc anh minh một ngày 20-11 vủi vẻ và có nhiều sức khỏe để viết blog nhé, tụi em hàng ngày đều vào blog anh mòn mỏi trong đợi các entry. Entry thì xa xôi qua chưa bay lại sài gòn được

    Reply
  12. xiuaj
    Posted 20/11/2008 at 9:34 am | Permalink

    ặc, sorry anh hưng, em chả hiểu đánh lung tung thế nào mà tên anh lại gõ lộc cộc thành minh mất.

    Reply
  13. Ngô Quang Hưng
    Posted 20/11/2008 at 10:50 am | Permalink

    Cảm ơn xiuaj.

    Reply
  14. TQKhoat
    Posted 26/11/2008 at 8:02 am | Permalink

    Vài ấn tượng về mấy hội thảo KHMT ở VN năm nay.

    Chào anh Hưng và các anh chị. Hôm nay cũng là một ngày rảnh nên em lên tâm sự với các anh chị vài cảm nhận của riêng em, cảm nhận của một người đang cần tầm sư học đạo, về một số hội thảo Quốc tế được tổ chức ở VN.

    Hiện nay em chỉ đang học nốt cái graduate study ở VN. Tuy nhiên em lại rất mong muốn là có thể đi tiếp vào con đường ngâm cứu về KHMT nhiều hơn. Biết vậy, quyết tâm vậy, nhưng mà kiến thức của em thì eo hẹp quá các anh chị ạ. Muốn nạp thêm vài bộ công phu hay quyền pháp gì đó nhưng thật khó. Khó vì lười :) , rồi khó vì bộ pháp đó khó, … Nói là thế, thế nhưng làm thế quái nào mà em lại mày mò ra được vài thứ cỏn con để đi “khoe” với thiên hạ VN :) ). Chắc anh Hưng và các anh chị khác buồn cười lắm. Nhưng đấy là sự thật 100%. Em mày mò ra vài thứ rồi cũng được nhận đăng tại hội thảo Quốc tế to đoành tại VN.

    Thú thật với mọi người là em cũng chưa đủ đẳng cấp (và xiền bạc) để có thể đi tham dự các hội thảo quốc tế lớn trong KHMT như STOC, FOCS,… Nhận được cái thông báo đi dự hội thảo, thế là em hăm hở chuẩn bị khăn gói quả mướp lên đường. Dòng rã vài tiếng đồng hồ cũng đến được HCM city để tham dự hội thảo RIVF08, hội thảo quốc tế đầu tiên mà em tham dự :) .

    Lần đầu tiên bước chân đến HCM, em cùng thằng bạn chân ướt chân ráo đã phải lăn lội đôn đáo tìm nhà trọ. Lại vài tiếng dòng rã nữa mới tìm được một nhà nghỉ phù hợp với túi tiền ít ỏi. May quá :) )

    Ngày đầu tiên tham dự hội thảo, thật thú vị !! Mở đầu là khoảng thời gian mọi người registration và nạp học phí. (May cho em không phải nạp vì em đang là sv – vớ bở). Rồi nửa tiếng sau tham dự màn chào hỏi của vị chủ toạ Pattric Ballot. Sau khi một vài vị được invited lên thuyết trinh diễn văn thật dài thì cũng được về từng phòng riêng của các chuyên môn.

    Mở đầu phòng em toạ thiền là một anh fellow ở Hàn Quốc biểu diễn Kinh vân hay gì đó em chả hiểu được (em thiền mà :) ). Nhưng phải công nhận là công phu english của anh ta thật tuyệt, ít nhất là hơn hẳn em (có khi phải khổ luyện đến 10 năm cũng chưa hạ được gã đó :) ). Buổi sáng đó chắc mọi người còn khoẻ mạnh và hăm hở nên tham dự khá đông; đến buổi chiều thì có vắng vẻ hơn (chắc là sáng ham luyện công quá :) ). Đến ngày thứ hai, ngày em phải biểu diễn, thì lại càng nghiêm trọng hơn. Không hiểu mọi người bận rộn tu luyện ở đâu mà phòng em ngồi vắng hoe, chỉ được vài mống (khoảng 5-6 gì đó bao gồm cả 2 vị chủ toạ phòng). Không khí luyện tập thật ảm đạm :( đến não lòng vì một Hội thảo Qtế !.

    Thế rồi đến lượt em biểu diễn bộ pháp vừa mới tu luyện được. Sau khoảng 25h thì mệt quá đành nghỉ vậy:). Không hiểu là mọi người ngồi nghe có để ý gì không mà chả thấy mấy người góp ý (hỏi han) gì cả, chỉ có mỗi một vị người pháp gốc việt hỏi. Chả hiểu công phu english của em luyện đến mức nào mà tồi thế, ông ấy hỏi những gì đó mà em nghe đầu chẳng xuôi đuôi chẳng lọt :( , rồi cuối cùng thế nào mọi người cũng đoán ra. Một vài người khác cũng tham gia vài câu cho vui, rồi chẳng thấy vị nào có vẻ hiểu sâu về bộ pháp của em mới tậu được. Vậy mà em vẫn ẵm quả Student Best Paper award đấy :) ).

    Hai ngày tham dự hội thảo rồi nhanh chóng qua đi, tất nhiên toàn bộ hội thảo dài tới 4-5 ngày ròng. Em mặc dù thích tham dự lắm nhưng lại phải quay về giải quyết chiến sự ở hà nội (chiến đấu với bọn kỳ thi :) ). Thế là khăn gói quả mướp lếch thếch quay về…

    Qua 2 ngày tham dự, một vài suy nghĩ cứ nhảy nhót trong đầu em mãi. Thứ nhất, người làm về khoa học lão thành trong nước đâu hết? Sao chỉ thấy toàn là các fellow đến, mà chủ yếu là từ hải ngoại về mới lạ chứ? Theo đánh giá của dân KHMT trong nước thì RIVF là một trong các hội thảo QT tốt nhất trong nước, vậy mà chả thấy bóng dáng báo cáo của các vị GS. Thứ hai, Một vài bộ pháp trong đó chất lượng vẫn còn chưa cao và chưa thể mang ra đấu trường ngoài được :) .

    Đấy là vài cảm nhận về RIVF. Tuy nhiên em thấy nó còn tốt hơn nhiều cái ICTACS ở Nha Trang sắp tới. Không tin thì mọi người cứ vào trang chủ của nó mà xem http://www.fit.hcmuns.edu.vn/ictacs09/Home.aspx

    Trong bảng thông báo important dates, các dòng chữ xoá nhoè nhoẹt. Ngày cứ thay đổi như chong chóng. Anh hưng và mọi người chắc không nhận được cái bảng poster đầu tiên của nó. Trong poster đó, Paper Submission Due là từ tháng 7; nhưng cuối cùng thì sao? chuyển sang ngày 29/9, rồi cuối cùng mới toạ ở ngày 10/10 không hiểu lý do là gì !!! (chắc là có quá ít bài gửi:). Xem quá khứ của nó thì năm 2006 cũng thế, có mỗi 7-8 bài gì đó – pótay. Thật đáng buồn cho cái đấu trường này.

    Còn hội thảo về “Một số vấn đề chọn lọc trong CNTT và TT” thì phải nói là vái lạy luôn :) ). Vậy mà các vị fellow ở nhà vẫn lấy đó là thành tích để hoàn thành Luận Án to đoành. :)

    Reply
  15. Ngô Quang Hưng
    Posted 28/11/2008 at 8:33 pm | Permalink

    Cảm ơn TQKhoat, bài cảm nhận rất thú vị. Mấy hôm nay bận quá không ngó ngàng đến blog, hôm nay mới thấy bài này.

    Reply
  16. Thang
    Posted 12/12/2008 at 7:26 pm | Permalink

    Chào anh Hưng
    Em có một câu đố đã gửi cho anh vào hungngo@cse.buffalo.edu
    Anh xem rồi giúp em nhé.
    Chúc anh vui vẻ.

    Reply
  17. Nguyen Hung Son
    Posted 05/01/2009 at 6:43 am | Permalink

    Chào anh Hưng, Chào TQKhoat,

    Hôm nay rất tình cờ tôi tìm được BLOG này của anh Hưng và thấy rất hay. Cám ơn anh Hưng đã mất nhiều công phu xây dựng và đã có rất nhiều bài hay và bổ ích cho cộng đồng KHMT ở VN. Tôi cũng là người có 1 ít kinh nghiệm về các lĩnh vực mà anh Hưng quan tâm như: computational complexity theory, COLT, Boolean functions … Còn major của tôi là machine learning, data mining, soft computing, MAS. Sau khi đọc hết các bài trong BLOG này tôi sẽ comments sau.

    Tôi cũng vừa về VN dự hội nghị PRICAI’08 mà anh Hồ Tú Bảo đã tổ chức rất thành công ở Hà nội và khẳng định rằng các quan sát của bạn TQKhoat là rất chính xác. Tôi thấy thực sự đáng tiếc khi nhìn thấy hội trường ngồi nghe các invited talks chỉ vẻn vẹn 1 vài sinh viên + 1 vài giáo viên đã từng du học ở nước ngoài đi nghe, còn các sessions thì hầu như không có ai. Đặc biệt GS. Hồ Tú Bảo có 1 tutorial (free for students) về cách viết research papers và làm presentation – chỉ có khoảng 20 người tham dự!!! Tất nhiên khi hỏi về lí do tại sao ở VN không có điều kiện làm research thì ai cũng bảo rằng không có điều kiện tiếp xúc với các nhà ngiên cứu thế giới.

    Đây không phải là lần đầu tiên tôi nhận ra vấn đề này. Các hội nghị trước đó cũng vậy. Tôi cũng không rõ lý do tại sao? Có lẽ là có nhiều nguyên nhân: giáo viên, sinh viên, kinh phí, phương pháp tiếp cận, tính thiếu tự tin, xông xáo, …

    Các anh chị nghĩ sao về vấn đề này? làm thế nào để thay đỏi đây?

    Reply
  18. Xuan Dong
    Posted 13/03/2009 at 5:59 am | Permalink

    E chao A!
    tinh co E duoc mot ng ban gioi thieu trang web nay
    nhung thuc su E chua vao bjo nen E cung khong chac tn nay se den duoc voi A
    nhung E van hy vong va hy vong
    vi E dang gap rac roi
    E dang lam de tai ve Abxtract Machine _ May truu tuong ma chua tim duoc mot tai lieu nao ca
    A co the giup E gioi thieu cho E mot vai tai lieu va link cua no duoc khong
    E sap phai bao cao de tai ma chua lam duoc j A ah
    Mong A l.l voi E qua mail: pxdong86@yahoo.com
    PhamXuanDong_svDH Nong nghiep HN

    Reply
  19. Ngô Quang Hưng
    Posted 13/03/2009 at 7:41 am | Permalink

    Chào Xuan Dong,

    Rất tiếc là tôi không biết “Abstract Machine” là gì, nên không giúp bạn được.

    Reply
  20. Thang
    Posted 23/03/2009 at 4:21 pm | Permalink

    Hi anh Hưng,
    Anh Hưng vui lòng giúp em hiểu rõ hơn về approximation ratio trong trường hợp optimal solution bằng ZERO được không ạ?

    Trong một bài toán approximation, nếu optimal solution có giá trị 0 thì bất kì C-factor approximation algorithm nào cũng phải trả về giá trị 0 đúng không ạ? Nếu việc xác định optimal solution có giá trị 0 hay không là một bài toán NP-C, mình có thể kết luận là bài toán đó không thể approximated by any constant factors (functions) được không ạ (vì nếu không ta có một Polynomial algorithm để decide optimal solution có bằng 0 hay không) ?

    Cảm ơn anh nhiều và chúc anh luôn vui.

    Reply
  21. Ngô Quang Hưng
    Posted 24/03/2009 at 7:36 am | Permalink

    Hi Thắng,

    Đúng rồi: nếu việc xác định opt sol = 0 hay không là NP-hard thì sẽ không có approximation algorithm cho bài toán optimization với bất kỳ ratio nào. (Không chỉ là constant ratio, mà bất kỳ ratio nào.)

    (Ví dụ: reduction từ Hamiltonian cycles về TSP tổng quát.)

    Reply
  22. Ninh
    Posted 30/03/2009 at 6:33 am | Permalink

    Chào anh Hưng, (bài post trước bị lỗi, em viết lại ở đây)

    Em đang có một bài toán nhỏ mà tìm mãi vẫn chưa có câu trả lời hợp lý. Em rất mong anh Hưng và các anh chị quan tâm và suy nghĩ câu trả lời hộ em. Bài toán của em là như sau:

    Giả thiết P là giao của siêu hình thoi (hình thoi trong không gian n chiều) và siêu hộp vuông. Giả thiết x là điểm nằm ngoài P, o là tâm của P, B là siêu cầu lớn nhất mà chứa trong P. Câu hỏi là liệu khoảng cách từ o đến x có lớn hơn bán kính của B không?

    Bài toán này có thể phát biểu theo cách khác như sau:
    cho 

    T=\{x \in R^n: |x_1|+\cdot+|x_n| \le d\}

    là hình thoi, 

    H=\{x \in R^n: ||x||_\infty \le t\}

    là hình hộp, 

    {P = T \cap H}

    . Gọi B là hình cầu lớn nhất chứa trong P, x là điểm không thuộc P. Liệu khoảng cách từ x đến tâm của P có lớn hơn bán kính của B?

    Nếu trong không gian 2 chiều thì có thể nhìn thấy ngay. Nhưng trong không gian n chiều thì có đúng không. Đến nay em vẫn chưa tìm được cách chứng minh. Các anh chị thử suy nghĩ và chứng minh hộ em nhé. Đáng lẽ em phải hỏi câu hỏi này bên Diendantoanhoc.net, nhưng họ đang nâng cấp nên em không hỏi được :)

    Chúc anh vui vẻ

    Reply
  23. Ngô Quang Hưng
    Posted 30/03/2009 at 8:04 pm | Permalink

    Ninh, chắc là tôi không hiểu câu hỏi.

    P là bất kỳ hình lồi nào thì bán kính hình cầu nội tiếp phải nhỏ hơn khoảng cách từ tâm đến một điểm nằm ngoài P rồi.

    Reply
  24. Ninh
    Posted 31/03/2009 at 6:56 pm | Permalink

    Vâng. có thể em phát biểu chưa đúng ý em hỏi. Ý của em là bài toán sau

    cho 

    T=\{x \in R^n: |x_1|+\cdots+|x_n| \le nd\}

    là hình thoi, 

    H=\{x \in R^n: ||x||_\infty \le d\}

    là hình hộp, 

    {P = T \cap H}

    . Gọi y thuộc P, t là tâm của P, x là điểm không thuộc P. Liệu khoảng cách từ x đến t có lớn hơn khoảng cách từ y đến t ?

    Reply
  25. Ngô Quang Hưng
    Posted 31/03/2009 at 7:34 pm | Permalink

    @Ninh,

    1. Trong post trước Ninh định nghĩa hình thoi dùng ‘d’, hình hộp dùng ‘t’

    2. Trong post trên thì ‘nd’ và ‘d’

    Cái nào đúng? Nếu ý Ninh là (1) thì liên hệ giữa d và t ra sao? Có ràng buộc gì không?

    À, nhưng chắc không cần ràng buộc gì. Dễ thấy P không phải hình cầu. Gọi y là điểm xa tâm nhất của P, x là điểm gần tâm nhất. Sau đó dịch x ra ngoài một chút là xong: x (nằm ngoài) vẫn gần tâm hơn y.

    Reply
  26. Ninh
    Posted 01/04/2009 at 8:24 pm | Permalink

    Vâng, cảm ơn anh Hưng. Anh giải thích dễ hiểu quá. Vậy mà em không nghĩ ra được :)

    Trường hợp y và x là các vector thực thì như thế. Nhưng nếu yêu cầu chúng là các vector nguyên thì sao? Liệu điều đó còn đúng không? Theo thiển ý của em thì sẽ phải chứng minh rất phức tạp :)

    Reply
  27. seraphpl
    Posted 04/04/2009 at 9:17 pm | Permalink

    Em chào anh Hưng, em là học sinh sắp tốt nghiệp THPT. Em đang định hướng chọn trường ĐH.
    Có xem qua một số khóa học về Computer Science (CS) của các trường Việt Nam lẫn nước ngoài, em thấy nó chung chung, không tập trung lắm về thuật toán, mỗi trường mỗi khác, không biết cái nào hợp với mình hơn.

    Liệu có chương trình nào học hết toàn bộ cái này không anh ?
    http://vi.wikipedia.org/wiki/Khoa_h%E1%BB%8Dc_m%C3%A1y_t%C3%ADnh

    Reply
  28. 1001001
    Posted 04/04/2009 at 9:37 pm | Permalink

    Em chào giáo sư Hưng! Em là du học sinh mới qua Mỹ học undergraduate năm thứ nhất. Em mới đang học 1st semester. Phải học các môn như English và macroeconomic chiếm thời gian đọc thêm sách quá. Em phải cố gắng mấy môn kia có GPA cao để còn transfer vào trường tốt nữa! :(
    Thời gian rãnh thì em đọc thêm sách liên quan đến Toán và Thuật toán nhưng thời gian học mấy môn chính khóa chiếm nhiều quá thành ra thời gian dành cho tự đọc thêm sách ít quá. Nếu chỉ học theo khung chương trình thì liệu có đủ để tốt nghiệp đại học xong là học lên Master hoặc Phd không ạ?

    Reply
  29. HaThuyAnh
    Posted 09/04/2009 at 8:29 pm | Permalink

    Các anh có thể giải thích ngắn gọn giúp tôi về ngành học “Các hệ thống thông tin và tri thức”
    vì tôi muốn biết yêu cầu của việc giảng dạy ngành này xem có đáp ứng được không
    vì tôi xem được trên http://fit.hnue.edu.vn/users/new/index.php?option=com_content&task=view&id=197&Itemid=82

    Reply
  30. Ngô Quang Hưng
    Posted 10/04/2009 at 1:16 pm | Permalink

    Chào anh Hà, “các hệ thống thông tin và tri thức” dịch tiếng Anh là gì?

    Reply
1 … 5 6 7 8 9 … 15

Post a Comment

Your email is never published nor shared. Required fields are marked *

*
*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>