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.
“15 tháng 01, 2008, vào lúc 5:56 am Ngô Quang Hưng viết:
@Little cat: quyển Operating System Concepts là quyển kinh điển. Hồi còn đi học tôi vẫn học quyển này. Bây giờ ra đến 7th edition rồi. Tuy nhiên, một lớp Operating Systems không thể thiếu thành phần implementation. Quyển của Sylberschatz thiên về lý thuyết. Về implementation projects thì có rất nhiều hướng tiếp cận. Tôi cực thích BSD vì clean codes and designs, vì thế giới thiệu quyển kinh điển The Design and Implementation of the 4.4 BSD Operating System. Đa số mọi người dùng Nachos làm platform thực tập.”
Chào anh Hưng,
Em đang quan tâm chủ đề này, anh có thể chia sẻ cuốn “The Design and Implementation of the 4.4 SD Operating System” và source code 4.4BSD được không? email phuong.xvnkv@gmail.com
Cám ơn anh nhiều nhiều
Anh Quang Hưng có phải là giảng viên của UIT ko vây? Blog của anh thật hay, chắc phải thường xuyên ghé thăm.
Nếu các anh/ chi không cười các hoạt động trong nước như:
“Hội thảo Quốc gia lần thứ XII
MỘT SỐ VẤN ĐỀ CHỌN LỌC CỦA
CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
Chủ đề: Phát hiện tri thức từ dữ liệu
Biên Hòa, 5-6/08/2009
http://www.ioit.ac.vn; http://www.lhu.edu.vn/”
Vậy nếu dùng blog này làm dữ liệu để phát hiện tri thức là hiệu quả nhất
Chào anh Hưng và các bạn đọc của blog khoa học máy tính hiện nay em có một bài toán như sau:
Xây dựng ma trận N:nxn các giá trị, sao cho khi chọn 2 tập hợp n1, n2 bất kì trong đó n1, n2 là tập hợp có n phần tử khác nhau được chọn ra từ các phần tử của ma trận N thì tổng các phẩn tử của tập n1 và n2 phải khác nhau.
Em đang trong giai đoạn tìm hiểu về bài toán này, nếu anh Hưng hay các bạn đọc blog có kiến thức hay kinh nghiệm về bài toán trên thì chỉ dẫn giúp em. Chân thành cám ơn mọi người.
@Tuong Vinh, tôi không thấy liên quan gì đến ma trận, chắc tại không hiểu đề bài. Bạn bỏ vào N các lũy thừa khác nhau của 2 là được.
Chào anh Hưng,
Cái ma trận là em thêm vào để chứa các giá trị và dễ hình dung thôi à. Bài toán của em liên quan đến việc lưu các nước đi của quân cờ trên bàn cờ thôi ạ. Ví dụ trong chương trình cờ tướng chẳng hạn, việc lưu lại các bước đã xét qua để không phải duyệt lại nó trong quá trình xây dựng không gian tìm kiếm mới. Em lấy ví dụ: khi mình xét các nước đi cho một lượt đi ta sẽ sinh ra tập tìm kiếm thứ 1: có các trường hợp như di chuyển quân xe tiến một bước, di chuyển quân chốt lên một bước…, giả sử ta chọn việc lên chốt rồi sao đó ta sinh tiếp tập tìm kiếm thứ 2: các khả năng mới bao gồm có việc di chuyển xe lên một bước,…. Tiếp tục như thế ta lại chọn việc di chuyển xe lên một bước, sau đó khi ta xem xét các trường hợp khác. Quá trình diễn ra tới một thời điểm nhất định sẽ quay trở lại tập tìm kiếm thứ 1, lúc này ta không chọn di chuyển chốt mà chọn di chuyển xe và lập ra tập tìm kiếm thứ n trong đó có việc di chuyển chốt lên một bước. Nếu ta chọn việc di chuyển chốt để xét thì sẽ tốn thời gian xem xét, trong khi ta đã xét qua(do việc lên chốt sau đó lên xe sẽ tương tự việc lên xe rồi lên chốt). Nên để loại bỏ việc duyệt lại này ta tiến hành xây dựng ma trận 8*8 cho từng quân cờ sao cho ứng với từng thế cờ ta có được một giá trị khác nhau(giá trị này được tính bằng cách lấy tổng của các giá trị ứng với các quân cờ trên bàn cờ). Việc lưu trữ giá trị nếu ta sử dụng cách mà anh đưa ra ta cần một biến 64 bit để lưu trữ trong trường hợp bàn cờ 8*8. Nếu như giả thuyết của ta không là bài toán cờ tướng mà một loại cờ khác như cờ vây chẳng hạn, việc ta dùng cách của anh thì biến để lưu giá trị một phần tử của ma trận sẽ rất lớn. Trở lại bài toán ban đầu nếu như số n > 18 thì nếu làm như cách của anh ta sẽ cần một biến lớn hơn 64 bit để có thể lưu một giá trị của một phần tử của ma trận. Vậy không biết chúng ta có cách nào khác để vẫn tạo ra ma trận ban đầu mà số bit cho việc lưu trữ một phần tử của ma trận là không quá lớn mà chỉ khống chế trong 64bit hay 32bit thôi ?
@TuongVinh: câu hỏi rất khó nếu đặt tổng quát như vậy. Gần như tương đương với một bài toán của Erdos:
http://garden.irmacs.sfu.ca/?q=op/sets_with_distinct_subset_sums
Tổng số bits nhỏ nhất cần cho mỗi phần tử bằng tổng số bits cho phần tử lớn nhất, và con số này là một hàm số của n, không thể tốt hơn
nhiều lắm được.
Chào tất cả các anh chị và các bạn
Hiện nay em đang nghiên cứu về bài toán Traveling Salesman Problem cho trường hợp đối xứng (symmetric).
Em muốn nghiên cứu bài toán này trong trường hợp mình đã cố định thời gian chạy (ví dụ 10 phút). Tức là cho dù số lượng thành phố là ít hoặc nhiều hoặc rất nhiều đi chăng nữa thì vẫn phải đưa ra được path (mà xác suất để path này là path ngắn nhất là cao)
Em chia bài toán này ra các trường hợp sau:
Case 1: Nếu số lượng thành phố ít
→Kiểm tra toàn bộ tức là kiểm tra tất cả (n-1)!/2 paths, rồi đưa ra đường đi thích hợp nhất.
Case 2: Nếu số lượng thành phố nhiều
→Không thể kiểm tra toàn bộ. Vì vậy sẽ bằng cách tính toán nào đó sẽ cố gắng để đưa ra path ngắn.
Case 3: Nếu số lượng thành phố quá nhiều
→Có thể sẽ không kết thúc tính toán của Case 2. Vì vậy, cho dù có dừng lại giữa chừng đi nữa thì cũng sẽ cố gắng đưa ra path ngắn.
Hiện tại em đang tìm các thuật toán để áp dụng cho Case 2 và Case 3 nhưng em chưa biết được nhiều.
Vì vậy em mong các anh chị và các bạn có thể chỉ giáo cho em.
Em xin cảm ơn!
Vừa rồi tôi định dùng tiêu chuẩn đánh giá độ ổn định của hệ thống tuyến tính bất biến theo thời gian (Linear Time Invariance) để đánh giá hệ thống biến đổi theo thời gian (dynamic structure) khi thuật toán điều khiển hệ thống này đã hội tụ.
Tôi có nhận được lời khuyên là: Điều kiện để sử dụng như vậy là phải dùng hàm “Làm già” hệ thống dynamic structure để trở thành Linear Time Invariance system.
Vì không có điều kiện để hỏi rõ thêm về hàm làm già, mong anh em, ai có biết thì giải thích giúp tôi
Cac anh cho hoi, lam sao doc duoc tieng viet trong Blog cua anh Ngo Bao Chau. Can cai dat phong chu gi?
Chào anh Hà, tôi vẫn đọc bình thường không cần font đặc biệt gì. Anh thử đổi lại character encoding của browser.
Vang toi se thu lam nhu vay, thanks
Tôi đã thử đổi encode của Internet explorer nhưng chưa đọc đươc blog của anh Châu. Phiền anh Hưng lần nữa xem hộ anh dùng encode gì trong web browser của anh để tôi làm y như vậy cho nhanh
@anh HaThuyAnh: thấy anh không đọc được blog của anh Châu, em tò mò xem thử Page Source thì thấy là trang blog đó dùng charset encoding là UTF-8. Tuy nhiên, khi mở bằng Firefox thì hiển thị ngon lành, còn IE thì chọn encoding kiểu gì cũng thua. Có lẽ anh chịu khó chuyển qua dùng Firefox xem sao
Chào anh Hưng và tất cả mọi người,
Em đang gặp một vấn đề nho nhỏ, nhưng khá thực tế, mà có lẽ nhiều người cũng gặp. Mong các anh chị có kinh nghiệm đi trước chỉ giúp (em đã cố tìm thông tin bằng google nhưng không có kết quả). Vấn đề là: sau khi mình viết xong 1 cái paper và muốn gửi nó đến 1 journal. Thì ngoài việc tìm ra 1 list những journals có hướng phù hợp, thì mình cần phải chọn ra 1 journal cuối cùng để gửi. Tuy nhiên, thời gian review trong CS thường là rất dài. Nhiều journal xịn, vd như VLDB journal hay ACM Transactions in Database Systems, thường mất cả 1 năm review và 1 năm revise, sau đó mới biết kết quả accept hay không. Như thế là quá dài, khi bị reject thì vấn đề đã cũ và có thể có người khác tìm ra 1 cách giải quyết khác hay hơn rồi, con như phí công. Vậy làm sao để biết thời gian trung bình của quá trình review, revise, và accept của các journals trong CS ?
(Biết được thông tin này thì mình có thể chọn 1 journal tốt, vừa tầm, và thời gian review có thể chấp nhận được mà gửi.)
Em xin cảm ơn !
thank Thanh
Bần đạo có việc cần nhờ vả quí vị. Bần đạo có một cái giáo trình soạn bằng tiếng việt từ lâu rồi, hình như ngày xưa dùng vntimes hay vnarial gì đó. Bây giờ hắn lại bon chen đi dùng mac nên chịu chết không đọc lại được nữa. Trình độ có hạn, khốn nạn chùng chùng, hì hục Google cả tiếng đồng hồ mà vẫn không hiểu làm thế nào convert từ vntimes sang unicode trên máy mac. Cái tệp này dùng vntex. Có ai mở lòng từ bi giúp hòa thượng nhé.
Xin lỗi đã làm phiền mọi người nhé. Bần đạo đã tự xử rồi.
Chuc’ mung` anh Hung nam nay lai. co’ them Soda de drink
Cảm ơn Thắng. Chưa đã khát nhưng có còn hơn không.
Anh Hưng cho em hỏi điều này:
- Có phải mọi chu trình có thể có của 1 đồ thị vô hướng phải chứa 1 back edge nào đó qua 1 phép tìm kiếm DFS từ 1 đỉnh bất kỳ?
- Câu hỏi tương tự nhưng hạn chế vào đồ thị có hướng liên thông.
Cám ơn anh nhé.
Hi Azetic,
1. Với đồ thị vô hướng thì chỉ có 2 loại edges: tree edge và back edge. Với một chu trình bất kỳ thì không thể nào mà tất cả các cạnh của chu trình đều là tree edge được (nếu không đã không phải là tree), do đó phải có một back edge.
2. Với đồ thị có hướng thì có đến 4 loại edges. Giả sử cách ta tô màu các đỉnh là trắng, xám, đen. Trắng là đỉnh chưa thăm. Xám là đỉnh đã thăm nhưng chưa khám phá hết con cháu của nó, và đen là đỉnh đã thăm và các con cháu cũng đã thăm xong. 4 loại cạnh bao gồm:
2a. Tree edge: khi ta gặp đỉnh trắng mới
2b. Back edge: từ một đỉnh con/cháu đến đỉnh cha/ông (từ xám đến xám)
2c. Forward edge: từ đỉnh cha/ông đến đỉnh con/cháu (từ xám đến đen)
2d. Cross edge: các cạnh còn lại (giữa các cây hoặc cây con)
Giả sử có một cycle, và v là đỉnh đầu tiên mà DFS thăm trên cycle đó. Lúc đó v xám, và sẽ không bị tô đen cho đến khi tất cả các đỉnh khác trên cycle đã được tô đen. Giả sử cycle đó là … u –> v –> w … thì cạnh uv sẽ phải là back edge.
Em cám ơn anh nhiều nhé! Em cũng có đọc trong tài liệu nhưng mà họ giải thích không rõ ràng lắm.
Việt nam có còn người tài ko ?
chỉ có 1 cái máy khắc dấu laser trung quốc mà ko một a chàng máy tính nào bít cách sử dụng phần mềm ??ko bít đc nó cần gì và thiếu điều gì ?? ai giỏi thì hãy thử sức nhé !công nghệ mà để trung quốc nó khi… sao ? liên hệ : 01656075748 để thử sức và nhận thưởng tiền triệu nếu phần mềm ok
Các anh chị cho em hỏi về thuật toán bài này với:
Cho 2 dãy số nguyên dương Pi(1 <= i <= m) và Qi (1 <= i <= n).
Hãy đặt các số nguyên dương vào 1 ma trận kích thước m x n sao cho tổng các số trên hàng i bằng Pi, và tổng các số trên cột j bằng Qj, đồng thời số lượng các số cần đặt là ít nhất có thể.
Em băn khoăn không biết có liên quan tới luồng cực đại hay không ?
Mong các anh chị cho ý kiến.
Anh Hưng cho em vài nhận xét về bài toán trên với.
Cám ơn anh nhé !
@Zeroman89,
Quick comment before my class in 20 minutes.
For feasibility (without the minimization problem), you can set up a flow network to solve it. Roughly, there’s a source $latex s$ with $latex m$ out-going arcs to $latex u_1, \dots, u_m$. The capacity of each link $latex (s,u_i)$ is $latex P_i$. Then, there are $latex n$ incoming links to sink $latex t$ from $latex v_1, \dots, v_n$. Link $latex (v_j, t)$ has capacity $latex Q_j$. Obviously $latex \sum P_i = \sum Q_j$ for the problem to be feasible. Finally, there’s a link $latex (u_i, v_j)$ with infinite capacity. An integral feasible max-flow gives you a feasible solution.
With the minimization problem, I’m pretty sure the problem is NP-hard.
Thực ra bài toán em đang gặp phải có kích thước m + n <= 10 và các số Pi, Qi <= 10000
Nhưng em chưa có cách tiếp cận nào khả thi mặc dù độ lớn của dữ liệu khá bé.
Anh Hưng có thể cho em vài gợi ý không ?
Hi Zeroman89,
Để tôi nghĩ thêm.
Cách brute-force là gán một tập con các $latex (u_i, v_j)$ capacities bằng 0, rồi giải bài maxflow ở trên. Mục tiêu là tối đa hóa kích thước của tập con này. Với $latex m+n \leq 10$ thì có nhiều nhất là $latex 25$ ô trong ma trận. Tuy nhiên, nếu tất cả các $latex P_i$ đều dương và tất cả các $latex Q_j$ đều dương thì chỉ cần xét các tập con với kích thước nhỏ hơn $latex mn – \max\{m,n\}$ thôi. Như vậy tổng số lần tối đa ta phải giải bài toán maxflow là khoảng $latex 2^{20} \approx 10^6$ lần, có thể làm được với Matlab trong vòng 5 ngày nếu mỗi maxflow instance mất 1/2 giây để giải
Tuy nhiên, ta dừng khi tìm được một tập con (đi từ lực lượng lớn = 20 đến nhỏ dần) làm cho bài toán feasible, cho nên chưa chắc đã lâu vậy.
À, có cách này chỉ cần loop khoảng 1000 lần thôi, như vậy chạy trong khoảng một tiếng là ra kết quả.
Cũng là cách brute-force như trên, nhưng ta có thể đặt ít nhất $latex mn – (m+n)$ biến bằng $latex 0$. Viết một linear-program (LP) đơn giản cho bài toán. LP này có $latex mn$ biến và $latex m+n$ ràng buộc. Ma trận ràng buộc là incident matrix của complete bipartite graph, do đó nó có tính chất totally unimodular; vì thế các extreme point solutions (EPS) đều là các vectors với tọa độ nguyên. Ngoài ra, tổng số các tọa độ khác 0 của một EPS nhiều nhất là tổng số hàng của ma trận này, nghĩa là $latex m+n$. Do đó, chỉ cần thử khoảng $latex 2^{10}$ trường hợp là xong.
Lấy matlab, chạy simplex khoảng 1000 lần. Chắc là dưới 1 tiếng.
Em làm được rồi, cám ơn anh Hưng nhiều lắm
Nhưng có một bài thế này:
Cho một đồ thị là một cây, hãy xóa đi 1 cạnh trong cây và thêm vào 1 cạnh sao cho đồ thị tạo thành vẫn là tree nhưng đường đi dài nhất trong cây là nhỏ nhất.
Yêu cầu đưa ra cạnh xóa, cạnh thêm vào, và độ dài đường đi dài nhất trong cây mới tạo thành ?
Anh Hưng lại giúp e nhé !
Zeroman89: cứ brute-force mà làm, running time $latex O(n^3)$ là cùng.
L. Lovász and M.D. Plummer, Matching Theory, Annals of Discrete Mathematics, 29, North-Holland Mathematics Studies, 121
Anh Hưng có quyển này thì share cho em với. Em tìm link download trên mạng nhưng không thấy.
Cám ơn anh.
Ah, anh cho em hỏi cách giải bài toán sau có đúng không ?
Bài toán: Cho 2 tập hợp điểm S1, S2 trên mặt phẳng. Tìm ở mỗi tập 1 điểm sao cho khoảng cách giữa chúng là lớn nhất. Số điểm thuộc 2 tập không quá 30000 điểm.
Thuật toán: Ban đầu lấy 1 điểm M bất kì ở tập S1, tìm điểm N xa nó nhất thuộc tập S2, rồi lại với điểm N ta tìm điểm xa nó nhất thuộc S1….Cứ tiếp tục như vậy thì sau một số ít các bước thì sẽ tìm được khoảng cách lớn nhất.
Cách làm này có vẻ mang cảm tính nhiều, liệu nó có đúng không anh ?
@zeroman89: Cách làm chưa đúng. Lấy S1 = { A, B}, S2 = { C, D} sao cho ABC & ACD là hai tam giác đều và B, D nằm trên 2 nửa mặt phẳng khác nhau chia bởi AC. Khoảng cách lớn nhất đạt được bởi BD. Tuy nhiên, nếu xuất phát với điểm A trong S1, điểm xa nhất với A trong S2 là C; điểm xa nhất trong S1 với C lại là A. Thuật toán dừng với kết quả sai AC.
Một cách làm là tìm bao lồi của mỗi tập, với mỗi điểm trên bao lồi của S1 tìm `nhị phân’ điểm xa nhất với nó trên bao lồi của S2. Độ phức tạp của thuật toán O(nlogn).
To zeroman89:
L. Lovász and M.D. Plummer, Matching Theory, Annals of Discrete Mathematics, 29, North-Holland Mathematics Studies, 121
Bạn tìm trên gigapedia.org nhé, đăng ký một account free, download thoải mái, cuốn càng nổi tiếng càng dễ có trong đó. Tôi đã tìm thấy cuốn Matching theory trên đó. Có gì trục trặc bạn mail cho tôi: anhhtu@gmail.com.
Đọc web nầy hây quá nên quên luôn đi học thế là toe
Em có bài toán thế này, anh Hưng và mọi người cùng cho ý kiến nhé:
Cho lưới ô vuông n hàng, m cột (2 <= n <= 7, 1 <= m <= 1000000000)
Hỏi có bao nhiêu đường đi đơn xuất phát từ ô (1, 1) và kết thúc ở ô (n, 1) (Đường đi đơn là đường đi qua mọi ô vuông của lưới, mỗi ô đúng một lần) ?
Bài này em đã đưa về tính số đường đi độ dài m trong đồ thị và giải bằng phép nhân ma trận. Nhưng cuối cùng phát hiện ra giải thuật có chỗ chưa kiểm soát được
, cũng có thể hiểu là nó sai 
. Hiện tại chưa biết làm thế nào ?
Chào các anh chị, các bạn,
Tôi đang định dạy 1 khóa 1 học kỳ cho học sinh trung học tại trường St. Paul’s bang NH, giới thiệu về Graph Theory. Các anh chị có lời khuyên về giáo trình và thiết kế chương trình cho 9 tuần, mỗi tuần 4 buổi không ?
Xin cảm ơn.