Category Archives: Combinatorics

Toán Tổ Hợp.

Cân xu

Ngô Quang Hưng | 04/08/2010 | Bản để in Bản để in
Bạn Huân hỏi về một bài toán đố cổ điển: bài toán cân xu tìm xu giả. Phiên bản thường nghe là như thế này: cho 12 đồng xu trong đó có 1 đồng xu giả (không biết nặng hay nhẹ hơn các đồng khác) và một cái cân thăng bằng, cân 3 lần tìm [...]
Cũng thuộc về chủ đề Thuật Toán | 6 phản hồi »

GT 6: Thử nhóm bất ứng biến giải mã nhanh

Ngô Quang Hưng | 29/01/2010 | Bản để in Bản để in
6. Thử nhóm bất ứng biến giải mã nhanh 6.1. Ý tưởng của Kautz-Singleton Hồi 1964, Kautz và Singleton đề xuất cách xây dựng ma trận -phân-cách dựa trên hai ý tưởng chính. Thứ nhất là nếu các cột của ma trận có “cân nặng” (số số trên cột) đủ lớn và nếu hai cột [...]
Cũng thuộc về chủ đề Lý thuyết mã hóa, Thuật Toán | 2 phản hồi »

GT 5: Sơ lược lý thuyết mã hóa

Ngô Quang Hưng | 26/01/2010 | Bản để in Bản để in
5. Sơ lược lý thuyết mã hóa Claude Shannon là cha đẻ của lý thuyết thông tin và lý thuyết mã hóa. Sẽ không có truyền thông hiện đại nếu không có Shannon. Nhà toán học lỗi lạc Kolmogorov từng nói về Shannon như sau: “Trong thời buổi mà kiến thức nhân loại càng lúc [...]
Cũng thuộc về chủ đề Lý thuyết mã hóa, Thuật Toán | Phản hồi »

GT 4: Bassalygo, Erdős, và Sperner

Ngô Quang Hưng | 29/12/2009 | Bản để in Bản để in
4. Chặn dưới Leonid Bassalygo là một học trò giỏi của người khổng lồ Kolmogorov. Từ những năm 1970, ông đã có nhiều đóng góp cơ bản trong lý thuyết thông tin, lý thuyết mã hóa, và lý thuyết các mạng chuyển mạch (switching networks). Có nhiều định lý và chặn mang tên ông. Ví [...]
Cũng thuộc về chủ đề Thuật Toán | 1 phản hồi »

GT 2: Phân Ly và Phân Cách

Ngô Quang Hưng | 15/12/2009 | Bản để in Bản để in
( tiếp theo bài trước ). 2. Ma trận phân ly và ma trận phân cách Tiến Sĩ Nguyễn Quang A là một trong các trí thức hàng đầu của Việt Nam hiện nay. Tôi không biết gì về các công việc làm ăn của anh Quang A, nhưng tôi biết anh đã một tay [...]
Cũng thuộc về chủ đề Thuật Toán, Xác suất & thống kê | 4 phản hồi »

Bổ đề Sauer

Ngô Quang Hưng | 11/11/2008 | Bản để in Bản để in
Bài học máy qua góc nhìn của lý thuyết tính toán số 4 có chứng minh bổ đề Sauer (bổ đề 5.2) bằng quy nạp. Tuy nhiên, một chứng minh bằng quy nạp không hay lắm vì nó “giấu” trực quan của chứng minh. Trong bài này, chúng ta sẽ chứng minh bổ đề Sauer [...]
Cũng thuộc về chủ đề Trí tuệ nhân tạo | Phản hồi »

Định trị một đại lượng bằng hai cách [6]

Ngô Quang Hưng | 30/09/2008 | Bản để in Bản để in
Hôm qua một phần bài giảng lớp randomized algorithms đẫn đến chứng minh đẳng thức sau đây: Có thể chứng minh đẳng thức này bằng cách viết lại vế trái thành Sau đó, chú ý rằng , ta khai triển tiếp thành: Đẳng thức cuối cùng có được là do . Có cách nào chứng [...]
Chủ đề Combinatorics | Phản hồi »

Đề thi toán quốc tế 2008

