Trang 2 trên tổng số 2 Đầu tiênĐầu tiên 12
Từ 11 tới 20 trên tổng số 20 kết quả

Đề tài: Mã hóa văn bản gửi ra ngoài hành tinh

  1. #11
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    495

    Mặc định Mã hóa văn bản gửi ra ngoài hành tinh

    À, còn 1 ngoại lệ nữa mà mình nhận thấy sau khi đọc kỹ file nguồn. Ở khai báo decode(n,x) họ yêu cầu "Decode x, up to n+1 chars, to C-string." Phải chăng họ muốn decode phải tạo ra kết quả x là một C-string (đóng) bằng mọi giá, trong bất cứ trường hợp nào? Không phải thế.

    Giả sử mã hóa rồi giải mã một chuỗi byte a bằng N = encode(m,a) và K = decode(m,a), gọi a(0) là giá trị ban đầu của a, a(1) là [giá trị của] a sau encodea(2) là [giá trị của] a sau decode. Nếu decode luôn đóng a(2) lại thì với m đủ nhỏ, sẽ gặp lỗi probably memory violation (dòng 84) hoặc length mismatch (dòng 85) và kể cả khi ta cố tình "bịp bợm" bằng cách trả lại một số K nào đó qua được 2 phép kiểm thử này thì cũng sẽ gặp lỗi memory violation (dòng 86) hoặc wrong original (dòng 87). Vậy, họ muốn gì?

    Mình nghĩ rằng họ muốn nếu a(0) vẫn mở ở độ dài m+1 thì a(2) bằng a(0) ở m+1 ký hiệu đầu tiên và vì thế, nói riêng, a(2) cũng phải [là một C-string] mở. Mình nhấn mạnh một C-string mở không phải là một C-string.

    Từ đó suy ra yêu cầu cho decode và cả encode. Ở bất cứ độ dài nào mà a(0) chưa đóng, nếu encode đóng a(1) là lỗi. Ở bất cứ độ dài nào mà a(1) chưa đóng, nếu decode đóng a(2) là lỗi. Nói một cách nôm na thì encodedecode phải mã hóa và giải mã chính xác về nguyên bản kể cả khi nguyên bản ấy là bất hợp lệ; họ không xem việc sửa sai dữ liệu là trách nhiệm của encodedecode.

    Chú ý rằng a(1) là một A-string, một khái niệm còn chưa được định nghĩa nói chi đến tính đóng mở của nó, nhưng yêu cầu này áp dụng bất kể ta định nghĩa như thế nào. Người ngoài hành tinh không biết và xem ra họ chẳng thèm biết đến định nghĩa. Và họ không thèm biết có lẽ bởi vì họ biết chắc rằng định nghĩa nào đó phải tồn tại: chúng ta không có cách nào truyền độ dài bản mã cho decode ngoài cách biểu diễn độ dài này ngay trong bản mã, tương tự như chúng ta vẫn làm với các C-string.

    EDIT: Thậm chí, mình còn có linh cảm chưa thể chứng minh, dù có muôn vàn cách mã hóa khác nhau nhưng cách định nghĩa A-string chỉ có một mà thôi. Nếu giả thuyết này đúng, người ngoài hành tinh chắc là đã biết và họ nghĩ chúng ta cũng biết hoặc, nếu chưa biết, thì cũng sẽ sớm tự tìm ra.

    - - - Nội dung đã được cập nhật ngày 22-10-2017 lúc 02:21 AM - - -

    Ở bài #1, mình diễn giải rằng đề bài được viết trong file nguồn C và cơ bản cả file là đề bài. Hôm nay, sau 1 tuần đọc và nghiền ngẫm, mình nhận ra rằng diễn giải đó chưa chính xác.

    Mọi comment viết trên một dòng riêng (hơn là viết ở cuối một dòng mã nguồn) đều đặc tả yêu cầu. Tuy nhiên, comment mô tả hàm test là yêu cầu mà người ngoài hành tinh đã giải xong -- nó không phải là đề bài đối với chúng ta.

    Chỉ có 2 dòng mã nguồn đặc tả yêu cầu. Đó là 2 dòng khai báo hàm encodedecode. Tuy nhiên, trong hàm main có hai dòng (hai lời gọi take(...,FSAMPL,...)) hơi mâu thuẫn với yêu cầu rằng dữ liệu là văn bản thực của ngôn ngữ loài người, vì chúng loại trừ hai loại văn bản thực: văn bản chỉ có 1 ký hiệu lặp đi lặp lại và văn bản chỉ toàn ký hiệu liên tiếp khác nhau. (Chính file nguồn C này là một ví dụ.) Nên nói main đặc tả dữ liệu thì cũng có một phần (vô cùng nhỏ) đúng.

    Mọi dòng mã nguồn khác đều không thể hiện đề bài. Nói riêng, các lời gọi takefail chỉ kiểm chứng những định lý (theo một nghĩa nào đó) suy từ các yêu cầu đặc tả, trong giả định rằng những yêu cầu đó đã được đáp ứng. Các hàm chỉ làm đúng những việc như cái tên của chúng đã nói lên; test() là "test", và main() là "main". Không hơn không kém.

    (Thật ra, mình cũng không chắc chắn đã tìm được chứng minh chính xác cho tất cả những điều mà mình nghĩ là "định lý" trên. Nhưng mình đã thấy được cốt lõi vấn đề. Cốt lõi ấy không bác bỏ "định lý" nào cả. Cốt lõi ấy đã giúp mình viết được code qua được test. Vậy, nếu test họ lập dư một chút, sai một chút thì đối với mình cũng có quan trọng gì đâu?)

    Giải thích rõ ràng mình đã "đọc và nghiền ngẫm" như thế nào để đi đến diễn giải mới như trên cũng chính là công bố [hầu] hết cả lời giải cho bài tập này. Mình sẽ hoãn "cái sự sung sướng" ấy lại một thời gian, để khỏi làm mất đi "cái sự sung sướng" ấy của người khác.
    Đã được chỉnh sửa lần cuối bởi Ada : 22-10-2017 lúc 02:56 AM.
    -...- -.- .. .-.. .-.. - .... . -... . .- ... - .-.-.

  2. #12
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    495

    Mình đã viết một test riêng, có thể dùng thêm bên cạnh test của người ngoài hành tinh.

    C Code:
    1. void test2(int g, int n)
    2. /*
    3.  * Do a random sequence of n encode-or-decode actions then the reverse
    4.  * sequence of counter-actions on a memory sector, which should revert
    5.  * to its original content when the sequences complete.
    6.  *
    7.  * Report failure using g as test case ID, and exit.
    8.  */
    9. {
    10.  long const MEM=256;
    11.  char x[MEM], y[MEM];
    12.  for(long i=0;i<MEM;i+=1) x[i]=y[i]=rand();
    13.  unsigned const a0=123456789, b0=987654321, a1=102505021, b1= -b0*a1;
    14.  fail(a0*a1-1, FLOGIC, "Bad reverse PRNG.",g);
    15.  long const m=176; /* Even point: Pr[strlen(x)<=m | x random] ~ 0.5 */
    16.  take(m<MEM, FLOGIC, "Logical bug: precondition #4.",g);
    17.  fail(m< -1, FLOGIC, "Logical bug: precondition #5.",g);
    18.  unsigned const msb=(unsigned)(-1)/2+1; /* MININT */
    19.  unsigned r = rand();
    20.  for(int k=n;k;k-=1){r = r*a0+b0; r&msb ? encode(m,x) : decode(m,x);}
    21.  for(int k=n;k;k-=1){r&msb ? decode(m,x) : encode(m,x); r = r*a1+b1;}
    22.  fail(memcmp(x,y,MEM), FSECUR, "Bad algo: non-bijective coding.",g);
    23. }

    Test này được viết để có thể nối hoặc chèn vào file nguồn C của đề bài (xem bài #1). Test được kích hoạt, ví dụ, 1E4 lần, bằng cách chèn vào hàm main một dòng lệnh

    C Code:
    1. for(int n=(int)1E4;n;n-=1) test2(10,101);

    Khi ấy, mỗi lần gọi, nó sẽ thực hiện một chuỗi "ngẫu nhiên" 101 hành động (mã hóa hoặc giải mã) trên một vùng nhớ được khởi tạo với nội dung ngẫu nhiên, sau đó thực hiện chuỗi 101 hành động nghịch theo trình tự ngược để "undo" chuỗi vừa rồi. Kết quả kỳ vọng là nội dung ban đầu của vùng nhớ sẽ được khôi phục.

    Test này dựa trên một yêu cầu suy được từ đề bài: encode phải là toàn ánh và, do đó, decode cũng vậy.

    Test này yếu hơn test bài #1 (bạn đọc tự đánh giá), nhưng cũng có chỗ lợi hại riêng của nó. Để dùng test bài #1 ta phải chọn dữ liệu mẫu hợp lệ và dù mẫu rất lớn, nhưng số lượng mẫu không nhiều. Còn test này tạo ra mẫu ngẫu nhiên, trong đó hợp lệ và bất hợp lệ ngang nhau, với số lượng tùy ý. Test này không giúp mình tìm được lỗi nào hơn so với test #1 khi giải bài tập này theo đúng đề (mã hóa C-string bất kỳ thành bản mã không nhất thiết là C-string), nhưng đã giúp mình tìm ra 1 lỗi (trong khi test #1 không tìm ra) khi giải theo yêu cầu nâng cao, mã hóa C-string chứa văn bản thực thành C-string.
    Đã được chỉnh sửa lần cuối bởi Ada : 24-10-2017 lúc 08:02 PM. Lý do: Bug fix: Hoán đổi thứ tự 2 lệnh r=... và r&msb?... trong cả 2 vòng for
    -...- -.- .. .-.. .-.. - .... . -... . .- ... - .-.-.

  3. #13
    Ngày gia nhập
    05 2017
    Bài viết
    12

    Trích dẫn Nguyên bản được gửi bởi Ada Xem bài viết
    À, còn 1 ngoại lệ nữa mà mình nhận thấy sau khi đọc kỹ file nguồn. Ở khai báo decode(n,x) họ yêu cầu "Decode x, up to n+1 chars, to C-string." Phải chăng họ muốn decode phải tạo ra kết quả x là một C-string (đóng) bằng mọi giá, trong bất cứ trường hợp nào? Không phải thế.

    Giả sử mã hóa rồi giải mã một chuỗi byte a bằng N = encode(m,a) và K = decode(m,a), gọi a(0) là giá trị ban đầu của a, a(1) là [giá trị của] a sau encodea(2) là [giá trị của] a sau decode. Nếu decode luôn đóng a(2) lại thì với m đủ nhỏ, sẽ gặp lỗi probably memory violation (dòng 84) hoặc length mismatch (dòng 85) và kể cả khi ta cố tình "bịp bợm" bằng cách trả lại một số K nào đó qua được 2 phép kiểm thử này thì cũng sẽ gặp lỗi memory violation (dòng 86) hoặc wrong original (dòng 87). Vậy, họ muốn gì?

    Mình nghĩ rằng họ muốn nếu a(0) vẫn mở ở độ dài m+1 thì a(2) bằng a(0) ở m+1 ký hiệu đầu tiên và vì thế, nói riêng, a(2) cũng phải [là một C-string] mở. Mình nhấn mạnh một C-string mở không phải là một C-string.

    Từ đó suy ra yêu cầu cho decode và cả encode. Ở bất cứ độ dài nào mà a(0) chưa đóng, nếu encode đóng a(1) là lỗi. Ở bất cứ độ dài nào mà a(1) chưa đóng, nếu decode đóng a(2) là lỗi. Nói một cách nôm na thì encodedecode phải mã hóa và giải mã chính xác về nguyên bản kể cả khi nguyên bản ấy là bất hợp lệ; họ không xem việc sửa sai dữ liệu là trách nhiệm của encodedecode.

    Chú ý rằng a(1) là một A-string, một khái niệm còn chưa được định nghĩa nói chi đến tính đóng mở của nó, nhưng yêu cầu này áp dụng bất kể ta định nghĩa như thế nào. Người ngoài hành tinh không biết và xem ra họ chẳng thèm biết đến định nghĩa. Và họ không thèm biết có lẽ bởi vì họ biết chắc rằng định nghĩa nào đó phải tồn tại: chúng ta không có cách nào truyền độ dài bản mã cho decode ngoài cách biểu diễn độ dài này ngay trong bản mã, tương tự như chúng ta vẫn làm với các C-string.

    EDIT: Thậm chí, mình còn có linh cảm chưa thể chứng minh, dù có muôn vàn cách mã hóa khác nhau nhưng cách định nghĩa A-string chỉ có một mà thôi. Nếu giả thuyết này đúng, người ngoài hành tinh chắc là đã biết và họ nghĩ chúng ta cũng biết hoặc, nếu chưa biết, thì cũng sẽ sớm tự tìm ra.

    - - - Nội dung đã được cập nhật ngày 22-10-2017 lúc 02:21 AM - - -

    Ở bài #1, mình diễn giải rằng đề bài được viết trong file nguồn C và cơ bản cả file là đề bài. Hôm nay, sau 1 tuần đọc và nghiền ngẫm, mình nhận ra rằng diễn giải đó chưa chính xác.

    Mọi comment viết trên một dòng riêng (hơn là viết ở cuối một dòng mã nguồn) đều đặc tả yêu cầu. Tuy nhiên, comment mô tả hàm test là yêu cầu mà người ngoài hành tinh đã giải xong -- nó không phải là đề bài đối với chúng ta.

    Chỉ có 2 dòng mã nguồn đặc tả yêu cầu. Đó là 2 dòng khai báo hàm encodedecode. Tuy nhiên, trong hàm main có hai dòng (hai lời gọi take(...,FSAMPL,...)) hơi mâu thuẫn với yêu cầu rằng dữ liệu là văn bản thực của ngôn ngữ loài người, vì chúng loại trừ hai loại văn bản thực: văn bản chỉ có 1 ký hiệu lặp đi lặp lại và văn bản chỉ toàn ký hiệu liên tiếp khác nhau. (Chính file nguồn C này là một ví dụ.) Nên nói main đặc tả dữ liệu thì cũng có một phần (vô cùng nhỏ) đúng.

    Mọi dòng mã nguồn khác đều không thể hiện đề bài. Nói riêng, các lời gọi takefail chỉ kiểm chứng những định lý (theo một nghĩa nào đó) suy từ các yêu cầu đặc tả, trong giả định rằng những yêu cầu đó đã được đáp ứng. Các hàm chỉ làm đúng những việc như cái tên của chúng đã nói lên; test() là "test", và main() là "main". Không hơn không kém.

    (Thật ra, mình cũng không chắc chắn đã tìm được chứng minh chính xác cho tất cả những điều mà mình nghĩ là "định lý" trên. Nhưng mình đã thấy được cốt lõi vấn đề. Cốt lõi ấy không bác bỏ "định lý" nào cả. Cốt lõi ấy đã giúp mình viết được code qua được test. Vậy, nếu test họ lập dư một chút, sai một chút thì đối với mình cũng có quan trọng gì đâu?)

    Giải thích rõ ràng mình đã "đọc và nghiền ngẫm" như thế nào để đi đến diễn giải mới như trên cũng chính là công bố [hầu] hết cả lời giải cho bài tập này. Mình sẽ hoãn "cái sự sung sướng" ấy lại một thời gian, để khỏi làm mất đi "cái sự sung sướng" ấy của người khác.
    có vẻ vui
    Mình hỏi tí, bạn ơi cái project này bạn lấy ở đâu ra thế ? Hack được từ trang government nào à :V

  4. #14
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    495

    Project gì đâu. Chỉ là 1 bài tập dễ, để giải chơi thôi mà.

    Nếu mình hack được "government" nào đó thì mình cũng không thể xác nhận, vì thông tin đó quá nhạy cảm: "government" đó chắc chắn phải hack được máy tính của người ngoài hành tinh mới lấy được file này bởi vì theo đường ngoại giao chính thức, giờ này chắc là nó còn chưa đến Trái Đất. Vẫn còn cách chúng ta ~72 giờ ánh sáng, tức ~72x bán kính của hệ Mặt Trời, theo tính toán không - thời gian chính xác đến +/- 0.5E-18 [m,m,m,s] của người ngoài hành tinh (xem #1).

    p/s. Kiểu float của họ còn chính xác hơn kiểu double của chúng ta. Hix.
    Đã được chỉnh sửa lần cuối bởi Ada : 26-10-2017 lúc 07:00 AM.
    -...- -.- .. .-.. .-.. - .... . -... . .- ... - .-.-.

  5. #15
    Ngày gia nhập
    08 2017
    Bài viết
    1,348

    Có điều không ổn. trong hệ người ta dùng đơn vị thiên văn (AU - Astronomical unit)

    Sao gần, cách mặt trời khoảng 2 năm ánh sáng (Light-year).

  6. #16
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    495

    Mặc định Mã hóa văn bản gửi ra ngoài hành tinh

    Mình nhớ nhầm là bán kính của hệ Mặt Trời khoảng hơn 1 tỉ km (~ 1 giờ ánh sáng). Thực ra, nó lớn hơn.

    Nhưng 72 giờ (tính từ nửa đêm hôm qua) là đúng đấy.

    Mình không nghĩ họ ở Cận Tinh (Proxima Centauri), trừ phi họ nhận được thông điệp từ Trái Đất nhưng không hồi đáp ngay mà "ngâm dấm" nó suốt hơn 40 năm.

    Nếu họ nhận thông điệp, vốn được phát đi từ 50 năm trước, và hồi đáp ngay, với dự kiến chúng ta sẽ nhận được trong năm nay, thì nơi phát hồi đáp cách Trái Đất xa nhất cũng chỉ là 5 năm ánh sáng (Facebook mới nổi tiếng khoảng 10 năm nay) còn nơi thu thông điệp cách Trái Đất gần nhất cũng phải là 45 năm ánh sáng => Họ úp mở cho loài người chúng ta biết họ có thể nhảy xuyên qua không gian >= 40 năm ánh sáng chỉ trong nháy mắt.

    Nhưng hồi đáp của họ đã bị "rò rỉ" trên mạng trước khi nó đến Trái Đất theo đường ngoại giao => Chúng ta cũng úp mở cho họ biết chúng ta không thua kém họ nhiều lắm về kỹ thuật xuyên không và vài "kỹ thuật" khác.
    Đã được chỉnh sửa lần cuối bởi Ada : 27-10-2017 lúc 10:05 AM. Lý do: Tính lại cho đúng: 50 năm -> gần nhất 45 năm
    -...- -.- .. .-.. .-.. - .... . -... . .- ... - .-.-.

  7. #17
    Ngày gia nhập
    01 2013
    Bài viết
    1,477

    Bạn Ada vui lòng tập trung vào chủ đề.
    Đã được chỉnh sửa lần cuối bởi prog10 : 26-10-2017 lúc 06:50 PM.

  8. #18
    Ngày gia nhập
    08 2017
    Bài viết
    1,348

    Trích dẫn Nguyên bản được gửi bởi prog10 Xem bài viết
    Bạn Ada vui lòng tập trung vào chủ đề.
    Nhắc luôn Prog chi đó cũng tập trung vào chủ đề, Tôi thấy Prog toàn nói lung tung, thiếu kiến thức đó.

  9. #19
    Ngày gia nhập
    08 2017
    Bài viết
    1,348

    Đủ sức cứ chơi nghen.

  10. #20
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    495

    Năm 1967, ngôn ngữ lập trình BCPL ra đời với một quyết định thiết kế gây nhiều tranh cãi nhất trong lịch sử công nghệ thông tin. Đó là định dạng xâu. Có hai phương án, độ dài xâu theo sau là chuỗi ký hiệu, hoặc chuỗi ký hiệu theo sau là một ký hiệu đóng xâu. Thời ấy, mọi ngôn ngữ lập trình đều chọn phương án thứ nhất, không kể hợp ngữ cho vài CPU lẻ tẻ, BCPL là ngôn ngữ đầu tiên lựa chọn phương án thứ hai.

    Ký hiệu đóng xâu được chọn là ký hiệu NUL, vốn có nghĩa là... chả có nghĩa gì cả, và vì thế, không bao giờ xuất hiện trong các xâu văn bản. Ký hiệu này có mã thống nhất là 0 trong mọi bảng mã. (Vì sao có nó, và vì sao nó luôn là 0, mình sẽ nói khi bài tập này đã được giải xong.)

    Bảng mã ASCII, vốn hình thành trước đó bốn năm và được hoàn thiện vào cùng năm, là một trong những bảng mã như thế.

    ASCII chính thức trở thành yêu cầu bắt buộc trong mọi sản phẩm công nghệ thông tin cung cấp cho chính phủ Mỹ do một sắc lệnh hành pháp (lệnh do tổng thống ký) đầu năm 1968.

    Nhắc lại chuyện đúng 50 năm trước vì đó là phần ít ai nhớ. Phần còn lại thì đã là lịch sử. Từ BCPL, người ta phát triển ngôn ngữ B và từ đó, ngôn ngữ C.
    Đã được chỉnh sửa lần cuối bởi Ada : 01-01-2018 lúc 01:07 AM.
    -...- -.- .. .-.. .-.. - .... . -... . .- ... - .-.-.

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn