Bỏ qua để đến nội dung

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 1018 thì vòng lặp phải chạy 1018 bước, còn ai biết công thức chỉ cần vài phép tính. 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í.
  • 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ỗi bài có icon mức độ trong mục lục và ở đầu bài:

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.

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

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

Các bài trong mục này so sánh hai cách làm bằng số phép tính, không bằng thời gian: thời gian chạy thật phụ thuộc rất nhiều vào máy, ngôn ngữ, trình biên dịch và cách viết code.

Mỗi khi có cách làm tốt hơn, bài viết nói cách đó chạy bao nhiêu bước và ít hơn cách cũ bao nhiêu lần. Ví dụ với n = 1012, tìm ước bằng cách thử từ 1 đến n mất 1012 bước, thử đến n\sqrt{n} chỉ mất 106 bước, ít hơn 106 lần.

Khi đọc số bước, để ý cỡ của nó (106, 109, 1018…) hơn là con số chính xác: 106 bước và 2 × 106 bước gần như ngang nhau, còn 106 với 1012 thì khác hẳn.

BàiMứ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
Miller-Rabin và Pollard rho
BàiMứ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
BàiMứ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
BàiMức độ
Hệ nhị phân và hệ cơ số
Phép toán bit
BàiMứ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
BàiMức độ
Vị trí thắng, vị trí thua
Trò chơi Nim và định lý Sprague-Grundy
BàiMức độ
Xác suất và kỳ vọng

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

Th.S Trần Huy Phúc

Th.S Trần Huy Phúc

Principal Software Engineer @Adnovum & Bumbii Academy