Blog Khoa Học Máy Tính

Tiếp theo các bài trước, bài này nói về DFT trên các nhóm Abel. Ta đã biết rằng các phép biểu diễn tối giản trên một nhóm Abel bất kỳ đều là các phép biểu diễn 1 chiều. Tổng số các (isomorphism classes của) các phép biểu diễn một chiều này bằng với tổng số conjugacy classes của nhóm, nghĩa là bằng với tổng số phần tử trong nhóm vì đây là nhóm Abel.

Để cho dễ hiểu, hãy xét trường hợp đơn giản khi . (Nhớ rằng mỗi nhóm Abel hữu hạn đều isomorphic với tổng trực tiếp của một mớ cyclic groups dạng .) Trong trường hợp này, một hàm số là một character của nếu nó là một phép đồng cấu từ vào , nghĩa là nó thỏa mãn

Từ đó, dễ thấy rằng và là một nth root of unity. Các giá trị khác thỏa . Đặt . Với mỗi phần tử , nếu ta đặt thì tập hợp bộ này chính là tập hợp characters của . Viết ra cụ thể hơn:

Bộ các characters này một hệ cơ sở trực chuẩn của nếu ta dùng inner-product

Như đã nói sơ lược trong bài 2 về DFT, xét một hàm (nghĩa là vector) bất kỳ; biểu diễn dùng hệ cơ sở trực chuẩn trên:

thì . Đây chính là cái định nghĩa DFT thường thấy trong sách giáo khoa. Như vậy, DFT thường dùng trong xử lý tín hiệu số là một trường hợp đặc biệt của DFT trên nhóm .

Trường hợp một nhóm Abel bất kỳ thì như thế nào?

Một nhóm Abel bất kỳ đề có thể viết dưới dạng . Hơn nữa, nếu và là hai characters của thì hàm định nghĩa bởi là một character của . Ngược lại, bất kỳ character nào của cũng có thể viết được dưới dạng “tích” của hai characters của . Tổng quát hơn, nếu thì mọi character của đều là “tích” (nói đúng hơn là “tổng trực tiếp”) của các characters của .

Nhờ đó, ta có thể viết cụ thể ra bộ characters của nhóm như sau: mỗi character sẽ được đánh chỉ số bởi một thành viên . Nhớ rằng là một vector. Character này được định nghĩa như sau:

Bộ characters này là một hệ cơ sở trực chuẩn của không gian . Từ đó ta dễ dàng viết lại DFT của một hàm bất kỳ, cùng với DFT nghịch đảo và các đẳng thức Parseval, Plancharel.

Chủ đề: Thuật Toán | Bình luận (6) »

Mấy tháng nay tôi đang giải một bài toán rất thú vị. Sau đây là mô tả bằng ngôn ngữ bình dân một trường hợp (rất) đặc biệt của nó.

Tí và Tèo chơi trò chơi sau đây:

• Cho trước các tham số nguyên dương m và n cho trò chơi
• Khi bắt đầu trò chơi: có một dãy dài n cái hộp rỗng xếp thành hàng ngang
• Tèo có bi thuộc về k màu khác nhau, mỗi màu có vô số viên
• Trò chơi được chia thành nhiều lượt. Mỗi lượt đi thì Tí đi trước.
  • Tí chỉ được làm một trong hai tác vụ: Hoặc là chọn một hộp X nào đó, hoặc là chọn một viên bi nào đó đang nằm trong một trong các hộp.
  • Đến lượt Tèo: nếu Tí chọn hộp X, thì Tèo phải bỏ vào X một viên bi có màu khác tất cả các viên bi trong X và khác tất cả các viên bi trong (các) hộp kề X (nếu không làm được thì Tèo “bị chặn“); nếu Tí chọn một viên bi thì Tèo lấy viên bi đó ra khỏi hộp.
• Nếu tổng số bi trong X và hộp bên trái đã là m thì Tí không được chọn hộp X
• Nếu tổng số bi trong X và hộp bên phải đã là m thì Tí không được chọn hộp X

