Khoe

NQH | 16/05/2012 | Bản để in Bản để in

Được cái này, nhờ bài báo này. Như bạn mlteppi đã loan báo từ trước.

Bài báo “Worst-case optimal join algorithms” có một lịch sử thú vị liên quan đến blog KHMT. Số là năm ngoái bọn tôi làm một vấn đề về giải mã tín hiệu trong compressed sensing. (Bài ở STACS 2012.) Một trong những kết quả tìm được là một thuật toán cho bài lính bắn tia laser. Bài lính bắn laser vốn là một bất đẳng thức hình học, và do có cấu trúc khá chặt chẽ tôi thấy rất khó chịu khi thuật toán chỉ làm cho trường hợp 3-chiều. Tôi có viết trong một lời bình ngày 1 tháng 3, 2011 là

Tôi tin là có chứng minh tốt hơn cái CM tôi có, và có lẽ đây là trường hợp đặc biệt của cái gì đó đã biết, nhưng tôi không biết là cái gì.

Bài học 1: luôn không thoả mãn với các trường hợp đặc biệt. Nếu kết quả của mình có vẻ cơ bản thì nó phải là một ví dụ của cái gì đó tổng quát hơn, đẹp hơn!

Đọc tiếp »

Chủ đề Cơ sở dữ liệu | Tagged , | 7 phản hồi »

Khoa học vị nhân xinh

Nguyễn Xuân Long | 08/05/2012 | Bản để in Bản để in

Chẳng mấy khi thấy một bài báo của mình lại được nhắc chung với một tạp chí uy tín như People Magazine hay những người nổi tiếng như ở bài báo sâu sắc này . Vui!

Chủ đề Vui - Giải Trí | 7 phản hồi »

Làm an toàn thông tin thì học gì?

thaidn | 02/05/2012 | Bản để in Bản để in

1 Giới thiệu

Tôi nhận được thư từ của nhiều bạn hỏi về việc nên học gì và như thế nào để có thể tìm được việc làm và làm được việc trong ngành an toàn thông tin (information security). Tôi nghĩ việc đầu tiên bạn cần phải làm là in toàn bộ bài viết “Làm thế nào để trở thành white hat hacker” ra giấy, nhưng đừng đọc, mà hãy để chúng trong toilet khi nào cần thì xài dần.

