Học Thế Nào

By NQH | Published: 16/04/2013 | Bản để in Bản để in

Các bạn đóng góp ý kiến, thảo luận, và bài vở cho trang này của các bác NBC, VHV, PT, nhé!

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

“Không quản lý được về an ninh”

By thaidn | Published: 10/04/2013 | Bản để in Bản để in

Trích từ đây:

[...]ông Vương Quang Khải, Phó Tổng Giám đốc Công ty VNG cũng cho rằng, các dịch vụ trong nước của VNG như Zing Mail, Zing Me… tuân theo rất nhiều chế tài của cơ quan quản lý trong khi các dịch vụ tương tự của nước ngoài như Yahoo Mail, Gmail, Facebook… thì không gặp phải bất cứ chế tài quản lý nào cả. Từ đó dẫn đến việc người dùng sẽ thích và sử dụng các dịch vụ nước ngoài vì không bị quản lý. VNG hi vọng thời gian tới sẽ có quy định để các doanh nghiệp trong và ngoài nước cùng “chơi” theo một luật để giúp CNTT Việt Nam phát triển. “Nếu cơ quan quản lý tiếp tục quản lý doanh nghiệp nội và ngoại như trên môi trường web thì VNG lo ngại chúng ta sẽ lại thua tiếp một lần nữa trên thị trường di động (mobile), giống như với thị trường mạng xã hội, máy tìm kiếm, email… dẫn đến thất thu về thuế và không quản lý được về an ninh”, ông Khải nhấn mạnh.

Quản lý an ninh là làm gì? Khoản 4, Điều 55 của Dự thảo nghị định quản lý Internet có quy định trách nhiệm của những công ty VNG như thế này (tôi in đậm những chỗ bên dưới, văn bản góc không có):

Điều 55. Trách nhiệm bảo đảm an ninh quốc gia, trật tự an toàn xã hội và phòng chống tội phạm trên mạng

4. Trách nhiệm của doanh nghiệp cung cấp dịch vụ Internet, viễn thông và nội dung thông tin trên mạng.

a. Triển khai các giải pháp, trang thiết bị kỹ thuật theo quy định của Bộ Công an để lưu trữ thông tin đưa vào, truyền đi trên mạng; ngăn chặn việc truy cập, truyền đưa thông tin có nội dung vi phạm Điều 5 của Nghị định này.

b. Xây dựng, ban hành quy định vận hành, khai thác, sử dụng dịch vụ Internet và nội dung thông tin trên mạng, Tổ chức việc đăng ký, quản lý và sử dụng thông tin cá nhân trên mạng theo quy định của Bộ Công an. Tuyên truyền, hướng dẫn, kiểm tra việc thực hiện đối với các đại lý Internet, người sử dụng dịch vụ, cán bộ, nhân viên trong nội bộ doanh nghiệp.

c. Cung cấp thông tin, phối hợp với đơn vị chức năng của Bộ Công an, các cơ quan Nhà nước có thẩm quyền thực hiện việc quản lý, kiểm tra, giám sát, phát hiện, ngăn chặn và xử lý các hành vi lợi dụng Internet, nội dung thông tin trên mạng vào hoạt động xâm phạm an ninh quốc gia và trật tự an toàn xã hội.

d. Ngừng ngay việc cung cấp dịch vụ Internet và thông tin trên mạng đối với các chủ thể lợi dụng các dịch vụ này để hoạt động chống lại Nhà nước Cộng hoà Xã hội chủ nghĩa Việt Nam, gây phương hại đến an ninh quốc gia khi có yêu cầu của cơ quan quản lý nhà nước có thẩm quyền.

e. Bố trí mặt bằng, điểm truy nhập mạng, các cổng kết nối, giao diện kết nối tại các điểm kết nối Internet quan trọng và những điều kiện kỹ thuật cần thiết cho các đơn vị chức năng thuộc Bộ Công an thực hiện nhiệm vụ bảo vệ an ninh quốc gia trong hoạt động Internet.

