Tin học

Ngôn ngữ hình thức

Ngôn ngữ hình thức, bảng chữ cái và xâu là gì. Các khái niệm cơ bản của lí thuyết ngôn ngữ hình thức, giải thích qua so sánh với ngôn ngữ thông thường và qua ví dụ.

Ôtômat hữu hạn

Ôtômat hữu hạn là mô hình tính toán gồm các trạng thái và các phép chuyển. Định nghĩa, đồ thị chuyển trạng thái, hình thức hoá quá trình tính toán và ví dụ về các xâu được đoán nhận.

Tối thiểu hoá ôtômat

Trạng thái không đến được của ôtômat hữu hạn là trạng thái không thể đi đến từ trạng thái bắt đầu. Định nghĩa và cách loại bỏ chúng khỏi ôtômat một cách an toàn.

Tính đóng của ngôn ngữ chính quy

Lớp ngôn ngữ chính quy đóng đối với phép hợp, phép giao, phép ghép và bao đóng. Tính đóng đối với một phép toán nghĩa là gì và vì sao ngôn ngữ chính quy có tính chất này.

Biểu thức chính quy

Biểu thức chính quy là gì và mô tả một tập hợp xâu như thế nào. Định nghĩa, so sánh với biểu thức số học và mối liên hệ với ôtômat hữu hạn.

Ước lượng số phần tử phân biệt

Linear counting: cách ước lượng số giá trị phân biệt trong dữ liệu lớn. Hàm băm, bitmap và vì sao cách làm đơn giản là không đủ.

Bloom filter: Phần tử có thuộc tập hợp không?

Bloom filter (bộ lọc Bloom) là cấu trúc dữ liệu xác suất cho biết nhanh một phần tử có thuộc tập hợp hay không. Nguyên lí, hàm băm và ứng dụng thực tế.

Mật mã Caesar

Mật mã Caesar hoạt động thế nào – một trong những cách mã hoá văn bản cổ xưa nhất. Nguyên tắc dịch chữ, mở rộng mật mã và công cụ mã hoá trực tuyến.

Mật mã Vigenère

Mật mã Vigenère dùng nhiều bảng chữ cái nên chống được phân tích tần suất. Nguyên tắc mã hoá, hình vuông Vigenère, cách chọn khoá và công cụ trực tuyến.