Câu hỏi là: giả sử Tí cực thông minh, tổng số màu bi k (chứ không phải tổng số bi) mà Tèo cần ít nhất là bao nhiêu để không bị chặn.

Nếu xếp các hộp thành hình tròn thay vì xếp hàng ngang thì sao?

Bài toán tôi đang giải phức tạp hơn nhiều. Các hộp được xếp theo một đồ thị cho trước (là các cạnh đồ thị). Các cạnh kề chung một đỉnh là các hộp “kề” nhau. Tí khi chọn hộp còn được chọn cân nặng cho viên bi mà Tèo phải bỏ vào. Tèo phải làm sao để tổng cân nặng các viên bi cùng màu kề cùng một đỉnh nhiều nhất là 1 kg. Còn nhiều biến thể khác cho bài này. Giải được mỗi biến thể đều viết paper được.

Chủ đề: Thuật Toán | Bình luận (5) »

Các routers trên Internet phải xử lý cực nhiều packets với tốc độ cực cao. Giả sử ta phải thiết kế một thuật toán để chỉ ra, trong một dòng các packets đã thấy cho đến thời điểm này (n packets, và n có thể cực lớn), có source-IP nào xuất hiện hơn n/2 lần hay không. Sự xuất hiện của một source-IP như vậy có thể là dấu hiệu của DoS từ IP nọ.

Do tốc độ xử lý phải cao tuyệt, thuật toán phải chạy nhanh và không dùng quá nhiều memory được (dùng cache memory thôi). Tóm lại thuật toán chỉ có thể thực hiện một scan qua dòng packets, dùng càng ít memory càng tốt.

Cách brute-force là dùng counters, mỗi counter cho một (potential) IP. Khi thấy IP mới thì tăng counter lên. Dĩ nhiên cách này không khả thi.

Hãy thiết kế một thuật toán như vậy dùng [O(log n) + 32 bit] memory, cho phép false positive nhưng không cho phép false negative. Nghĩa là thuật toán luôn output một IP address. Nếu có IP xuất hiện hơn n/2 lần thì thuật toán phải output nó. Nếu không có IP xuất hiện hơn n/2 lần thì output gì cũng được.

Chủ đề: Thuật Toán | Bình luận (9) »

Nhân đọc một entry về xếp thứ tự giấy tờ bên unfogged: trong cuộc sống hàng ngày có không ít các trường hợp ta có thể áp dụng một ý tưởng thuật toán nào đó. Vài ví dụ:

• Nếu phải xếp thứ tự an-pha-bê khoảng trăm bài kiểm tra cuối kỳ nào đó, bạn dùng quick sort, merge sort, insertion sort, bubble sort, hay radix sort, v.v.? Tôi thường dùng chung insertion & merge sort.
• Hàng tuần có nhiều việc phải làm. Làm gì trong ngày nào là một dạng bin-packing hoặc weighted scheduling with deadlines. Ta không muốn ngắt một việc làm nhiều ngày (nếu có thể) vì mất công re-boot. Tôi thường ghét các việc lắt nhắt, nên dồn chúng lại làm một lúc và để đến sau cùng, tương tự như thuật toán FFD cho bin-packing.
• Mua quà Noel cho nhiều người với một túi tiền có hạn là bài toán Knapsack.
• Mồng 2 Tết, đi lòng vòng chúc tết nhà bà con bạn bè là bài toán TSP.
• Chọn thức ăn từng bữa cho đủ chất và giá rẻ nhất là bài toán qui hoạch tuyến tính (mixed với quy hoạch nguyên).
• …

Chủ đề: Thuật Toán & Vui - Giải Trí | Bình luận (2) »

