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 post 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ủa blog 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ó implication sâu hơn thì ta chuyển thành một bài mới.

361 Comments

  1. Thắng.
    Posted 02/08/2010 at 12:51 pm | Permalink

    PS: Ở trên viết nhầm, sửa “determined” –> “deterministic”

    7. Người ta nghĩ về máy Turing nhưng lại ngồi gõ bàn phím máy Intel. Liệu trong lịch sử “Theory of computation” có bài báo nào chứng minh: “Máy Turing quả thật có thể mô phỏng hoạt động của máy Intel (giả sử với bộ vi xử lý sơ khai nhất của hãng) mà số bước mô phỏng chỉ bị chậm đi với hệ nhân O(n^k).” Chiều ngược lại thì đơn giản. Điều này được gọi là máy Turing và máy Intel tương đương đa thức với nhau về khả năng tính toán hiệu quả (độ phức tạp thuật toán).

    Reply
  2. Nguyễn Văn Huân
    Posted 04/08/2010 at 6:50 am | Permalink

    Anh Hưng! Chắc anh Hưng và mọi người không lạ lùng gì với bài toán cân đồng xu! Bữa trước học môn Toán rời rạc, em nhớ là có một định lý đưa ra số lần cân tối thiểu để xác định đồng xu giả! Nhưng mà chỉ dừng lại ở việc đếm số lần cân thôi! Em muốn hỏi anh Hưng liệu có phương pháp giải tổng quát nào cho bài toán này không, em nghĩ tới việc viết một thuật toán cho máy chạy nhưng mà giải thuật này có vẻ em chưa thể hiện được!
    Dưới đây là một bài toán riêng và cách giải của em:
    ” Bài toán: Có 12 đồng xu, trong đó có một đồng giả khác trọng lượng so với đồng thật, bằng 3 lần cân hãy tìm ra đồng xu giả.
    Lời giải:
    Chia các xu thành 3 phần bằng nhau và đặt 2 phần lên cân, trường hợp cân thăng bằng xử lý đơn giản.

    Trường hợp cân bị lệch, 4 xu bên ngoài là các xu thật, ta tiến hành hoán đổi các đồng xu như sau trước khi cân lần thứ 2:

    (Gọi 1,2,3,4 là nhóm các xu thật, ABCD là các xu bên nặng cân, abcd là các xu bên nhẹ hơn)

    Lấy 3 xu ABC bỏ ra ngoài,
    Lấy 3 xu abc chuyển sang thế chỗ ABC
    Lấy 3 xu 1,2,3 chuyển vào thế chỗ abc
    Sau đó cân lần thứ 2.

    Có 3 trường hợp xảy ra,

    Nếu cân thăng bằng, như vậy đồng xu giả đã được chuyển ra ngoài và xu giả nặng hơn xu thật, nó là 1 trong 3 xu ABC
    Nếu cân bị lệch ngược lại so với lần 1, như vậy xu giả được chuyển từ đĩa này sang đĩa khác, nó là 1 trong 3 xu abc, xu giả nhẹ hơn xu thật
    Nếu cân bị lệch theo hướng ban đầu, như vậy xu giả còn nguyên vị trí trên đĩa cân, và nó là 1 trong 2 xu D hoặc d

    Sau bước này, việc tìm đồng xu giả không còn là vấn đề nữa!”

    Vấn đề của em là trong giải thuật, mình thể hiện lập luận trong lần cân thứ 2 như thế nào (kể cả bước hoán đổi các đồng xu)?

    Em đang là sinh viên năm thứ 3 trường Đại học Khoa học Huế!

    Reply
  3. newwave2k
    Posted 12/08/2010 at 4:05 pm | Permalink

    Chào anh Hưng, em thấy link này hay hay, gửi anh: http://projecteuler.net/

    Trích từ phần giới thiệu:

    What is Project Euler?

    Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

    The motivation for starting Project Euler, and its continuation, is to provide a platform for the inquiring mind to delve into unfamiliar areas and learn new concepts in a fun and recreational context.

    Reply
  4. Ngô Quang Hưng
    Posted 13/08/2010 at 3:40 am | Permalink

    Cool! Cảm ơn Newwave2k.

    Reply
  5. Nguyễn Văn Huân
    Posted 24/08/2010 at 3:28 am | Permalink

    Gửi anh Hưng!
    Em muốn viết một bài viết để khuyên các bạn đang có dự định theo học lĩnh vực Khoa học máy tính hay Công nghệ Thông tin nói chung “từ bỏ” cái ý định đó đi, nếu đã là sinh viên thì cũng chuyển sang ngành khác mà học khi còn chưa quá muôn nếu không có đam mê, hứng thú thực sự!
    Cách đây 3 năm, khoa CNTT trường em – Đại học Khoa học Huế – lấy 300 chỉ tiêu, một nửa lấy từ nguyện vọng 2. Từ 2 năm trước, số lượng chỉ tiêu hạ xuống còn 200 và với 200 đó thì cũng khoảng một nửa là lấy từ nguyện vọng 2. Năm nay, khoa chỉ mới tuyển được chưa đến 75 người ( số lượng thí sinh từ điểm chuẩn trở lên là 75 và chưa biết bao nhiêu trong số đó không nhập học).
    Những khóa trước em thì em chưa thấy rõ lắm nhưng từ khóa em trở đi, mỗi khóa chỉ khoảng vài ba chục người là có thể làm được việc dính dáng đến lập trình! Em không biết là với khả năng đó sau khi ra trường, các bạn sẽ làm được gì với tấm bằng “cử nhân tin học”. Nhiều đứa năm một năm hai thấy học mấy môn lập trình khó khó, cũng cố tự nhủ là vài bữa học thêm quản trị mạng rồi xin làm chỗ nào đó, nhưng đến khi học môn mạng máy tính, thì đa phần đều thấy con đường “quản trị mạng” cũng tắt dần! Đến lúc này thì bỏ đi đâu nữa, cuối năm ba rồi!
    Trong suốt ba năm học, trừ học kì đầu tiên toàn những môn toán lý hóa, thì học kì nào cũng phải chống chọi một cách đau khổ với mấy môn chuyên ngành, nào là Pasca(giờ bỏ rồi), nào là C, Assembly, cấu trúc dữ liệu, giải thuật ,…. Gần như rất ít bạn đi học mà có cảm giác “đã”! Dù là giảng viên của khoa CNTT đa phần đều là những người truyền đạt tốt, rất nhiệt tình với sinh viên!
    Em nhận ra rằng, điều kiện cần để theo nghiệp “Tin” là phải có sự đam mê! Đặc biệt khi đi làm, nhiều ngành khác có lẽ không đam mê vẫn có thể làm được việc, riêng anh Tin học, mấy chục năm đi làm mà cứ ngắc nghẻo thì thiệt quá khổ!
    Nhưng mà, với cái “kinh nghiệm” còn chưa được hình thành của em thì em chẳng biết phải nói thế nào để mọi người hiểu! Đặc biệt là hiểu rồi đi tìm một con đường khác thích hợp hơn, đúng đắn hơn với mình! Nếu có thời gian, mong anh Hưng bỏ chút thì giờ tâm sự về con đường Khoa học máy tính và đưa ra vài lời khuyên cho những ai có ý định và những ai sắp bước chân vào “Tin học”!
    Cảm ơn anh đã lắng nghe chút “rối” trong lòng em!

    Reply
  6. xiuaj
    Posted 26/08/2010 at 3:24 am | Permalink

    @Nguyễn Văn Huân: tôi thì tôi lại thấy chán cái chương trình KHMT của việt nam, nhạt thếch và không có gì để học toàn là lập trình là lập trình.

    Reply
  7. v.hoat
    Posted 04/09/2010 at 4:31 am | Permalink

    e vua` moj’ nhap truong` cnHN. e kug dang ky’ hoc khoa hoc may’ tinh’
    e ko hieu do’ la` caj’ j` va` e dang rat’ hoang mang ve` nhung j` a Huân noj’
    nhung e ko thể va` kug ko muô’n rút lui
    các a chỉ dùm e phương pháp với

    Reply
  8. Nguyễn Văn Huân
    Posted 04/09/2010 at 10:30 pm | Permalink

    Ở Việt Nam, kết quả xổ số phổ biến có 18 dãy số(độ dài 2 đến 6) chia cho 8 giải (không tính giải khuyến khích) . Một người mua xổ số lấy 2 chữ số cuối của mỗi dãy số và thống kê trong kết quả của 100 ngày gần nhất( 100*18 = 1800 mẫu). Sau đó, cô ta đi mua xổ số lô tô (vé chỉ có 2 chữ số và dò trong 2 chữ số cuối của 18 dãy kết quả, vé 2000 thì trúng được 6000) lấy 2 số có tần suất xuất hiện cao nhất và thấp nhất. Giả sử giải thưởng là 1 ăn 100/18 và cô ta không may mắn cũng không xui xẻo, như vậy thì cô ấy có phải là một “cô bờm” không!
    Smile!

    Reply
  9. Vũ Trường Lâm
    Posted 09/09/2010 at 12:15 am | Permalink

    Chào anh Hưng,

    Em không biết anh có đi sâu về khai phá dữ liệu và các mô hình mạng neural như SVM, LVQ, ELM ? Chắc là có, em cứ giả định thế. Dù em thấy anh có vẻ thích ông Markov và chuyên sâu về xác suất thống kê hơn. Giả định là điều giả định của em là đúng, một ngày đẹp trời anh làm một bài về các mô hình mạng neural được không ? Nhất là về ELM đang nổi lên như một hiện tượng hot về tốc độ, và các vấn đề mà ELM đang phải giải quyết

    Reply
    • Ngô Quang Hưng
      Posted 09/09/2010 at 11:29 am | Permalink

      Chào Vũ Trường Lâm, tôi sẽ có một bài về SVM. Mấy cái khác thì bạn nhờ bác Xuân Long nhé.

      Reply
  10. zeroman89
    Posted 09/09/2010 at 9:02 am | Permalink

    Anh Hưng ơi,
    Em đang gặp phải 1 bài toán về ma trận, anh xem mô tả bài toán trong link này nhé:
    http://acm.pku.edu.cn/JudgeOnline/problem?id=3529
    Anh giúp em ý tưởng giải quyết với.
    Em cám ơn anh !

    Reply
    • Ngô Quang Hưng
      Posted 09/09/2010 at 11:28 am | Permalink

      Chào zeroman89, tôi chưa nghĩ kỹ lắm. Bài toán thú vị. Nếu là tôi thì đầu tiên thôi sẽ thử viết lại định nghĩa của b^k_{ij} xem có cách nào biển diễn nó trực tiếp hơn là một định nghĩa đệ qui như vậy không. Ví dụ, thử 2 entries đầu tiên thì thấy b^k_{11} = b_{11}, và b^k_{12} = (k-1)a_{11}b_{11}+b_{12}, vân vân. Sau đó, tôi sẽ nghĩ về một thứ tự để xem bộ ba (i_t,j_t,k_t) nào đên được định trị trước, tại vì — cho dù đã viết lại công thức — vẫn có thể có thành tố đệ qui ở trong đó; và vì thế một entry (i_t,j_t,k_t) này sẽ phụ thuộc vào entry (i'_t,j'_t,k'_t) khác.

      Reply
  11. zeroman89
    Posted 09/09/2010 at 9:05 am | Permalink

    Dữ liệu bài toán khá lớn, anh xem có cách nào giải quyết được không ?
    Em cám ơn !

    Reply
  12. XuanLong Nguyen
    Posted 09/09/2010 at 11:43 am | Permalink

    Tôi cũng biết đôi chút về SVM, nhưng LVQ và ELM là gì vậy?

    Reply
  13. XuanLong Nguyen
    Posted 10/09/2010 at 8:22 am | Permalink

    Cảm ơn Nguyên. Dạo này có gì mới không?
    OK, vector quantization (kiểu như SOM hay MDS) thì mình biết, nhưng ELM thì vẫn chịu.

    Theo toi VQ nên hiểu rộng hơn thay vì bó hẹp trong phạm vi mạng neural.

    Reply
1 ... 16 17 18

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>