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.

350 Comments

  1. someStudent
    Posted 26/01/2008 at 2:25 am | Permalink

    Chào anh Hưng và các anh chị khác.
    Em mới đang học CTDL & GT, có suy nghĩ sau không biết đúng hay sai, mong anh bình luận hộ:

    1) Đã khử đệ quy thì phải dùng stack. Nếu việc viết lại một thuật toán đệ quy dưới dạng không dùng đệ quy mà không dùng stack thì đó không phải là công việc “khử đệ quy” (đó chỉ đơn giản là viết lại thuật toán)
    Xét ví dụ tìm UCLN của 2 số dương a, b

    // dạng (1): đệ quy
int UCLN(unsigned a, unsigned b)
{
	unsigned 	big, little;
	if (a == b) return b;
	else
	{
		big = max (a, b);
		little = min (a, b);
		return UCLN (big – little, little);
	}
}

// dạng (2): không đệ quy
int UCLN(unsigned a, unsigned b)
{
	unsigned 	big, little;
	while ( a != b)
	{
		big = max (a, b);
		little = min (a, b);
		a  = big – little;
		b = little;
	}
	return little;
}

    Dạng (2) không phải là khử đệ quy của dạng (1); Nếu khử đệ quy cho (1) thì phải dùng stack nhưng như vậy trong trường hợp này là rườm rà và không tỏ ra hiệu quả.

    2) Việc khử đệ quy có thể làm thuật toán tối ưu hơn nhưng không thể làm độ phức tạp của thuật toán đệ quy giảm hẳn xuống được. Chẳng hạn nếu số thao tác cho thuật toán đệ quy là 3n^2 + 5n + 1 thì khi khử đệ quy đi số thao tác của thuật toán có thể giảm xuống 1/2 n^2 chứ không thể giảm xuống còn O(n) hay O(nlogn).

    3) Các vòng lặp while, for luôn được Compiler chuyển thành lệnh go to dưới dạng mã máy. Hiển nhiên đoạn mã sau:
    for (int i = 0, i < 2; i++)
    dosmth (i);
    sẽ không bao giờ được dịch ra dạng mã máy dưới dạng
    dosmth (0); dosmth(1); dosmth(2);

    Reply
  2. little_cat
    Posted 26/01/2008 at 5:47 am | Permalink

    Mình nghĩ cái 3) dùng tùy chọn tối ưu tốc độ sẽ dịch được như thế.

    Reply
  3. tdh
    Posted 14/02/2008 at 4:40 am | Permalink

    Hi anh Hưng,
    Em có một câu hỏi, mong anh giải đáp. Có thể em hiểu lý thuyết xác suất không kỹ. Em muốn hỏi là: Nếu cho tập hợp các số tự nhiên N. Thì xác suất chọn một số tự nhiên n nào đó là bao nhiêu và/hoặc tính thế nào?

    Reply
  4. Ngô Quang Hưng
    Posted 14/02/2008 at 7:12 am | Permalink

    Hi TDH,

    Tùy theo ta định nghĩa cái distribution thế nào. Không tồn tại distribution trên tập các số tự nhiên mà xác xuất chọn mỗi số như nhau (there’s no uniform distribution on N). Còn nếu không phải uniform thì, again, tùy distribution. Ví dụ: nếu sample space là {1,2,3,…} thì có thể định nghĩa distribution bằng cách gán 1/2^n thành probability cho n.

    Nếu TDH mới bắt đầu học prob theory thì tôi nghĩ không nên nghĩ về các discrete infinite probability spaces vội. Hiểu các khái niệm trong các finite spaces trước. Nếu thật sự muốn hiểu thêm về các infinite space thì tìm các continuous spaces trước để phát triển trực quan của mình về chúng. Sau đó đọc thêm measure theory và quay lại với infinite & discrete spaces.

    Reply
  5. CNB
    Posted 15/02/2008 at 2:05 am | Permalink

    Xin chào ! Em đang làm 1 đề án TN về Web Semantic-Ontology và xây dựng một ứng dụng minh họa, các anh chị có tài liệu hay ứng dụng nào cho em xin với ! Xin cám ơn !

    Reply
  6. HaThuyAnh
    Posted 18/02/2008 at 11:20 pm | Permalink

    Gửi anh Hưng
    Tôi vừa gửi một bài viết cua tôi vào email của anh. Kinh mong nhận được review của anh
    HTA

    Reply
  7. little_cat
    Posted 22/02/2008 at 11:32 pm | Permalink

    các thầy cô anh chị ở đây cho em hỏi xíu: ngành CS bậc đại học thì nên học toán gì ạ (có thứ tự học thì càng tốt), vì em thấy nhiều nhánh hay quá (em đang đọc về lambda calculus). Cảm ơn mọi người nhiều.

    Reply
  8. THT
    Posted 28/02/2008 at 7:19 pm | Permalink

    Chào anh Hưng,
    Anh cho em hỏi sinh viên mới năm thứ I, II thì nên đọc sách gì về đại số và giải tích ??
    Cám ơn anh, chúc anh mạnh khỏe.

    Reply
  9. Thang
    Posted 29/02/2008 at 11:23 am | Permalink

    Chào anh Hưng và các anh chị khác.
    I.
    Em là undergrad, đang học về số phức, các sách đều định nghĩa cặp số (a,b) cùng với phép cộng, nhân tạo thành một trường, sau cái định nghĩa trường số phức thật formal thì tác giả mới chuyển sang viết ở dạng đại số a + bi.
    Tuy nhiên em thấy vẫn nhiều tài liệu em cho là KHÔNG CHUẨN, cụ thể tính đến ngày 1 March 08 (em phải ghi thế này vì có thể lúc mọi người đọc, họ sửa khác đi)
    - Wolfram Mathworl vẫn để chềnh ềnh căn -1 :
    “The complex numbers are the field of numbers of the form a+bi, where x and y are real numbers and i is the IMAGINARY unit equal to the square root of -1″ tại dhttp://mathworld.wolfram.com/ComplexNumber.html
    - Eng Wiki http://en.wikipedia.org/wiki/Complex_number thì trình bày luôn dạng đại số với qui ước i2 = -1 trước khi trình bày tiên đề. Rất khó hiểu cho người mới học về cái số bình phương bằng -1 (mà không phải là (-1,0) ).
    - rất nhiều trang web, ebooks (kể cả sách về giải tích phức) định nghĩa số phức qua căn -1 hoặc ra qui ước i2 = -1 …
    Em định comment cho họ nhưng kiến thức + tiếng Anh không thật vững muốn nhờ anh giúp, tiện thể anh xem qua luôn Vietnamese wiki về số phức.

    II.
    Em thấy nhiều lúc (ví dụ trong phương trình sóng) khi gặp sinx (x thực) thì người ta thay bằng hai cái e mũ phức trừ đi nhau (suy ra từ công thưc Euler) tức là chuyển từ không gian thực sang phức để tính toán cho nhanh (chẳng hạn lợi dụng tính chất hàm mũ). Nhưng không lẽ số phức chỉ là cái mẹo tính toán thôi không liên quan gì đến physical reality ?. Có cái gì rất reality ẩn sau cặp số (a,b) thuộc trường C thế ?.
    Mong các anh chị trả lời giúp. Em cám ơn.

    Reply
  10. ANM
    Posted 01/03/2008 at 8:19 am | Permalink

    Chào các anh chị,
    Em gặp cụm từ: “finding square roots modulo a prime” em không biết dịch như thế nào nên cũng chẳng hiểu đó là bài toán gì. Chỉ thấy loáng thoáng sách nói bài toán này được giải một cách không efficient ???. Anh chị nào nói giúp em với nghĩa tiếng Việt của nó.

    Reply
  11. Thắng
    Posted 01/03/2008 at 4:41 pm | Permalink

    @ANM: “finding square roots modulo a prime” – tính căn bậc 2 modulo một số nguyên tố, là bài toán tìm nghiệm nguyên cho phương trình đồng dư
    x^2 \equiv a(mod p) trong đó p là số nguyên tố và a không chia hết cho p.

    Reply
  12. ANM
    Posted 01/03/2008 at 8:48 pm | Permalink

    Chào các anh chị,

    1. Từ trước đến giờ em vẫn thấy trong sách nói về công thức Newton-Lebniz:
    ” nếu f: [a,b] -> R và f liên tục trên [a,b], có một nguyên hàm là g(x) thì tích phân xác định của f với cận a,b là g(b) – g(a) ”
    Tuy nhiên em đọc được một chú ý rất chi là subtle về định lí trên tại trang:
    http://blog.wolfram.com/2008/01/mathematica_and_the_fundamental_theorem_of_calculus.html#more
    Nếu theo cái link này thì để tích phân xác định bằng g(b) – g(a) phải có thêm điều kiện là g(x) liên tục, nhưng em tra một số sách và eng wiki thì đều không thấy nói đến mà cái ví dụ ở link trên lại rất đúng. Không lẽ sách sai.

    2. Không ai có ý kiến gì về bài post số phức của Thang ở trên ?

    3. @ Thắng: cám ơn anh, em đã hiểu. Có phải hiện nay bài toán này không có thuật toán thời gian đa thức đúng không anh.

    Reply
  13. little_cat
    Posted 02/03/2008 at 4:41 am | Permalink

    I have a course using the book Logic in Computer Science: Modelling and Reasoning about Systems (Michael Huth), and there is a review about it saying that
    “This peculiarity of the order of exposition, partly repeated in Chapter 2, is in my view the most controversial feature of the book, as it can create in the reader with little or no prior experience in logic (to whom the book is clearly addressed) the wrong impression that logical semantics is mainly used to give meaning to deductive systems, rather than that deductive systems are designed in order to capture logical validity and consequence” and
    “Further in Chapter 1 the authors explain and prove the soundness and completeness of the earlier introduced system of natural deduction (not of the propositional logic itself, as the subsection titles suggest)”.
    Unfortunately, I don’t understand this review :( , so I hope someone will help me explain it more clearly :) .

    By the way, could you please suggest some good books for my “Logic in Computer Science” course? Thanks very much for your help :) .

    Reply
  14. little_cat
    Posted 03/03/2008 at 1:15 pm | Permalink

    @ANM. Theo mình nghĩ thì nếu g(x) có đạo hàm là f(x) thì nó phải liên tục rồi.

    Reply
  15. pdt
    Posted 03/03/2008 at 1:33 pm | Permalink

    @Thang :tôi ko hiểu lắm.có lẽ là do tiếng Anh của bạn. vỉ theo hiểu biết của tôi thì “căn bậc 2 của 1 số x là a sao cho a^2=x@
    trong TH này ta goi i là căn bậc 2 cơ bản của -1.ok?
    thật nực cười nếu cho rằng số phức là cái mẹo của số thực. vậy chắc số thực cũng là mẹo của số nguyên.

    @ ANM : cái đó hồi tôi học chuyên toán ng` ta gọi là thặng dư chính phương. thay 2 – k gọi là thặng dư k-phương. Bạn tìm hiểu nó thì có thể xem http://en.wikipedia.org/wiki/Quadratic_residue
    cái thứ 2: bạn biết tại sao ng` ta ko nhét vào 0? tại vì khả vi–> liện tục. hãy chú ý: Let f be a continuous real-valued function defined on a closed interval [a, b]. Let F be the function defined, for all x in [a, b], …( F ko well-defined ok ?) nếu nó mà well-defined+khả tích->liên tục ngon.

    Reply
  16. HaThuyAnh
    Posted 03/03/2008 at 10:06 pm | Permalink

    Các anh cho hỏi chút nhé.
    Tôi có đứa cháu đang theo học high school ở bang Missouri.
    Vừa rồi cháu đó xin được một khoản tiền học gì đó của Trường Central methodist university cũng ở bang missouri và có ý định sẽ vào học ở đó.
    Ở VN không có thông tin gì về trường đó nên bố mẹ cháu rất lo lắng.
    Mong các anh tư vấn giúp với.
    Cám ơn nhiều
    HTA

    Reply
  17. kamellia
    Posted 05/03/2008 at 10:03 am | Permalink

    Em chào anh Hưng và các anh chị,

    Em tình cờ biết đc blog này trong quá trình lướt web. Sau khi đọc rất nhiều topics trên trang blog, em thực sự cảm thấy rất khâm phục kiến thức của các anh chị. Nhân đây em muốn xin các anh chị tư vấn cho 1 bài toán mà em đang rất bối rối…

    Em đang nghiên cứu về routing trên MANET và Sensor Networks, và có 1 ý tưởng xây dựng một routing algorithm dựa trên Random Walk approach on Random Geometric Graph, with physical location knowledge. Em xin trình bày ý tưởng như sau:

    ————————————————————————-
    1. Assumptions
    – The network is connected
    – All nodes have the same transmission range
    – All nodes know their own geographical locations
    – A source node knows the geographical location of the destination node
    – All nodes know the locations of their 1-hop neighbors

    2. Model a given network scenario as an undirected graph –> we have an associated finite Markov chain to this graph, which is irreducible and ergodic

    3. The probability transition matrix P of this Markov is obtained by assigning
    wij = (2*d(i,des) – d(j,des)) / d(j,des)
    pij = wij / sum(wij | j belongs to 1-hop neighbourhood of i) (normalizing to get probabilites which sum to 1)
    where d(x,y) is the The Euclidean distance between s and d
    (With is way of assigning weights, I beleive that the data packets will move with increasing bias towards the destination, while no need to predefine a path to the destination. That is, different packets move in different paths –> traffic load and energy consumption are distributed over the network)

    4. Given a pair of source and destination (S, D). I do routing by starting the random walk at S, and forward the data packet over series of intermediate nodes with probabilities defined by P.
    ———————————————————-

    Em đã thử simulation 1 scenario với 20 nodes in an area of 1000m * 1000m, transmission radius is 300m (the scenario description is given at the end of this article). Em chọn node0 là source, node12 là sink và route 100 packets. Ket qua nhu sau (out of 100 packets):
    – Average number of hops = 11
    – Minimum number of hops = 6
    – Maximum number of hops = 21

    Shortest path length is indeed 6 –> flooding rate = 11/6 < 2, which is promising in this case (compare to optimal flooding, greedy strategies…).

    Sau khi simulate, em đã sử dụng tính chất của absorbing Markov chains bằng cách đặt node12 (the sink) là absorbing state của chuỗi (i.e., p[12,12] = 1), và bằng cách viết lại P dưới dạng Canonical form, em đã tính được: The expected number of steps(hops), for the chain to be at node12, if the chain starts at node0, is 11,7. Kết quả này cho thấy simulation và mathematical computing results are somewhat harmonic (11hops compared to 11,7hops).

    —————————————————————————————
    Tuy nhiên có một số vấn đề mà em cảm thấy không an tâm về mô hình này:

    1. Kiến thức của em về Markov theory hiện vẫn rất hạn chế, ngoài việc áp dụng Absorbing Markov chain cho ý tưởng của mình, những kiến thức khác như mixing time, hitting time, cover time,… để xây dựng một mathematical framwork cho mô hình của em, thì em vẫn chưa được rõ ràng. Hiện nay em đang tìm đọc sách về đề tài này, có 1 quyển nhan đề là: “Finite Markov Chains” By John G. Kemeny, James Laurie Snell, đề cập khá gần tới công việc em đang làm (theo ý kiến chủ quan của em). Tuy nhiên em ko download được nó hoặc tìm đc trong thư viện của chỗ em học. Nếu các anh chị có biết link download nó, và recommend thêm các sách khác giúp em thì tốt quá…

    2. Em đã tiếp tục thử mô hình này trên nhiều scenarios khác nhau với different network sizes and densities, results show that (from both simulation and matrix operation), the average expected number of hops for routing a packet varies dramatically with network size and density. So, how or is there a mathematical method to derive an upper bound for the average expected number of hops (with respect to network size and density)? Does the algorithm scale?

    3. Em cũng quan tâm tới how to investigate the load and energy consumption distribution over the network during routing of packets, with this routing algorithm. Is there a clue to build a mathematical framework, which tells us that, with this policy of defining the probability transition matrix P, the random walk will give a good balancing in the netowork, while keeping acceptable small average number of hops?
    ——————————————————————————-

    Những câu hỏi trên đây sẽ giúp em tìm kiếm một phương pháp toán học để đánh giá tính hiệu quả hoạt động của ý tưởng này và so sánh nó với các thuật toán routing cổ điển khác trên MANET…

    Em xin cảm ơn các anh chị đã bỏ thời gian đọc bài của em và cho lời khuyên cũng như gợi ý…

    Kamellia@

    ps: Dưới đây là scenario mà em đề cập ở trên:
    20 (number of node)
    300 (transmission radius)
    90 100 (tọa độ X,Y của node 0) (source node)
    280 110 (tọa độ X,Y của node 1)
    170 250 (…)
    530 130
    715 175
    780 90
    895 135
    785 265
    655 365
    898 395
    878 610
    745 680
    885 870 (tọa độ X,Y của node 12) (destination node)
    625 895
    505 678
    375 875
    312 570
    125 570
    180 815
    375 415

    Reply
  18. sinhvienbeo
    Posted 06/03/2008 at 4:00 am | Permalink

    Chào chú Hưng và các cô chú,
    Cháu đang định đi theo con đường Programming Language, Software Verification và Program Analysis mà đụng vô thấy background khủng hoảng quá, không biết bắt đầu từ đâu @_@.
    Cô chú gợi ý cho cháu những quyển sách must-read cho undergraduate student được không ạ.
    Cảm ơn cô chú.

    Reply
  19. little_cat
    Posted 06/03/2008 at 7:33 pm | Permalink

    @svbeo: bạn xem ở đây trước thử

    Reply
  20. GopYVeBlog
    Posted 07/03/2008 at 1:45 am | Permalink

    Chào anh Hưng, em thấy có một vài chỗ không thật thuận tiện lắm trong blog của anh:
    - KHông có chỗ xem lại trước khi “Gửi lời bình”
    - Phần bài post chỉ chiếm chưa hết chiều dài màn hình trong khi đó cột “Bài gần đây” … thì lại tụt hẳn xuống, thừa hẳn một khoảng trống ở góc phải.
    - Gỡ rối tơ lòng dài quá rồi, phân trang đi anh ơi.
    Lúc nào rảnh anh sửa nhé. Chúc anh vui vẻ.

    Reply
1 ... 5 6 7 8 9 ... 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>