Lâu rồi không dùng một phần mềm cho symbolic computation như Mathematica hay Maple. Hồi xưa còn làm về q-series nhiều tôi chọc ngoáy Mathematica hàng ngày. Mấy hôm nay tôi cần chúng cho một bài toán đang giải, dùng lại Maple thấy quả thật là hùng mạnh. Dưới đây là ví dụ về output của Maple. Dĩ nhiên, tôi có GUI output cẩn thận chứ không phải output kiểu text cổ điển như thế này.

> x := 2/5;
                                      2
                                      -
                                      5
> y := 1/3;
                                      1
                                      -
                                      3
> C := [2*x*a+2*y*b+(1/2)*c >= 2, max(2*y, 1-x)*b+(1-x)*c >= 2, (1-y)*c >= 2];
              [     4     2     1         2     3         2  ]
              [2 <= - a + - b + - c, 2 <= - b + - c, 2 <= - c]
              [     5     3     2         3     5         3  ]
> P := a+b+c;
                                  a + b + c
> with(Optimization);
> LPSolve(P, C, assume = nonnegative);
[3.67500000000000,
  [a = 0.374999999999999834, b = 0.300000000000001098, c = 2.99999999999999868]
]
> with(simplex);
> minimize(P, C, NONNEGATIVE);
                           /    3       3       \
                          { b = –, a = -, c = 3 }
                           \    10      8       /

Các phần mềm tính toán như Matlab, Mathematica, Maple đều rất đắt tiền (cỡ 500USD chứ không ít). May mà trường tôi có deal gì đó với Mathematica và Maple nên tôi mua chúng chỉ mất 10USD. Sinh viên thì còn mua thêm được phiên bản sinh viên của Matlab, 50USD. Nếu dùng máy trong khoa thì tôi có thể dùng Matlab thoải mái vì có license tập thể. Tôi không biết có open-source symbolic hay scientific computation softwares nào dùng được không?

Muốn viết các phần mềm cho scientific computation hay symbolic computation cần phải rất giỏi cả KHMT lẫn Toán. Tính hữu dụng của chúng trong nghiên cứu khoa học thì phải nói là vô hạn.

Chủ đề: Công nghệ phần mềm & Thuật Toán | Bình luận (3) »

Học kỳ này tôi (lại) dạy lớp phân tích và thiết kế giải thuật. Đây là lớp mở đầu phân tích thiết kế thuật toán cho sinh viên sau đại học (năm đầu). Các chủ đề sẽ được thảo luận bao gồm:

asymptotic notations and analysis, greedy algorithms, divide and conquer, dynamic programming, linear programming, network flows, NP-completeness, approximation algorithms, randomized algorithms

Bạn nào quan tâm có thể xem homepage của lớp cùng với một blog cho lớp. Trên blog này sẽ có các thông báo, bình luận, tin tức, và liên kết đến các nguồn tin, bài báo, v.v. liên quan đến phân tích và thiết kế thuật toán. Ngoài ra trên homepage của lớp còn có bài tập và các bài kiểm tra, cùng với tóm tắt bài giảng.

Tôi sẽ để bài tập và bài kiểm tra cho mọi người đều truy cập được. Tuy nhiên, phần đáp án thì chỉ có sinh viên trong lớp tôi truy cập được dùng username/password tôi cho. Lý do mà tôi không muốn để đáp án mở: nếu ai đó thật sự quan tâm và muốn học phân tích và thiết kế thuật toán thì nên tự giải quyết các bài tập. Sinh viên của tôi phải nộp bài rồi mới được xem đáp án. Tương tự như việc tôi đăng các câu hỏi phỏng vấn nhưng không đăng câu trả lời. Cuộc đời sẽ thú vị hơn nhiều khi không có đáp án.

Từ quan điểm cá nhân, tôi không thể tưởng tượng một lớp đại học trong thế kỷ 21 mà lại không có homepage cùng một loại forum nào đó để thảo luận các đề tài trong lớp! Bây giờ làm homepage trên Internet dễ cực: wordpress, blogger, googlepages, etc.

Chủ đề: Dành cho du học sinh & Thuật Toán | Bình luận (8) »