g. Phối hợp với cơ quan chức năng của Bộ Công an triển khai các biện pháp bảo đảm an ninh quốc gia, trật tự an toàn xã hội và phòng chống tội phạm trên mạng trước khi chính thức cung cấp dịch vụ. Thực hiện chế độ báo cáo đột xuất, định kỳ, cung cấp các thông tin cần thiết theo quy định của Bộ Công an.

h. Chịu trách nhiệm hướng dẫn đại lý Internet, điểm cung cấp dịch vụ trò chơi trực tuyến công cộng của doanh nghiệp thực hiện các quy định về bảo đảm an ninh quốc gia, trật tự an toàn xã hội và phòng chống tội phạm trên mạng của Bộ Công an trong hoạt động Internet và nội dung thông tin trên mạng.

i. Chịu sự thanh tra, kiểm tra việc chấp hành các quy định của pháp luật về bảo đảm an ninh quốc gia, trật tự an toàn xã hội và phòng chống tội phạm trên mạng của cơ quan quản lý nhà nước có thẩm quyền.

Như vậy VNG có đáng tin để chúng ta trao gửi thông tin cá nhân không? Câu trả lời của cá nhân tôi là không. Thật ra không chỉ riêng VNG mà tất cả các công ty Việt Nam đều phải thực hiện các điểm đã dẫn ở trên. Dẫu vậy tôi thất vọng khi VNG dùng lá bài “quản lý an ninh” để vận động chính quyền đưa ra chính sách có lợi cho họ.

Từ chỗ bị ép buộc, VNG bây giờ đã sỗ sàng gợi ý. Đây là một bước đi rất dài, chỉ tiếc là đi thụt lùi. Bao giờ thì ra được thế giới?

Chủ đề Chưa phân loại | Phản hồi »

Phân tích khảo sát góp ý dự thảo Hiến Pháp bằng Bổ Đề Johnson-Lindenstrauss

By NQH | Published: 03/04/2013 | Bản để in Bản để in

Các bác bên trang Cùng Viết Hiến Pháp vừa cho đăng bài phân tích kết quả khảo sát về bản dự thảo Hiến Pháp 2013. Phương pháp chính được dùng là MDS (đại khái PCA, tổng quát hơn xíu). Các bạn có thể nhận ra tinh thần của MDS mô tả trong bản phân tích trong bài đã viết về trị đặc trưng và vector đặc trưng.

Trong bản phân tích khảo sát Hiến Pháp thì cỡ khoảng {n=4000} điểm trong không gian {d = 12} chiều được chiếu xuống không gian {k = 2} chiều sao cho khoảng cách giữa các cặp ý kiến vẫn gần như là được bảo toàn. Ngoài ý nghĩa rõ ràng về mặt hiển thị dữ liệu một cách trực quan, giảm số chiều là một thành phần cực kỳ quan trọng không thể thiếu của các phân tích thống kê hiện đại. Bài Dimension Reduction: A Guided Tour của Christopher Burges (MSR) là một tham khảo nhập môn rất tốt! (Đề mục 4.2 nói về MDS.)

Một cách giảm số chiều là dùng (các biến thể của) bổ đề Johnson-Lindenstrauss, một bổ đề rất quan trọng trong thống kê, tính toán hình học, cơ sở dữ liệu, v.v. Có rất nhiều cách chứng minh bổ đề này. Trong bài này ta thảo luận chứng minh của DasGupta và Gupta, phần nào để minh hoạ thêm về cái mẹo của Bernstein. Trước hết ta phát biểu một cách đại khái bổ đề JL.

Bổ Đề 1 (Bổ đề JL — phiên bản hoa tay múa chân) Cho một tập {S} gồm {n} điểm trong không gian {\mathbb R^d}, thì tồn tại một ánh xạ {f: \mathbb R^d \rightarrow \mathbb R^k} với {k} “nhỏ” sao cho khoảng cách giữa hai điểm bất kỳ {\mathbf x} và {\mathbf y} trong {S} gần như là bằng với khoảng cách giữa hai ảnh {f(\mathbf x)} and {f(\mathbf y)} của chúng qua ánh xạ {f}. Ánh xạ thoả tính chất này thường được gọi là biến đổi Johnson-Lindenstrauss.

Đọc tiếp »