Ngô Quang Hưng | 01/08/2008 | Bản để in Bản để in
Như mọi khi, tôi quan tâm đến bài tổ hợp trong đề năm nay: Let n and k be positive integers with k ≥ n and k−n an even number. Let 2n lamps labelled 1, 2, . . . , 2n be given, each of which can be either on or off. Initially all the [...]
Chủ đề Combinatorics | 1 phản hồi »

Một bài toán đồ thị

Ngô Quang Hưng | 09/01/2008 | Bản để in Bản để in
Một người bạn gửi cho bài toán sau đây. Tôi vừa tìm được lời giải rất gọn. Cho n là một số nguyên lẻ lớn hơn 2. Mỗi cạnh của complete graph K_n được gán một cân nặng khác nhau. Chứng minh rằng có một walk chiều dài n trên graph K_n này với các [...]
Chủ đề Combinatorics | 14 phản hồi »

Định trị một đại lượng bằng hai cách [5]

Ngô Quang Hưng | 22/12/2007 | Bản để in Bản để in
Lần này ta chứng minh một định lý kinh điển của đại số: định lý Cayley-Hamilton. Mặc dù có thể phát biểu tổng quát hơn, ta chỉ phát biểu nó cho các trường số thực và phức. Định lý Cayley-Hamilton: Gọi là một ma trận vuông thực hoặc phức. Gọi là đa thức đặc trưng [...]
Chủ đề Combinatorics | 6 phản hồi »

Đề thi toán quốc tế 2007

Ngô Quang Hưng | 27/07/2007 | Bản để in Bản để in
Anh Nghị mới gửi cho tôi đề thi toán quốc tế 2007 ở Hà Nội dạng pdf. Chưa biết kết quả thế nào. Theo thông lệ, mỗi năm tôi cũng xem đề và giải các bài mình thích. Tôi rất ngại hình học, còn phương trình hàm thì nhàm, cho nên đa số chỉ giải [...]
Chủ đề Combinatorics | 7 phản hồi »

Định trị một đại lượng bằng hai cách [4]

Ngô Quang Hưng | 27/06/2007 | Bản để in Bản để in
Lần này ta xét một số chứng minh kinh điển về các số vô tỉ và các số siêu việt (transcendental numbers). Ví dụ 7: khoảng 500 năm trước công nguyên, Hippasus khám phá ra số vô tỉ đầu tiên, , với chứng minh chặt chẽ. (Theo truyền thuyết thì chứng minh này đem lại [...]
Chủ đề Combinatorics | Phản hồi »

Định trị một đại lượng bằng hai cách [3]

Ngô Quang Hưng | 16/04/2006 | Bản để in Bản để in
Ví dụ 6: Tiếp theo bài 1 và bài 2, lần này ta xét vài kết quả liên quan đến hệ số Gauss (Gaussian coefficients, còn gọi là q-binomial coefficients vì nó là q-analog của binomial coefficients). Xét không gian vector , là không gian hữu hạn chiều trên trường ( là lũy thừa của [...]
Chủ đề Combinatorics | 1 phản hồi »

Định trị một đại lượng bằng hai cách [2]

Ngô Quang Hưng | 12/04/2006 | Bản để in Bản để in
Tiếp theo bài trước, lần này ta xét một ví dụ kinh điển. Ví dụ 5. Euler là bậc thầy của kỹ thuật định trị hai cách (và là bậc thầy của ti tỉ thứ khác). Năm ông 24 tuổi (1731), Euler là người đầu tiên trong lịch sử toán học tìm được biểu thức [...]
Chủ đề Combinatorics | 3 phản hồi »

Đề tài nào hấp dẫn lời bình?

Ngô Quang Hưng | 05/04/2006 | Bản để in Bản để in
Có vẻ như viết cái gì “technical” quá hoặc thuần túy news thì ít có lời bình, cái gì philosophical hoặc khôi hài một chút thì hấp dẫn hơn. Bằng chứng là bác Ái Việt đang tiếp tục bình hai posts cũ: “nếu phải làm lại từ đầu” và “going to higher dimensional space” Nhân [...]
Chủ đề Combinatorics | 2 phản hồi »