Nhân bạn npson thắc mắc về chữ Hanoi trong bài toán “Tower of Hanoi”, tôi đi tìm hiểu thêm ngọn ngành thì ra đại khái thế này. Trong quyển L’arithmétique amusante của chính Lucas, người sáng tạo ra trò chơi “Tower of Hanoi”, có đoạn như sau:

: Un de nos amis, le professeur N. Claus (de Siam), mandarin du college Li-Sou-Stian, a publie en 1884 un jeu inedit et brevete, qu’il a appele la Tour d’Hanoi, veritable casse-te^te annamite qu’il n’a pas rapporte du Tonkin, quoi qu’en dise le prospectus.

Như vậy không còn nghi ngờ gì nữa, Hanoi chính là Hà Nội, Việt Nam! Một đoạn kế tiếp viết về truyền thuyết tháp Brahma, có đến 64 đĩa.

Le mandarin N. Claus (de Siam) nous raconte qu’il a vu, dans ses voyages pour la publication des ecrits de Fer-Fer-Tam-Tam, dans le grand temple de Benares, au dessous du dome qui marque le centre du monde, trois aiguilles de diamant, plantees dans une dalle d’airain, hautes d’une coudee et grosses comme le corps d’une abeille. Sur une de ces aiguilles Dieu enfila, au commencement des siecles, soixante-quatre disques d’or pur, le plus large reposant sur l’airain, et les autres de plus en plus etroits, superposes jusqu’au sommet; c’est la tour sacree de Brahma. Nuitet jour, les pre^tres se succedent sur les marches de l’autel, occupes a transporter la tour de la premiere aiguille de diamant sur la troisieme, sans s’ecarter des regles fixes que nous venons d’indiquer, et qui ont ete posees par Brahma. Quand tout serafini, la tour et les brahmes tomberont, et ce sera la fin des mondes!
…
L’industrie etrangere s’est emparee depuis peu du jeu de notre ami et de sa legende; mais nous pouvons affirmer que le tout a ete imagine, il y a une dizaine d’annees, au no. 56 de la rue: Monge, a Paris, dans la maison habitee alors par M. Viette, ministre de l’Agriculture, et batie sur l’emplacement de celle ou mourut Pascal, le 19 aout 1662.

Cái đồ chơi Tower of Hanoi mà Lucas xuất xưởng đầu tiên chỉ có 8 đĩa. Tôi đoán rằng vì lượng đĩa bé hơn mà Lucas không dùng chữ Brahma. Hình dưới đây là hình bìa của đồ chơi nguyên thuỷ của Lucas. Trong hình ta cũng thấy chữ “Annamite” và một anh chàng đội nón lá thời thuộc địa.

(Image Source: The Puzzle Museum)

Chủ đề: Thuật Toán | Bình luận (4) »

Tôi muốn giới thiệu một bài báo thú vị của David Donoho với tựa đề: The blessings and curses of dimensionality. Donoho là một siêu sao trong ngành thống kê của thập niên 90, ông cũng là một cây viết thú vị. Các bài viết của Donoho dù technical hay không, thường tạo ra nhiều cảm hứng và nhiệt tình cho người đọc. Bài báo trên của Donoho là một lời kêu gọi sự chú ý của giới làm toán nói chung hãy quan tâm hơn và đóng góp các công cụ toán học đến những vấn đề xử lý dữ liệu hóc búa của thế kỷ 21. Đọc nó, và hy vọng bạn sẽ thấy đó cũng là lời kêu gọi đến những nhà khoa học máy tính của hôm nay và ngày mai.

