Thông tin chung
Một khóa học toán học rời rạc có nhiều hơn một mục đích. Để giải quyết một vấn đề sinh viên cần học một tập hợp các dữ kiện toán học và làm thế nào để xử lý các dữ kiện toán học đó bằng các suy luận hoặc quy nạp, để đưa ra các kết quả mà có thể giải quyết được vấn đề; Quan trọng hơn, với một khóa học như vậy sinh viên cần biết cách suy nghĩ logic và toán học. Để đạt được những mục tiêu này, có rất nhiều kỹ năng toán học cần phải đạt được. Năm kỹ năng quan trọng đan xen trong việc học tập toán học là: lý luận toán học, phân tích tổ hợp, cấu trúc rời rạc, tư duy thuật toán, ứng dụng và mô hình hóa. Một khóa học toán học rời rạc thành công nên cẩn thận pha trộn và cân bằng tất cả năm chủ đề.
1 – Lý luận toán học: sinh viên phải hiểu lý luận toán học để đọc, hiểu, và xây dựng lập luận toán học. Trong khóa học này bắt đầu với vấn đề logic toán học và nó là nền tảng cho các kiến thức tiếp theo cho các vấn đề cần chứng mình sau này. Kỹ thuật quy nạp toán học được nhấn mạnh thông qua nhiều loại khác nhau và nó cho thấy đó là một cách chứng minh hợp lệ.
2 – Phân tích tổ hợp: Một kỹ năng giải quyết vấn đề quan trọng là khả năng đếm liệt kê các đối tượng. Trong khóa học này có giới thiệu về kỹ thuật cơ bản của đếm, nó được áp dụng trong các kỹ năng phân tích độ phức tạp của thuật toán sau này đối với các bạn sinh viên học ngành khoa học máy tính.
3 – Cấu trúc rời rạc: Một khóa học trong toán học rời rạc nên sinh viên sẽ biết làm thế nào để làm việc với cấu trúc rời rạc, đó là những cấu trúc toán học trừu tượng sử dụng để đại diện cho đối tượng rời rạc và các mối quan hệ giữa các đối tượng. Những cấu trúc rời rạc bao gồm các bộ, hoán vị, quan hệ, đồ thị, cây xanh, và các phần tử hữu hạn.
4 – Tư duy thuật toán: Sau một thuật toán đã được mô tả, một chương trình máy tính có thể được xây dựng thực hiện nó. Các phần toán học của hoạt động này, trong đó bao gồm các đặc điểm kỹ thuật của thuật toán, việc xác minh rằng nó hoạt động đúng, và phân tích của bộ nhớ máy tính và thời gian cần thiết để thực hiện nó, tất cả đều được xác định trong khóa học này
5 – Ứng dụng và mô hình hóa: Toán rời rạc có ứng dụng cho hầu hết các khu vực có thể tưởng tượng và đã được nghiên cứu. Có rất nhiều ứng dụng khoa học máy tính trong khóa học này, cũng như các ứng dụng cho các khu vực khác nhau như hóa học, thực vật học, động vật học, ngôn ngữ học, địa lý, kinh doanh, và Internet.
Mục tiêu môn học
A. Về mặt hiểu biết
Nắm được khái niệm cơ bản về biểu diễn logic và các vị từ logic
Nắm được khái niệm cơ bản của tập hợp, hàm, dãy số và tổng của chúng
Nắm được phương pháp quy nạp
Khái niệm cơ bản về thuật toán, thuật toán đệ quy.
Nắm được khái niệm cơ bản của hệ đếm, nắm được công thức truy hồi
Nắm được khái niệm cơ bản của quan hệ và các tính chất của nó
Nắm được một số khái niệm cơ bản của đồ thị, các thuật ngữ về đồ thị, các dạng đồ thị, biểu diễn đồ thị và tính liên thông của chúng
Nắm được đường đi Euler và Hamilton để áp dụng cho bài toán tìm đường ngắn nhất.
Nắm được khái niệm cơ bản của cây và ứng dụng của nó
B. Về mặt kỹ năng
Sinh viên có thể thao tác với các biểu thức logic, từ đó dẫn ra các biểu thức logic tương đương
Sinh viên có thể chứng minh các mệnh đề toán học đơn giản, bao gồm áp dụng cả nguyên lý quy nạp
Giải quyết các vấn đề trong hệ đếm, áp dụng trong việc phân tich thuật toán
Sử dụng cấu trúc quan hệ
Giải quyết các bài toán liên quan đến đường đi và các bài toán về cây đồ thị
C. Các vấn đề khác
Sau khi học xong môn này sinh viên có thể áp dụng toán rời rạc đề giải quyết các vấn đề liên quan đề khoa học máy tính
Trải nghiệm học tập
Phần 1: Kiến thức cơ sở: logic và chứng minh
– Giới thiệu về mệnh đề logic, mệnh đề kéo theo, mệnh đề đảo và mệnh đề 2 điều kiện, đồng thời giới thiệu về mệnh đề tương đương, giới thiệu về ngôn ngữ vị từ và các lượng từ, các lượng từ lồng nhau.
Phần 2: Cấu trúc cơ bản của: Tập hợp, hàm số, dãy số và tổng của chúng
– Giới thiệu một số khái niệm, thế nào là tập hợp, tập con, và các phép toán trên tập hợp, thế nào là hàm số, dãy số và tổng của chúng như thế nào.
Phần 3: Những kiến thức cơ bản: Thuật toán, số nguyên
– Giới thiệu những kiến thức cơ bản của thuật toán cũng như độ tăng của hàm, các bài toán liên quan đến số nguyên như: tìm ước số chung lớn nhất hoặc tìm bội số chung nhỏ nhất, trong đó có giới thiệu thuật toán Euclid
Phần 4: Suy luận toán học, phép quy nạp và đệ quy
– Giới thiệu nguyên lý quy nạp, cũng như công thức đệ quy, thuật toán đệ quy cho các bài toán từ đơn giản đến phức tạp
Phần 5: Đếm các phần tử
– Giới thiệu về nguyên lý đếm, gồm 2 bài toán cơ bản đó là có kể đến thứ tự-công thức chỉnh hợp và không kể đến thứ tự-công thức tổ hợp
Phần 6: Hệ thức truy hồi
– Giới thiệu công thức truy hồi, và các ví dụ của nó
Phần 7: Quan hệ và các tính chất của nó
– Giới thiệu về quan hệ và các tính chất của nó
Phần 8: Đồ thị
– Các khái niệm cơ bản liên quan đến đồ thị như: thuật ngữ về đồ thị, một vài dạng đồ thị đặc biệt, biểu diễn đồ thị, đồ thị đẳng cấu, và tính liên thông của đồ thị, đường đi Euler và Hamilton, và áp dụng của nó trong việc tìm đường đi ngắn nhất
Phần 9: Cây
– Giới thiệu về cây đồ thị, bao gồm khái niệm về cây và ứng dụng của cây nhị phân
Nguồn học liệu
Danh sách nguồn học liệu mở miễn phí (MOOC) mà FUNiX đang sử dụng trong môn học này: Ant0nMath, Arnaldo Pedro Figueira Figueira, CourseHack, Daniel Krashen, Derek Banas, Dragonfly Statistics, GVSUmath, James Olsen, Jang Soo Kim, Jason Pallett, Kailee Gray, Karen Daly, Khan Academy, nagerhard, patrickJMT, Professor Heather Pierce, TheTrevTutor.
Đừng ngần ngại!
Bạn sẽ dễ dàng chuẩn bị nền tảng cùng FUNiX!
