Toán tin

Rất nhiều bài thi lập trình thực chất là bài toán. Viết vòng lặp đếm từ 1 tới n thì ai cũng làm được, nhưng khi n lên tới 10¹⁸ thì chỉ ai biết công thức mới giải kịp thời gian. Toán tin là phần toán giúp các bạn viết chương trình đúng và nhanh.

Mỗi bài trong mục này gồm:

• Lý thuyết giải thích bằng cách nhìn đơn giản nhất, có ví dụ giải mẫu.
• Chương trình Python và C++ cho từng ý quan trọng.
• Bài luyện tập có đáp số để tự kiểm tra (miễn phí). Lời giải chi tiết các bài luyện tập có trong bộ tài liệu có phí.

Dành cho ai?

• Học sinh THCS, THPT ôn thi học sinh giỏi Tin học và tuyển sinh chuyên Tin lớp 10.
• Học sinh thi Tin học trẻ Bảng B, C (lập trình Python, C++).
• Thầy cô dạy đội tuyển cần tài liệu có hệ thống.

Mức độ

Mỗi bài có icon mức độ trong mục lục và ở đầu bài:

Cơ bản

Kiến thức Toán cơ bản (nhiều phần học từ tiểu học), học cách dùng trong chương
trình. Các bạn nên bắt đầu từ đây.

Nâng cao

Kiến thức cho thi học sinh giỏi cấp tỉnh, tuyển sinh chuyên Tin lớp 10.

Chuyên sâu

Kiến thức cho thi học sinh giỏi quốc gia, lập trình thi đấu (ICPC).

Ước lượng thời gian chạy

Các bài trong mục này thường so sánh hai cách làm bằng số phép tính. Để đổi ra thời gian, ta dùng một ước lượng quen thuộc: máy tính làm được khoảng 10⁸ phép tính đơn giản mỗi giây với C++. Python thường chậm hơn nhiều lần. Thời gian thật còn phụ thuộc máy, trình biên dịch và cách viết code, nên các con số thời gian trong bài chỉ để so sánh cỡ lớn, không phải số đo chính xác.

Số phép tính	Ước lượng (C++)
106	rất nhanh
108	khoảng 1 giây
1012	khoảng 3 tiếng
1018	hơn 300 năm

Đề thi thường giới hạn khoảng 1 giây cho mỗi test, nên cần chọn cách làm có số phép tính ở mức 10⁷ đến 10⁸ trở xuống.

Các chuyên đề

Số học

Bài	Mức độ
Phép chia có dư và chia hết
Ước và bội
Số nguyên tố
Sàng Eratosthenes
Ước chung lớn nhất, bội chung nhỏ nhất - thuật toán Euclid
Đồng dư và phép toán modulo
Lũy thừa nhanh, nghịch đảo modulo, lũy thừa ma trận
Thuật toán Euclid mở rộng, phương trình nghiệm nguyên
Định lý số dư Trung Hoa
Hàm Euler và định lý Euler
Hàm nhân tính và hàm Möbius
Chia khối theo giá trị n // i

Tổ hợp và đếm

Bài	Mức độ
Quy tắc cộng, quy tắc nhân
Hoán vị, chỉnh hợp, tổ hợp
Nguyên lý bù trừ
Nguyên lý Dirichlet
Quy hoạch động chữ số
Tổ hợp modulo số nguyên tố nhỏ: Legendre, Kummer, Lucas

Dãy số

Bài	Mức độ
Cấp số cộng, cấp số nhân
Tổng tiền tố và mảng hiệu
Dãy truy hồi

Biểu diễn số

Bài	Mức độ
Hệ nhị phân và hệ cơ số
Phép toán bit

Hình học tọa độ

Bài	Mức độ
Điểm, khoảng cách và tích có hướng
Diện tích đa giác và điểm nguyên
Bao lồi nâng cao và kỹ thuật xoay compa

Lý thuyết trò chơi

Bài	Mức độ
Vị trí thắng, vị trí thua
Trò chơi Nim và định lý Sprague-Grundy

Xác suất

Bài	Mức độ
Xác suất và kỳ vọng

Luyện đề

Sau khi học xong một chuyên đề, các bạn luyện đề thật để quen với cách ra đề:

• Đề thi học sinh giỏi Tin học
• Bộ 30 đề ôn thi học sinh giỏi Tin học THCS
• Đề thi tuyển sinh chuyên Tin lớp 10