- Giáo trình toán học dành cho sinh viên chuyên ngành khoa học máy tính do MIT cung cấp, trình bày có hệ thống các khái niệm toán học cốt lõi từ logic và chứng minh đến xác suất, truy hồi và lý thuyết đồ thị
- Gồm năm phần: chứng minh, cấu trúc, đếm, xác suất, truy hồi, mỗi phần đều kết hợp nền tảng lý thuyết với ứng dụng trong khoa học máy tính
- Bao gồm các chủ đề thiết yếu cho lập trình và phân tích thuật toán như công thức logic, quy nạp toán học, máy trạng thái, đồ thị, biến ngẫu nhiên
- Thể hiện cách vận dụng các khái niệm toán học thông qua các trường hợp thực tế và bài toán ứng dụng như mã hóa RSA, mã của Turing và bài toán Monty Hall
- Là giáo trình do các nhà nghiên cứu từ MIT và Google đồng biên soạn, được phát hành theo giấy phép Creative Commons BY-SA 3.0, cho phép học tập và tái sử dụng tự do
Tổng quan giáo trình
- Mathematics for Computer Science (MCS) là giáo trình cho học phần bậc cử nhân ngành khoa học máy tính và kỹ thuật điện của MIT (6.042), nhằm rèn luyện tư duy logic và năng lực mô hình hóa toán học
- Tác giả gồm Eric Lehman (Google Inc.), F. Thomson Leighton (MIT, Akamai Technologies), Albert R. Meyer (MIT)
- Là bản hiệu đính ngày 6 tháng 6 năm 2018, được phân phối theo giấy phép Creative Commons Attribution-ShareAlike 3.0
I. Proofs (Chứng minh)
- Trình bày các nguyên lý cơ bản của chứng minh toán học như mệnh đề, vị từ, phương pháp tiên đề, phản chứng, chứng minh bằng chia trường hợp
- Giải thích mối quan hệ giữa Well Ordering Principle (nguyên lý thứ tự tốt) và phép quy nạp, áp dụng qua các ví dụ như phân tích thừa số nguyên tố
- Bao gồm công thức logic và logic mệnh đề, bài toán SAT, kiểu dữ liệu toán học (tập hợp, hàm, quan hệ)
II. Structures (Cấu trúc)
- Trình bày nền tảng toán học của khoa học máy tính xoay quanh lý thuyết số, lý thuyết đồ thị, cấu trúc mạng
- Ứng dụng lý thuyết số như số nguyên tố, ước chung lớn nhất, số học mô-đun, mã hóa RSA
- Mô tả các mô hình cấu trúc như đồ thị có hướng, thứ tự bộ phận, định tuyến mạng, đồ thị đơn, đồ thị phẳng
- Đề cập đến mã của Turing và mối liên hệ với bài toán SAT, cho thấy sự kết nối giữa lý thuyết tính toán và mật mã học
III. Counting (Đếm và tổ hợp)
- Trình bày các kỹ thuật đếm tổ hợp như tổng, tích, ký hiệu tiệm cận, quy tắc tổ hợp, hàm sinh
- Bao gồm các ví dụ thực tiễn như nguyên lý chuồng bồ câu, nguyên lý bao hàm-loại trừ, ví dụ về tay bài poker
- Ứng dụng vào phân tích thuật toán và tính toán dãy số thông qua hàm sinh và phương pháp giải truy hồi tuyến tính
IV. Probability (Xác suất)
- Bao quát toàn bộ phạm vi lý thuyết xác suất như không gian xác suất, xác suất có điều kiện, biến ngẫu nhiên, phương sai, ước lượng mẫu, bước đi ngẫu nhiên
- Bao gồm các trường hợp kiểm tra tư duy trực giác như bài toán Monty Hall, nghịch lý Simpson, bài toán ngày sinh
- Cung cấp nền tảng phân tích dữ liệu thông qua định lý Markov, định lý Chebyshev và lấy mẫu ngẫu nhiên
V. Recurrences (Truy hồi)
- Trình bày các chủ đề cốt lõi trong phân tích thuật toán như Tháp Hà Nội, sắp xếp trộn, truy hồi chia để trị
- Giải thích cấu trúc tính toán hiệu quả thông qua phương pháp giải truy hồi tuyến tính và tư duy đệ quy
Phụ lục
- Bao gồm tài liệu tham khảo, giải thích ký hiệu, mục lục tra cứu, thuận tiện cho học tập và tham khảo
- Toàn bộ giáo trình được cung cấp miễn phí dưới dạng PDF trên website MIT CSAIL
1 bình luận
Ý kiến trên Hacker News
Có người nhắc rằng Thomson Leighton là nhà sáng lập Akamai và giới thiệu chuỗi bài giảng do ông giảng dạy
Đây là nội dung về Internet gây ấn tượng mạnh nhất mà họ từng xem
Cấu trúc của từng phần khá chuẩn mực, nhưng họ thích việc mỗi trích dẫn đều có liên kết ngược tới toàn bộ nguồn tham khảo
Họ mong sẽ có nhiều cuốn sách được làm theo cách này hơn
Tuy vậy, họ thấy tiếc vì việc biên soạn đã dừng lại sau năm 2018
Có người nói họ thực sự rất thích cuốn sách này. Độ khó cao, nhưng ở mỗi mục họ vẫn hiểu được khoảng 1–2 trang
Họ có được một trực giác rằng hàm số là một danh sách vô tận của đầu vào và đầu ra, và cũng ấn tượng với sự hài hước trong ký hiệu toán học
Họ muốn có thể hiểu hoàn toàn nó trước khi chết
Có người đặt câu hỏi liệu có thể chọn ra chỉ 5 cuốn sách bắt buộc phải đọc trong khoa học máy tính hay không
Danh sách gồm Brookshear, Forta, Stallings, CLRS, Kurose & Ross, Sipser, Aumasson, Russell & Norvig và nhiều tên khác
Họ nói Python trên thực tế đã trở thành ngôn ngữ chung, và cũng khuyên đọc Python Crash Course 3rd Edition của Matthes
Ở đó cũng có hướng dẫn về 2 cuốn cốt lõi nên đọc khi thời gian hạn chế
Có người đặc biệt thích phần xác suất của cuốn sách này
Bài toán Monty Hall được giải thích rất sáng rõ bằng “phương pháp 4 bước”, dễ hiểu hơn phim rất nhiều
Nó phù hợp để học từng phần bằng sách giấy
Có người ngạc nhiên khi thấy chương 2 trong mục lục là Well-Ordering Principle
Khác với định lý của Zermelo, cách tiếp cận giả định sẵn thứ tự của số tự nhiên khiến họ thấy lạ
Bởi bình thường họ được học theo kiểu định nghĩa thứ tự từ các tiên đề Peano rồi sau đó mới chứng minh nguyên lý này
Cũng thú vị ở chỗ số thực cũng có một thứ tự tốt, nhưng ta không thể biểu diễn cụ thể thứ tự đó trong thực tế
Họ cũng trích lại câu đùa: “Tiên đề chọn thì hiển nhiên đúng, nguyên lý sắp thứ tự thì hiển nhiên sai, còn bổ đề Zorn thì tôi không biết”
Có người diễn giải lại nguyên lý pigeonhole ở mục 15.8 theo cách tiếp cận của Dijkstra
Nếu 500.000 người ở Boston có từ 1 đến 200.000 sợi tóc, thì do trung bình là 2,5 người cho mỗi giá trị, có thể chứng minh rằng ít nhất 3 người có cùng số lượng tóc
Điều thú vị là bài toán được giải chỉ bằng sự thật đơn giản rằng giá trị trung bình không thể lớn hơn giá trị lớn nhất
Có người nói đây là lần đầu họ gặp một cuốn sách theo kiểu tuyển tập bài tập, và thắc mắc liệu có đáp án hay không
Họ đã thử giải vài bài nhưng không có cách nào kiểm tra kết quả
Có người gửi lời cảm ơn và nói đây là tài liệu rất hữu ích
Có người vui mừng vì nhờ Hacker News mà tìm được đúng file PDF mình đang cần
Họ hỏi xin gợi ý về trình đọc màn hình có thể đọc PDF
Bản thân họ cũng không đọc được phần lớn các ký hiệu công thức