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.

526 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
  21. sinhvienbeo
    Posted 07/03/2008 at 3:32 am | Permalink

    @little_cat: cảm ơn bạn little_cat ,mình đã có đọc rất kỹ bài viết ấy và note lại tất cả các sách, để trong tương lai rảnh rỗi sẽ phải lai rai dần. Mình thấy programming language involves rất nhiều ngành khác trong đó: data mining, machine learning, network, logic … @_@ nên chắc sẽ phải tu luyện tuốt để có basic background, không biết có đúng không :@). Còn về bác programming language, nội cái local background của bác mình cũng thấy huge lắm rồi, nhiều nhánh nữa(practice or theory, function, logic or object-oriented, design, implementation or verification, xx or yy and ???) nên mình không biết nên học theo thứ tự nào cho tốt nhất, và trong mỗi thứ tự đó thì nên đọc sách gì là tốt nhất.

    Reply
  22. xuantung1010
    Posted 11/03/2008 at 9:59 am | Permalink

    Em có đọc một số bài trên blog và cũng có thắc mắc từ lâu muốn hỏi các anh chị bloggers. Nó thì đơn giản thế này thôi:

    Có lần em được đọc trong một cuốn sách là nếu không dự đoán được các bit tiếp theo của dữ liệu thì lượng thông tin càng lớn. Vậy thì nếu có một dãy bit ngẫu nhiên thì hóa ra là nó có nhiều thông tin nhất hay sao? Trong khi đó em nghĩ là nếu vậy thì chẳng có thông tin gì cả vì nó là ngẫu nhiên.

    Reply
  23. Nguyễn Xuân Long
    Posted 11/03/2008 at 11:26 am | Permalink

    Chao xuantung, biến ngẫu nhiên chỉ là cách người ta mô tả uncertainty, nhưng điều này không có nghĩa, ngẫu nhiên nghĩa là chúng ta không biết gì, theo cách hiểu nôm na của những người chưa biết về thuyết xác suất. Người ta thường nói: there is nothing random about a random variable! Chữ random đầu tiên chính là cách hiểu “ngẫu nhiên” nôm na trong cuộc sống thường ngày, còn khái niệm “random variable” là một khái niệm toán học chặt chẽ và có những tính chất rõ ràng.

    Trong lý thuyết xác suất, khi chỉ nói ngẫu nhiên không thôi thì còn mơ hồ; phải hỏi là ngẫu nhiên như thế nào. Khi tung một đồng xu, có thể xác suất head/tail là p=0.5, nhưng cũng có thể là 0.99 hoặc 0.001. Lượng thông tin ở đây chỉ nên hiểu là số lượng bits dùng đề mã hóa chuỗi giá trị (realized values) của một biến ngẫu nhiên. Nếu p=0.999 thì rõ ràng chỉ cần rất ít bits (vì ta biết gần như chắc chắn giá trị của chuỗi rồi) nhưng nếu p=0.5 thì phải cần nhiều bits hơn. Bạn nên tìm hiểu khái niệm entropy của Shannon và các cách interpretation khác nhau của nó trong các hoàn cảnh (như coding, estimation, v.v). Các bạn học undergrad hoàn toàn có đủ background để tìm nhiểu về những khái niệm này.

    Reply
  24. tmtam
    Posted 12/03/2008 at 6:19 pm | Permalink

    Xin chào GS Hưng và các anh chị,
    Em đang tìm hiểu về Directed Minimum Spanning Tree (cái này thuộc về Graph Theory và Combinatorial Optimization thì phải), em muốn down 1 số tài liệu về tham khảo nhưng chỉ tìm thấy trên trang Wiley Interscience do tuổi thọ của chúng cũng “khá lâu”. Những tài liệu đó là:
    - R.E. Tarjan “Finding Optimum Branchings” (1977)
    - Edmonds “Optimum Branchings” (1967)
    - Camerini “A note on finding optimum branchings” (1979)
    Anh chị nào có thể gửi giúp em những tài liệu này được không (qua e-mail minhtam146 at yahoo.com)? Em rất cám ơn! Em đã search trên blog nhưng không thấy topic nào nói về thuật toán này.
    Trần Minh Tâm

    Reply
  25. HT
    Posted 17/03/2008 at 6:24 am | Permalink

    Chào các anh chị blogger.
    Em có một vài suy nghĩ về Formal/Natural language, Automata, TM nhưng không thật rõ ràng. Mong các anh chị chỉnh sửa để em có cách hiểu đúng.

    1. Theo từ điển Merriam – Webster thì từ “grammar”, từ “predicate”, từ “noun”, “verb” … có từ thế kỉ 14, 15 tức là từ rất xa xưa người ta đã biết phân loại được các từ trong ngôn ngữ tự nhiên thành từ loại động từ, danh từ, … và cũng thấy được cấu trúc: câu được tạo bởi Chủ ngữ – vị ngữ, vị ngữ được tạo bởi động từ và danh từ hoặc trạng từ … Như vậy đóng góp (quan trọng nhưng lại mới cách đây chỉ khoảng nửa thế kỉ) của Noam Chomsky chỉ là ở mỗi việc formalize lại cái ý tưởng phân loại từ vựng cũng như cấu tạo câu (vốn đã có từ xa xưa) thành Generative grammar ?!!. Nếu không phải như vậy thì liệu đóng góp quan trọng nhất của Noam Chomsky có phải là ở chỗ ông phân loại văn phạm thành 3 mức: văn phạm tuyến tính (chính quy), văn phạm phi ngữ cảnh (CFG), cảm ngữ cảnh (CSG) và chỉ ra văn phạm CFG là “khá đủ” để mô tả ngôn ngữ tự nhiên. Chomsky là nhà ngôn ngữ học (vậy chắc ông cũng không quan tâm đến “computation” làm gì cả) nhưng generative grammar cho ngôn ngữ tự nhiên của ông làm không ngờ sau đó lại trở thành tối quan trọng cho ngôn ngữ hình thức và nhất là trong Compiler.
    (Sở dĩ em có câu hỏi này là do không download được (bị đòi purchase) bài báo gốc của Chomsky để đọc)

    2. Động lực chủ yếu để ra đời Regular Expression là từ việc nghiên cứu cách mô tả ngôn ngữ lập trình để những người làm chương trình dịch dễ làm ? Cũng vậy, trong quá trình nghiên cứu mô tả ngông ngữ lập trình người ta phát minh ra Backus Normal Form mà sau đó lại thấy nó chính là Context Free Grammar. Vậy nếu không để ý đến chi tiết thời gian ra đời các khái niệm thì có thể cho rằng Context Free Grammar được ra đời và phát triển là từ nghiên cứu mô tả ngôn ngữ tự nhiên và ngôn ngữ lập trình. Tương tự như vậy (non)Deterministic Finite Automata (FA) hay Pushdown Automata (PA) ra đời cũng chỉ do nghiên cứu mô tả ngôn ngữ hình thức mà không xuất phát từ nhu cầu nào khác ?

    3. Về mặt thời gian lịch sử thì Turing machine ra đời sớm nhất (trước khi có máy tính) còn FA, PA ra đời sau khi có ngôn ngữ lập trình. Cách định nghĩa Turing machine và PA khá gần nhau. Vậy liệu có phải PA (và có thể cả FA nữa) là do đơn giản hóa Turing machine (để có được những abstract machine phù hợp với nghiên cứu mô tả ngôn ngữ lập trình hay là PA, FA được phát minh độc lập không dựa vào Turing machine.

    Xin cám ơn các anh, chị. Chúc anh chị mạnh khỏe, vui vẻ.

    Reply
  26. aldsvn
    Posted 18/03/2008 at 11:04 pm | Permalink

    cho em hỏi Procul có nghĩa là gì thế ạ ?

    Reply
  27. Svnam1
    Posted 30/03/2008 at 5:37 am | Permalink

    Chào các anh chị blogger.
    Em đang học đại số tuyến tính, có khúc mắc sau mong các anh chị giải đáp giúp. Khi học về toán tử chiếu (toán tử P mà P^2 = P) và direct sum em thấy các tính chất rất dễ hiểu khi nhìn toán tử chiếu là sự trừu tượng hóa của khái niệm chiếu trên không gian R^3 quen thuộc. Tuy nhiên khi sang khái niệm adjoint of operator, self adjoint operator, unitary operator em không tìm được khái niệm nào tương ứng trong R^3 nên toàn phải “nhớ” công thức và có cảm giác đây là những khái niệm từ trên trời rơi xuống, không hề tự nhiên như là toán tử chiếu kia. Vậy anh chị nào giúp em hình dung trực quan được 3 khái niệm trên không ?
    Thêm nữa, có phải tất cả các khái niệm trên không gian tuyến tính đều là sự trừu tượng hóa các khái niệm trong không gian R^3 quen thuộc ?
    Em xin cám ơn.

    Reply
  28. HaThuyAnh
    Posted 02/04/2008 at 6:29 pm | Permalink

    Chac anh Hung quen vu sua bai viet cua toi roi
    HTA

    Reply
  29. Tam
    Posted 07/04/2008 at 11:01 am | Permalink

    Chào GS Hưng và các bạn!

    Hiện nay mình đang là sinh viên năm thứ 3 nghành toán học, ở Vịệt Nam. Mình đang muốn theo nghành Computer Science. Cụ thể là mình muốn học Master về CS nhưng khó một điều là những trường mình tìm hiểu qua đều yêu cầu sinh viên tốt nghiệp khoa CNTT hoặc nghành gần nó như Đện tử viễn thông hay toán tin. Mình đang rất băn khoăn, vậy chẳng lẽ để học Master về CS mình sẽ phải học thêm một bằng đại học nữa về tin học ? Hay có trường nào nhận thẳng mình vào học Master ?
    Xin cám ơn vì đã đọc câu hỏi của mình.

    Reply
  30. Đức Anh
    Posted 09/04/2008 at 10:13 pm | Permalink

    Chào anh,
    Tình cờ lướt net tôi đọc được blog của anh. Tôi thấy rất thú vị và quan tâm tới những vấn đề trình bày. Tôi cũng có một số vấn đề, hy vọng được các anh/chị và các bạn “gỡ rối tơ lòng” hộ cho.
    Tôi đang tìm hiểu về Semantic web và chuẩn bị làm PhD về cái này. Có rất nhiều vấn đề chưa được giải quyết cũng như cần phải bàn trong S W, trong đó tôi thực sự chưa rõ về S W modeling. Conceptual modeling trong S W gồm những gì? Mong anh chỉ giáo. Cám ơn anh!

    Reply
1 … 3 4 5 6 7 … 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>