Chủ đề Xác suất & thống kê | Tagged | 20 phản hồi »

Giải thưởng Turing 2012

By Phan Dương Hiệu | Published: 21/03/2013 | Bản để in Bản để in

Giải thưởng Turing (được ví như giải Nobel của ngành Khoa học máy tính) lần này sẽ được trao cho Shafi Goldwasser và Silvio Micali. Các bạn có thể xem thông báo chính thức “Goldwasser, Micali Receive ACM Turing Award for Advances in Cryptography” tại đây.

Hai đóng góp nổi bật của Goldwasser và Micali là về mật mã xác suất và chứng minh tương tác/chứng minh không để lộ tri thức. Loạt bài PCP của anh Hưng liên quan mật thiết tới chứng minh tương tác. Ngoài ra, một giới thiệu vui về  chứng minh không để lộ tri thức các bạn có thể xem bài này.

Dưới đây mình sẽ bàn về bài báo Mật mã xác suất (Probabilistic Encryption). Bài báo này cùng lúc đưa vào : một cách nhìn mới về việc mã hoá ; những khái niệm nền tảng về an toàn ; và một phương pháp chứng minh tính an toàn của các hệ mã.

Đọc tiếp »

Chủ đề Bảo mật và mật mã học, Lý thuyết mã hóa, Lý thuyết tính toán | 1 phản hồi »

Những toilet không cửa hay là tại sao phải biết thiết kế

By thaidn | Published: 15/03/2013 | Bản để in Bản để in

Tôi rất thích đoạn phim này. Có lẽ là do tôi đồng cảm với nhân vật. Không hẳn là tôi bị hội chứng sợ dơ, nhưng tôi rất ngán các nhà vệ sinh có cửa nắm thế này và hơn một lần tôi cũng đứng chờ có người mở cửa vào để đi ra mà không phải chạm tay :-) .

Tôi bắt đầu chú ý đến thiết kế của các toilet công cộng từ cách đây vài năm. Tôi thấy thiết kế toilet không phải chuyện đơn giản. Có rất nhiều vấn đề, đôi khi rất nhỏ thôi, mà nếu làm không tốt sẽ có thể gây ảnh hưởng đến sức khỏe của nhiều người.

Đọc tiếp »

Chủ đề Chưa phân loại | 2 phản hồi »

Tây tiến cùng Hiến pháp

By Nguyễn Xuân Long | Published: 06/03/2013 | Bản để in Bản để in

Lấy cảm hứng từ Tây tiến:

Tây tiến cùng Hiến pháp

Hiến pháp đâu rồi Tây tiến ơi!
Nói về chính trị nói khơi khơi
Điều 4, đất đai hai tử huyệt
Lập hành tư pháp rối bời bời
Chủ nghĩa xã hội dốc thăm thẳm
Heo hút cồn mây chết bao đời
Nghị quyết lên cao nghị quyết xuống
Bầy sâu tham lam tít mù khơi
Ông tổng giãi lòng không kỷ luật
Gục trên bục gỗ mắt lưng tròng!
Oan khiên Tiên Lãng trời gầm thét
Chuyện “Bên thắng cuộc” chấn lòng người
Nhớ đồng chí X bị hun khói
“Tôi có làm sao Ðảng hiểu tôi!”

Ðất nước bừng lên chuyện sửa sang
Kìa em hiến pháp tự bao giờ
Khèn lên man dại tình giai cấp
Dân chủ pháp quyền ai hay mơ
Người vào Bô xít chiều sương ấy
Có thấy bẩy hai cụ trên hình
Có nhớ ký vào trang kiến nghị
Trôi dòng thác lũ hoa đong đưa

Tây tiến toàn dân muốn tự do
Biển Ðông xanh thẳm lắm sóng ngầm
Quân đội nhất định vì Dân tộc
Cho đảng suy thoái trong hòa bình
Các trí thức cùng viết Hiến pháp
Bloggers, facebooks thổi lửa xanh
Ðắc Kiên dõng dạc đòi dân chủ
Nhân sĩ gầm lên khúc độc hành

