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