Toán rời rạc
Toán rời rạc là môn cơ sở ngành của hầu hết các môn có dính dáng tới máy tính, và nó là một môn cũng rất quan trọng cho các bạn nào theo ngành IT. Toán rời rạc cung cấp cho mọi người những kiến thức cơ bản về tổ hợp và lý thuyết đồ thị.
Phần tổ hợp thì khá là quen thuộc vì hầu hết mọi người đều được làm quen từ hồi học THPT. Các bài toán đề cập đến như là : bài toán đếm, bài toán liệt kê, bài toán tồn tại, nguyên lý Dirichlet, nguyên lý cực hạn. Sau đó còn có tổ hợp, chỉnh hợp, hoán vị, số Sterling, số Catalan,… Các lý thuyết tổ hợp là nền tảng cho lý thuyết tính toán, độ phức tạp, …
Lý thuyết đồ thị là phần mới. Toán rời rạc sẽ đề cập tới khái niệm đồ thị, những loại đồ thị khác nhau, các thuật toán trên đồ thị ( DFS, BFS, Djikstra, thuật toán tham lam…), những bài toán có thể giải trên đồ thị ( hay mô hình hóa chúng bằng đồ thị để giải quyết), ứng dụng của đồ thị vào các bài toán thực tế ( như là sắp xếp lịch thi, ghép cặp, …), …
Một số ví dụ về các bài toán giải quyết trong toán rời rạc
Bài toán xếp lịch học bằng tô màu đồ thị :