Những vấn đề xử lý dữ liệu không hề xa lạ với dân KHMT chúng ta. Quả thật đó cũng chính là nồi cơm của chúng ta: Làm thế nào để “make sense of” luồng dữ liệu khổng lồ trên web, trong hệ thống máy, trong các sensor networks, trong genome của người và các sinh vật khác, các loại dữ liệu ở dạng text, ảnh, âm thanh, v.v. Làm thế nào để máy tính được grounded trong data mà không bị chết sặc. Những tiến bộ trong công nghệ thông tin — communication, networking, hardware, software, data structure và algorithms — đã tạo nên một cơ sở hạ tầng tuyệt vời để thu thập và biểu hiện dữ liệu. Song chưa đủ. Xử lý luồng dữ liệu khổng lồ như thế nào lại là một chuyện phức tạp hơn nhiều. Ở thế kỷ 21, rất nhiều ngành khoa học lý thuyết, tính toán và thực nghiệm phải cùng nhau xắn tay vào để giải quyết những vấn đề như vậy.

Dân KHMT cũng không lạ gì khái niệm “curses of dimensionality” do Richard Bellman sử dụng lần đầu tiên. Curses of dimensionality nói đến sự khó khăn trong việc giải quyết các bài toán liên quan đến high dimension. Một cách cụ thể, số lượng dimension của bài toán có thể là số lượng biến số liên quan, có thể do số lượng sensors dùng để thu thập data rất lớn. Tùy theo dạng dữ liệu khác nhau mà sensors ở đây cũng nên hiểu theo nghĩa rất linh động, có thể là các routers trong một network, các cameras, các websites, các pixels của từng hình ảnh, độ dài của chuỗi DNA và protein trong sinh học phân tử, v.v. Để xử lý data với dimension khổng lồ như trên với số lượng khổng lồ đòi hỏi tìm kiếm trong một state space lớn gấp nhiều lần, có thể theo đa thức hoặc hàm số mũ (exponential). Đó chính là curses of dimensionality. Đừng vội nghĩ exponential complexity mới là tồi tệ. Nếu thuật toán của bạn scan database lần, với số dimension ở mức hàng chục triệu thì đã khó chấp nhận rồi.

Điều thú vị là high-dimension có nhiều blessings. Bạn hãy tự hỏi, tại sao con người ta luôn luôn phải đối mặt với rất nhiều sensory data (qua 7 giác quan) mà thường vẫn không bị tẩu hỏa nhập ma. Tất nhiên đây là một câu hỏi mở để ta cùng suy ngẫm. Trong toán học, một trong những yếu tố thuận lợi của high dimensions chính là khái niệm concentration of measure. Trong lý thuyết xác suất chúng ta đều biết law of large numbers: giá trị trung bình của các sự thể hiện ngẫu nhiên thường hội tụ về giá trị kỳ vọng của biến ngẫu nhiên (constant). Hay định luật central limit: Giá trị trung bình của các sự thể hiện ngẫu nhiên có hành vi giống như biến Gauss. Sâu hơn một chút, một hàm số được định nghĩa trên rất nhiều biến (high dimension), mà sự đóng góp của từng biến vào giá trị hàm số đều nhỏ, thì hàm số đó có hành vi giống như constant vậy. Kỳ thực rất nhiều hàm số mà chúng ta quan tâm trong cuộc sống đều có tính chất này. Trong hình học lồi (convex geometry), rất nhiều vật thể lồi trong high dimension thường có những tính chất phản trực quan: ví dụ một hình hộp trong không gian nhiều chiều có hình dạng rất khác một hình hộp ta biết trong 2 hay 3 chiều. Song những tính chất đó lại được tận dụng một cách hiệu quả để đưa ra những đáp án rất ngoạn mục cho các vấn đề liên quan đến high dimension.
[[Addition 04/03/07: Một quyển sách rất hay và dễ đọc giới thiệu về v/đ này: Keith Ball, Elementary introduction to convex geometry, ở đây .]]
Donoho còn liệt kê ra và dẫn chứng một số yếu tố blessings khác trong không gian nhiều chiều. Để có nó ta cần phải sử dụng các công cụ khác trong toán học.