Tây tiến người đi không hẹn ước
Ðường lên thăm thẳm một chia phôi
Ai tìm Hiến pháp mùa xuân ấy
Hồn về Dân Nước chớ buông xuôi

CHI 6/3/2013
N.X.L.

Chép lại bài thơ Tây Tiến nổi tiếng của cụ Quang Dũng về một giai đoạn hào hùng của dân tộc:

Đọc tiếp »

Chủ đề Thơ | Phản hồi »

All the lonely people/ where do they all come from

By Nguyễn Xuân Long | Published: 27/02/2013 | Bản để in Bản để in

Nhân đọc Nguyễn Đắc Kiên.
Phiên bản Ray Charles của Eleanor Rigby (the Beatles).

Chủ đề Âm Nhạc | Tagged | Phản hồi »

Thơ Nguyễn Đắc Kiên

By NQH | Published: 26/02/2013 | Bản để in Bản để in

Thấy bài này thơ này bên nhà Hoà Thượng hay quá

(Thơ Nguyễn Đắc Kiên)

tôi chưa thấy một đêm nào dài thế,
bốn ngàn năm, giờ lại ngót trăm năm.
hết phong kiến độc tài, đến lũ bạch tuộc thực dân,
hết quân, hết vương, đến lũ tượng thần chủ nghĩa.

bao thế hệ siết rên trong gọng kềm nô lệ.
chuyên chế dã man đục rỗng chí con người.
cha tôi, ông tôi, bao thế hệ ngủ vùi.
tôi chưa thấy một đêm nào dài thế.

không ánh mặt trời, bóng tối chí tôn,
lũ quỷ ám thừa cơ toàn trị,
khủng bố dã man, reo rắc những kinh hoàng,
biến lẽ sống thành châm ngôn “mày phải sợ”.

mày phải sợ mày ơi mày phải sợ,
sợ nữa đi có sợ mãi được không,
cốt tủy mục rỗng rồi trí óc cũng tối đen,
mày lại đẻ ra lũ cháu con “biết sợ”.

bao thế hệ đã ngậm ngùi mắc nợ,
lũ chúng ta lẽ nào lại mắc nợ mai sau,
còn chần chừ gì mà không tỉnh dậy mau,
sống cho xứng danh xưng con người trên mặt đất.

tôi chưa thấy một đêm nào dài thế,
cũng chưa thấy có ngày mai nào không thể.
vì người ta cần ánh mặt trời,
tỉnh dậy đi lũ chúng ta ơi!

hà nội, 25.2.2012

Đọc tiếp »

Chủ đề Lịch sử Việt Nam, Tin tức đó đây | Tagged | 19 phản hồi »

Bốn thế giới ảo và một thế giới thực…

By Phan Dương Hiệu | Published: 18/02/2013 | Bản để in Bản để in

Bốn thế giới ảo và một thế giới thực…
(Từ “P=NP” đến Mật mã hóa khóa công khai)

Gần 20 năm trước, Russell Impagliazzo đưa ra định nghĩa rất thú vị về 5 thế giới khác nhau (cseweb.ucsd.edu/~russell/average.ps). Chúng ta sống ở một trong 5 thế giới đó, nhưng không biết chắc mình sống trong thế giới nào. Gần 20 năm trôi qua, vẫn chưa có thế giới nào chia tay chúng ta. Hiện vẫn đang có 5 thế giới quanh ta, và ta không biết là mình đang ở đâu.

Đến một ngày, nếu có anh hùng nào may mắn chứng minh chúng ta đang thực sự sống ở đâu, thì cũng là ngày tận thế của 4 thế giới ảo còn lại, điều đó thật buồn và những người còn lại thật kém may… Chẳng hạn một chứng minh P=NP sẽ là ngày tận thế của 4 thế giới. Tuy nhiên, ta sẽ thấy rằng, một chứng minh P khác NP thì chỉ làm 1 thế giới suy tàn và vẫn còn lại 4 thế giới lung linh :) Vì vậy, nếu Bụt hiện xuống và cho chọn giữa “ P=NP” hay “P khác NP” thì mình sẽ chọn “P khác NP” ^_^

