Bài toán ba lô - The kanpsack Algorithm

Bài toán: Cho 1 cái ba lô được nhét đầy các đồ vật cho ở hình dưới (trọng lượng tính theo grams). Biết rằng ba lô nặng 3064 grams, bạn có thể xác định những vật có trong ba lô đó không ?

Vấn đề trở nên phức tạp và khó tính toán khi trong ba lô chứa 100 đồ vật. Tuy nhiên, nếu cách sắp xếp khối lượng đồ vật có vài thông tin đặc biệt "trapdoor" đã được biết trước, và người có được thông tin đó sẽ dễ dạng tìm được thông tin bí mật. Tức là, 100-bit thông tin đó xác định được những đồ vật có trong ba lô.

Read More

Mã hóa XOR - Phép mã hóa đơn giản - C#

Mã hóa Exclusive-OR là phép mã hóa đối xứng sử dụng hàm đại số boolean XOR. Do tính đối xứng cả hai encryptor và decryptor phải biết được khóa mã, trong khi thuật toán xử dụng thật đơn giản, gần như là không thể phá vỡ.

Các vấn đề thực ta phải quan tâm: Dễ bị khớp mẫu, nhưng điểm yếu này có thể tránh được thông qua việc nén trước thông tin (để có thể loại bỏ các mẫu).  Một số điều lưu ý:

1. XOR áp dụng cho 1 chuỗi văn bản không là thuật toán mã hóa mạnh.
2. Mã hóa thông tin trong ứng dụng XML dễ bị đụng độ với các ký tự chuẩn trong XML
3. Nếu cần mã hóa mạnh, KHÔNG sử dụng thuật toán XOR đơn thuần. Cần có các hệ mật mã an toàn đang được sử dụng (DES, TDES, AES, RC4, RC6, IDEA .. RSA, Elgamal, hệ mật sắp ba lô, hệ mã tuyến tính [n, k, d], ...) hoặc cần được sử dụng phức hợp.

Read More

Tổng quan về hàm băm

Hàm băm là hàm chuyển đổi một thông điệp có độ dài bất kỳ thành một dãy bit có độ dài cố định. Các hàm băm nhận một chuỗi bit có chiều dài tùy ý (hữu hạn) làm dữ liệu đầu vào và tạo ra một chuỗi bit mới có chiều dài cố định n bit (n > 0), được gọi là giá trị băm hay mã băm.

Tính chất cơ bản của hàm băm:

    Tính kháng tiền ảnh: Với mọi đầu ra y cho trước không thể tính toán để tìm được bất kỳ dữ liệu đầu vào x’ nào sao cho giá trị băm h(x’) bằng giá trị đầu ra y đã cho.
    Tính kháng tiền ảnh thứ hai: Với mọi dữ liệu đầu vào x1 cho trước, không thể tính toán để tìm ra được bất kỳ một đầu vào x2 nào (x1 ≠ x2) sao cho giá trị băm h(x2) = h(x1).
    Tính kháng xung đột: Không thể tính toán để tìm được hai dữ liệu đầu vào x1 ≠ x2 sao cho chúng có cùng giá trị băm.

Read More

Sử dụng otomat cài đặt các phép toán cơ sở

Bài toán: Cho 2 số a, b ở cơ số n bất kỳ, hãy cài đặt các phép toán +, -, *, /
Trong đó: a, b được biểu diễn tương tự như hệ đếm cơ số 10 quen thuộc của chúng ta, tức là:

a = a(k)a(k - 1)… a(i) … a(2)a(1) ; với a(i) thuộc [0, n – 1]

A. Biểu diễn nhị phân (hệ đếm cơ số 2) cài đặt phép toán: +, -
Cách 1: Phương pháp thuần túy, sử dụng các lệnh IF THEN ELSE
Giải thuật:

Nhận xét: Với phương pháp thuần túy này áp dụng cho hệ đếm cơ số lớn, cơ số 256 chẳng hạn thì độ phức tạp về thời gian là rất lớn. Và ở trên các phép toán cơ sở là gán và so sánh.

Read More

Quan Điểm Thực Hành - Độ Phức Tạp Thuật Toán

Giả sử có 1 thuật toán A nào đó.
Trong A có 1 loại thao tác P có đặc điểm sau:

1. Tổng thời gian chạy P ảnh hưởng chủ yếu đến thời gian chạy của A.
2. P lặp đi lặp lại nhiều lần

Ta dùng P làm thao tác cơ sở, tgian thực hiện P dùng làm đơn vị đo thời gian.
Số lần thực hiện P trong giải thuật A sẽ dùng làm đại lượng đo thời gian chạy của A, đại lượng này được gọi là độ phức tạp tính toán về mặt thời gian của giải thuật A với thao tác cơ sở là P

Read More