Đây là một ví dụ của những bài báo mà khi đọc xong, tôi không khỏi cảm thấy mình thật là may mắn vì được sống trong một không gian rất nhiều chiều. Không phải vì mình đã nắm hết được hết các blessings kể trên, mà vì khả năng được tìm tòi và sử dụng các công cụ toán học đẹp đó để giải quyết các vấn đề rất thiết thực. Bring it on, your curses, dear Professor Bellman!

Chủ đề: Giới thiệu sách & Lý thuyết thông tin & Lý thuyết tính toán & Thuật Toán & Toán tối ưu & Trí tuệ nhân tạo & Xác suất & thống kê | Bình luận (2) »

Cha đẻ của kỹ thuật dynamic prorgramming (quy hoạch động) là Richard Bellman. Hồi đầu những năm 50, Bellman làm tư vấn cho RAND Corp, một trong những think tank có ảnh hưởng cực lớn của quân đội Mỹ. (Lý thuyết game, quy hoạch tuyến tính, và nhiều nhánh khác của toán học, kinh tế học hiện đại có phần gốc gác từ RAND.) Hồi đó Bellman đang nghiên cứu về planning, multistage decision process, … và ông khám ra kỹ thuật quy hoạch động. Tuy nhiên, hồi đó bộ trưởng bộ quốc phòng Mỹ là Charles Wilson rất ghét cụm từ “nghiên cứu”, đặc biệt là “nghiên cứu toán học”. Wilson vốn là một kỹ sư giỏi, nhưng sau đó đi làm business (salesman), lên đến tổng giám đốc của General Motors. Trong quyển tiểu sử tự thuật của mình, Bellman giải thích tại sao ông chọn tên “dynamic programming” như sau:

I spent the Fall quarter (of 1950) at RAND. My first task was to find a name for multistage decision processes. “An interesting question is, ‘Where did the name, dynamic programming, came from?’ The 1950s were not good years for mathematical research. We had a very interesting gentlemen in Washington named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word, research. I’m not using the term lightly; I’m using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term, research, in his presence. You can imagine how he felt, about the term, mathematical. The RAND Corporation was employed by the Air Force, and the Air Force had Wilson as its boss, essentially. Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation. What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word, ‘programming.’ I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying–I thought, let’s kill two birds with one stone. Let’s take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense. It also has a very interesting property as an adjective, and that is it’s impossible to use the word, dynamic, in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It’s impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressmann could object to. So I used it as an umbrella for my activities

(Xem thêm bài viết này có nhiều trích đoạn hay từ hồi ký của Bellman.) Đọc đoạn này tôi chợt nhớ đến vụ toán học vô dụng vì nếu Bellman không che giấu cái “nghiên cứu toán học” của ông bằng cái tên khó hiểu, thì đã không có tiền để phát triển một ý tưởng mà ngày nay được dùng rộng rãi trong computational biology, operation research, control theory, … chưa kể ít nhất một nửa cái Internet ta dùng hàng ngày đang chạy Distance Vector protocol theo thuật toán Bellman-Ford, một thuật toán quy hoạch động.

Chủ đề: Nhân vật và sự kiện & Thuật Toán & Thuật ngữ chuyên ngành | Bình luận (4) »

Với dạng cây nhị phân như hiện nay, có khả năng đấu thủ mạnh thứ hai trong giải (do bị đấu thủ mạnh nhất loại từ trước) không được huy chương bạc. Nếu ai đó (như Andy Rodick) mà xui xẻo nằm ở nửa nhánh cây chung với Federer thì coi như là … hẻo.

Lewis Carroll (tác giả Alice in Wonderland) còn là một nhà toán học có cỡ. Ông đã nêu vấn đề bất công này từ hồi 1883 trong tạp chí St. James’s Gazette. Chương 5 quyển 3 của bộ sách của Knuth ghi lại khá chi tiết các phát triển sau đó của câu hỏi này.

1 Nếu bạn phải thiết kế một lịch thi đấu tennis để xác định đấu thủ mạnh nhất và đấu thủ mạnh nhì, bạn cần tối thiểu bao nhiêu trận đấu, cho biết tổng số đấu thủ ban đầu là n?

