Tờ Mờ Sáng học Thuật toán và Lập trình thi đấu

Tổng hợp danh sách những tài liệu hay và bổ ích về Thuật toán và Lập trình thi đấu

Người tổng hợp: Trần Minh Sáng

Series video "Lên trình Thuật toán - Lập trình thi đấu":

Cài đặt extension Random Algorithm Topics trên Google Chrome để học ngẫu nhiên một chủ đề trong danh sách mỗi khi mở 1 tab mới trên trình duyệt

Install on Google Chrome

Nội dung chính

• Nhập môn
• Sách hay về Thuật toán và Lập trình thi đấu
• Toán học trong lập trình thi đấu
• Kỹ thuật lập trình
• Các thuật toán sắp xếp
• Các thuật toán tìm kiếm
• Cấu trúc dữ liệu (Data Structures)
• Tham lam
• Quy hoạch động
• Thiết kế giải thuật
• Range Queries
• Đồ thị
• Cây
• Hình học
• Xử lý chuỗi
• Các chủ đề nâng cao
• Một số chủ đề khác

Nhập môn

• Thuật toán là gì?
• Lập trình thi đấu là gì?
• Những kỳ thi Lập trình thi đấu nổi tiếng
• Các trang web luyện tập Thuật toán và Lập trình thi đấu
• Lợi ích của việc tham gia Lập trình thi đấu

Sách hay về Thuật toán và Lập trình thi đấu

• Competitive Programming - Steven Halim
• Introduction to Algorithms - Bản dịch tiếng Việt
• Giải thuật và lập trình (DSAP) - thầy Lê Minh Hoàng
• Tài liệu giáo khoa chuyên Tin
  • Quyển 1
  • Quyển 2
  • Quyển 3 - phần 1
  • Quyển 3 - phần 2
• Competitive Programmer's Handbook
• Guide To Competitive Programming
• The Art Of Computer Programming - Donald Knuth
• KC Book
  • Quyển 1
  • Quyển 3
• Một số vấn đề đáng chú ý trong môn Tin học
• Chuyên đề bồi dưỡng học sinh giỏi Toán Trung học phổ thông - Số học

Toán học trong lập trình thi đấu

• Kiến thức nền tảng
  • Hệ cơ số
  • Cấp số cộng
  • Cấp số nhân
  • Lý thuyết tập hợp
  • Đại số logic
  • Logarithm
• Số học
  • Modulo
  • Nghịch đảo modulo
  • Số nguyên tố
  • Sàng nguyên tố
  • Giải thuật Euclid
  • Lũy thừa modulo
  • Lũy thừa nhị phân
  • Phi hàm Euler
  • Giải phương trình
  • Định lý Wilson
  • Hàm Mobius
  • Hàm nhân tính
• Tổ hợp
  • Hệ số nhị thức
  • Dãy số Catalan
  • Bao hàm - Loại trừ
  • Bổ đề Burnside
  • Công thức Cayley
  • Biến đổi Fourier nhanh - FFT
• Ma trận
  • Nhân ma trận
  • Khử nhân ma trận
  • Truy hồi tuyến tính
  • Ma trận kề
  • Phép khử Gauss
• Xác suất
  • Biến cố
  • Biến ngẫu nhiên
  • Chuỗi Markov
  • Thuật toán ngẫu nhiên
• Lý thuyết trò chơi
  • Game State
  • Trò chơi Nim
  • Định lý Sprague–Grundy

Kỹ thuật lập trình

• Ngôn ngữ lập trình C++
• Cách tiếp cận bài toán
• Độ phức tạp
• Đệ quy
• Thao tác với bit

Các thuật toán sắp xếp

• Sắp xếp nổi bọt (Bubble sort)
• Sắp xếp chèn (Insertion sort)
• Sắp xếp trộn (Merge sort)
• Sắp xếp chọn (Selection sort)
• Sắp xếp vun đống (Heap sort)
• Sắp xếp nhanh (Quick sort)
• Sắp xếp cơ số (Radix sort)
• Sắp xếp đếm phân phối (Counting sort)

Các thuật toán tìm kiếm

• Tìm kiếm tuần tự (Linear search)
• Tìm kiếm nhị phân (Binary search)
• Tìm kiếm tam phân (Ternary search)
• Tìm kiếm nhảy (Jump search)
• Tìm kiếm nội suy (Interpolation search)

Cấu trúc dữ liệu (Data Structures)

Đang cập nhật

• Tổng quan về cấu trúc dữ liệu
• Mảng (Array) và Danh sách liên kết (Linked list)
• Dynamic Array
• Ngăn xếp (Stack)
• Hàng đợi (Queue)
• Set và Multiset
• Hàng đợi ưu tiên (Priority Queue)
• Mảng cộng dồn và mảng hiệu
• Deque và tìm min max trên đoạn tịnh tiến
• Heap
• Bảng băm (Hash table)
• Disjoint Set Union (DSU)
• Cây Phân Đoạn (Segment Tree)
• Chia căn
• Fenwick Tree (Binary Indexed Tree)
• Heavy Light Decomposition (HLD)
• Persistent Data Structures
• Lowest Common Ancestor (LCA) - Binary Lifting
• Bài toán RMQ & bài toán LCA
• Trie
• Suffix Array
• Palindrome Tree
• Skip List
• Range Tree

Tham lam

• Đang cập nhật

Quy hoạch động

• Đang cập nhật

Thiết kế giải thuật

• Đang cập nhật

Range Queries

• Đang cập nhật

Đồ thị

• Đang cập nhật

Cây

• Đang cập nhật

Hình học

• Đang cập nhật

Xử lý chuỗi

• Đang cập nhật

Các chủ đề nâng cao

• Đang cập nhật

Một số chủ đề khác

• Đang cập nhật