Impagliazzo minh họa 5 thế giới một cách rất xuất sắc để ai cũng hiểu được, thông qua câu chuyện tưởng tượng giữa thầy giáo Grouse và cậu học trò Gauss. Cậu trò Gauss thông minh nổi tiếng, trên lớp thầy giao bài nào cũng giải ngon ơ rồi rỗi rãi chọc phá các bạn làm thầy giáo rất là cay cú. Ông thầy Grouse quyết tâm tìm những bài toán siêu khó để nhằm mục đích làm cho Gauss bớt kiêu.

Và từ đó hình thành 5 thế giới theo định nghĩa của Impagliazzo:

Đọc tiếp »

Chủ đề Chưa phân loại | 1 phản hồi »

Kích thước tối đa của mảng 1 chiều dùng C/C++

By NQH | Published: 14/02/2013 | Bản để in Bản để in

Bạn Hoang Nguyen có câu hỏi thú vị:

em đã làm quen với lập trình vài năm gần đây nhưng chưa khi nào phải xử lý dữ liệu với kích thước lớn đến hàng triệu. Em muốn hỏi là có cách nào để tăng kích thước lưu trữ của mảng một chiều không? Em thử trong free-Pascal thì thấy mặc dù có thể khai báo kích thước mảng lên đến hàng trăm triệu nhưng khi chạy chương trình thì lại báo lỗi. Trong C/C++ thì em thấy chỉ khai báo kích thước tối đa của mảng là 500.000. Thanks mọi người.

Kích thước của mảng tuỳ vào vài yếu tố, quan trọng nhất là cấu hình máy (32 bits hay 64 bits), kích thước bộ nhớ/ổ cứng, và … tuỳ theo bạn lập trình thế nào nữa. Tại vì, nếu bạn khai báo mảng tĩnh dùng cú pháp int a[SIZE]; thì mảng a được đặt ở trên stack, và do đó nó bị giới hạn bởi kích thước tối đa của stack, thường mặc định là nhỏ; tuy nhiên bạn có thể tăng kích thước nó lên.

Lấy ví dụ, chương trình sau chạy sẽ bị lỗi segmentation fault

#include <iostream>
using namespace std;

#define S 5000000

int main() {
    int a[S];
    for (size_t i=0; i<S; i++) 
        a[i] = i;
}

Tại vì kích thước mảng này to hơn kích thước stack mặc định. Nhưng chương trình sau không bị lỗi vì cái heap chứa đủ (5 triệu) nhân 4 = 20 triệu bytes.

#include <iostream>
using namespace std;

#define S 5000000

int main() {
    int* a = new int[S];
    for (size_t i=0; i<S; i++)
        a[i] = i;
}
Chủ đề C++ | Tagged , , | 1 phản hồi »

I miss my Valentine’s Day

By Lê Hoàng Long | Published: 14/02/2013 | Bản để in Bản để in

Xin giới thiệu đến quý khán giả một bài hát cho ngày lễ Tình Nhân. Chúc mọi người hạnh phúc và… ngủ ngon :-) .
I miss my Valentine’s Day

Chủ đề Âm Nhạc, Vui - Giải Trí | 1 phản hồi »

Tập làm bánh chưng (và nghĩ về Hiến pháp)

By Nguyễn Xuân Long | Published: 03/02/2013 | Bản để in Bản để in

Picture 2

Ngày hai ba tháng chạp. Tập tọe gói bánh chưng. Và nghĩ về Hiến pháp.

Giải thích cho con: Chiếc bánh chưng. Từ thuở vua Hùng. Tích Lang Liêu. Chuyện đất trời người Việt. Chiếc bánh xanh. Lung linh ảnh hình. Của nước mình rất xa. Nhạt nhòa. Giữa tuyết trời xứ người tím ngát.

Cứ hàng năm màu xanh bánh chưng này. Làm tôi bồi hồi về một thời đói khát. Nhưng nó cũng mang cho tôi một vài niềm vui và hy vọng. Có lẽ vì cái màu xanh thắm giữa tiết trời lạnh lẽo ấy. Có nếp trắng tinh khôi với ba chỉ, đậu xanh. Kết keo âm ỉ. Rộn lòng người bên bếp lửa hồng ấm áp …