2 Nếu ta muốn biết cả đấu thủ mạnh thứ 3 (huy chương đồng), thì cần tổng cộng bao nhiêu trận đấu, lịch thi đấu thế nào?

(Dĩ nhiên, câu hỏi tổng quát nhất là xác định m đấu thủ mạnh nhất, và đã có vài câu trả lời gần tối ưu cho câu hỏi này, nhưng chưa phải là tối ưu.)

Chủ đề: Thuật Toán | Bình luận (6) »

• M. E. J. Newman, The structure and function of complex networks, SIAM Review, vol. 45, no. 2, pp. 167–256, 2003. [pdf]
• J. Kleinberg. Navigation in a Small World. Nature 406(2000), 845. [pdf]
• J. Kleinberg. Complex Networks and Decentralized Search Algorithms. Proceedings of the International Congress of Mathematicians (ICM), 2006. [pdf]

Chủ đề: Mạng máy tính & Thuật Toán | Bình luận »

Trong bài trước ta kết thúc với định lý Maschke rằng bất kỳ phép biểu diễn (phức) nào trên một nhóm hữu hạn đều là tổng của các phép biểu diễn tối giản. (Biểu diễn các nhóm vô hạn cũng được, nhưng ta không xét ở đây.)

Như vậy, ta có thể nghiên cứu các phép biểu diễn dùng các phép biểu diễn “đơn giản” hơn một chút. Tuy nhiên, một phép biểu diễn vẫn là một đối tượng rất phức tạp để mô tả (nó là một phép đồng cấu thỏa mãn một số tính chất đại số, hoặc cũng có thể xem nó là một ma trận nếu ta chọn trước một hệ cơ sở trên không gian ). Thậm chí, có bao nhiêu phép biểu diễn (không isomorphic với nhau) ta cũng không biết. Có thể có vô hạn các phép biểu diễn không? Làm thế nào để phân loại chúng?

Để phân loại các phép biểu diễn, có một cách để loại bỏ đa số thông tin về phép biểu diễn, chỉ giữ lại một vài con số! Các con số này chứa rất nhiều thông tin về phép biểu diễn, và ta có thể dùng chúng để phân loại các phép biểu diễn. Kết quả này là một trong những định lý đẹp nhất trong đại số.

Các con số “kỳ diệu” này được chứa trong một hàm gọi là đặc trưng (character) của phép biểu diễn. Đặc trưng của phép biểu diễn trên nhóm là một hàm định nghĩa như sau

(Nhớ rằng là một toán tử tuyến tính khả nghịch trên không gian phức , cái trace của là tổng các eigenvalues — trị đặc trưng — của nó.) Hàm đặc trưng cũng có thể được xem như một vector mà các tọa độ được đánh chỉ sổ bởi các thành viên của nhóm .

Định nghĩa số chiều (dimension) của một character là số chiều của không gian V của phép biểu diễn. Định nghĩa một tích vô hướng Hermitian giữa các characters như sau:

( là complex conjugate của .) Đặc trưng của phép biểu diễn chứa cực kỳ nhiều thông tin về phép biểu diễn. Sau đây tôi trích ra vài kết luận quan trọng:

• chính là số chiều của phép biểu diễn
• , với mọi phần tử , nghĩa là character có giá trị như nhau trên mỗi conjugacy class của nhóm.
• 
• Character của là tổng của các characters thành phần .
• Gọi , và là các đại diện của các isomorphism classes của các phép biểu diễn tối giản trên , và gọi là character của . Ta có:
  • Các vectors vuông góc với nhau và có chiều dài đơn vị. (Orthogonality relation.) Gọi là tổng số các conjugacy classes của nhóm. Gọi là không gian vector của các hàm sao cho có giá trị như nhau trên mỗi conjugacy class của . Ta có, các characters tạo thành một hệ cơ sở trực chuẩn của . Ta sẽ dùng tính chất này để nói thêm về DFT trên các nhóm Abel trong bài tới.
  • Tổng số các isomorphism classes của các phép biểu diễn tối giản bằng với tổng số các conjugacy classes của nhóm . Gọi là tổng số này.
  • Gọi là số chiều của , ta có chia hết cho , và
    
