Toán rời rạc – Giáo trình nhập môn mở bản 4
(discrete.openmathbooks.org)- Bản 4 của Discrete Mathematics: An Open Introduction, có thể dùng ngay cho các lớp toán rời rạc nhập môn ở bậc đại học, đã được phát hành và có sẵn dưới dạng giáo trình trực tuyến miễn phí cùng PDF
- Bản mới củng cố mạch nội dung bắt đầu từ logic và chứng minh, sau đó luyện chứng minh qua lý thuyết đồ thị rồi chuyển sang đếm và dãy số
- Từ mùa xuân năm 2013, sách đã được dùng làm giáo trình chính hoặc tài liệu bổ trợ tại hơn 200 trường đại học trên toàn thế giới, được AIM Open Textbook Initiative giới thiệu và có đánh giá trên Open Textbook Library
- Có đầy đủ ebook trực tuyến, PDF, bản in, mã nguồn GitHub, cùng bộ bài tập cho Runestone Academy·Edfinity·WeBWorK nên hạ thấp rào cản đưa vào giảng dạy
- Phiên bản trực tuyến sẽ tiếp tục được duy trì miễn phí, và bản 4 dùng giấy phép CC BY-NC-SA 4.0 cho phép sử dụng, in ấn và chỉnh sửa phi thương mại
Công bố bản 4 và tính chất của giáo trình
- Discrete Mathematics: An Open Introduction bản 4 có thể sử dụng trực tuyến và trên Runestone Academy
- Bản 3 vẫn tiếp tục được cung cấp
- Đây là giáo trình mã nguồn mở miễn phí dành cho môn toán rời rạc ở năm 1~2 cho sinh viên chuyên ngành toán học và khoa học máy tính
- Đặc biệt phù hợp với các lớp học có tích hợp học tập dựa trên khám phá
- Từ mùa xuân năm 2013, sách đã được sử dụng làm giáo trình chính hoặc tài liệu bổ trợ tại hơn 200 trường đại học trên toàn thế giới
- Sách được Open Textbook Initiative của American Institute of Mathematics giới thiệu, và cũng có đánh giá trên Open Textbook Library
Cấu trúc thay đổi trong bản 4
- Bản mới tái cấu trúc đáng kể thứ tự nội dung
- Mở đầu với logic và chứng minh
- Tiếp theo là luyện chứng minh qua lý thuyết đồ thị
- Phần sau bố trí các nội dung về đếm và dãy số
- Chương về đếm có thêm mục mới về ứng dụng xác suất
- Điều này phản ánh kinh nghiệm trong vài năm gần đây rằng sinh viên đạt kết quả tốt hơn với cách sắp xếp này
- Mức độ nhấn mạnh vào cấu trúc rời rạc cũng được tăng lên
- Bao gồm tập hợp, hàm và quan hệ
- Hữu ích hơn cho sinh viên khoa học máy tính, đồng thời vẫn giữ được sự hiểu biết về các khái niệm toán học cần thiết cho sinh viên toán và giáo viên toán tương lai
Tính tương tác và hỗ trợ bài tập
- Bản 4 có nhiều yếu tố tương tác hơn
- Nếu tạo khóa học dựa trên giáo trình trên Runestone Academy, có thể dùng bài tập tương tác để chấm điểm cho sinh viên
- Có kèm mã tương tác Sage và Python để khám phá một số chủ đề
- Bộ bài tập trực tuyến được cung cấp qua nhiều kênh
- Runestone Academy là miễn phí
- Edfinity là lựa chọn chi phí thấp
- Bộ WeBWorK có thể được yêu cầu từ tác giả, và cũng có trong thư mục Contrib của OPL
- Có thể gửi lỗi hoặc lỗi chính tả qua GitHub issue
Định dạng cung cấp và khả năng tiếp cận
- Toàn bộ giáo trình được cung cấp dưới dạng ebook trực tuyến tương tác miễn phí
- Được thiết kế để hoạt động tốt trên mọi kích thước màn hình, bao gồm cả điện thoại thông minh
- Có tính đến việc sử dụng trình đọc màn hình cho sinh viên khiếm thị
- Gợi ý và lời giải của ví dụ cùng bài tập được ẩn, có thể xem bằng cách nhấp vào liên kết
- Một số bài tập cho phép nhập đáp án và kiểm tra, nhờ đó có thể thử nhiều lần mà không phải xem ngay đáp án đúng
- Cũng có PDF miễn phí để dùng ngoại tuyến
- Phù hợp để đọc trên máy tính bảng hoặc máy tính
- Hỗ trợ tìm kiếm và điều hướng bằng liên kết tích hợp
- Có thể truy cập gợi ý và lời giải bằng cách nhấp vào số bài tập, và nhấp vào số của gợi ý hoặc lời giải sẽ quay lại bài tập tương ứng
- Bản in được xuất bản bởi CRC Press
- Phiên bản trực tuyến sẽ tiếp tục được cung cấp miễn phí
Mã nguồn, tài liệu giảng dạy và cộng đồng
- Các tệp nguồn PreTeXt và LaTeX của giáo trình được cung cấp trên GitHub
- Cũng có các tài liệu video sử dụng giáo trình
- Mathematical Visual Proofs: video minh họa bằng hoạt hình các ý tưởng trong giáo trình
- Dr. Trevor Bazett's Course: khóa học đầy đủ dựa trên giáo trình này
- Giảng viên dùng giáo trình trong lớp có thể yêu cầu tài liệu dành cho giảng viên
- Nếu có quyền truy cập máy chủ WeBWorK, cũng có thể yêu cầu bộ bài tập WeBWorK
- Có Google Group dành cho giảng viên dạy toán rời rạc
Nội dung giáo trình và cách dùng trong giảng dạy
- Giáo trình này bắt đầu từ ghi chú bài giảng cho môn toán rời rạc tại University of Northern Colorado
- Môn học đó vừa là phần nhập môn các chủ đề toán rời rạc, vừa đóng vai trò là môn nhập môn chứng minh cho sinh viên chuyên ngành toán
- Lớp học bao gồm nhiều hoạt động khám phá của sinh viên, và giáo trình cũng được viết để hỗ trợ điều đó
- Ban đầu sách được thiết kế để hỗ trợ giáo viên toán tương lai, và sử dụng giọng văn thân thiện, ít trang trọng
- Sách nhấn mạnh sự thấu hiểu các khái niệm được đề cập hơn là ghi nhớ quy trình
- Sách cũng được dùng trong các môn học dành cho sinh viên khoa học máy tính, với trọng tâm giúp đạt được hiểu biết sâu hơn
- Bốn chủ đề chính là logic, lý thuyết đồ thị, đếm và dãy số
- Các phương pháp chứng minh bao gồm phản chứng, quy nạp và chứng minh tổ hợp
- Các chủ đề bổ sung còn có hàm sinh và lý thuyết số
- Sách cũng có các tính năng hỗ trợ dùng làm giáo trình chính
- Hơn 750 bài tập
- Nhiều bài có lời giải và gợi ý
- Bao gồm từ bài dễ đến bài khá phức tạp
- Có nhiều bài phù hợp để giao bài tập về nhà
- Các hoạt động Investigate! và hoạt động xem trước hỗ trợ học tập chủ động, dựa trên khám phá
- Chỉ mục đầy đủ và danh sách ký hiệu
- Bố cục trang và định dạng nhất quán như đánh dấu ví dụ, khung định nghĩa·định lý
Giấy phép
- Discrete Mathematics: an Open Introduction, 4th edition được phát hành theo giấy phép CC BY-NC-SA 4.0
- Với mục đích phi thương mại, có thể tải xuống, sử dụng và in ấn
- Cũng cho phép chỉnh sửa văn bản
- Có thể tạo bản tùy biến cho sinh viên
- Phải ghi rõ tác giả của phần đã sử dụng
- Bản chỉnh sửa phải được phát hành theo giấy phép tương thích
- Nếu muốn kết hợp với văn bản theo giấy phép tương tự nhưng khác, như GFDL, có thể yêu cầu cấp phép sửa đổi giấy phép
1 bình luận
Ý kiến trên Hacker News
Với người tự học mà không có bằng CS “chính quy”, toán rời rạc từng trông như một chủ đề nâng cao hơn và là chiếc chìa khóa để giải các vấn đề thực tiễn trong lập trình, và thực tế nó đã giúp ích nhiều lần
Tôi cũng thích “A Primer of Discrete Mathematics” của Finkbeiner II và Lindstrom từ năm 1987 https://archive.org/details/isbn_0716718154. Hơi cũ và không miễn phí, nhưng vẫn ổn, có bài tập hay và một số lời giải
Tôi cũng định xem thử cuốn này, vì có vẻ là một cách tiếp cận hiện đại hơn với bài tập tương tác, lại hoàn toàn miễn phí
Sách khá dày nhưng nội dung tương đối dễ tiếp cận. Tôi cũng là dân tự học, và giờ đã ở độ tuổi 30, đang học các môn toán/lý chính quy để bù những phần còn thiếu
California Community Colleges cũng là một nguồn lực tuyệt vời. Tất cả giáo viên toán tôi gặp đến giờ đều nhiệt huyết đáng kinh ngạc, và hầu hết các lớp toán đều có phần học không đồng bộ/trực tuyến nên người lớn học vì vui hay để tự phát triển bản thân cũng rất phổ biến
Tôi bị thu hút bởi phần “logic”, và nó không làm tôi thất vọng. Có thể tải miễn phí từ trang web
Bạn nói nó “hơi cũ và tiếc là không miễn phí”, nhưng nếu ai đang tìm thì trên Anna's Archive cũng có
Tôi ước các tài liệu được liên kết, nhất là giáo trình miễn phí, cung cấp nhiều đáp án hơn. Sách thiếu lời giải tạo ra một vòng luẩn quẩn với tôi
Muốn biết lời giải của mình có đúng không thì tôi phải thực sự hiểu khái niệm. Nhưng nếu đã thực sự hiểu khái niệm thì ngay từ đầu tôi đâu cần giải bài đó nữa. Tôi không hiểu phải học kiểu gì mà không có phản hồi
Nhờ PreTeXt, tôi đã dùng nhiều bài tập tương tác có thể chèn thẳng vào nội dung, để sinh viên nhập đáp án và nhận phản hồi xem đúng hay không. Cách này rất hợp với bài toán tính toán
Với các bài dựa trên chứng minh hoặc thiên về lý thuyết, tôi cố gắng đưa vào đủ ví dụ có lời giải đầy đủ, và cũng thêm một số bài tập có đáp án. Đồng thời, tôi vẫn muốn để lại cơ hội cho những ai thích các bài mở hơn, không có lời giải
Nếu các giảng viên khác muốn dùng cuốn sách này hữu ích trong lớp học của họ, thì các bài không có đáp án để chấm điểm cũng rất quan trọng. Dù sao, mong rằng tài liệu này sẽ hữu ích
Nếu học bằng giáo trình ngoài lớp học mà không có phản hồi bên ngoài, bạn phải đọc tài liệu một cách chủ động hơn nhiều
Hãy coi mỗi phát biểu trong phần nội dung như một bài tập không chính thức. Bất cứ khi nào có một mệnh đề xuất hiện, dù là định lý hay một khẳng định trong phần giải thích, bạn nên thử tự chứng minh hoặc biện minh cho nó trước khi đọc tiếp
Ví dụ, Theorems 2.3.1 và 2.3.2 rất giống nhau. Nếu bạn hiểu chứng minh của 2.3.1, bạn có thể tự thử làm 2.3.2. Nếu bí, hãy đọc vài câu trong phần chứng minh có sẵn như gợi ý, rồi khi làm xong thì so với chứng minh trong sách
Nếu đọc đủ chủ động, bạn có thể học nội dung khá tốt ngay cả khi không giải bài tập. Người ta thường nói muốn học toán thì phải làm bài tập hình thức, nhưng điều đó không đúng. Nhiều giáo trình toán cao cấp thậm chí không có bài tập hay bài toán chính thức nào, vậy mà mọi người vẫn học tốt
Tất nhiên, bản thân việc đọc toán đã là một kỹ năng riêng, nên đừng kỳ vọng sẽ thấy nó dễ ngay từ đầu. Có gia sư một kèm một thì là tốt nhất, nhưng hiếm ai may mắn như vậy
Trước hết giải bằng tay, rồi mô hình hóa lại bằng Mathematica hoặc các công cụ như OR-Tools để xem có ra cùng đáp án không
Cách này còn hiệu quả hơn ở các mảng toán cơ bản hơn như đại số hay giải tích. Với nhiều bài, chỉ cần dùng hàm
Solve[]của Mathematica là có thể biết mình đúng hay saiTrong các lớp thuật toán cũng có thể áp dụng cách tiếp cận tương tự. Tự viết một chương trình ngây thơ để giải các test case theo cách đơn giản nhưng chắc chắn đúng, rồi so sánh với kết quả từ thuật toán tinh vi hơn. Hoặc dùng một triển khai tham chiếu từ thư viện khác. Ví dụ, bạn có thể so kết quả lời giải thuật toán đồ thị tự viết với kết quả mà Neo4j trả về
Nếu ít hơn mức đó thì cùng lắm nó chỉ phù hợp làm tài liệu tham khảo cho giáo viên. Vì giáo viên cần kiểm tra xem lời giải có thực sự đầy đủ và đúng hay không
Khi học kỹ thuật và kinh tế vài chục năm trước, nếu không có lời giải thì bài làm của tôi thường sẽ không hoàn chỉnh, dễ bỏ sót chi tiết hoặc các trường hợp cụ thể
Có lẽ bạn cũng sẽ quan tâm đến PreTeXt, công nghệ dựa trên XML được dùng để làm cuốn sách này: https://pretextbook.org/
Thật vui khi thấy những tài liệu tuyệt vời như thế này. Đặc biệt cảm ơn tất cả các tác giả, bao gồm cả các tác giả giáo trình, đã công khai miễn phí trên mạng công trình của mình
Sự tận tâm của họ thể hiện rất rõ. Nhờ những tài liệu miễn phí hoặc gần như miễn phí như thế này, nhiều người, bao gồm cả người tự học hay những người có nguồn lực hạn chế, vẫn có thể tiếp tục việc học
Mong là các tác giả hiểu rằng nỗ lực của họ thực sự được ghi nhận rất nhiều
Hơi muộn một chút, nhưng tôi rất muốn giới thiệu Discrete mathematics with applications của Susanna Epp
Có vài cuốn sách có tiêu đề tương tự, nhưng sách của Epp được viết hay đến kinh ngạc. Đây là một giáo trình được đầu tư cực kỳ kỹ lưỡng và chú ý đến từng chi tiết, và điều đó hiện ra rất rõ. Nó cũng rất tuyệt cho việc tự học
Cũng có một video của The Math Sorcerer nói về một ấn bản cũ hơn, gần như là một bài ca ngợi đầy trìu mến dành cho cuốn sách. Có vẻ ông ấy thực sự mê nó: https://www.youtube.com/watch?v=FPr5-X9nZc4
Giống như nhiều giáo trình toán rời rạc khác, phần phương pháp nghiệm đặc trưng cho nghiệm kép không đưa ra chứng minh của công thức
r, ta khai triểnx^2 - 2r + r^2và khớp các hạng để đượca = 2r,b = -r^2. Tức là hệ thức truy hồi trở thànha(n) = 2r a(n-1) - r^2 a(n-2)Chia cho
r^nthì tương đương vớic(n) = 2c(n-1) - c(n-2), trong đóc(n) = a(n)/r^nĐây là truy hồi sai phân không đổi
c(n) - c(n-1) = c(n-1) - c(n-2)Vì thế
c(n)là một cấp số cộngc(n) = x*n + yvới một sốx,ynào đó được xác định bởi điều kiện đầu. Dãy ban đầu làa(n) = c(n) r^n = (x*n + y) r^nVí dụ, nếu dùng đại số tuyến tính thì có một chứng minh khá ngắn gọn, có thể phác lại một phần như sau. Tôi thích cách chứng minh này vì nó không bắt đầu từ một dạng được giả định trước mà suy ra công thức từ những nguyên lý đầu tiên
Giả sử ta có một dãy
x_nđược xác định bởi hệ thức truy hồix_{n+1} = a * x_{n-1} + b * x_nNếu định nghĩa dãy vector gồm hai phần tử liên tiếp
[x_0; x_1],[x_1; x_2],[x_2; x_3], ... thì có thể lập quan hệ bằng phép nhân ma trận/vector[x_1; x_2] = [[0 1], [a b]] [x_0; x_1]Gọi dãy vector là
y_nvà ma trận làMthìy_1 = M * y_0Hạng tiếp theo là
y_2 = M * y_1 = M * (M * y_0) = M^2 * y_0, và theo quy nạp thìy_n = M^n * y_0Đa thức đặc trưng của
Mlàr^2 - br - a = 0, các nghiệm làr_1 = (b - c)/2,r_2 = (b + c)/2, vớic = √(b^2 + 4a)Do đó, bằng phép chéo hóa, ta được
y_n = S * [[r_1^n 0], [0 r_2^n]] * S^(-1) * y_0, trong đóSlà ma trận các vector riêngTừ đây có thể hoàn tất chứng minh tính tồn tại và tính duy nhất bằng sự tồn tại và tính duy nhất của các trị riêng của
MKnuth tìm dạng đóng của các dãy truy hồi bằng hàm sinh, và nếu tôi nhớ không nhầm thì hầu như không bàn nhiều đến các phương pháp khác. Môn tôi học thì hoàn toàn không đụng đến hàm sinh, và phần lớn các giáo trình khác tôi từng đọc cũng vậy
Thật thú vị khi cuốn sách này có đề cập đến chủ đề đó. Có lẽ “toán rời rạc” thực sự có thể bao gồm rất nhiều thứ
Mong là tôi cũng yêu lĩnh vực của mình như những người viết giáo trình miễn phí này yêu lĩnh vực của họ
Đây là môn học tôi thích nhất ở đại học. Năm nhất tôi đã thích toán rời rạc đến mức quyết định học song ngành toán và AI, và tôi chọn toán vì kiểm chứng hình thức
Có ghi là “PDF sẽ được cung cấp đến ngày 15 tháng 8”, nhưng ở thanh bên chỉ thấy “PDF coming soon” :(
Nếu quan tâm đến mật mã học thì toán rời rạc có phải là điểm khởi đầu tốt không? Chắc chắn còn tốt hơn giải tích đúng không?