Còn Hiến pháp?
Nó là thứ mà họ lại hô hào góp ý, sửa sang.
Cứ như thể đến ngày tàn cuối năm
Ta lại được lôi vài thứ ra lau chùi đánh bóng
Vôi ve một tí mái hiên, cánh cổng
Chờ đón tất niên.
Dẫu nó cho ta một cảm giác mới mẻ một cách tạm thời
Tôi sợ mọi chuyện sẽ lại xảy ra như kỳ tắm rửa vừa rồi.

Nghĩ rằng rồi sẽ chẳng có thay đổi thực sự gì cả
Hiến pháp chỉ có thể thay, khi trong xã hội hình thành những tầng lớp có thế lực.
Họ có một nhu cầu đổi thay thành thực:
Để giành chính danh, chính nghĩa, cả những lợi quyền.
Và họ phải đủ sức mạnh để làm nên thay đổi.
(Không phải ngẫu nhiên những thay đổi hiến pháp bản chất nhất
Chỉ có được khi một đất nước giành độc lập
Khi những người đặt bút viết nên hiến pháp
Họ nghĩ trước tiên đến quyền lợi của Dân rồi mới tới bản thân mình).

Dẫu thế nào, tôi vẫn mong một ngày đất nước này sẽ lại hồi sinh
Còn những kẻ có tâm có quyền có chức
Cắn miếng bánh chưng xanh ngày xuân
sẽ thử nghĩ một lần về gốc
Của dân tộc
Đất nước này
Của sự tích bánh chưng bánh giầy:

Vào thời dựng nước cách đây mấy nghìn năm, Hùng Vương thứ 6 trị vì nước Việt. Một ngày nọ vua cha thấy mình đã già, cần người khôn ngoan nối dõi cai trị đất nước tốt đẹp. Sau khi đã sát hạch các hoàng tử về văn tài cũng như võ công, nhà vua rất đẹp lòng về tài nghệ song toàn của các hoàng tử nhưng còn phân vân chưa biết chọn ai. Một ngày nọ vua cha cho vời các con đến và bảo rằng: “Ai trong các con có thể nấu món ăn nào ngon nhất, kẻ ấy sẽ được ta truyền ngôi cho”.

Bảo bối của Lang Liêu, xin nghi lại đây cho rõ:

“Dưới Trời và trên Đất không có gì quí hơn hạt gạo mọc khắp đồng ruộng đất nước. Không cần phải sục sạo rừng rú hay biển sâu để tìm. Vậy con hãy chọn loại gạo tốt nhất, đó là thứ gạo nếp trên cánh đồng nhà, lấy thêm đậu xanh trong vườn nhà hay mua của vườn nhà hàng xóm, rất dễ gặt hái, sau đó mua thịt lợn nơi trại nuôi lợn trong làng và năm thứ gia vị ở sau vườn. Hãy vút gạo cho kỹ, đãi đỗ xanh sạch vỏ, gia vị tiêu hành muối nước mắm cho thịt heo, hái lá chuối hay lá dong sau vườn, rửa sạch và chẻ tre làm dây buộc. Cho gạo cùng thịt trên lá, lớp gạo bên dưới, đậu xanh và thịt heo ở giữa hai lớp gạo, gói lại thành hình vuông, biểu tượng của Đất, rồi gói đòn dài hình tròn, biểu tượng của Trời, lấy lạt buộc kỹ, sau đó bỏ vào nồi nước sôi, luộc chúng một đêm rồi lấy ra để ráo nước. Con sẽ thấy phép mầu hiện ra”.

Được cái,
Bây giờ đun bếp ga
Cũng khỏe hơn nhiều cái thời canh bếp than bếp củi….

A2, 3/2/2013

Chủ đề Thơ | 5 phản hồi »

Thuật toán Yannakakis

By NQH | Published: 10/01/2013 | Bản để in Bản để in