• Một character bất kỳ của nhóm đều có thể biểu diễn (theo một cách duy nhất) thành tổ hợp tuyến tính của các characters tối giản.
• Hai phép biểu diễn có character giống nhau thì isomorphic với nhau
• Một character là tối giản nếu và chỉ nếu nó có chiều dài đơn vị (nghĩa là )
• Nếu là một nhóm Abel thì các characters tối giản của nó đều có số chiều bằng .

Có một hệ quả tuyệt đẹp của lý thuyết biểu diễn nhóm khi là nhóm các hoán vị của phần tử. Gọi là số các standard Young tableaux dạng . Ta có:

Định lý này cũng có thể chứng minh bằng giải thuật Robinson-Schensted.

Chủ đề: Thuật Toán | Bình luận (13) »

Talk của Nick Harvey (MIT), talk của Baochun Li (Toronto), talk của Yunnan Wu (Princeton). Trong đó talk của Baochun Li hay nhất.

Tôi sẽ viết tiếp chuỗi bài về lý thuyết mã mạng trong vài tuần tới.

Chủ đề: Lý thuyết thông tin & Lý thuyết tính toán & Mạng máy tính & Thuật Toán | Bình luận (4) »

Quyển Computers and Intractability: A Guide to the Theory of NP-Completeness của Garey và Johnson là tham khảo kinh điển về lý thuyết NP-đầy đủ. Trong 30 năm qua, Johnson vẫn tiếp tục viết các NP-complete columns để cho ta biết các cập nhật mới nhất về các bài toán NP-đầy đủ.

Hồi xưa, ta có thể viết một bài báo chứng minh một bài nào đó là NP-Hard. Nay thì 99.9% các kết quả loại này chỉ là một bổ đề trong phần appendix của một bài báo. Các chứng minh NP-hardness đã trở thành routine như kiểu tính tích phân (mặc dù tính tích phân không phải lúc nào cũng đơn giản!).

Ngày nay, khi đối chọi với một bài toán mới, để có thể đăng tải kết quả thì ngoài chuyện chứng minh là nó NP-hard ta thường phải làm thêm 2 việc nữa: (1) tìm một thuật toán xấp xỉ tốt, và (2) chứng minh rằng xấp xỉ bài này đến một tỉ lệ nhất định cũng NP-hard nốt. Công việc (2) được gọi là chứng minh “hardness of approximation”. (Ta có thể thay giả thiết P khác NP bằng một giả thiết khác trong complexity theory. Giả thiết “hot” nhất hiện nay là Unique Game Conjecture. Xem thêm ở Khot’s homepage, và bài này, bài này nữa.) Kỹ thuật chính để chứng minh các kết quả loại này là dùng Probabilistically Checkable Proofs.

Lẽ tự nhiên, column mới nhất của David Johnson nói về các kết quả loại này — một bước nhảy lượng tử từ NP-hardness lên NP-hardness of approximation. Muốn biết chi tiết hơn, đọc các bài [Trevisan 2004] và [Khot 2005].

Chủ đề: Lý thuyết tính toán & Thuật Toán | Bình luận »

Sau lớp 11, chắc ai cũng biết định nghĩa (vô hạn các) hàm không liên tục. Tuy nhiên, có một số nhà toán học theo trường phái constructive mathematics cho rằng tất cả các hàm tính được (computable) đều liên tục. Andrej Bauer có một bài ngắn về đề tài này.

Constructive Mathematics và intuitionism ra đời cũng chỉ tại Cantor (xem toàn bài dạng pdf).

Chủ đề: Lý thuyết tính toán & Thuật Toán | Bình luận (2) »