Blog Khoa Học Máy Tính

Trang a còng có phải thuộc báo Người Lao Động, “tiếng nói của liên đoàn lao động TPHCM” không nhỉ?

Ai đó đăng lại bài của tôi ở trang a còng, không hỏi han gì hết.

Đây không phải là lần đầu tiên và chắc không phải lần cuối cùng tôi … được đạo văn.

Chủ đề: Vui - Giải Trí | Bình luận (7) »

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 mình đẳng thức đầu tiên nhanh gọn và trực quan hơn không?

Xét tập . Vế phải đếm tổng số cách chọn một tập con gồm số từ , sao cho trong có một số thuộc tô màu xanh và số còn lại tô màu đỏ. Một tập như vậy có thể được chọn bằng cách chọn một tập con kích thước từ trước, tô một phần tử màu xanh, phần còn lại đỏ, và chọn một tập con kích thước từ . Như thế ta chứng minh được một đẳng thức … khác:

Chuyện này khá thường xảy ra khi làm nghiên cứu và giảng dạy. Các “khám phá” nho nhỏ như vậy là các bài tập về nhà tốt. Đẳng thức trên, sau khi viết lại một chút, dễ thấy là trường hợp đặc biệt của đẳng thức Chu-Vandermonde mà ta đã đề cập trong phần 1 chuỗi bài này.

Hừm, quay lại với đẳng thức đầu tiên. Làm thế nào để “phiên dịch” vế trái? Trước hết, ta viết lại đẳng thức để vế phải có diễn dịch “sạch” hơn.

Vế phải đếm tổng số tập hợp gồm phần tử trong đó có một phần tử được tô màu đỏ. Vế trái đếm tổng số các tấp hợp thỏa mãn: (a) , và (b) một trong số phần tử lớn nhất của được tô màu đỏ.

Tôi tìm được một song ánh (bijection) từ bộ các tập vào bộ các tập , nhưng song ánh này hơi phức tạp. Cũng có thể dùng nguyên lý involution của Garcia-Milne, nhưng như vậy song ánh cũng không được trực tiếp.

Lạ thật, một đẳng thức đơn giản như vậy mà tôi không tìm được một song ánh đơn giản. Bạn có tìm được không?

Chủ đề: Combinatorics | Bình luận »

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) »

The following story is fairly well-known.

This assignment was actually turned in by two English students:

Rebecca and Gary
English 44A
SMU
Creative Writing
Prof Miller
In-class Assignment for Wednesday

The Assignment: Today we will experiment with a new form called the tandem story. The process is simple. Each person will pair off with the person sitting to his or her immediate right. One of you will then write the first paragraph of a short story. The partner will read the first paragraph and then add another paragraph to the story. The first person will then add a third paragraph, and so on back and forth. Remember to reread what has been written each time in order to keep the story coherent. The story is over when both agree a conclusion has been reached.

---

The Submission:

At first, Laurie couldn’t decide which kind of tea she wanted. The camomile, which used to be her favorite for lazy evenings at home, now reminded her too much of Carl, who once said, in happier times, that he liked camomile. But she felt she must now, at all costs, keep her mind off Carl. His possessiveness was suffocating, and if she thought about him too much her asthma started acting up again. So camomile was out of the question.

Meanwhile, Advance Sergeant Carl Harris, leader of the attack squadron now in orbit over Skylon 4, had more important things to think about than the neuroses of an air-headed asthmatic bimbo named Laurie with whom he had spent one sweaty night over a year ago. “A.S. Harris to Geostation 17,” he said into his transgalactic communicator. “Polar orbit established. No sign of resistance so far…” But before he could sign off a bluish particle beam flashed out of nowhere and blasted a hole through his ship’s cargo bay. The jolt from the direct hit sent him flying out of his seat and across the cockpit.

He bumped his head and died almost immediately, but not before he felt one last pang of regret for psychically brutalizing the one woman who had ever had feelings for him. Soon afterwards, Earth stopped its pointless hostilities towards the peaceful farmers of Skylon 4. “Congress Passes Law Permanently Abolishing War and Space Travel.” Laurie read in her newspaper one morning. The news simultaneously excited her and bored her. She stared out the window, dreaming of her youth — when the days had passed unhurriedly and carefree, with no newspapers to read, no television to distract her from her sense of innocent wonder at all the beautiful things around her. “Why must one lose one’s innocence to become a woman?” she pondered wistfully.

Little did she know, but she has less than 10 seconds to live. Thousands of miles above the city, the Anu’udrian mothership launched the first of its lithium fusion missiles. The dim-witted wimpy peaceniks who pushed the Unilateral Aerospace Disarmament Treaty through Congress had left Earth a defenseless target for the hostile alien empires who were determined to destroy the human race. Within two hours after the passage of the treaty the Anu’udrian ships were on course for Earth, carrying enough firepower to pulverize the entire planet. With no one to stop them they swiftly initiated their diabolical plan. The lithium fusion missile entered the atmosphere unimpeded. The President, in his top- secret mobile submarine headquarters on the ocean floor off the coast of Guam, felt the inconceivably massive explosion which vaporized Laurie and 85 million other Americans. The President slammed his fist on the conference table. “We can’t allow this! I’m going to veto that treaty! Let’s blow’em out of the sky!”

This is absurd. I refuse to continue this mockery of literature. My writing partner is a violent, chauvinistic, semi-literate adolescent.

Yeah? Well, you’re a self-centered tedious neurotic whose attempts at writing are the literary equivalent of Valium.

You total $*&.

Stupid %&#$!.

Chủ đề: Vui - Giải Trí | Bình luận »