Bài trước nói về độ phức tạp của bài toán định trị truy vấn hội, trong đó ta thảo luận tầm quan trọng của việc phân biệt độ phức tạp biểu thức và độ phức tạp dữ liệu của một truy vấn. Một cách vắn tắt, nếu ta cố định kích thước của CSDL và xem bản thân truy vấn là input của bài toán thì độ phức tạp của bài toán định trị phép truy vấn hội được tính theo độ phức tạp biểu thức. Khi đó, từ bài báo kinh điển của Chandra và Merlin từ năm 1977 ta đã biết rằng bài toán định trị truy vấn hội là bài toán NP-khó. Còn nếu ta xem bản thân truy vấn là cố định còn CSDL là input thì ta đang xét độ phức tạp dữ liệu của bài toán. Độ phức tạp dữ liệu là số đo độ phức tạp “tốt” hơn một chút vì trên thực tế các CSDL có kích thước lớn hơn các phép truy vấn nhiều. Vardi đã chứng minh rằng bài toán {\mathsf{BCQ}} nằm trong lớp {\mathsf{LOGSPACE}} tính theo độ phức tạp dữ liệu; nghĩa là bài toán rất dễ. Rất tiếc rằng độ phức tạp dữ liệu vẫn chưa phải là số đo độ phức tạp tốt nhất vì thời gian chạy của thuật toán có thể là, ví dụ, {|\mathcal A|^{|q|}}, trong đó {\mathcal A} là CSDL còn {q} là truy vấn. Cuối cùng, hiện nay người ta dùng độ phức tạp tham số (parameterized complexity) của các truy vấn làm cái khung phân tích thuật toán định trị truy vấn. Papadimitrious và Yannakakis đã chứng minh rằng bài toán {\mathsf{BCQ}} là bài toán {\mathsf W[1]}-đầy đủ, và do đó rất khó có khả năng tồn tại thuật toán cho bài {\mathsf{BCQ}} với thời gian chạy là {O(f(|q|) \cdot |\mathcal A|^c)}, trong đó {f} là một hàm tính được và {c} là một hằng số. Nếu tồn tại thuật toán như vậy thì {\mathsf W[1] = \mathsf{FPT}}, và từ đó suy ra giả thiết thời gian mũ (Exponential Time Hypothesis) sẽ bị sai.

Trong bài này, ta xét hai lớp con quan trọng của các truy vấn hội:

  • lớp các truy vấn hội phi chu trình (acyclic conjunctive queries)
  • lớp các truy vấn hội có độ rộng cây bị chặn (bounded tree-width queries)

Ta sẽ chứng minh rằng cả hai lớp truy vấn này đều có thể định trị được trong thời gian đa thức. Để định nghĩa thế nào là truy vấn hội phi chu trình và truy vấn hội có độ rộng cây bị chặn thì ta cần đến khái niệm siêu đồ thị của truy vấn hội.

Đọc tiếp »

Chủ đề Cơ sở dữ liệu, Thuật Toán | Tagged , , , , | 1 phản hồi »

Mật mã trong bầu cử điện tử

By Phan Dương Hiệu | Published: 03/01/2013 | Bản để in Bản để in

Đây là bản nháp cho bài viết theo lời mời của báo Tia Sáng cho số báo Tết. Rất mong nhận được ý kiến đóng góp của các bạn để mình có thể chỉnh sửa bài viết tốt hơn. Mình phải gửi bài trước 20/1. Sau bài tổng quan về mật mã khóa công khai cũng đăng trên Tia Sáng trong số kỷ niệm 20 năm (tại đây và ở phiên bản đầy đủ hơn ở đây ), bài này giới thiệu một ứng dụng cụ thể của lý thuyết mật mã.

Cập nhật (09/1): Sửa một số phần theo góp ý của bạn HNTung; giải thích thêm phần chống bán phiếu bầu với chứng minh tương tác; bổ sung phần “Tài liệu tham khảo”; bổ sung mục “Ngoài lề” với ví dụ về một hệ mã xác suất khóa công khai và có tính chất đồng cấu (hệ mã Paillier).

——————–

Một sự vận hành các hệ thống bầu cử tốt là một điều kiện cần tất yếu của một chế độ dân chủ. Tuy nhiên, hiện tại các hệ thống bầu cử đều chưa đạt được đồng thời hai yêu cầu cần thiết sau đây của một hệ thống bầu cử dân chủ:

