Xem mẫu
- TOÁN RỜI RẠC
CHƢƠNG 0
GIỚI THIỆU MÔN HỌC
Giảng viên: ThS. Trần Quang Khải
- “TOÁN RỜI RẠC” là gì?
Discrete mathematics
Là tên chung của nhiều ngành toán học
nghiên cứu về các cấu trúc toán học mà về
cơ bản là “rời rạc” (discrete) chứ không
“liên tục” (continuous).
(theo Wikipedia)
Chưa có định nghĩa chính xác về thuật ngữ
“Discrete mathematics” được tất cả công nhận.
Toán rời rạc Chương 0: Giới thiệu 2
- “TOÁN RỜI RẠC” là gì?
Ví dụ:
Có bao nhiêu cách xếp chỗ ngồi cho SV trong kỳ thi cuối
kỳ?
Xác suất thắng độ 1 trận bóng đá?
Đường đi nào ngắn nhất tới nhà người yêu?
Đường đi nào nhanh nhất tới phòng trọ thằng bạn thân?
Toán rời rạc Chương 0: Giới thiệu 3
- Toán rời rạc
Các đối tượng được nghiên cứu:
Có giá trị phân biệt, không “dính liền”.
Có thể được liệt kê ra.
Giải quyết các bài toán thuộc các tập hợp đếm được
(countable sets).
Tập các đối tượng cố thể có số lượng:
hữu hạn.
vô hạn.
Toán rời rạc Chương 0: Giới thiệu 4
- Toán rời rạc
Bao gồm:
Lý thuyết tổ hợp.
Lý thuyết đồ thị.
Lý thuyết độ phức tạp.
Logic, quan hệ, đại số Boole.
…
Không bao gồm:
Các kiến thức thuộc “toán học liên tục”.
Ví dụ: Giải tích.
Toán rời rạc Chương 0: Giới thiệu 5
- Grand Challenges
Four color theorem:
1852: Tô mọi bản đồ chỉ bằng
4 màu?
→ 1976: Kenneth Appel và
Wolfgang Haken đã chứng
minh nhờ sự hỗ trợ của máy
tính.
Toán rời rạc Chương 0: Giới thiệu 6
- Grand Challenges
Logic:
1900: Mọi tiên đề số học là nhất quán?
→ 1931: Điều này là không thể?
Xác thực hình thức trong phát biểu logic
→ Hệ thống thông minh, hệ thống tự động.
Toán rời rạc Chương 0: Giới thiệu 7
- Grand Challenges
World War II & Cold War :
Mật mã và Phá khóa mật mã:
→ Mã hóa (Cryptography).
→ Khoa học Máy tính mang tính lý thuyết.
Quản lý kinh tế:
Phương thức hoạt động:
→ Khoa học quản lý (Management science).
→ Khoa học quyết định (Decision science).
Toán rời rạc Chương 0: Giới thiệu 8
- Grand Challenges
Telecommunication Industry:
Lý thuyết đồ thị.
Lý thuyết thông tin.
Tính toán hình học:
Đồ họa máy tính.
Công cụ thiết kế được hỗ trợ bởi máy tính (Computer
Aided Design - CAD).
Video Games.
Toán rời rạc Chương 0: Giới thiệu 9
- Grand Challenges
Present & Future:
Bioinformatics.
Độ phức tạp tính toán:
Bài toán P = NP
☺1,000,000 $
Toán rời rạc Chương 0: Giới thiệu 10
- Toán rời rạc
Các nhánh nghiên cứu trên các đối tượng
rời rạc được tập hợp lại từ khi có Khoa học
Máy tính.
Cơ sở toán học của Khoa học Máy tính.
Phát triển mạnh từ nửa sau thế kỷ 20.
Toán rời rạc Chương 0: Giới thiệu 11
- Toán rời rạc Khoa học Máy tính
Cryptography
Concepts
Programming
languages
Discrete Computer Algorithms
Maths Science
Automated
theorem
Notations
Software
development
Toán rời rạc Chương 0: Giới thiệu 12
- Vì sao phải học Toán Rời Rạc?
Đối với khóa học:
✏ TRR hỗ trợ các môn khác?
✏ Sử dụng TRR trong các môn khác thế nào?
✏ “Học „gạo‟ để lấy điểm 5 àh?”
✏ Kiến thức có dễ nhớ không?
Toán rời rạc Chương 0: Giới thiệu 13
- Vì sao phải học Toán Rời Rạc?
Đối với sự nghiệp lâu dài:
☺Sử dụng trong kỹ thuật phần mềm, mạng?
☺Ứng dụng trong giao tiếp, đàm phán?
☺Học lên Thạc sĩ, Tiến sĩ?
Khoa học Máy tính.
Toán ứng dụng.
Tài chính – ngân hàng.
☺Kiếm nhiều tiền hơn?
☺Toán Rời Rạc rất khó → Đẳng cấp, Bản lĩnh?
Toán rời rạc Chương 0: Giới thiệu 14
- Nội dung chính của môn học
Logic. Xác suất.
Tập hợp. Độ phức tạp giải thuật.
Suy luận toán học. Topology.
Hàm và quan hệ. Tính toán hình học.
Phép đếm. Nghiên cứu về hoạt động.
Lý thuyết đồ thị. …
Đại số Boolean.
Toán rời rạc Chương 0: Giới thiệu 15
- Toán Rời Rạc trong các môn khác
Cấu trúc dữ liệu. Lý thuyết tự động.
Giải thuật. Ngôn ngữ hình thức.
Cơ sở dữ liệu. …
Mạng máy tính.
Game, Trí tuệ nhân
tạo.
Hệ điều hành.
Bảo mật máy tính.
Toán rời rạc Chương 0: Giới thiệu 16
- Phƣơng pháp học?
☺Đọc trước slide bài giảng, textbook.
☺Đến lớp nghe giảng.
☺Bài tập: “Để mai tính”?
☺Làm việc, làm bài tập theo nhóm.
Toán rời rạc Chương 0: Giới thiệu 17
- Thang điểm – Thi cử
Thang điểm: Hình thức:
Thường xuyên: 30%. Bài tập tuần:
Giữa kỳ: 20%. • Trắc nghiệm.
Cuối kỳ: 50%. • Tự luận.
BT cộng điểm: ±20%. Thi:
Lần 1: • Trắc nghiệm.
Đăng ký: tuần 2 • Tự luận.
3 đề tài (3 SV) BT cộng điểm:
Lần 2: • Viết chương trình.
Đăng ký: tuần 4 (sau tết)
2 hoặc 3 nhóm (nhóm 2 SV)
• Seminar.
Toán rời rạc Chương 0: Giới thiệu 18
nguon tai.lieu . vn
