Toán rời rạc
Toán rời rạc là gì?
Toán rời rạc là một lĩnh vực nghiên cứu và xử lý các đối tượng rời rạc dùng để đếm các đối tượng, và nghiên cứu mối quan hệ giữa các tập rời rạc. Một trong những yếu tố làm Toán rời rạc trở nên quan trọng là việc lưu trữ, xử lý thông tin trong các hệ thống máy tính về bản chất là rời rạc.
Toán học rời rạc (tiếng Anh: discrete mathematics) còn được gọi là toán học dành cho máy tính. Người ta thường kể đến trong toán học rời rạc lý thuyết tổ hợp, lý thuyết đồ thị, lý thuyết độ phức tạp, đại số Boole.
Toán rời rạc trong công nghệ thông tin?
Toán học rời rạc là một môn học bắt buộc mang tính chất kinh điển của các ngành Công nghệ thông tin và Điện tử Viễn thông.Nó 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, …), …
Toán rời rạc và ứng dụng thực tế
- Có bao nhiêu password hợp lệ cho một hệ thống máy tính ?
- Có tồn tại một đường nối giữa 2 máy tính trong một mạng:: bài toán tìm đường??
- Có bao nhiêu địa chỉ internet hợp lệ?
- Đường đi ngắn nhất giữa 2 máy tính trong một mạng là gì?
- Có bao nhiêu bước trong quá trình sắp xếp?
- Có bao nhiêu mạch để cộng 2 số nguyên được thiết kế?
- Khả năng trúng giải thưởng cho một vé số là bao nhiêu?
- Cây thì nhờ đó có thuật giải huffman giúp nén thông tin. hoặc giúp làm cây quyết định, xây dựng chiến thuật min-max dùng trong trí tuệ nhân tạo để giải quyết các bài toàn về chơi cờ, nim. Xây dựng cây tiền tố, hậu tố để máy tính có thể hiểu và tính toán đc các phép tính thông thường của con người.
- Xây dựng thuật toán AI cho game
- Xây dựng trí thông minh nhân tạo
- giả lập môi trường cả về phần mềm trong lập trình tự động của robot và trong game (như sóng vỗ, lửa cháy,…)
- Đặc biệt là dùng để rút gọn code tiết kiệm thời gian lập trình
Chủ đề toán rời rạc
Chương 1: Logic, tập hợp và ứng dụng
Chương 2: Bài toán đếm
Chương 3: Bài toán liệt kê
Chương 4: Bài toán tối ưu
Chương 5: Bài toán tồn tại
Chương 6: Một số khái niệm cơ bản của đồ thị
Chương 7: Biểu diễn đồ thị trên máy tính
Chương 8: Tìm kiếm đồ thị
Chương 9: Đồ thị Euler, đồ thị Hamilton
Chương 10: Cây khung đồ thị
Chương 11: Bài toán tìm đường ngắn nhất
Hi vọng với những thông tin trên đã phần nào giúp các bạn hiểu hơn về toán rời rạc trong công nghệ thông tin. Cảm ơn bạn đã tham khảo tài liệu trên ttnguyen.net