Quay trở lại câu hỏi. An toàn thông tin là một ngành rộng lớn với rất nhiều lĩnh vực. Những gì tôi biết và làm được chỉ gói gọn trong một hai lĩnh vực. Có rất nhiều mảng kiến thức cơ bản mà tôi không nắm vững và cũng có nhiều kỹ năng mà tôi không thạo. Hack tài khoản Yahoo! Mail là một trong số đó. Tôi cũng không biết cách tìm địa chỉ IP của bạn chat :-( .

Đọc tiếp »

Chủ đề Bảo mật và mật mã học, Giáo dục, Giới thiệu sách | 4 phản hồi »

Con sãi ở chùa thì đi săn lỗ

thaidn | 24/04/2012 | Bản để in Bản để in

Chương trình tìm lỗ lấy tiền của Google vừa mới nâng giá giải thưởng:

$20,000 for qualifying vulnerabilities that the reward panel determines will allow code execution on our production systems.

$10,000 for SQL injection and equivalent vulnerabilities; and for certain types of information disclosure, authentication, and authorization bypass bugs.

Up to $3,133.7 for many types of XSS, XSRF, and other high-impact flaws in highly sensitive applications.

3.000 Mỹ kim cho một lỗ hổng XSS, quá ngon! Với số lượng ứng dụng khổng lồ của Google, việc tìm được những lỗi như XSS hay XSRF, vốn không đòi hỏi kiến thức hay kinh nghiệm gì cao siêu cả, là không quá khó. Thực tế là kể từ khi chương trình này bắt đầu cho đến nay, đã có hơn hai trăm người gửi lỗi và được Google thưởng cho hơn 460.000 Mỹ kim. Nhưng chưa có con sãi nào đến từ Việt Nam cả!

Nếu không săn lỗ thì đi viết app cũng được.

Chủ đề Bảo mật và mật mã học, Tin tức đó đây | 2 phản hồi »

Con sãi ở chùa lại đánh bi-da

NQH | 20/04/2012 | Bản để in Bản để in

Năm 24 tuổi, hầu hết thời gian trong đời tớ dùng vào việc đánh bi da. À không, hình như lúc đó đang lui cui học lệnh cd, ls, cp trên một máy SGI. Đánh bi da là năm 18-22 tuổi.

Năm 24 tuổi, cô gái này đi “đến thăm, động viên đội ngũ cán bộ, công nhân đang thi công … chỉ đạo Ban quản lý chu đáo các vấn đề liên quan đến việc làm lán, trại, chỗ ở cho công nhân để anh em yên tâm làm việc và đảm bảo sức khỏe“.

Thiệt là hậu sinh khả uý.

Chủ đề Vui - Giải Trí | Tagged , , | 23 phản hồi »

Hàm băm FNV

NQH | 18/04/2012 | Bản để in Bản để in

Khi xây dựng bảng băm, ví dụ bảng băm cho một bộ tự điển, đầu tiên ta cần tính mã băm (hash codes) của các từ trong tự điển. Mỗi mã băm của một từ là một số nguyên dài 4 bytes chẳng hạn. Sau đó ta dùng một hàm băm nữa gọi là hàm nén (compression function) chuyển số nguyên này xuống miền nhỏ hơn, cỡ vài trăm ngàn tuỳ tự điển. Tóm lại, một hàm băm từ tập các từ thường là composition của hai hàm băm — một hàm chuyển về miền số nguyên dài 32 bits, hàm thứ hai từ miền số nguyên đến miền nhỏ cỡ trăm ngàn, tuỳ theo load factor của bảng băm.

Có rất nhiều cách tính mã băm chuyển chuỗi ký tự thành số nguyên dài 32 bits. Các sách giáo khoa thường nói đến mã băm đa thức (polynomial hash codes). Ví dụ, với một chuỗi bytes s = s[0]...s[k-1] với chiều dài k ta có thể dùng hash code sau:

\text{hashcode(s)} = \sum_{i=0}^{k-1}s[i]*a^i

trong đó a thường được chọn là một số nguyên tố. Hàm hashCode() strong trong lớp string của Java dùng mã băm đa thức với a=31. Một lợi điểm của mã băm đa thức là nó có thể tính đương đối nhanh được dùng luật Horner:

\text{hashcode(s)} = s[0] + a*(s[1] + a*(\dots (s[k-2] + a * s[k-1])\dots)

Đọc tiếp »

Chủ đề Cấu trúc dữ liệu | Tagged , , | 6 phản hồi »

Các câu hỏi phỏng vấn [43]

thaidn | 18/04/2012 | Bản để in Bản để in

113. Tính cube root modulo 2^n: cho a và n, tính nhanh x sao cho a = x^3 (mod\;2^n).

Thiệt ra đây không phải câu hỏi phỏng vấn (có nơi nào phỏng vấn mà hỏi những câu dạng này không nhỉ?) mà là của một anh đồng nghiệp hỏi tôi hôm nay. Tôi thấy nó thú vị và thích hợp với những ai đang theo học lớp crypto của Stanford nên gửi lên đây.

Chủ đề Dành cho du học sinh | Tagged , , | 12 phản hồi »

Câu hỏi về câu hỏi về câu hỏi …

Administrator | 14/04/2012 | Bản để in Bản để in

Bạn nghĩ gì về cái tên mới của "blog tên cũ"

View Results

Loading ... Loading ...

Chủ đề Thông báo | Tagged | 2 phản hồi »

Drama

NQH | 13/04/2012 | Bản để in Bản để in

Chủ đề Vui - Giải Trí | Tagged | Phản hồi »

Các cây tìm kiếm cân bằng: AVL, đỏ đen, (2,4), và cây loe

NQH | 06/04/2012 | Bản để in Bản để in

Bài giảng cho lớp cấu trúc dữ liệu. Bạn nào rảnh đọc thì góp ý giùm, nhất là phần C++.

Bài trước: Cây nhị phân và cây tìm kiếm nhị phân
Bài sau: bảng băm.

In the previous lecture we have discussed binary search trees (BSTs) and several basic results such as the number of BSTs with n keys and the height of a random BST with n node. Perhaps the most important result is that in a BST the three basic operations — search, insert, and delete — take O(h) time where h is the height of the tree (at the time an operation is performed). Since the average height of a random BST is O(log n) (with a small variance), these operations are pretty fast on average. However, the run-time in the worst case could be bad.

Exercise: come up with a sequence of n inserts such that the tree height is \Omega(n).

In this lecture, we describe several schemes for maintaining BSTs such that the height of the tree is (about) logarithmic in the number of nodes. One of the main ideas is to ensure that for each node in the tree the height of the left sub-tree and the height of the right-subtree are roughly equal. For a visual illustration of three of the trees described in this lecture, you can make use of the Java applet on this page.

Đọc tiếp »

Chủ đề C++, Cấu trúc dữ liệu | Tagged , , , , , | Phản hồi »

Các câu hỏi phỏng vấn [42]

NQH | 31/03/2012 | Bản để in Bản để in
  1. Cho một cây nhị phân với cấu trúc đỉnh như sau: 
    struct BTNode {
    int data;
    BTNode* left;
    BTNode* right;
}

    viết hàm void foo(BTNode* root) nhận vào con trỏ đến gốc cây và in ra các node trên cây theo thứ tự inorder mà chỉ được dùng O(1)-không gian. (Do đó, các loại giải pháp dùng recursion hay dùng stack là không được phép.)

  2. Tiếp theo câu trước, giả sử cây nhị phân cho trước là cây tìm kiếm nhị phân: data bên trái nhỏ hơn gốc và nhỏ hơn data bên phải. Viết hàm BTNode* bar(BTNode* root), sắp xếp lại các con trỏ, để biến cây nhị phân này thành một danh sách liên kết kép và vòng lặp (circular doubly-linked list). Hàm trả về con trỏ vào phần tử đầu của danh sách. Ở đây, ta sẽ hiểu left là con trỏ về phần tử trước (previous) và right trả về phần tử sau (next) trong danh sách liên kết kép.

Chủ đề Lập trình | Tagged , , | 1 phản hồi »

GLIIMPSE is so cool!

NQH | 27/03/2012 | Bản để in Bản để in

Chủ đề Tin tức đó đây | Tagged | 1 phản hồi »

Cây nhị phân và cây tìm kiếm nhị phân

NQH | 20/03/2012 | Bản để in Bản để in

Bài giảng cho lớp cấu trúc dữ liệu. Bạn nào rảnh đọc thì góp ý giùm, nhất là phần C++.

Bài trước: Danh sách liên kết và danh sách nhảy cóc
Bài sau: Các cây tìm kiếm cân bằng: AVL, đỏ đen, (2,4), và cây loe

1. Binary trees

1.1. Terminologies

A binary tree is a set of nodes connected in the following way. There’s a designated node called the root. Every node has two pointers named left and right. Each pointer either points to another node or is equal to NULL. All nodes are reachable from the root by a sequence of left/right pointers. We have seen a binary tree before when we discussed heap sort:

Đọc tiếp »

Chủ đề C++, Cấu trúc dữ liệu, Combinatorics, Thuật Toán | Tagged , , | 2 phản hồi »

Judea Pearl thắng giải Turing năm nay

NQH | 15/03/2012 | Bản để in Bản để in

Thông cáo.

Vài posts cũ của blog có nhắc đến ông.

Một điều có lẽ mọi người ít để ý là con trai ông, Daniel Pearl, là nhà báo nổi tiếng, bị bắt cóc và bị chặt đầu ở Pakistan. Phim A Mighty Heart do Angelina Jolie đóng là nói về cuộc đời của anh.

Chủ đề Tin tức đó đây | Tagged , | Phản hồi »

Danh sách liên kết và danh sách nhảy cóc

NQH | 12/03/2012 | Bản để in Bản để in

Bài giảng cho lớp cấu trúc dữ liệu. Bạn nào rảnh đọc thì góp ý giùm, nhất là phần C++.

Bài trước: Lớp Vector và phân tích khấu hao
Bài sau: cây nhị phân và cây tìm kiếm nhị phân.

1. Singly linked lists

The UBVector class and dynamic arrays in general have several disadvantages:

  • Inserting and removing an element somewhere in the middle of the sequence takes linear time. Furthermore, if the items we hold in the sequence are large, the cost of shifting a suffix of the array down one position is proportionally large.
  • A vector wastes \Omega(n) space in the worst case, where the constant inside \Omega(n) is propotional to the item size. We have to allocate space to hold about n items.
  • A vector is stored in a contiguous block of memory in the freestore (there’s a subtle difference with the heap but we couln’t care less). Sometimes, it is possible that the freestore has sufficient free space to store all elements of a vector, but it doesn’t have a sufficiently large contiguous block of memory to store the vector. This is called the fragmentation problem, which is very common in all kinds of memory/disk allocation tasks in operating system design.
  • Inserting and deleting from a vector are highly global operations: we shift an entire suffix of the underlying array. List updates are highly local: we only need to lock two adjacent elements. This advantage cannot be overlooked in a concurrent environment because we may want multiple threats to modify/access a llong list at the same time. In fact, locality is also a key advantage of linked lists over more elaborate search structures such as various types of binary search trees.

Đọc tiếp »

Chủ đề C++, Cấu trúc dữ liệu, Lập trình | Tagged , , , | 6 phản hồi »