- Khóa học CS251 của CMU nói về việc nghiên cứu một cách chặt chẽ về tính toán, yếu tố nền tảng của vũ trụ, xã hội, công nghệ mới và cả tâm trí của chúng ta trong việc hiểu chúng.
- Điều quan trọng là phải có ngôn ngữ và công cụ phù hợp để nghiên cứu tính toán.
- Khóa học này khám phá các kết quả và câu hỏi trung tâm về bản chất của tính toán.
Hình thức hóa tính toán
Mô-đun 1: Giới thiệu
- Mục tiêu chính là giải thích ở mức khái quát khoa học máy tính lý thuyết là gì, đồng thời thiết lập bối cảnh phù hợp cho những nội dung sẽ được đề cập sau này.
- Bắt đầu bằng cách biểu diễn dữ liệu một cách hình thức và định nghĩa một cách hình thức khái niệm về bài toán tính toán.
Mô-đun 2: Ôtômat hữu hạn
- Mục tiêu là giới thiệu deterministic finite automata (DFA), một mô hình tính toán đơn giản và bị giới hạn.
- DFA tự thân đã thú vị và có ứng dụng hữu ích, nhưng ở đây được dùng như bước đầu để định nghĩa một cách hình thức khái niệm thuật toán.
Mô-đun 3: Hình thức hóa tính toán
- Mục tiêu chính là giới thiệu định nghĩa về máy Turing, mô hình toán học tiêu chuẩn cho mọi loại thiết bị tính toán.
- Việc nghiên cứu nghiêm ngặt máy Turing mang lại hiểu biết không chỉ về những gì laptop có thể làm mà còn về những gì vũ trụ có thể và không thể làm về mặt tính toán.
Mô-đun 4: Giới hạn của tính toán
- Chứng minh rằng phần lớn các bài toán là không thể quyết định, đồng thời đưa ra các ví dụ cụ thể về bài toán không thể quyết định.
- Sử dụng hai kỹ thuật cốt lõi là chéo hóa và thu gọn.
Mô-đun 5: Giới hạn của suy luận con người
- Cần có công việc hình thức hóa suy luận toán học bằng chính toán học, và điều này bao gồm cả việc hình thức hóa "thuật toán" hoặc "tính toán".
- Sử dụng ngôn ngữ của khoa học máy tính lý thuyết để trả lời hiệu quả các câu hỏi quan trọng về nền tảng của toán học.
Độ phức tạp tính toán
Mô-đun 6: Độ phức tạp thời gian
- Nhiều bài toán trên thực tế là có thể quyết định, nhưng nếu thuật toán hiệu quả nhất vẫn cần số bước tính toán cực lớn thì trên thực tế bài toán đó là không thể quyết định.
- Nghiên cứu độ phức tạp tính toán đối với nhiều loại tài nguyên khác nhau, bao gồm độ phức tạp thời gian, nhưng tập trung vào độ phức tạp thời gian.
Mô-đun 7: Lý thuyết đồ thị
- Đồ thị đóng vai trò rất cơ bản trong việc trừu tượng hóa các bài toán tính toán phát sinh trong khoa học máy tính.
- Có thể tận dụng kho tài liệu đồ sộ của lý thuyết đồ thị để hiểu rõ hơn độ phức tạp tính toán của các bài toán đồ thị.
Mô-đun 8: P đối đầu NP
- Giới thiệu lớp độ phức tạp NP và thảo luận về bài toán P đối đầu NP, bài toán chưa được giải quyết quan trọng nhất trong khoa học máy tính.
- Nếu có thể quyết định nhiều ngôn ngữ tự nhiên và đã được nghiên cứu kỹ thuộc NP trong thời gian đa thức thì sẽ có những ứng dụng đáng kinh ngạc.
Mô-đun 9: Thuật toán ngẫu nhiên
- Tính ngẫu nhiên là một khái niệm và công cụ thiết yếu để mô hình hóa và phân tích tự nhiên.
- Thuật toán ngẫu nhiên là các thuật toán có thể truy cập vào nguồn ngẫu nhiên như bộ sinh số ngẫu nhiên, và có thể mắc lỗi với xác suất lỗi rất nhỏ.
Mô-đun 10: Mật mã học
- Cuộc cách mạng khoa học máy tính đã khiến lĩnh vực mật mã học bắt đầu phát triển mạnh mẽ.
- Việc nghiên cứu độ phức tạp tính toán đã cách mạng hóa hoàn toàn mật mã học.
Những điểm nổi bật của khoa học máy tính lý thuyết
Mô-đun 11: Chủ đề bổ sung
- Trình bày một số điểm nhấn được chọn lọc trong khoa học máy tính lý thuyết.
Ý kiến của GN⁺
- Khóa học này mang lại sự hiểu biết sâu sắc về khía cạnh lý thuyết của khoa học máy tính, đồng thời tạo cơ hội để người học khám phá bản chất của tính toán và học các chủ đề quan trọng như lý thuyết độ phức tạp và mật mã học.
- Đặc biệt, các thảo luận về những bài toán chưa được giải như P đối đầu NP mang đến cho người học góc nhìn sâu sắc về nghiên cứu đang diễn ra ở tuyến đầu của khoa học máy tính.
- Khóa học này đóng vai trò quan trọng trong việc xây nền tảng cho khoa học máy tính, đồng thời cung cấp kiến thức thiết yếu để trở thành một kỹ sư phần mềm có nền tảng lý thuyết.
- Mô-đun mật mã học nhấn mạnh tầm quan trọng của bảo mật dữ liệu và quyền riêng tư trong xã hội hiện đại, đồng thời đặt nền móng để trở thành chuyên gia trong lĩnh vực này.
- Khóa học này rất có giá trị vì giúp sinh viên trang bị nền tảng lý thuyết thiết yếu và kỹ năng giải quyết vấn đề để xây dựng sự nghiệp trong lĩnh vực khoa học máy tính.
2 bình luận
À.. nhớ lại hồi còn là sinh viên đã từng khổ sở đến mức vò đầu bứt tai..
Chắc có lẽ giờ vẫn không hiểu nổi, nhưng thôi cứ cố gắng nghe chăm chỉ vậy.
Ý kiến trên Hacker News
Khóa học này giới thiệu nhiều khái niệm khác nhau và đặc biệt tập trung vào việc nâng cao năng lực giải quyết vấn đề.
Lý thuyết khoa học máy tính có thể rất thú vị, nhưng đôi khi cũng cực kỳ khó chịu.
Tôi từng thấy một bài đăng trên Reddit hỏi cách giải một bài toán lý thuyết khoa học máy tính, và hóa ra đó là một nỗ lực gian lận để làm bài tập của COMS 331 (Lý thuyết tính toán) tại Đại học Bang Iowa.
Nếu muốn tự học trực tiếp những ý tưởng này qua lập trình, tôi khuyên đọc "Understanding Computation From Simple Machines to Impossible Programs" của Tom Stuart.
Có thể xem một phiên bản đầy đủ hơn của khóa học này trong playlist trên YouTube.
Có một phiên bản khác của khóa học này bao gồm "phương pháp xác suất", và tôi không thể hình dung ra các chứng minh về rào cản của không gian nghiệm topo nếu không có cách tư duy về các chứng minh tồn tại hiện đại (không mang tính kiến tạo).
Nếu bạn quan tâm đến chủ đề này, có thể xem website của Boaz Barak và giáo trình được cung cấp dưới dạng PDF.
Hai ý tưởng quan trọng nhất trong lý thuyết khoa học máy tính:
Một phiên bản của khóa học này trong các lĩnh vực khác sẽ trông như thế nào?
Tôi nhớ một buổi học về độ phức tạp thời gian hồi còn đại học. Giáo sư gọi ngẫu nhiên sinh viên lên và hỏi độ phức tạp thời gian của các thuật toán phức tạp; nếu trả lời sai thì sẽ gọi người khác.
Có thể hiểu tính toán như một thuộc tính nền tảng của vũ trụ theo cách nào? Thực vật và động vật thực hiện tính toán ra sao?