-       Tính kiểm tra được: việc kiểm phiếu được kiểm tra một cách công khai và mỗi cử tri đều có thể kiểm tra chắc chắn rằng lá phiếu của mình đã được tính.

-       Tính tự do trong lựa chọn: mỗi cử tri đều được đảm bảo tuyệt đối quyền lựa chọn lá phiếu của mình, không bị ai ép buộc và cũng không thể bán phiếu bầu của mình cho bất cứ bên nào.

Trong một số cuộc bầu cử, để đảm bảo yêu cầu thứ nhất thì người ta công khai danh sách ai đã bầu cho ai, và vì thế việc kiểm phiếu là hoàn toàn công khai và ai cũng có thể kiểm tra phiếu bầu của mình đã được tính. Tuy nhiên, điều đó lại không đảm bảo quyền hoàn toàn tự do lựa chọn của cử tri: người bầu có thể bị khống chế buộc phải bầu cho một ứng cử viên; hoặc người bầu có thể bán lá phiếu của mình vì chứng minh được cho người mua thấy mình đã bầu cho ai.

Để tránh những hạn chế của việc cử tri bị khống chế hoặc việc mua bán phiếu bầu, hầu hết các cuộc bầu cử chọn việc đảm bảo yêu cầu thứ hai bằng cách ẩn danh lá phiều bầu: cử tri đến trung tâm bầu cử, được phát một lá phiếu bầu, chọn ứng cử phiên và cho lá phiếu ẩn danh vào thùng phiếu. Cử tri do vậy hoàn toàn tự do lựa chọn và bản thân họ khi ra khỏi phòng bỏ phiếu cũng không thể chứng minh là mình đã bỏ cho ai và do vậy cũng không bán được phiếu bầu. Cách làm này tuy vậy lại không thể đảm bảo yêu cầu thứ nhất: một khi lá phiếu đã cho vào hòm phiếu, cử tri buộc phải đặt tin tưởng vào người kiểm phiếu và không có cách nào chắc chắn được liệu lá phiếu của mình sẽ được tính và cũng không thể kiểm tra liệu lá phiếu của mình có bị thay đổi. Việc buộc phải đặt sự tin tưởng tuyệt đối vào người kiểm phiếu đã đem đến những sai sót ở những mức độ lớn nhất: năm 2000, hơn 50000 phiếu ở quận Brown bị bỏ sót và việc Bush thắng AlGore ở Florida với 537 phiếu chênh lệch (và dẫn tới thắng cuộc bầu cử tổng thống)  đã gây ra những cuộc tranh luận nảy lửa ; mới đây năm 2012, trong cuộc bầu chủ tịch đảng cộng hòa Pháp, Jean-François Copé được tuyên bố thắng cử với chênh lệch sít sao so với François Fillon nhưng cuối cùng trưởng ban kiểm phiếu đã phải thừa nhận có đến hơn 300 phiếu của một số vùng bị bỏ sót mà nếu tính những phiếu này thì kết quả bị đảo ngược và François Fillon lại vượt hơn 26 phiếu.

Đọc tiếp »

Chủ đề Bảo mật và mật mã học | 4 phản hồi »

Một blog hay về thống kê và học máy

By Nguyễn Xuân Long | Published: 01/01/2013 | Bản để in Bản để in

Giới thiệu với các bạn blog của Larry Wasserman. Với tôi đây là blog thú vị nhất về chuyên ngành này ở thời điểm hiện tại.

Wasserman là GS khoa Thống kê và khoa Học máy ở Carnegie Mellon University, có viết một số sách giáo khoa rất được ưa chuộng về thống kê (với những tên rất kêu: “All of Statistics”, “All of Nonparametrics”). Là một trong số ít các nhà thống kê hàng đầu tạo được dấu ấn trong cả hai cộng đồng làm về thống kê và học máy; cũng là một trong số ít người có những đóng góp giá trị trong cả thống kê Bayes và thống kê tần suất…. Một trong những nhà thống kê mà tôi yêu thích.

Chủ đề Chưa phân loại | Phản hồi »